patricia_trie_test.cc File Reference

Tests for Aleph::PatriciaSet and Aleph::PatriciaMap. More...

#include <prefix-tree.H>
#include <tpl_patricia_trie.H>
#include <tpl_radix_tree.H>
#include <gtest/gtest.h>
#include <algorithm>
#include <cstdint>
#include <limits>
#include <map>
#include <memory>
#include <random>
#include <set>
#include <string>
#include <type_traits>
#include <vector>

Include dependency graph for patricia_trie_test.cc:

Go to the source code of this file.

Functions
	TEST (PatriciaSet, DefaultConstructedSetIsEmpty)
	TEST (PatriciaSet, InsertAndContainsSingleKey)
	TEST (PatriciaSet, InsertRejectsDuplicateKeys)
	TEST (PatriciaSet, HandlesZeroAndExtremes)
	TEST (PatriciaSet, KeysReturnsAllStoredValues)
	TEST (PatriciaSet, EraseMissingKeyReturnsFalse)
	TEST (PatriciaSet, EraseOnlyKeyEmptiesSet)
	TEST (PatriciaSet, EraseCollapsesInternalNodeAndPreservesSibling)
	TEST (PatriciaSet, ClearRemovesAllKeys)
	TEST (PatriciaSet, CopyConstructorProducesIndependentClone)
	TEST (PatriciaSet, MoveConstructorTransfersKeysAndLeavesSourceEmpty)
	TEST (PatriciaSet, CopyAssignmentProducesIndependentClone)
	TEST (PatriciaSet, MoveAssignmentTransfersKeysAndLeavesSourceEmpty)
	TEST (PatriciaSet, SelfAssignmentDoesNotCorruptState)
	TEST (PatriciaSet, RandomizedOperationsMatchStdSet)
	TEST (PatriciaSet, MatchesRadixTreeAndPrefixTreeOnEncodedIntegerKeys)
	TEST (PatriciaMap, DefaultConstructedMapIsEmpty)
	TEST (PatriciaMap, InsertAndFindSingleValue)
	TEST (PatriciaMap, InsertRejectsDuplicateAndKeepsOriginalValue)
	TEST (PatriciaMap, DuplicateMoveInsertDoesNotConsumeValue)
	TEST (PatriciaMap, InsertOrAssignInsertsThenOverwrites)
	TEST (PatriciaMap, MutableFindAllowsInPlaceUpdate)
	TEST (PatriciaMap, EraseRemovesValueAndPreservesSibling)
	TEST (PatriciaMap, ClearRemovesAllValues)
	TEST (PatriciaMap, CopyConstructorProducesIndependentClone)
	TEST (PatriciaMap, MoveConstructorTransfersValuesAndLeavesSourceEmpty)
	TEST (PatriciaMap, CopyAssignmentProducesIndependentClone)
	TEST (PatriciaMap, MoveAssignmentTransfersValuesAndLeavesSourceEmpty)
	TEST (PatriciaMap, SelfAssignmentDoesNotCorruptState)
	TEST (PatriciaMap, RandomizedOperationsMatchStdMap)
	TEST (PatriciaMap, MatchesRadixTreeValuesAndPrefixTreeMembership)

Detailed Description

Tests for Aleph::PatriciaSet and Aleph::PatriciaMap.

Definition in file patricia_trie_test.cc.

Function Documentation

TEST() [1/31]

TEST	(	PatriciaMap	,
		ClearRemovesAllValues
	)

Definition at line 552 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::clear(), Aleph::ODhashTable< Key, Cmp >::contains(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::is_empty(), OhashCommon< HashTbl, Key >::keys(), and m.

TEST() [2/31]

TEST	(	PatriciaMap	,
		CopyAssignmentProducesIndependentClone
	)

Definition at line 601 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaMap< UInt, T >::check_invariants(), Aleph::PatriciaMap< UInt, T >::contains(), Aleph::PatriciaMap< UInt, T >::find(), Aleph::PatriciaMap< UInt, T >::insert(), and Aleph::PatriciaMap< UInt, T >::insert_or_assign().

TEST() [3/31]

TEST	(	PatriciaMap	,
		CopyConstructorProducesIndependentClone
	)

Definition at line 566 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaMap< UInt, T >::check_invariants(), Aleph::PatriciaMap< UInt, T >::find(), Aleph::PatriciaMap< UInt, T >::insert(), and Aleph::PatriciaMap< UInt, T >::insert_or_assign().

TEST() [4/31]

TEST	(	PatriciaMap	,
		DefaultConstructedMapIsEmpty
	)

Definition at line 451 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ODhashTable< Key, Cmp >::contains(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::is_empty(), OhashCommon< HashTbl, Key >::keys(), m, and OhashCommon< HashTbl, Key >::size().

TEST() [5/31]

TEST	(	PatriciaMap	,
		DuplicateMoveInsertDoesNotConsumeValue
	)

Definition at line 485 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), and m.

TEST() [6/31]

TEST	(	PatriciaMap	,
		EraseRemovesValueAndPreservesSibling
	)

Definition at line 532 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ODhashTable< Key, Cmp >::contains(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), m, and OhashCommon< HashTbl, Key >::size().

TEST() [7/31]

TEST	(	PatriciaMap	,
		InsertAndFindSingleValue
	)

Definition at line 462 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ODhashTable< Key, Cmp >::contains(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::is_empty(), and m.

TEST() [8/31]

TEST	(	PatriciaMap	,
		InsertOrAssignInsertsThenOverwrites
	)

Definition at line 500 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::find(), m, and OhashCommon< HashTbl, Key >::size().

TEST() [9/31]

TEST	(	PatriciaMap	,
		InsertRejectsDuplicateAndKeepsOriginalValue
	)

Definition at line 474 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), m, and OhashCommon< HashTbl, Key >::size().

TEST() [10/31]

TEST	(	PatriciaMap	,
		MatchesRadixTreeValuesAndPrefixTreeMembership
	)

Definition at line 716 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::prefix(), rng, to_sorted_vector(), Aleph::to_vector(), and value.

TEST() [11/31]

TEST	(	PatriciaMap	,
		MoveAssignmentTransfersValuesAndLeavesSourceEmpty
	)

Definition at line 624 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaMap< UInt, T >::check_invariants(), Aleph::PatriciaMap< UInt, T >::contains(), Aleph::PatriciaMap< UInt, T >::find(), Aleph::PatriciaMap< UInt, T >::insert(), and Aleph::PatriciaMap< UInt, T >::is_empty().

TEST() [12/31]

TEST	(	PatriciaMap	,
		MoveConstructorTransfersValuesAndLeavesSourceEmpty
	)

Definition at line 585 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaMap< UInt, T >::check_invariants(), Aleph::PatriciaMap< UInt, T >::find(), Aleph::PatriciaMap< UInt, T >::insert(), and Aleph::PatriciaMap< UInt, T >::is_empty().

TEST() [13/31]

TEST	(	PatriciaMap	,
		MutableFindAllowsInPlaceUpdate
	)

Definition at line 518 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), and m.

TEST() [14/31]

TEST	(	PatriciaMap	,
		RandomizedOperationsMatchStdMap
	)

Definition at line 668 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), rng, to_sorted_vector(), and value.

TEST() [15/31]

TEST	(	PatriciaMap	,
		SelfAssignmentDoesNotCorruptState
	)

Definition at line 644 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), OhashCommon< HashTbl, Key >::find(), OhashCommon< HashTbl, Key >::insert(), m, and OhashCommon< HashTbl, Key >::size().

TEST() [16/31]

TEST	(	PatriciaSet	,
		ClearRemovesAllKeys
	)

Definition at line 247 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::clear(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), Aleph::Array< T >::is_empty(), Aleph::PatriciaSet< UInt >::is_empty(), and Aleph::PatriciaSet< UInt >::keys().

TEST() [17/31]

TEST	(	PatriciaSet	,
		CopyAssignmentProducesIndependentClone
	)

Definition at line 292 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::erase(), and Aleph::PatriciaSet< UInt >::insert().

TEST() [18/31]

TEST	(	PatriciaSet	,
		CopyConstructorProducesIndependentClone
	)

Definition at line 261 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::erase(), and Aleph::PatriciaSet< UInt >::insert().

TEST() [19/31]

TEST	(	PatriciaSet	,
		DefaultConstructedSetIsEmpty
	)

Definition at line 151 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::Array< T >::is_empty(), Aleph::PatriciaSet< UInt >::is_empty(), Aleph::PatriciaSet< UInt >::keys(), and Aleph::PatriciaSet< UInt >::size().

TEST() [20/31]

TEST	(	PatriciaSet	,
		EraseCollapsesInternalNodeAndPreservesSibling
	)

Definition at line 230 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::erase(), Aleph::PatriciaSet< UInt >::insert(), and Aleph::PatriciaSet< UInt >::size().

TEST() [21/31]

TEST	(	PatriciaSet	,
		EraseMissingKeyReturnsFalse
	)

Definition at line 210 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::erase(), and Aleph::PatriciaSet< UInt >::insert().

TEST() [22/31]

TEST	(	PatriciaSet	,
		EraseOnlyKeyEmptiesSet
	)

Definition at line 220 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::erase(), Aleph::PatriciaSet< UInt >::insert(), and Aleph::PatriciaSet< UInt >::is_empty().

TEST() [23/31]

TEST	(	PatriciaSet	,
		HandlesZeroAndExtremes
	)

Definition at line 182 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), max(), and Aleph::PatriciaSet< UInt >::size().

TEST() [24/31]

TEST	(	PatriciaSet	,
		InsertAndContainsSingleKey
	)

Definition at line 161 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), Aleph::PatriciaSet< UInt >::is_empty(), and Aleph::PatriciaSet< UInt >::size().

TEST() [25/31]

TEST	(	PatriciaSet	,
		InsertRejectsDuplicateKeys
	)

Definition at line 172 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), and Aleph::PatriciaSet< UInt >::size().

TEST() [26/31]

TEST	(	PatriciaSet	,
		KeysReturnsAllStoredValues
	)

Definition at line 200 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::insert(), Aleph::PatriciaSet< UInt >::keys(), and to_sorted_vector().

TEST() [27/31]

TEST	(	PatriciaSet	,
		MatchesRadixTreeAndPrefixTreeOnEncodedIntegerKeys
	)

Definition at line 377 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::prefix(), rng, to_sorted_vector(), and Aleph::to_vector().

TEST() [28/31]

TEST	(	PatriciaSet	,
		MoveAssignmentTransfersKeysAndLeavesSourceEmpty
	)

Definition at line 313 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), and Aleph::PatriciaSet< UInt >::is_empty().

TEST() [29/31]

TEST	(	PatriciaSet	,
		MoveConstructorTransfersKeysAndLeavesSourceEmpty
	)

Definition at line 278 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), and Aleph::PatriciaSet< UInt >::is_empty().

TEST() [30/31]

TEST	(	PatriciaSet	,
		RandomizedOperationsMatchStdSet
	)

Definition at line 351 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), rng, to_sorted_vector(), and Aleph::to_vector().

TEST() [31/31]

TEST	(	PatriciaSet	,
		SelfAssignmentDoesNotCorruptState
	)

Definition at line 331 of file patricia_trie_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::PatriciaSet< UInt >::check_invariants(), Aleph::PatriciaSet< UInt >::contains(), Aleph::PatriciaSet< UInt >::insert(), and Aleph::PatriciaSet< UInt >::size().