prefix_tree_test.cc File Reference

Tests for Prefix Tree. More...

#include <gtest/gtest.h>
#include <prefix-tree.H>
#include <tpl_radix_tree.H>
#include <algorithm>
#include <atomic>
#include <cstddef>
#include <cstdlib>
#include <map>
#include <memory>
#include <new>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

Include dependency graph for prefix_tree_test.cc:

Go to the source code of this file.

Classes
class	PrefixTreeTest

Macros
#define	ALEPH_PREFIX_TREE_TEST_UNDER_TSAN   0

Functions
void *	operator new (std::size_t size)
void *	operator new[] (std::size_t size)
void *	operator new (std::size_t size, const std::nothrow_t &) noexcept
void *	operator new[] (std::size_t size, const std::nothrow_t &) noexcept
void	operator delete (void *ptr) noexcept
void	operator delete[] (void *ptr) noexcept
void	operator delete (void *ptr, std::size_t) noexcept
void	operator delete[] (void *ptr, std::size_t) noexcept
void	operator delete (void *ptr, const std::nothrow_t &) noexcept
void	operator delete[] (void *ptr, const std::nothrow_t &) noexcept
static std::vector< std::string >	to_sorted_vector (const DynArray< std::string > &words)
static std::vector< std::string >	to_sorted_vector (const Array< std::string > &words)
	TEST_F (PrefixTreeTest, NodeConstruction)
	TEST_F (PrefixTreeTest, NodeSymbol)
	TEST_F (PrefixTreeTest, InitiallyNoChildren)
	TEST_F (PrefixTreeTest, InitiallyNotEndWord)
	TEST_F (PrefixTreeTest, MarkEndWord)
	TEST_F (PrefixTreeTest, SearchChildNotFound)
	TEST_F (PrefixTreeTest, InsertAndSearchChild)
	TEST_F (PrefixTreeTest, ChildrenSortedOrder)
	TEST_F (PrefixTreeTest, GreaterChild)
	TEST_F (PrefixTreeTest, InsertSingleWord)
	TEST_F (PrefixTreeTest, InsertDuplicateWord)
	TEST_F (PrefixTreeTest, InsertMultipleWords)
	TEST_F (PrefixTreeTest, InsertWordsWithCommonPrefix)
	TEST_F (PrefixTreeTest, InsertEmptyString)
	TEST_F (PrefixTreeTest, InsertSingleCharacter)
	TEST_F (PrefixTreeTest, WordEndSurvivesLowerSortedChild)
	TEST_F (PrefixTreeTest, InsertWordCleansDetachedPathOnAllocationFailure)
	TEST_F (PrefixTreeTest, PrefixNotAWord)
	TEST_F (PrefixTreeTest, WordThenPrefix)
	TEST_F (PrefixTreeTest, PrefixThenWord)
	TEST_F (PrefixTreeTest, SearchWordNotFound)
	TEST_F (PrefixTreeTest, SearchWordFound)
	TEST_F (PrefixTreeTest, ContainsNonExistent)
	TEST_F (PrefixTreeTest, SearchPrefixEmpty)
	TEST_F (PrefixTreeTest, SearchPrefixFullMatch)
	TEST_F (PrefixTreeTest, SearchPrefixPartialMatch)
	TEST_F (PrefixTreeTest, SearchPrefixNoMatch)
	TEST_F (PrefixTreeTest, WordsEmpty)
	TEST_F (PrefixTreeTest, WordsSingle)
	TEST_F (PrefixTreeTest, WordsMultiple)
	TEST_F (PrefixTreeTest, WordsWithCommonPrefixes)
	TEST_F (PrefixTreeTest, WordsCanContainDollarCharacter)
	TEST_F (PrefixTreeTest, WordsCanContainEmptyString)
	TEST_F (PrefixTreeTest, CloneEmpty)
	TEST_F (PrefixTreeTest, CloneWithWords)
	TEST_F (PrefixTreeTest, ClonePreservesWordEndFlags)
	TEST_F (PrefixTreeTest, CloneCleansPartialCopyOnAllocationFailure)
	TEST_F (PrefixTreeTest, ToStringEmpty)
	TEST_F (PrefixTreeTest, ToStringWithWord)
	TEST_F (PrefixTreeTest, LongWord)
	TEST_F (PrefixTreeTest, ManyWords)
	TEST_F (PrefixTreeTest, SpecialCharacters)
	TEST_F (PrefixTreeTest, NumericStrings)
	TEST_F (PrefixTreeTest, CountEmpty)
	TEST_F (PrefixTreeTest, CountSingle)
	TEST_F (PrefixTreeTest, CountMultiple)
	TEST_F (PrefixTreeTest, CountWithPrefixes)
	TEST_F (PrefixTreeTest, WordsWithPrefixEmpty)
	TEST_F (PrefixTreeTest, WordsWithPrefixMatch)
	TEST_F (PrefixTreeTest, WordsWithPrefixExactWord)
	TEST_F (PrefixTreeTest, WordsWithPrefixNoMatch)
	TEST_F (PrefixTreeTest, WordsWithEmptyPrefixMatchesWords)
	TEST (PrefixTreeDestroyTest, DestroyWorks)
	TEST (PrefixTreeWrapperTest, DelegatesWordOperations)
	TEST (PrefixTreeWrapperTest, CachedCountTracksWrapperInsertions)
	TEST (PrefixTreeWrapperTest, CachedCountRecomputesAfterMutableRootAccess)
	TEST (PrefixTreeWrapperTest, OwnsRootAndDestroysNodes)
	TEST (PrefixTreeWrapperTest, RootExposesLowLevelAccessWithoutOwnershipTransfer)
	TEST (PrefixTreeWrapperTest, CopyConstructorCreatesIndependentTree)
	TEST (PrefixTreeWrapperTest, CopyAssignmentCreatesIndependentTree)
	TEST (PrefixTreeWrapperTest, MoveConstructorTransfersOwnership)
	TEST (PrefixTreeWrapperTest, MoveAssignmentTransfersOwnershipAndFreesOldRoot)
	TEST (PrefixTreeWrapperTest, CopyAssignmentKeepsOldTreeOnAllocationFailure)
	TEST (PrefixTreeMapTest, DefaultConstructedMapIsEmpty)
	TEST (PrefixTreeMapTest, InsertAndFindValues)
	TEST (PrefixTreeMapTest, DuplicateInsertKeepsOriginalValue)
	TEST (PrefixTreeMapTest, DuplicateMoveInsertDoesNotConsumeValue)
	TEST (PrefixTreeMapTest, InsertOrAssignInsertsThenOverwrites)
	TEST (PrefixTreeMapTest, MutableFindAllowsInPlaceUpdate)
	TEST (PrefixTreeMapTest, EraseRemovesLogicalKeyAndAllowsReinsert)
	TEST (PrefixTreeMapTest, WordsAndWordsWithPrefixReturnStoredKeys)
	TEST (PrefixTreeMapTest, CopyConstructorCreatesIndependentClone)
	TEST (PrefixTreeMapTest, MoveConstructorTransfersContents)
	TEST (PrefixTreeMapTest, ClearRemovesAllKeys)
	TEST (PrefixTreeMapTest, RandomizedOperationsMatchStdMap)
	TEST (PrefixTreeMapTest, MatchesPrefixTreeAndRadixTree)
int	main (int argc, char **argv)

Detailed Description

Tests for Prefix Tree.

Comprehensive test suite for prefix-tree.H (Trie)

Tests all aspects of the Cnode prefix tree including:

• Node construction and basic operations
• Word insertion and search
• Prefix search
• Tree traversal and word extraction
• Cloning
• Edge cases

Definition in file prefix_tree_test.cc.

Macro Definition Documentation

ALEPH_PREFIX_TREE_TEST_UNDER_TSAN

#define ALEPH_PREFIX_TREE_TEST_UNDER_TSAN   0

Definition at line 80 of file prefix_tree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 1411 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator delete() [1/3]

void operator delete ( void *  ptr )

noexcept

Definition at line 195 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator delete() [2/3]

void operator delete ( void *  ptr, const std::nothrow_t &    )

noexcept

Definition at line 215 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator delete() [3/3]

void operator delete ( void *  ptr, std::size_t    )

noexcept

Definition at line 205 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator delete[]() [1/3]

void operator delete[] ( void *  ptr )

noexcept

Definition at line 200 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator delete[]() [2/3]

void operator delete[] ( void *  ptr, const std::nothrow_t &    )

noexcept

Definition at line 220 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator delete[]() [3/3]

void operator delete[] ( void *  ptr, std::size_t    )

noexcept

Definition at line 210 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

operator new() [1/2]

void * operator new

(

std::size_t

size

)

Definition at line 161 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::size().

operator new() [2/2]

void * operator new ( std::size_t  size, const std::nothrow_t &    )

noexcept

Definition at line 171 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::size().

operator new[]() [1/2]

void * operator new[]

(

std::size_t

size

)

Definition at line 166 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::size().

operator new[]() [2/2]

void * operator new[] ( std::size_t  size, const std::nothrow_t &    )

noexcept

Definition at line 183 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::size().

TEST() [1/24]

TEST	(	PrefixTreeDestroyTest	,
		DestroyWorks
	)

Definition at line 896 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching().

TEST() [2/24]

TEST	(	PrefixTreeMapTest	,
		ClearRemovesAllKeys
	)

Definition at line 1301 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::clear(), Aleph::Prefix_Tree_Map< T >::contains(), Aleph::Prefix_Tree_Map< T >::insert(), Aleph::Prefix_Tree_Map< T >::is_empty(), and Aleph::Prefix_Tree_Map< T >::words().

TEST() [3/24]

TEST	(	PrefixTreeMapTest	,
		CopyConstructorCreatesIndependentClone
	)

Definition at line 1264 of file prefix_tree_test.cc.

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

TEST() [4/24]

TEST	(	PrefixTreeMapTest	,
		DefaultConstructedMapIsEmpty
	)

Definition at line 1142 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::contains(), Aleph::Prefix_Tree_Map< T >::count(), Aleph::Prefix_Tree_Map< T >::find(), Aleph::Prefix_Tree_Map< T >::is_empty(), Aleph::Prefix_Tree_Map< T >::size(), and Aleph::Prefix_Tree_Map< T >::words().

TEST() [5/24]

TEST	(	PrefixTreeMapTest	,
		DuplicateInsertKeepsOriginalValue
	)

Definition at line 1174 of file prefix_tree_test.cc.

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

TEST() [6/24]

TEST	(	PrefixTreeMapTest	,
		DuplicateMoveInsertDoesNotConsumeValue
	)

Definition at line 1185 of file prefix_tree_test.cc.

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

TEST() [7/24]

TEST	(	PrefixTreeMapTest	,
		EraseRemovesLogicalKeyAndAllowsReinsert
	)

Definition at line 1231 of file prefix_tree_test.cc.

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

TEST() [8/24]

TEST	(	PrefixTreeMapTest	,
		InsertAndFindValues
	)

Definition at line 1154 of file prefix_tree_test.cc.

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

TEST() [9/24]

TEST	(	PrefixTreeMapTest	,
		InsertOrAssignInsertsThenOverwrites
	)

Definition at line 1199 of file prefix_tree_test.cc.

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

TEST() [10/24]

TEST	(	PrefixTreeMapTest	,
		MatchesPrefixTreeAndRadixTree
	)

Definition at line 1364 of file prefix_tree_test.cc.

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

TEST() [11/24]

TEST	(	PrefixTreeMapTest	,
		MoveConstructorTransfersContents
	)

Definition at line 1284 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::insert(), and Aleph::Prefix_Tree_Map< T >::is_empty().

TEST() [12/24]

TEST	(	PrefixTreeMapTest	,
		MutableFindAllowsInPlaceUpdate
	)

Definition at line 1217 of file prefix_tree_test.cc.

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

TEST() [13/24]

TEST	(	PrefixTreeMapTest	,
		RandomizedOperationsMatchStdMap
	)

Definition at line 1315 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::insert_or_assign(), keys, to_sorted_vector(), and value.

TEST() [14/24]

TEST	(	PrefixTreeMapTest	,
		WordsAndWordsWithPrefixReturnStoredKeys
	)

Definition at line 1249 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree_Map< T >::insert(), to_sorted_vector(), Aleph::Prefix_Tree_Map< T >::words(), and Aleph::Prefix_Tree_Map< T >::words_with_prefix().

TEST() [15/24]

TEST	(	PrefixTreeWrapperTest	,
		CachedCountRecomputesAfterMutableRootAccess
	)

Definition at line 950 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Prefix_Tree::count(), Aleph::Prefix_Tree::insert_word(), Aleph::Prefix_Tree::root(), root(), and Aleph::Prefix_Tree::size().

TEST() [16/24]

TEST	(	PrefixTreeWrapperTest	,
		CachedCountTracksWrapperInsertions
	)

Definition at line 937 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::count(), Aleph::Prefix_Tree::insert_word(), and Aleph::Prefix_Tree::size().

TEST() [17/24]

TEST	(	PrefixTreeWrapperTest	,
		CopyAssignmentCreatesIndependentTree
	)

Definition at line 1028 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), and Aleph::Prefix_Tree::insert_word().

TEST() [18/24]

TEST	(	PrefixTreeWrapperTest	,
		CopyAssignmentKeepsOldTreeOnAllocationFailure
	)

Definition at line 1099 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Prefix_Tree::insert_word(), to_sorted_vector(), and Aleph::Prefix_Tree::words().

TEST() [19/24]

TEST	(	PrefixTreeWrapperTest	,
		CopyConstructorCreatesIndependentTree
	)

Definition at line 1008 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::copy(), Aleph::Prefix_Tree::count(), and Aleph::Prefix_Tree::insert_word().

TEST() [20/24]

TEST	(	PrefixTreeWrapperTest	,
		DelegatesWordOperations
	)

Definition at line 916 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Prefix_Tree::count(), Aleph::Prefix_Tree::insert_word(), Aleph::Prefix_Tree::size(), to_sorted_vector(), Aleph::Prefix_Tree::words(), and Aleph::Prefix_Tree::words_with_prefix().

TEST() [21/24]

TEST	(	PrefixTreeWrapperTest	,
		MoveAssignmentTransfersOwnershipAndFreesOldRoot
	)

Definition at line 1074 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Prefix_Tree::count(), Aleph::Prefix_Tree::insert_word(), Aleph::DynArray< T >::is_empty(), Aleph::Prefix_Tree::words(), and Aleph::Prefix_Tree::words_with_prefix().

TEST() [22/24]

TEST	(	PrefixTreeWrapperTest	,
		MoveConstructorTransfersOwnership
	)

Definition at line 1053 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Prefix_Tree::count(), Aleph::Prefix_Tree::insert_word(), Aleph::DynArray< T >::is_empty(), Aleph::Prefix_Tree::words(), and Aleph::Prefix_Tree::words_with_prefix().

TEST() [23/24]

TEST	(	PrefixTreeWrapperTest	,
		OwnsRootAndDestroysNodes
	)

Definition at line 972 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::count(), Aleph::count(), and Aleph::Prefix_Tree::insert_word().

TEST() [24/24]

TEST	(	PrefixTreeWrapperTest	,
		RootExposesLowLevelAccessWithoutOwnershipTransfer
	)

Definition at line 995 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Prefix_Tree::contains(), Aleph::Cnode::insert_word(), Aleph::Prefix_Tree::root(), and Aleph::Cnode::symbol().

TEST_F() [1/52]

TEST_F	(	PrefixTreeTest	,
		ChildrenSortedOrder
	)

Definition at line 351 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [2/52]

TEST_F	(	PrefixTreeTest	,
		CloneCleansPartialCopyOnAllocationFailure
	)

Definition at line 711 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::clone(), root(), and to_sorted_vector().

TEST_F() [3/52]

TEST_F	(	PrefixTreeTest	,
		CloneEmpty
	)

Definition at line 658 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::clone(), and root().

TEST_F() [4/52]

TEST_F	(	PrefixTreeTest	,
		ClonePreservesWordEndFlags
	)

Definition at line 691 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::clone(), root(), and to_sorted_vector().

TEST_F() [5/52]

TEST_F	(	PrefixTreeTest	,
		CloneWithWords
	)

Definition at line 669 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::clone(), and root().

TEST_F() [6/52]

TEST_F	(	PrefixTreeTest	,
		ContainsNonExistent
	)

Definition at line 529 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [7/52]

TEST_F	(	PrefixTreeTest	,
		CountEmpty
	)

Definition at line 817 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [8/52]

TEST_F	(	PrefixTreeTest	,
		CountMultiple
	)

Definition at line 828 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [9/52]

TEST_F	(	PrefixTreeTest	,
		CountSingle
	)

Definition at line 822 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [10/52]

TEST_F	(	PrefixTreeTest	,
		CountWithPrefixes
	)

Definition at line 836 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [11/52]

TEST_F	(	PrefixTreeTest	,
		GreaterChild
	)

Definition at line 369 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [12/52]

TEST_F	(	PrefixTreeTest	,
		InitiallyNoChildren
	)

Definition at line 311 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Cnode::children().

TEST_F() [13/52]

TEST_F	(	PrefixTreeTest	,
		InitiallyNotEndWord
	)

Definition at line 317 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Cnode::is_end_word().

TEST_F() [14/52]

TEST_F	(	PrefixTreeTest	,
		InsertAndSearchChild
	)

Definition at line 342 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [15/52]

TEST_F	(	PrefixTreeTest	,
		InsertDuplicateWord
	)

Definition at line 390 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [16/52]

TEST_F	(	PrefixTreeTest	,
		InsertEmptyString
	)

Definition at line 418 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [17/52]

TEST_F	(	PrefixTreeTest	,
		InsertMultipleWords
	)

Definition at line 396 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [18/52]

TEST_F	(	PrefixTreeTest	,
		InsertSingleCharacter
	)

Definition at line 425 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [19/52]

TEST_F	(	PrefixTreeTest	,
		InsertSingleWord
	)

Definition at line 384 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [20/52]

TEST_F	(	PrefixTreeTest	,
		InsertWordCleansDetachedPathOnAllocationFailure
	)

Definition at line 445 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), root(), and to_sorted_vector().

TEST_F() [21/52]

TEST_F	(	PrefixTreeTest	,
		InsertWordsWithCommonPrefix
	)

Definition at line 407 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [22/52]

TEST_F	(	PrefixTreeTest	,
		LongWord
	)

Definition at line 772 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [23/52]

TEST_F	(	PrefixTreeTest	,
		ManyWords
	)

Definition at line 779 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), N, and root().

TEST_F() [24/52]

TEST_F	(	PrefixTreeTest	,
		MarkEndWord
	)

Definition at line 323 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Cnode::children(), Aleph::Cnode::is_end_word(), and Aleph::Cnode::mark_end_word().

TEST_F() [25/52]

TEST_F	(	PrefixTreeTest	,
		NodeConstruction
	)

Definition at line 296 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Cnode::symbol().

TEST_F() [26/52]

TEST_F	(	PrefixTreeTest	,
		NodeSymbol
	)

Definition at line 302 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Cnode::symbol().

TEST_F() [27/52]

TEST_F	(	PrefixTreeTest	,
		NumericStrings
	)

Definition at line 803 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [28/52]

TEST_F	(	PrefixTreeTest	,
		PrefixNotAWord
	)

Definition at line 479 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [29/52]

TEST_F	(	PrefixTreeTest	,
		PrefixThenWord
	)

Definition at line 499 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [30/52]

TEST_F	(	PrefixTreeTest	,
		SearchChildNotFound
	)

Definition at line 337 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [31/52]

TEST_F	(	PrefixTreeTest	,
		SearchPrefixEmpty
	)

Definition at line 542 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [32/52]

TEST_F	(	PrefixTreeTest	,
		SearchPrefixFullMatch
	)

Definition at line 550 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [33/52]

TEST_F	(	PrefixTreeTest	,
		SearchPrefixNoMatch
	)

Definition at line 570 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [34/52]

TEST_F	(	PrefixTreeTest	,
		SearchPrefixPartialMatch
	)

Definition at line 560 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [35/52]

TEST_F	(	PrefixTreeTest	,
		SearchWordFound
	)

Definition at line 520 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [36/52]

TEST_F	(	PrefixTreeTest	,
		SearchWordNotFound
	)

Definition at line 512 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [37/52]

TEST_F	(	PrefixTreeTest	,
		SpecialCharacters
	)

Definition at line 792 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [38/52]

TEST_F	(	PrefixTreeTest	,
		ToStringEmpty
	)

Definition at line 751 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [39/52]

TEST_F	(	PrefixTreeTest	,
		ToStringWithWord
	)

Definition at line 758 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [40/52]

TEST_F	(	PrefixTreeTest	,
		WordEndSurvivesLowerSortedChild
	)

Definition at line 431 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), root(), and to_sorted_vector().

TEST_F() [41/52]

TEST_F	(	PrefixTreeTest	,
		WordsCanContainDollarCharacter
	)

Definition at line 629 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), root(), and to_sorted_vector().

TEST_F() [42/52]

TEST_F	(	PrefixTreeTest	,
		WordsCanContainEmptyString
	)

Definition at line 643 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), root(), and to_sorted_vector().

TEST_F() [43/52]

TEST_F	(	PrefixTreeTest	,
		WordsEmpty
	)

Definition at line 584 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [44/52]

TEST_F	(	PrefixTreeTest	,
		WordsMultiple
	)

Definition at line 599 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), root(), and w.

TEST_F() [45/52]

TEST_F	(	PrefixTreeTest	,
		WordsSingle
	)

Definition at line 590 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [46/52]

TEST_F	(	PrefixTreeTest	,
		WordsWithCommonPrefixes
	)

Definition at line 618 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [47/52]

TEST_F	(	PrefixTreeTest	,
		WordsWithEmptyPrefixMatchesWords
	)

Definition at line 885 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), root(), and to_sorted_vector().

TEST_F() [48/52]

TEST_F	(	PrefixTreeTest	,
		WordsWithPrefixEmpty
	)

Definition at line 848 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [49/52]

TEST_F	(	PrefixTreeTest	,
		WordsWithPrefixExactWord
	)

Definition at line 866 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [50/52]

TEST_F	(	PrefixTreeTest	,
		WordsWithPrefixMatch
	)

Definition at line 855 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [51/52]

TEST_F	(	PrefixTreeTest	,
		WordsWithPrefixNoMatch
	)

Definition at line 876 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

TEST_F() [52/52]

TEST_F	(	PrefixTreeTest	,
		WordThenPrefix
	)

Definition at line 490 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), and root().

to_sorted_vector() [1/2]

static std::vector< std::string > to_sorted_vector ( const Array< std::string > &  words )

static

Definition at line 258 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Array< T >::size(), and w.

to_sorted_vector() [2/2]

static std::vector< std::string > to_sorted_vector ( const DynArray< std::string > &  words )

static

Definition at line 250 of file prefix_tree_test.cc.

References Aleph::blossom_maximum_cardinality_matching(), FunctionalMethods< Container, T >::for_each(), and w.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().