rb-tree.cc File Reference

Tests for Rb Tree. More...

#include <algorithm>
#include <cmath>
#include <random>
#include <set>
#include <vector>
#include <functional>
#include <gtest/gtest.h>
#include <tpl_rb_tree.H>
#include <tpl_hRbTree.H>

Include dependency graph for rb-tree.cc:

Go to the source code of this file.

Functions
	TEST (RbTree, EmptyTreeProperties)
	TEST (RbTree, InsertSingleElement)
	TEST (RbTree, InsertMultipleElements)
	TEST (RbTree, InsertRejectsDuplicates)
	TEST (RbTree, DuplicateAtIntermediateLevel)
	TEST (RbTree, DuplicateAfterOnlyLeftDescents)
	TEST (RbTree, DuplicateDeepInTree)
	TEST (RbTree, InsertDupAllowsDuplicates)
	TEST (RbTree, SearchFindsExistingKey)
	TEST (RbTree, SearchReturnsNullForMissingKey)
	TEST (RbTree, SearchOrInsertBehavior)
	TEST (RbTree, RemoveExistingKey)
	TEST (RbTree, RemoveReturnsNullForMissingKey)
	TEST (RbTree, RemoveFromEmptyTree)
	TEST (RbTree, RemoveRoot)
	TEST (RbTree, RemoveAllElements)
	TEST (RbTree, RemoveInOrder)
	TEST (RbTree, RemoveInReverseOrder)
	TEST (RbTree, RemoveDuplicatesInsertedWithInsertDup)
	TEST (RbTree, TreeRemainsValidAfterMultipleInserts)
	TEST (RbTree, NoConsecutiveReds)
	TEST (RbTree, BlackHeightConsistent)
	TEST (RbTree, SingleElementOperations)
	TEST (RbTree, InsertInDescendingOrder)
	TEST (RbTree, InsertInAscendingOrder)
	TEST (RbTree, CustomComparatorGreater)
	TEST (RbTree, RandomInsertSearchRemove)
	TEST (RbTree, LargeTreeOperations)
	TEST (RbTree, IteratorEmptyTree)
	TEST (RbTree, IteratorTraversesInOrder)
	TEST (RbTree, IteratorAfterRemoval)
	TEST (RbTree, VerifyDetectsValidTree)
	TEST (RbTree, IsEmptyMethod)
	TEST (RbTree, SizeMethod)
	TEST (RbTree, SwapTrees)
	TEST (RbTree, MoveConstructor)
	TEST (RbTree, MoveAssignment)
	TEST (HtdRbTreeCompat, EmptyTreeProperties)
	TEST (HtdRbTreeCompat, InsertRejectsDuplicates)
	TEST (HtdRbTreeCompat, InsertDupAllowsDuplicates)
	TEST (HtdRbTreeCompat, SearchOrInsertBehavior)
	TEST (HtdRbTreeCompat, RemoveExistingKey)
	TEST (HtdRbTreeCompat, RemoveFromSingleElementTree)
	TEST (HtdRbTreeCompat, RemoveAllElementsInOrder)
	TEST (HtdRbTreeCompat, RemoveReturnsNullForMissingKey)
	TEST (HtdRbTreeCompat, RemoveDuplicatesInsertedWithInsertDup)
	TEST (HtdRbTreeCompat, IteratorTraversesInOrder)
	TEST (HtdRbTreeCompat, IteratorEmptyTree)
	TEST (HtdRbTreeCompat, SwapTrees)
	TEST (HtdRbTreeCompat, StatefulComparatorAffectsEquality)
	TEST (HtdRbTreeCompat, NegativeKeys)
	TEST (HtdRbTreeCompat, RandomInsertSearchRemove)
	TEST (HtdRbTreeCompat, InsertSingleElement)
	TEST (HtdRbTreeCompat, InsertMultipleElements)
	TEST (HtdRbTreeCompat, SearchFindsExistingKey)
	TEST (HtdRbTreeCompat, SearchReturnsNullForMissingKey)
	TEST (HtdRbTreeCompat, RemoveFromEmptyTree)
	TEST (HtdRbTreeCompat, RemoveRoot)
	TEST (HtdRbTreeCompat, RemoveInReverseOrder)
	TEST (HtdRbTreeCompat, InsertInDescendingOrder)
	TEST (HtdRbTreeCompat, InsertInAscendingOrder)
	TEST (HtdRbTreeCompat, LargeTreeOperations)
	TEST (HtdRbTreeCompat, CustomComparatorGreater)
	TEST (HtdRbTreeCompat, IteratorAfterRemoval)
	TEST (HtdRbTreeCompat, MoveConstructor)
	TEST (HtdRbTreeCompat, MoveAssignment)
	TEST (RbTreeVtl, BasicOperations)
	TEST (RbTree, NegativeKeys)
	TEST (RbTree, CustomComparatorWithRemove)
	TEST (RbTree, Stress_AscendingInsertion)
	TEST (RbTree, Stress_DescendingInsertion)
	TEST (RbTree, Stress_ZigzagInsertion)
	TEST (RbTree, Fuzz_LargeScaleRandomOps)
	TEST (RbTree, Stress_BulkInsertBulkRemove)
	TEST (RbTree, Stress_ManyDuplicates)
	TEST (RbTree, Stress_AlternatingInsertRemove)
	TEST (RbTree, Stress_StringKeys)
	TEST (HtdRbTreeCompat, Stress_LargeScaleOps)

Detailed Description

Tests for Rb Tree.

Definition in file rb-tree.cc.

Function Documentation

TEST() [1/78]

TEST	(	HtdRbTreeCompat	,
		CustomComparatorGreater
	)

Definition at line 1453 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, KEY, and keys.

TEST() [2/78]

TEST	(	HtdRbTreeCompat	,
		EmptyTreeProperties
	)

Definition at line 957 of file rb-tree.cc.

References Aleph::check_bst(), and Aleph::divide_and_conquer_partition_dp().

TEST() [3/78]

TEST	(	HtdRbTreeCompat	,
		InsertDupAllowsDuplicates
	)

Definition at line 985 of file rb-tree.cc.

References Aleph::check_bst(), and Aleph::divide_and_conquer_partition_dp().

TEST() [4/78]

TEST	(	HtdRbTreeCompat	,
		InsertInAscendingOrder
	)

Definition at line 1412 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and keys.

TEST() [5/78]

TEST	(	HtdRbTreeCompat	,
		InsertInDescendingOrder
	)

Definition at line 1397 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and keys.

TEST() [6/78]

TEST	(	HtdRbTreeCompat	,
		InsertMultipleElements
	)

Definition at line 1301 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), k, and keys.

TEST() [7/78]

TEST	(	HtdRbTreeCompat	,
		InsertRejectsDuplicates
	)

Definition at line 968 of file rb-tree.cc.

References Aleph::check_bst(), and Aleph::divide_and_conquer_partition_dp().

TEST() [8/78]

TEST	(	HtdRbTreeCompat	,
		InsertSingleElement
	)

Definition at line 1286 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [9/78]

TEST	(	HtdRbTreeCompat	,
		IteratorAfterRemoval
	)

Definition at line 1478 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and KEY.

TEST() [10/78]

TEST	(	HtdRbTreeCompat	,
		IteratorEmptyTree
	)

Definition at line 1134 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [11/78]

TEST	(	HtdRbTreeCompat	,
		IteratorTraversesInOrder
	)

Definition at line 1117 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and KEY.

TEST() [12/78]

TEST	(	HtdRbTreeCompat	,
		LargeTreeOperations
	)

Definition at line 1427 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and N.

TEST() [13/78]

TEST	(	HtdRbTreeCompat	,
		MoveAssignment
	)

Definition at line 1518 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [14/78]

TEST	(	HtdRbTreeCompat	,
		MoveConstructor
	)

Definition at line 1497 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [15/78]

TEST	(	HtdRbTreeCompat	,
		NegativeKeys
	)

Definition at line 1198 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and keys.

TEST() [16/78]

TEST	(	HtdRbTreeCompat	,
		RandomInsertSearchRemove
	)

Definition at line 1217 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), k, KEY, keys, and rng.

TEST() [17/78]

TEST	(	HtdRbTreeCompat	,
		RemoveAllElementsInOrder
	)

Definition at line 1056 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and keys.

TEST() [18/78]

TEST	(	HtdRbTreeCompat	,
		RemoveDuplicatesInsertedWithInsertDup
	)

Definition at line 1092 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), KEY, and QuadTree::remove().

TEST() [19/78]

TEST	(	HtdRbTreeCompat	,
		RemoveExistingKey
	)

Definition at line 1019 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and KEY.

TEST() [20/78]

TEST	(	HtdRbTreeCompat	,
		RemoveFromEmptyTree
	)

Definition at line 1350 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [21/78]

TEST	(	HtdRbTreeCompat	,
		RemoveFromSingleElementTree
	)

Definition at line 1038 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and KEY.

TEST() [22/78]

TEST	(	HtdRbTreeCompat	,
		RemoveInReverseOrder
	)

Definition at line 1377 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [23/78]

TEST	(	HtdRbTreeCompat	,
		RemoveReturnsNullForMissingKey
	)

Definition at line 1078 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [24/78]

TEST	(	HtdRbTreeCompat	,
		RemoveRoot
	)

Definition at line 1358 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and KEY.

TEST() [25/78]

TEST	(	HtdRbTreeCompat	,
		SearchFindsExistingKey
	)

Definition at line 1316 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and KEY.

TEST() [26/78]

TEST	(	HtdRbTreeCompat	,
		SearchOrInsertBehavior
	)

Definition at line 999 of file rb-tree.cc.

References Aleph::check_bst(), Aleph::divide_and_conquer_partition_dp(), and KEY.

TEST() [27/78]

TEST	(	HtdRbTreeCompat	,
		SearchReturnsNullForMissingKey
	)

Definition at line 1334 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [28/78]

TEST	(	HtdRbTreeCompat	,
		StatefulComparatorAffectsEquality
	)

Definition at line 1173 of file rb-tree.cc.

References Aleph::check_bst(), Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), QuadTree::remove(), and QuadTree::search().

TEST() [29/78]

TEST	(	HtdRbTreeCompat	,
		Stress_LargeScaleOps
	)

Definition at line 1884 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.

TEST() [30/78]

TEST	(	HtdRbTreeCompat	,
		SwapTrees
	)

Definition at line 1142 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [31/78]

TEST	(	RbTree	,
		BlackHeightConsistent
	)

Definition at line 567 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and rng.

TEST() [32/78]

TEST	(	RbTree	,
		CustomComparatorGreater
	)

Definition at line 640 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), k, KEY, keys, LLINK, nodes, r, and RLINK.

TEST() [33/78]

TEST	(	RbTree	,
		CustomComparatorWithRemove
	)

Definition at line 1589 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [34/78]

TEST	(	RbTree	,
		DuplicateAfterOnlyLeftDescents
	)

Definition at line 266 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [35/78]

TEST	(	RbTree	,
		DuplicateAtIntermediateLevel
	)

Definition at line 243 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [36/78]

TEST	(	RbTree	,
		DuplicateDeepInTree
	)

Definition at line 288 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [37/78]

TEST	(	RbTree	,
		EmptyTreeProperties
	)

Definition at line 183 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::search().

TEST() [38/78]

TEST	(	RbTree	,
		Fuzz_LargeScaleRandomOps
	)

Definition at line 1679 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, keys, QuadTree::remove(), and QuadTree::search().

TEST() [39/78]

TEST	(	RbTree	,
		InsertDupAllowsDuplicates
	)

Definition at line 309 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), and keys.

TEST() [40/78]

TEST	(	RbTree	,
		InsertInAscendingOrder
	)

Definition at line 621 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, and keys.

TEST() [41/78]

TEST	(	RbTree	,
		InsertInDescendingOrder
	)

Definition at line 606 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, and keys.

TEST() [42/78]

TEST	(	RbTree	,
		InsertMultipleElements
	)

Definition at line 207 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, and keys.

TEST() [43/78]

TEST	(	RbTree	,
		InsertRejectsDuplicates
	)

Definition at line 225 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [44/78]

TEST	(	RbTree	,
		InsertSingleElement
	)

Definition at line 192 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [45/78]

TEST	(	RbTree	,
		IsEmptyMethod
	)

Definition at line 842 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and QuadTree::remove().

TEST() [46/78]

TEST	(	RbTree	,
		IteratorAfterRemoval
	)

Definition at line 804 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, KEY, and QuadTree::remove().

TEST() [47/78]

TEST	(	RbTree	,
		IteratorEmptyTree
	)

Definition at line 780 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [48/78]

TEST	(	RbTree	,
		IteratorTraversesInOrder
	)

Definition at line 788 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and KEY.

TEST() [49/78]

TEST	(	RbTree	,
		LargeTreeOperations
	)

Definition at line 749 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, N, and QuadTree::remove().

TEST() [50/78]

TEST	(	RbTree	,
		MoveAssignment
	)

Definition at line 934 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [51/78]

TEST	(	RbTree	,
		MoveConstructor
	)

Definition at line 912 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [52/78]

TEST	(	RbTree	,
		NegativeKeys
	)

Definition at line 1571 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, keys, and QuadTree::search().

TEST() [53/78]

TEST	(	RbTree	,
		NoConsecutiveReds
	)

Definition at line 554 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [54/78]

TEST	(	RbTree	,
		RandomInsertSearchRemove
	)

Definition at line 678 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, KEY, keys, QuadTree::remove(), rng, and QuadTree::search().

TEST() [55/78]

TEST	(	RbTree	,
		RemoveAllElements
	)

Definition at line 447 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, keys, and QuadTree::remove().

TEST() [56/78]

TEST	(	RbTree	,
		RemoveDuplicatesInsertedWithInsertDup
	)

Definition at line 508 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), KEY, and QuadTree::remove().

TEST() [57/78]

TEST	(	RbTree	,
		RemoveExistingKey
	)

Definition at line 383 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), QuadTree::insert(), k, KEY, keys, QuadTree::remove(), and QuadTree::search().

TEST() [58/78]

TEST	(	RbTree	,
		RemoveFromEmptyTree
	)

Definition at line 420 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::remove().

TEST() [59/78]

TEST	(	RbTree	,
		RemoveInOrder
	)

Definition at line 468 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and QuadTree::remove().

TEST() [60/78]

TEST	(	RbTree	,
		RemoveInReverseOrder
	)

Definition at line 488 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and QuadTree::remove().

TEST() [61/78]

TEST	(	RbTree	,
		RemoveReturnsNullForMissingKey
	)

Definition at line 405 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and QuadTree::remove().

TEST() [62/78]

TEST	(	RbTree	,
		RemoveRoot
	)

Definition at line 428 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), KEY, and QuadTree::remove().

TEST() [63/78]

TEST	(	RbTree	,
		SearchFindsExistingKey
	)

Definition at line 324 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, KEY, and QuadTree::search().

TEST() [64/78]

TEST	(	RbTree	,
		SearchOrInsertBehavior
	)

Definition at line 358 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and KEY.

TEST() [65/78]

TEST	(	RbTree	,
		SearchReturnsNullForMissingKey
	)

Definition at line 342 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and QuadTree::search().

TEST() [66/78]

TEST	(	RbTree	,
		SingleElementOperations
	)

Definition at line 589 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), QuadTree::remove(), and QuadTree::search().

TEST() [67/78]

TEST	(	RbTree	,
		SizeMethod
	)

Definition at line 858 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and QuadTree::remove().

TEST() [68/78]

TEST	(	RbTree	,
		Stress_AlternatingInsertRemove
	)

Definition at line 1799 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and QuadTree::remove().

TEST() [69/78]

TEST	(	RbTree	,
		Stress_AscendingInsertion
	)

Definition at line 1623 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, N, and QuadTree::search().

TEST() [70/78]

TEST	(	RbTree	,
		Stress_BulkInsertBulkRemove
	)

Definition at line 1739 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, N, and QuadTree::remove().

TEST() [71/78]

TEST	(	RbTree	,
		Stress_DescendingInsertion
	)

Definition at line 1645 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and N.

TEST() [72/78]

TEST	(	RbTree	,
		Stress_ManyDuplicates
	)

Definition at line 1770 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), k, N, and QuadTree::remove().

TEST() [73/78]

TEST	(	RbTree	,
		Stress_StringKeys
	)

Definition at line 1842 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), nodes, and random_string().

TEST() [74/78]

TEST	(	RbTree	,
		Stress_ZigzagInsertion
	)

Definition at line 1662 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), k, and N.

TEST() [75/78]

TEST	(	RbTree	,
		SwapTrees
	)

Definition at line 884 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), and QuadTree::insert().

TEST() [76/78]

TEST	(	RbTree	,
		TreeRemainsValidAfterMultipleInserts
	)

Definition at line 538 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and QuadTree::insert().

TEST() [77/78]

TEST	(	RbTree	,
		VerifyDetectsValidTree
	)

Definition at line 827 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), QuadTree::insert(), and k.

TEST() [78/78]

TEST	(	RbTreeVtl	,
		BasicOperations
	)

Definition at line 1539 of file rb-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), k, and KEY.