rand-tree.cc File Reference

Tests for Rand Tree. More...

#include <gtest/gtest.h>
#include <tpl_rand_tree.H>
#include <tpl_binNodeUtils.H>
#include <random>
#include <set>
#include <vector>
#include <algorithm>

Include dependency graph for rand-tree.cc:

Go to the source code of this file.

Classes
class	NodePool

Typedefs
using	Tree = Rand_Tree< int >
using	Node = Tree::Node

Functions
template<typename NodeT >
std::vector< int >	inorder_keys (NodeT *root)
	TEST (RandTree, EmptyTreeProperties)
	TEST (RandTree, SearchOnEmptyTreeReturnsNull)
	TEST (RandTree, RemoveFromEmptyTreeReturnsNull)
	TEST (RandTree, InsertSingleElement)
	TEST (RandTree, InsertMultipleElements)
	TEST (RandTree, InsertRejectsDuplicates)
	TEST (RandTree, InsertDupAllowsDuplicates)
	TEST (RandTree, InsertInAscendingOrder)
	TEST (RandTree, InsertInDescendingOrder)
	TEST (RandTree, SearchFindsExistingKey)
	TEST (RandTree, SearchReturnsNullForMissingKey)
	TEST (RandTree, SearchOrInsertReturnsExisting)
	TEST (RandTree, SearchOrInsertInsertsNew)
	TEST (RandTree, RemoveExistingKey)
	TEST (RandTree, RemoveReturnsNullForMissingKey)
	TEST (RandTree, RemoveRoot)
	TEST (RandTree, RemoveAllElements)
	TEST (RandTree, RemoveInOrder)
	TEST (RandTree, RemoveInReverseOrder)
	TEST (RandTree, SelectReturnsCorrectNode)
	TEST (RandTree, SelectOutOfRangeThrows)
	TEST (RandTree, PositionOfExistingKey)
	TEST (RandTree, PositionOfMissingKey)
	TEST (RandTree, FindPositionOfExistingKey)
	TEST (RandTree, FindPositionOfMissingKeyInMiddle)
	TEST (RandTree, FindPositionLessThanMin)
	TEST (RandTree, FindPositionGreaterThanMax)
	TEST (RandTree, RemovePosValidPosition)
	TEST (RandTree, RemovePosFirst)
	TEST (RandTree, RemovePosLast)
	TEST (RandTree, SplitKeyNotInTree)
	TEST (RandTree, SplitKeyInTree)
	TEST (RandTree, SplitKeyDup)
	TEST (RandTree, SplitPos)
	TEST (RandTree, JoinWithNoDuplicates)
	TEST (RandTree, JoinWithDuplicates)
	TEST (RandTree, JoinDup)
	TEST (RandTree, JoinExclusive)
	TEST (RandTree, IteratorTraversesInOrder)
	TEST (RandTree, IteratorOnEmptyTree)
	TEST (RandTree, IteratorAfterRemoval)
	TEST (RandTree, SwapTrees)
	TEST (RandTree, SeedAffectsStructure)
	TEST (RandTree, CustomComparatorGreater)
	TEST (RandTree, NegativeKeys)
	TEST (RandTree, SingleElementOperations)
	TEST (RandTree, RandomInsertSearchRemove)
	TEST (RandTree, LargeTreeOperations)
	TEST (RandTreeVtl, BasicOperations)
	TEST (RandTree, VerifyDetectsValidTree)
	TEST (RandTree, GetRootReturnsReference)
	TEST (RandTree, KeyCompAndGetCompare)
	TEST (RandTree, GslRngObjectNotNull)
	TEST (RandTree, SetSeedChangesSequence)

Detailed Description

Tests for Rand Tree.

Definition in file rand-tree.cc.

Typedef Documentation

Node

using Node = Tree::Node

Definition at line 55 of file rand-tree.cc.

Tree

using Tree = Rand_Tree<int>

Definition at line 54 of file rand-tree.cc.

Function Documentation

inorder_keys()

template<typename NodeT >

std::vector< int > inorder_keys

(

NodeT *

root

)

Definition at line 59 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), KEY, keys, LLINK, RLINK, and root().

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

TEST() [1/54]

TEST	(	RandTree	,
		CustomComparatorGreater
	)

Definition at line 875 of file rand-tree.cc.

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

TEST() [2/54]

TEST	(	RandTree	,
		EmptyTreeProperties
	)

Definition at line 103 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [3/54]

TEST	(	RandTree	,
		FindPositionGreaterThanMax
	)

Definition at line 521 of file rand-tree.cc.

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

TEST() [4/54]

TEST	(	RandTree	,
		FindPositionLessThanMin
	)

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

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

TEST() [5/54]

TEST	(	RandTree	,
		FindPositionOfExistingKey
	)

Definition at line 480 of file rand-tree.cc.

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

TEST() [6/54]

TEST	(	RandTree	,
		FindPositionOfMissingKeyInMiddle
	)

Definition at line 493 of file rand-tree.cc.

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

TEST() [7/54]

TEST	(	RandTree	,
		GetRootReturnsReference
	)

Definition at line 1098 of file rand-tree.cc.

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

TEST() [8/54]

TEST	(	RandTree	,
		GslRngObjectNotNull
	)

Definition at line 1125 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and rng.

TEST() [9/54]

TEST	(	RandTree	,
		InsertDupAllowsDuplicates
	)

Definition at line 180 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [10/54]

TEST	(	RandTree	,
		InsertInAscendingOrder
	)

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

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

TEST() [11/54]

TEST	(	RandTree	,
		InsertInDescendingOrder
	)

Definition at line 209 of file rand-tree.cc.

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

TEST() [12/54]

TEST	(	RandTree	,
		InsertMultipleElements
	)

Definition at line 149 of file rand-tree.cc.

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

TEST() [13/54]

TEST	(	RandTree	,
		InsertRejectsDuplicates
	)

Definition at line 164 of file rand-tree.cc.

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

TEST() [14/54]

TEST	(	RandTree	,
		InsertSingleElement
	)

Definition at line 134 of file rand-tree.cc.

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

TEST() [15/54]

TEST	(	RandTree	,
		IteratorAfterRemoval
	)

Definition at line 800 of file rand-tree.cc.

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

TEST() [16/54]

TEST	(	RandTree	,
		IteratorOnEmptyTree
	)

Definition at line 792 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [17/54]

TEST	(	RandTree	,
		IteratorTraversesInOrder
	)

Definition at line 777 of file rand-tree.cc.

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

TEST() [18/54]

TEST	(	RandTree	,
		JoinDup
	)

Definition at line 732 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.

TEST() [19/54]

TEST	(	RandTree	,
		JoinExclusive
	)

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

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

TEST() [20/54]

TEST	(	RandTree	,
		JoinWithDuplicates
	)

Definition at line 706 of file rand-tree.cc.

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

TEST() [21/54]

TEST	(	RandTree	,
		JoinWithNoDuplicates
	)

Definition at line 683 of file rand-tree.cc.

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

TEST() [22/54]

TEST	(	RandTree	,
		KeyCompAndGetCompare
	)

Definition at line 1111 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp().

TEST() [23/54]

TEST	(	RandTree	,
		LargeTreeOperations
	)

Definition at line 1016 of file rand-tree.cc.

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

TEST() [24/54]

TEST	(	RandTree	,
		NegativeKeys
	)

Definition at line 909 of file rand-tree.cc.

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

TEST() [25/54]

TEST	(	RandTree	,
		PositionOfExistingKey
	)

Definition at line 446 of file rand-tree.cc.

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

TEST() [26/54]

TEST	(	RandTree	,
		PositionOfMissingKey
	)

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

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

TEST() [27/54]

TEST	(	RandTree	,
		RandomInsertSearchRemove
	)

Definition at line 956 of file rand-tree.cc.

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

TEST() [28/54]

TEST	(	RandTree	,
		RemoveAllElements
	)

Definition at line 352 of file rand-tree.cc.

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

TEST() [29/54]

TEST	(	RandTree	,
		RemoveExistingKey
	)

Definition at line 297 of file rand-tree.cc.

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

TEST() [30/54]

TEST	(	RandTree	,
		RemoveFromEmptyTreeReturnsNull
	)

Definition at line 122 of file rand-tree.cc.

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

TEST() [31/54]

TEST	(	RandTree	,
		RemoveInOrder
	)

Definition at line 372 of file rand-tree.cc.

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

TEST() [32/54]

TEST	(	RandTree	,
		RemoveInReverseOrder
	)

Definition at line 392 of file rand-tree.cc.

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

TEST() [33/54]

TEST	(	RandTree	,
		RemovePosFirst
	)

Definition at line 558 of file rand-tree.cc.

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

TEST() [34/54]

TEST	(	RandTree	,
		RemovePosLast
	)

Definition at line 576 of file rand-tree.cc.

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

TEST() [35/54]

TEST	(	RandTree	,
		RemovePosValidPosition
	)

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

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

TEST() [36/54]

TEST	(	RandTree	,
		RemoveReturnsNullForMissingKey
	)

Definition at line 320 of file rand-tree.cc.

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

TEST() [37/54]

TEST	(	RandTree	,
		RemoveRoot
	)

Definition at line 332 of file rand-tree.cc.

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

TEST() [38/54]

TEST	(	RandTree	,
		SearchFindsExistingKey
	)

Definition at line 230 of file rand-tree.cc.

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

TEST() [39/54]

TEST	(	RandTree	,
		SearchOnEmptyTreeReturnsNull
	)

Definition at line 113 of file rand-tree.cc.

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

TEST() [40/54]

TEST	(	RandTree	,
		SearchOrInsertInsertsNew
	)

Definition at line 278 of file rand-tree.cc.

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

TEST() [41/54]

TEST	(	RandTree	,
		SearchOrInsertReturnsExisting
	)

Definition at line 260 of file rand-tree.cc.

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

TEST() [42/54]

TEST	(	RandTree	,
		SearchReturnsNullForMissingKey
	)

Definition at line 246 of file rand-tree.cc.

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

TEST() [43/54]

TEST	(	RandTree	,
		SeedAffectsStructure
	)

Definition at line 846 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.

TEST() [44/54]

TEST	(	RandTree	,
		SelectOutOfRangeThrows
	)

Definition at line 434 of file rand-tree.cc.

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

TEST() [45/54]

TEST	(	RandTree	,
		SelectReturnsCorrectNode
	)

Definition at line 416 of file rand-tree.cc.

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

TEST() [46/54]

TEST	(	RandTree	,
		SetSeedChangesSequence
	)

Definition at line 1133 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.

TEST() [47/54]

TEST	(	RandTree	,
		SingleElementOperations
	)

Definition at line 929 of file rand-tree.cc.

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

TEST() [48/54]

TEST	(	RandTree	,
		SplitKeyDup
	)

Definition at line 638 of file rand-tree.cc.

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

TEST() [49/54]

TEST	(	RandTree	,
		SplitKeyInTree
	)

Definition at line 624 of file rand-tree.cc.

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

TEST() [50/54]

TEST	(	RandTree	,
		SplitKeyNotInTree
	)

Definition at line 602 of file rand-tree.cc.

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

TEST() [51/54]

TEST	(	RandTree	,
		SplitPos
	)

Definition at line 658 of file rand-tree.cc.

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

TEST() [52/54]

TEST	(	RandTree	,
		SwapTrees
	)

Definition at line 823 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.

TEST() [53/54]

TEST	(	RandTree	,
		VerifyDetectsValidTree
	)

Definition at line 1077 of file rand-tree.cc.

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

TEST() [54/54]

TEST	(	RandTreeVtl	,
		BasicOperations
	)

Definition at line 1055 of file rand-tree.cc.

References Aleph::divide_and_conquer_partition_dp(), and k.