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 <numeric>
#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 1454 of file rb-tree.cc.

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

TEST() [2/78]

TEST	(	HtdRbTreeCompat	,
		EmptyTreeProperties
	)

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

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

TEST() [3/78]

TEST	(	HtdRbTreeCompat	,
		InsertDupAllowsDuplicates
	)

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

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

TEST() [4/78]

TEST	(	HtdRbTreeCompat	,
		InsertInAscendingOrder
	)

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

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

TEST() [5/78]

TEST	(	HtdRbTreeCompat	,
		InsertInDescendingOrder
	)

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

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

TEST() [6/78]

TEST	(	HtdRbTreeCompat	,
		InsertMultipleElements
	)

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

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

TEST() [7/78]

TEST	(	HtdRbTreeCompat	,
		InsertRejectsDuplicates
	)

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

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

TEST() [8/78]

TEST	(	HtdRbTreeCompat	,
		InsertSingleElement
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [9/78]

TEST	(	HtdRbTreeCompat	,
		IteratorAfterRemoval
	)

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

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

TEST() [10/78]

TEST	(	HtdRbTreeCompat	,
		IteratorEmptyTree
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [11/78]

TEST	(	HtdRbTreeCompat	,
		IteratorTraversesInOrder
	)

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

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

TEST() [12/78]

TEST	(	HtdRbTreeCompat	,
		LargeTreeOperations
	)

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

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

TEST() [13/78]

TEST	(	HtdRbTreeCompat	,
		MoveAssignment
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [14/78]

TEST	(	HtdRbTreeCompat	,
		MoveConstructor
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [15/78]

TEST	(	HtdRbTreeCompat	,
		NegativeKeys
	)

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

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

TEST() [16/78]

TEST	(	HtdRbTreeCompat	,
		RandomInsertSearchRemove
	)

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

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

TEST() [17/78]

TEST	(	HtdRbTreeCompat	,
		RemoveAllElementsInOrder
	)

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

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

TEST() [18/78]

TEST	(	HtdRbTreeCompat	,
		RemoveDuplicatesInsertedWithInsertDup
	)

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

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

TEST() [19/78]

TEST	(	HtdRbTreeCompat	,
		RemoveExistingKey
	)

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

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

TEST() [20/78]

TEST	(	HtdRbTreeCompat	,
		RemoveFromEmptyTree
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [21/78]

TEST	(	HtdRbTreeCompat	,
		RemoveFromSingleElementTree
	)

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

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

TEST() [22/78]

TEST	(	HtdRbTreeCompat	,
		RemoveInReverseOrder
	)

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

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

TEST() [23/78]

TEST	(	HtdRbTreeCompat	,
		RemoveReturnsNullForMissingKey
	)

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

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

TEST() [24/78]

TEST	(	HtdRbTreeCompat	,
		RemoveRoot
	)

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

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

TEST() [25/78]

TEST	(	HtdRbTreeCompat	,
		SearchFindsExistingKey
	)

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

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

TEST() [26/78]

TEST	(	HtdRbTreeCompat	,
		SearchOrInsertBehavior
	)

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

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

TEST() [27/78]

TEST	(	HtdRbTreeCompat	,
		SearchReturnsNullForMissingKey
	)

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

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

TEST() [28/78]

TEST	(	HtdRbTreeCompat	,
		StatefulComparatorAffectsEquality
	)

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

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

TEST() [29/78]

TEST	(	HtdRbTreeCompat	,
		Stress_LargeScaleOps
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and k.

TEST() [30/78]

TEST	(	HtdRbTreeCompat	,
		SwapTrees
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [31/78]

TEST	(	RbTree	,
		BlackHeightConsistent
	)

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

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

TEST() [32/78]

TEST	(	RbTree	,
		CustomComparatorGreater
	)

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

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

TEST() [33/78]

TEST	(	RbTree	,
		CustomComparatorWithRemove
	)

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

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

TEST() [34/78]

TEST	(	RbTree	,
		DuplicateAfterOnlyLeftDescents
	)

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

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

TEST() [35/78]

TEST	(	RbTree	,
		DuplicateAtIntermediateLevel
	)

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

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

TEST() [36/78]

TEST	(	RbTree	,
		DuplicateDeepInTree
	)

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

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

TEST() [37/78]

TEST	(	RbTree	,
		EmptyTreeProperties
	)

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

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

TEST() [38/78]

TEST	(	RbTree	,
		Fuzz_LargeScaleRandomOps
	)

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

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

TEST() [39/78]

TEST	(	RbTree	,
		InsertDupAllowsDuplicates
	)

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

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

TEST() [40/78]

TEST	(	RbTree	,
		InsertInAscendingOrder
	)

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

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

TEST() [41/78]

TEST	(	RbTree	,
		InsertInDescendingOrder
	)

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

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

TEST() [42/78]

TEST	(	RbTree	,
		InsertMultipleElements
	)

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

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

TEST() [43/78]

TEST	(	RbTree	,
		InsertRejectsDuplicates
	)

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

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

TEST() [44/78]

TEST	(	RbTree	,
		InsertSingleElement
	)

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

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

TEST() [45/78]

TEST	(	RbTree	,
		IsEmptyMethod
	)

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

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

TEST() [46/78]

TEST	(	RbTree	,
		IteratorAfterRemoval
	)

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

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

TEST() [47/78]

TEST	(	RbTree	,
		IteratorEmptyTree
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [48/78]

TEST	(	RbTree	,
		IteratorTraversesInOrder
	)

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

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

TEST() [49/78]

TEST	(	RbTree	,
		LargeTreeOperations
	)

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

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

TEST() [50/78]

TEST	(	RbTree	,
		MoveAssignment
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [51/78]

TEST	(	RbTree	,
		MoveConstructor
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [52/78]

TEST	(	RbTree	,
		NegativeKeys
	)

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

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

TEST() [53/78]

TEST	(	RbTree	,
		NoConsecutiveReds
	)

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

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

TEST() [54/78]

TEST	(	RbTree	,
		RandomInsertSearchRemove
	)

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

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

TEST() [55/78]

TEST	(	RbTree	,
		RemoveAllElements
	)

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

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

TEST() [56/78]

TEST	(	RbTree	,
		RemoveDuplicatesInsertedWithInsertDup
	)

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

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

TEST() [57/78]

TEST	(	RbTree	,
		RemoveExistingKey
	)

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

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

TEST() [58/78]

TEST	(	RbTree	,
		RemoveFromEmptyTree
	)

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

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

TEST() [59/78]

TEST	(	RbTree	,
		RemoveInOrder
	)

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

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

TEST() [60/78]

TEST	(	RbTree	,
		RemoveInReverseOrder
	)

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

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

TEST() [61/78]

TEST	(	RbTree	,
		RemoveReturnsNullForMissingKey
	)

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

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

TEST() [62/78]

TEST	(	RbTree	,
		RemoveRoot
	)

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

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

TEST() [63/78]

TEST	(	RbTree	,
		SearchFindsExistingKey
	)

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

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

TEST() [64/78]

TEST	(	RbTree	,
		SearchOrInsertBehavior
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and KEY.

TEST() [65/78]

TEST	(	RbTree	,
		SearchReturnsNullForMissingKey
	)

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

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

TEST() [66/78]

TEST	(	RbTree	,
		SingleElementOperations
	)

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

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

TEST() [67/78]

TEST	(	RbTree	,
		SizeMethod
	)

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

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

TEST() [68/78]

TEST	(	RbTree	,
		Stress_AlternatingInsertRemove
	)

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

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

TEST() [69/78]

TEST	(	RbTree	,
		Stress_AscendingInsertion
	)

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

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

TEST() [70/78]

TEST	(	RbTree	,
		Stress_BulkInsertBulkRemove
	)

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

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

TEST() [71/78]

TEST	(	RbTree	,
		Stress_DescendingInsertion
	)

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

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

TEST() [72/78]

TEST	(	RbTree	,
		Stress_ManyDuplicates
	)

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

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

TEST() [73/78]

TEST	(	RbTree	,
		Stress_StringKeys
	)

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

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

TEST() [74/78]

TEST	(	RbTree	,
		Stress_ZigzagInsertion
	)

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

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

TEST() [75/78]

TEST	(	RbTree	,
		SwapTrees
	)

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

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

TEST() [76/78]

TEST	(	RbTree	,
		TreeRemainsValidAfterMultipleInserts
	)

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

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

TEST() [77/78]

TEST	(	RbTree	,
		VerifyDetectsValidTree
	)

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

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

TEST() [78/78]

TEST	(	RbTreeVtl	,
		BasicOperations
	)

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

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