radix_tree_test.cc File Reference

Tests for Aleph::RadixTree (tpl_radix_tree.H). More...

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

Include dependency graph for radix_tree_test.cc:

Go to the source code of this file.

Functions
	TEST (RadixTree, DefaultConstructedTreeIsEmpty)
	TEST (RadixTree, VerifyHoldsForEmptyTree)
	TEST (RadixTree, InsertAndFindSingleKey)
	TEST (RadixTree, InsertRejectsDuplicateKeys)
	TEST (RadixTree, InsertMoveOverloadIsSupported)
	TEST (RadixTree, InsertOrAssignInsertsThenOverwrites)
	TEST (RadixTree, EmptyStringKeyIsSupported)
	TEST (RadixTree, EraseReturnsFalseForMissingKey)
	TEST (RadixTree, EraseRemovesKeyAndShrinksSize)
	TEST (RadixTree, InsertingSharedPrefixSplitsEdgeCorrectly)
	TEST (RadixTree, InsertingKeyThatIsPrefixOfExistingKeySplitsWithoutExtraLeaf)
	TEST (RadixTree, InsertingKeyThatExtendsExistingKeyAddsLeafUnderIt)
	TEST (RadixTree, EraseMergesCompressedNodeBackTogether)
	TEST (RadixTree, EraseOfInternalNodeWithValueKeepsChildrenReachable)
	TEST (RadixTree, LongestPrefixFindsDeepestMatchingStoredKey)
	TEST (RadixTree, LongestPrefixMatchesEmptyStringKeyAsFallback)
	TEST (RadixTree, KeysWithPrefixReturnsAllMatchingKeys)
	TEST (RadixTree, KeysWithPrefixEmptyPrefixReturnsEverything)
	TEST (RadixTree, KeysWithPrefixExactKeyIncludesItself)
	TEST (RadixTree, MoveConstructorTransfersOwnershipLeavesSourceEmpty)
	TEST (RadixTree, MoveAssignmentTransfersOwnershipLeavesSourceEmpty)
	TEST (RadixTree, CopyConstructorProducesIndependentDeepCopy)
	TEST (RadixTree, CopyAssignmentProducesIndependentDeepCopy)
	TEST (RadixTree, FailedInsertCopyLeavesTreeUnchanged)
	TEST (RadixTree, FailedInsertCopyDuringEdgeSplitLeavesTreeUnchanged)
	TEST (RadixTree, FailedInsertCopyDuringEdgeSplitWithExactPrefixLeavesTreeUnchanged)
	TEST (RadixTree, RandomizedOperationTraceMatchesStdMapReferenceModel)
	TEST (RadixTree, RandomizedPrefixQueriesMatchBruteForceScan)
	TEST (RadixTree, MatchesPrefixTreeInsertContainsAndPrefixQueries)

Detailed Description

Tests for Aleph::RadixTree (tpl_radix_tree.H).

Definition in file radix_tree_test.cc.

Function Documentation

TEST() [1/29]

TEST	(	RadixTree	,
		CopyAssignmentProducesIndependentDeepCopy
	)

Definition at line 438 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::insert_or_assign(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [2/29]

TEST	(	RadixTree	,
		CopyConstructorProducesIndependentDeepCopy
	)

Definition at line 417 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::insert_or_assign(), and Aleph::RadixTree< T, Char >::size().

TEST() [3/29]

TEST	(	RadixTree	,
		DefaultConstructedTreeIsEmpty
	)

Definition at line 94 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::is_empty(), and Aleph::RadixTree< T, Char >::size().

TEST() [4/29]

TEST	(	RadixTree	,
		EmptyStringKeyIsSupported
	)

Definition at line 154 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::size().

TEST() [5/29]

TEST	(	RadixTree	,
		EraseMergesCompressedNodeBackTogether
	)

Definition at line 254 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::is_empty(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [6/29]

TEST	(	RadixTree	,
		EraseOfInternalNodeWithValueKeepsChildrenReachable
	)

Definition at line 286 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [7/29]

TEST	(	RadixTree	,
		EraseRemovesKeyAndShrinksSize
	)

Definition at line 183 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [8/29]

TEST	(	RadixTree	,
		EraseReturnsFalseForMissingKey
	)

Definition at line 173 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::size().

TEST() [9/29]

TEST	(	RadixTree	,
		FailedInsertCopyDuringEdgeSplitLeavesTreeUnchanged
	)

Definition at line 482 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), value, and Aleph::RadixTree< T, Char >::verify().

TEST() [10/29]

TEST	(	RadixTree	,
		FailedInsertCopyDuringEdgeSplitWithExactPrefixLeavesTreeUnchanged
	)

Definition at line 511 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), value, and Aleph::RadixTree< T, Char >::verify().

TEST() [11/29]

TEST	(	RadixTree	,
		FailedInsertCopyLeavesTreeUnchanged
	)

Definition at line 465 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), and value.

TEST() [12/29]

TEST	(	RadixTree	,
		InsertAndFindSingleKey
	)

Definition at line 109 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::size().

TEST() [13/29]

TEST	(	RadixTree	,
		InsertingKeyThatExtendsExistingKeyAddsLeafUnderIt
	)

Definition at line 240 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [14/29]

TEST	(	RadixTree	,
		InsertingKeyThatIsPrefixOfExistingKeySplitsWithoutExtraLeaf
	)

Definition at line 225 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [15/29]

TEST	(	RadixTree	,
		InsertingSharedPrefixSplitsEdgeCorrectly
	)

Definition at line 197 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [16/29]

TEST	(	RadixTree	,
		InsertMoveOverloadIsSupported
	)

Definition at line 131 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::find(), and Aleph::RadixTree< T, Char >::insert().

TEST() [17/29]

TEST	(	RadixTree	,
		InsertOrAssignInsertsThenOverwrites
	)

Definition at line 140 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert_or_assign(), and Aleph::RadixTree< T, Char >::size().

TEST() [18/29]

TEST	(	RadixTree	,
		InsertRejectsDuplicateKeys
	)

Definition at line 121 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::size().

TEST() [19/29]

TEST	(	RadixTree	,
		KeysWithPrefixEmptyPrefixReturnsEverything
	)

Definition at line 353 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::keys_with_prefix(), and Aleph::to_vector().

TEST() [20/29]

TEST	(	RadixTree	,
		KeysWithPrefixExactKeyIncludesItself
	)

Definition at line 363 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::keys_with_prefix(), and Aleph::to_vector().

TEST() [21/29]

TEST	(	RadixTree	,
		KeysWithPrefixReturnsAllMatchingKeys
	)

Definition at line 335 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::insert(), k, Aleph::RadixTree< T, Char >::keys_with_prefix(), and Aleph::to_vector().

TEST() [22/29]

TEST	(	RadixTree	,
		LongestPrefixFindsDeepestMatchingStoredKey
	)

Definition at line 307 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::longest_prefix().

TEST() [23/29]

TEST	(	RadixTree	,
		LongestPrefixMatchesEmptyStringKeyAsFallback
	)

Definition at line 322 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::longest_prefix().

TEST() [24/29]

TEST	(	RadixTree	,
		MatchesPrefixTreeInsertContainsAndPrefixQueries
	)

Definition at line 661 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Prefix_Tree::count(), Aleph::Prefix_Tree::insert_word(), Aleph::prefix(), rng, Aleph::to_vector(), w, Aleph::Prefix_Tree::words(), and Aleph::Prefix_Tree::words_with_prefix().

TEST() [25/29]

TEST	(	RadixTree	,
		MoveAssignmentTransfersOwnershipLeavesSourceEmpty
	)

Definition at line 391 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::contains(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::is_empty(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

TEST() [26/29]

TEST	(	RadixTree	,
		MoveConstructorTransfersOwnershipLeavesSourceEmpty
	)

Definition at line 375 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::find(), Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::is_empty(), and Aleph::RadixTree< T, Char >::size().

TEST() [27/29]

TEST	(	RadixTree	,
		RandomizedOperationTraceMatchesStdMapReferenceModel
	)

Definition at line 534 of file radix_tree_test.cc.

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

TEST() [28/29]

TEST	(	RadixTree	,
		RandomizedPrefixQueriesMatchBruteForceScan
	)

Definition at line 607 of file radix_tree_test.cc.

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

TEST() [29/29]

TEST	(	RadixTree	,
		VerifyHoldsForEmptyTree
	)

Definition at line 103 of file radix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::RadixTree< T, Char >::verify().