tdrbtree_test.cc File Reference

Tests for Tdrbtree. More...

#include <gtest/gtest.h>
#include <tpl_tdRbTree.H>
#include <tpl_rb_tree.H>
#include <ahSort.H>
#include <random>
#include <set>
#include <vector>
#include <string>
#include <functional>

Include dependency graph for tdrbtree_test.cc:

Go to the source code of this file.

Classes
class	TdRbTreeTest
class	TdRbTreeCustomCompareTest
struct	TdRbTreeCustomCompareTest::ReverseCompare

Functions
	TEST_F (TdRbTreeTest, EmptyTree)
	TEST_F (TdRbTreeTest, InsertSingleNode)
	TEST_F (TdRbTreeTest, InsertMultipleNodes)
	TEST_F (TdRbTreeTest, InsertDuplicateKey)
	TEST_F (TdRbTreeTest, SearchNonExistent)
	TEST_F (TdRbTreeTest, RemoveSingleNode)
	TEST_F (TdRbTreeTest, RemoveLeafNode)
	TEST_F (TdRbTreeTest, RemoveInternalNode)
	TEST_F (TdRbTreeTest, RemoveRoot)
	TEST_F (TdRbTreeTest, RemoveNonExistent)
	TEST_F (TdRbTreeTest, RemoveAllNodes)
	TEST_F (TdRbTreeTest, Reset)
	TEST_F (TdRbTreeTest, Swap)
	TEST_F (TdRbTreeCustomCompareTest, ReverseOrder)
	TEST (TdRbTreeFunctorCompare, AbsoluteValueComparator)
	TEST (TdRbTreeStringTest, StringKeys)
	TEST_F (TdRbTreeTest, InsertAscending)
	TEST_F (TdRbTreeTest, InsertDescending)
	TEST_F (TdRbTreeTest, InsertZigZag)
	TEST (TdRbTreeStressTest, RandomInsertRemove)
	TEST (TdRbTreeStressTest, LargeTree)
	TEST (TdRbTreeComparisonTest, SameResultsAsBottomUp)
	TEST_F (TdRbTreeTest, InsertRemoveInsert)
	TEST_F (TdRbTreeTest, NegativeKeys)
	TEST_F (TdRbTreeTest, MinMaxIntKeys)
	TEST (TdRbTreeVtlTest, BasicOperations)
	TEST (TdRbTreeMoveTest, MoveConstructor)
	TEST (TdRbTreeMoveTest, MoveAssignment)
	TEST (TdRbTreeInsertDupTest, AllowsDuplicates)
	TEST (TdRbTreeInsertDupTest, MixedInsert)
	TEST (TdRbTreeSearchOrInsertTest, InsertWhenNotFound)
	TEST (TdRbTreeSearchOrInsertTest, ReturnsExistingWhenFound)
	TEST (TdRbTreeIteratorTest, InOrderTraversal)
	TEST (TdRbTreeIteratorTest, EmptyTree)
	TEST (TdRbTreeIteratorTest, SingleElement)
int	main (int argc, char **argv)

Detailed Description

Tests for Tdrbtree.

Exhaustive tests for Top-Down Red-Black Tree implementation.

Tests cover:

• Basic operations (insert, search, remove)
• Red-black property invariants
• Custom comparators
• Edge cases (empty tree, single node, duplicates)
• Stress tests with random operations
• Comparison with bottom-up implementation

Definition in file tdrbtree_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 967 of file tdrbtree_test.cc.

References Aleph::maps().

TEST() [1/15]

TEST	(	TdRbTreeComparisonTest	,
		SameResultsAsBottomUp
	)

Definition at line 583 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), N, Aleph::DynList< T >::remove(), rng, and Aleph::HTList::size().

TEST() [2/15]

TEST	(	TdRbTreeFunctorCompare	,
		AbsoluteValueComparator
	)

Definition at line 354 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST() [3/15]

TEST	(	TdRbTreeInsertDupTest	,
		AllowsDuplicates
	)

Definition at line 805 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert_dup(), Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST() [4/15]

TEST	(	TdRbTreeInsertDupTest	,
		MixedInsert
	)

Definition at line 830 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert_dup(), Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST() [5/15]

TEST	(	TdRbTreeIteratorTest	,
		EmptyTree
	)

Definition at line 940 of file tdrbtree_test.cc.

References Aleph::maps().

TEST() [6/15]

TEST	(	TdRbTreeIteratorTest	,
		InOrderTraversal
	)

Definition at line 908 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), and nodes.

TEST() [7/15]

TEST	(	TdRbTreeIteratorTest	,
		SingleElement
	)

Definition at line 948 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), KEY, and Aleph::maps().

TEST() [8/15]

TEST	(	TdRbTreeMoveTest	,
		MoveAssignment
	)

Definition at line 771 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST() [9/15]

TEST	(	TdRbTreeMoveTest	,
		MoveConstructor
	)

Definition at line 739 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::HTList::is_empty(), Aleph::maps(), nodes, and Aleph::HTList::size().

TEST() [10/15]

TEST	(	TdRbTreeSearchOrInsertTest	,
		InsertWhenNotFound
	)

Definition at line 859 of file tdrbtree_test.cc.

References Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::search_or_insert(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::size().

TEST() [11/15]

TEST	(	TdRbTreeSearchOrInsertTest	,
		ReturnsExistingWhenFound
	)

Definition at line 880 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::search_or_insert(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::size().

TEST() [12/15]

TEST	(	TdRbTreeStressTest	,
		LargeTree
	)

Definition at line 535 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::maps(), N, nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST() [13/15]

TEST	(	TdRbTreeStressTest	,
		RandomInsertRemove
	)

Definition at line 477 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), rng, Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST() [14/15]

TEST	(	TdRbTreeStringTest	,
		StringKeys
	)

Definition at line 393 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST() [15/15]

TEST	(	TdRbTreeVtlTest	,
		BasicOperations
	)

Definition at line 703 of file tdrbtree_test.cc.

References Aleph::GenTdRbTree< NodeType, Key, Compare >::insert(), Aleph::maps(), nodes, Aleph::GenTdRbTree< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTree< NodeType, Key, Compare >::search(), Aleph::GenTdRbTree< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTree< NodeType, Key, Compare >::verifyRedBlack().

TEST_F() [1/20]

TEST_F	(	TdRbTreeCustomCompareTest	,
		ReverseOrder
	)

Definition at line 338 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [2/20]

TEST_F	(	TdRbTreeTest	,
		EmptyTree
	)

Definition at line 140 of file tdrbtree_test.cc.

References Aleph::maps().

TEST_F() [3/20]

TEST_F	(	TdRbTreeTest	,
		InsertAscending
	)

Definition at line 428 of file tdrbtree_test.cc.

References Aleph::maps().

TEST_F() [4/20]

TEST_F	(	TdRbTreeTest	,
		InsertDescending
	)

Definition at line 440 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), and Aleph::maps().

TEST_F() [5/20]

TEST_F	(	TdRbTreeTest	,
		InsertDuplicateKey
	)

Definition at line 176 of file tdrbtree_test.cc.

References Aleph::maps().

TEST_F() [6/20]

TEST_F	(	TdRbTreeTest	,
		InsertMultipleNodes
	)

Definition at line 160 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [7/20]

TEST_F	(	TdRbTreeTest	,
		InsertRemoveInsert
	)

Definition at line 650 of file tdrbtree_test.cc.

References COLOR, Aleph::LLINK(), Aleph::maps(), RED, and Aleph::RLINK().

TEST_F() [8/20]

TEST_F	(	TdRbTreeTest	,
		InsertSingleNode
	)

Definition at line 149 of file tdrbtree_test.cc.

References Aleph::maps().

TEST_F() [9/20]

TEST_F	(	TdRbTreeTest	,
		InsertZigZag
	)

Definition at line 452 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::low(), and Aleph::maps().

TEST_F() [10/20]

TEST_F	(	TdRbTreeTest	,
		MinMaxIntKeys
	)

Definition at line 682 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [11/20]

TEST_F	(	TdRbTreeTest	,
		NegativeKeys
	)

Definition at line 667 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [12/20]

TEST_F	(	TdRbTreeTest	,
		RemoveAllNodes
	)

Definition at line 273 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [13/20]

TEST_F	(	TdRbTreeTest	,
		RemoveInternalNode
	)

Definition at line 228 of file tdrbtree_test.cc.

References Aleph::maps(), nodes, and Aleph::DynList< T >::remove().

TEST_F() [14/20]

TEST_F	(	TdRbTreeTest	,
		RemoveLeafNode
	)

Definition at line 211 of file tdrbtree_test.cc.

References KEY, Aleph::maps(), nodes, and Aleph::DynList< T >::remove().

TEST_F() [15/20]

TEST_F	(	TdRbTreeTest	,
		RemoveNonExistent
	)

Definition at line 262 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [16/20]

TEST_F	(	TdRbTreeTest	,
		RemoveRoot
	)

Definition at line 247 of file tdrbtree_test.cc.

References Aleph::maps(), nodes, and Aleph::DynList< T >::remove().

TEST_F() [17/20]

TEST_F	(	TdRbTreeTest	,
		RemoveSingleNode
	)

Definition at line 199 of file tdrbtree_test.cc.

References Aleph::maps(), and Aleph::DynList< T >::remove().

TEST_F() [18/20]

TEST_F	(	TdRbTreeTest	,
		Reset
	)

Definition at line 297 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [19/20]

TEST_F	(	TdRbTreeTest	,
		SearchNonExistent
	)

Definition at line 188 of file tdrbtree_test.cc.

References Aleph::maps(), and nodes.

TEST_F() [20/20]

TEST_F	(	TdRbTreeTest	,
		Swap
	)

Definition at line 310 of file tdrbtree_test.cc.

References Aleph::DynList< T >::insert(), Aleph::maps(), Aleph::HTList::size(), and Aleph::DynList< T >::swap().