rand-tree.cc File Reference

Tests for Rand Tree. More...

#include <gtest/gtest.h>
#include <numeric>
#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 56 of file rand-tree.cc.

Tree

using Tree = Rand_Tree<int>

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

Function Documentation

inorder_keys()

template<typename NodeT >

std::vector< int > inorder_keys

(

NodeT *

root

)

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

References Aleph::blossom_maximum_cardinality_matching(), 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 876 of file rand-tree.cc.

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

TEST() [2/54]

TEST	(	RandTree	,
		EmptyTreeProperties
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [3/54]

TEST	(	RandTree	,
		FindPositionGreaterThanMax
	)

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

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

TEST() [4/54]

TEST	(	RandTree	,
		FindPositionLessThanMin
	)

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

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

TEST() [5/54]

TEST	(	RandTree	,
		FindPositionOfExistingKey
	)

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

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

TEST() [6/54]

TEST	(	RandTree	,
		FindPositionOfMissingKeyInMiddle
	)

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

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

TEST() [7/54]

TEST	(	RandTree	,
		GetRootReturnsReference
	)

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

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

TEST() [8/54]

TEST	(	RandTree	,
		GslRngObjectNotNull
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and rng.

TEST() [9/54]

TEST	(	RandTree	,
		InsertDupAllowsDuplicates
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [10/54]

TEST	(	RandTree	,
		InsertInAscendingOrder
	)

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

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

TEST() [11/54]

TEST	(	RandTree	,
		InsertInDescendingOrder
	)

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

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

TEST() [12/54]

TEST	(	RandTree	,
		InsertMultipleElements
	)

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

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

TEST() [13/54]

TEST	(	RandTree	,
		InsertRejectsDuplicates
	)

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

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

TEST() [14/54]

TEST	(	RandTree	,
		InsertSingleElement
	)

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

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

TEST() [15/54]

TEST	(	RandTree	,
		IteratorAfterRemoval
	)

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

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

TEST() [16/54]

TEST	(	RandTree	,
		IteratorOnEmptyTree
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [17/54]

TEST	(	RandTree	,
		IteratorTraversesInOrder
	)

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

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

TEST() [18/54]

TEST	(	RandTree	,
		JoinDup
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and k.

TEST() [19/54]

TEST	(	RandTree	,
		JoinExclusive
	)

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

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

TEST() [20/54]

TEST	(	RandTree	,
		JoinWithDuplicates
	)

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

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

TEST() [21/54]

TEST	(	RandTree	,
		JoinWithNoDuplicates
	)

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

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

TEST() [22/54]

TEST	(	RandTree	,
		KeyCompAndGetCompare
	)

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

References Aleph::blossom_maximum_cardinality_matching().

TEST() [23/54]

TEST	(	RandTree	,
		LargeTreeOperations
	)

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

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

TEST() [24/54]

TEST	(	RandTree	,
		NegativeKeys
	)

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

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

TEST() [25/54]

TEST	(	RandTree	,
		PositionOfExistingKey
	)

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

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

TEST() [26/54]

TEST	(	RandTree	,
		PositionOfMissingKey
	)

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

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

TEST() [27/54]

TEST	(	RandTree	,
		RandomInsertSearchRemove
	)

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

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

TEST() [28/54]

TEST	(	RandTree	,
		RemoveAllElements
	)

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

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

TEST() [29/54]

TEST	(	RandTree	,
		RemoveExistingKey
	)

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

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

TEST() [30/54]

TEST	(	RandTree	,
		RemoveFromEmptyTreeReturnsNull
	)

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

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

TEST() [31/54]

TEST	(	RandTree	,
		RemoveInOrder
	)

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

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

TEST() [32/54]

TEST	(	RandTree	,
		RemoveInReverseOrder
	)

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

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

TEST() [33/54]

TEST	(	RandTree	,
		RemovePosFirst
	)

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

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

TEST() [34/54]

TEST	(	RandTree	,
		RemovePosLast
	)

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

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

TEST() [35/54]

TEST	(	RandTree	,
		RemovePosValidPosition
	)

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

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

TEST() [36/54]

TEST	(	RandTree	,
		RemoveReturnsNullForMissingKey
	)

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

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

TEST() [37/54]

TEST	(	RandTree	,
		RemoveRoot
	)

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

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

TEST() [38/54]

TEST	(	RandTree	,
		SearchFindsExistingKey
	)

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

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

TEST() [39/54]

TEST	(	RandTree	,
		SearchOnEmptyTreeReturnsNull
	)

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

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

TEST() [40/54]

TEST	(	RandTree	,
		SearchOrInsertInsertsNew
	)

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

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

TEST() [41/54]

TEST	(	RandTree	,
		SearchOrInsertReturnsExisting
	)

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

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

TEST() [42/54]

TEST	(	RandTree	,
		SearchReturnsNullForMissingKey
	)

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

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

TEST() [43/54]

TEST	(	RandTree	,
		SeedAffectsStructure
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and k.

TEST() [44/54]

TEST	(	RandTree	,
		SelectOutOfRangeThrows
	)

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

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

TEST() [45/54]

TEST	(	RandTree	,
		SelectReturnsCorrectNode
	)

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

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

TEST() [46/54]

TEST	(	RandTree	,
		SetSeedChangesSequence
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and k.

TEST() [47/54]

TEST	(	RandTree	,
		SingleElementOperations
	)

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

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

TEST() [48/54]

TEST	(	RandTree	,
		SplitKeyDup
	)

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

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

TEST() [49/54]

TEST	(	RandTree	,
		SplitKeyInTree
	)

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

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

TEST() [50/54]

TEST	(	RandTree	,
		SplitKeyNotInTree
	)

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

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

TEST() [51/54]

TEST	(	RandTree	,
		SplitPos
	)

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

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

TEST() [52/54]

TEST	(	RandTree	,
		SwapTrees
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and k.

TEST() [53/54]

TEST	(	RandTree	,
		VerifyDetectsValidTree
	)

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

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

TEST() [54/54]

TEST	(	RandTreeVtl	,
		BasicOperations
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and k.