avl-rb-rk.cc File Reference

Tests for Avl Rb Rk. More...

#include <gtest/gtest.h>
#include <random>
#include <vector>
#include <algorithm>
#include <tpl_avlRk.H>
#include <tpl_rbRk.H>

Include dependency graph for avl-rb-rk.cc:

Go to the source code of this file.

Classes
class	RankTreeTest< Tree >

Typedefs
using	AvlRkTest = RankTreeTest< Avl_Tree_Rk< int > >
using	RbRkTest = RankTreeTest< Rb_Tree_Rk< int > >

Functions
static mt19937	rng (42)
	TEST_F (AvlRkTest, InsertAndVerify)
	TEST_F (AvlRkTest, SelectOperations)
	TEST_F (AvlRkTest, PositionOperations)
	TEST_F (AvlRkTest, PositionNotFound)
	TEST_F (AvlRkTest, RemoveAndVerify)
	TEST_F (AvlRkTest, SelectAfterRemoval)
	TEST_F (RbRkTest, InsertAndVerify)
	TEST_F (RbRkTest, SelectOperations)
	TEST_F (RbRkTest, PositionOperations)
	TEST_F (RbRkTest, PositionNotFound)
	TEST_F (RbRkTest, RemoveAndVerify)
	TEST_F (RbRkTest, SelectAfterRemoval)
	TEST (StressTest, MixedOperationsAvl)
	TEST (StressTest, MixedOperationsRb)
	TEST (EdgeCases, EmptyAvlTree)
	TEST (EdgeCases, EmptyRbTree)
	TEST (EdgeCases, SingleElementAvl)
	TEST (EdgeCases, SingleElementRb)
	TEST (SearchOrInsert, AvlTree)
	TEST (SearchOrInsert, RbTree)
	TEST (InsertDup, AvlTree)
	TEST (InsertDup, RbTree)
template<typename Tree >
void	destroy_tree (Tree &tree)
	TEST (JoinSplitAvl, JoinExclusiveBasic)
	TEST (JoinSplitAvl, JoinExclusiveEmptyLeft)
	TEST (JoinSplitAvl, JoinExclusiveEmptyRight)
	TEST (JoinSplitAvl, SplitKeyBasic)
	TEST (JoinSplitAvl, SplitKeyNotFound)
	TEST (JoinSplitAvl, SplitPosBasic)
	TEST (JoinSplitAvl, SplitPosZero)
	TEST (JoinSplitAvl, SplitPosEnd)
	TEST (JoinSplitAvl, JoinThenSplit)
	TEST (JoinSplitRb, JoinExclusiveBasic)
	TEST (JoinSplitRb, JoinExclusiveEmptyLeft)
	TEST (JoinSplitRb, JoinExclusiveEmptyRight)
	TEST (JoinSplitRb, SplitKeyBasic)
	TEST (JoinSplitRb, SplitKeyNotFound)
	TEST (JoinSplitRb, SplitPosBasic)
	TEST (JoinSplitRb, SplitPosZero)
	TEST (JoinSplitRb, SplitPosEnd)
	TEST (JoinSplitRb, JoinThenSplit)
	TEST (JoinSplitStress, AvlLargeJoinSplit)
	TEST (JoinSplitStress, RbLargeJoinSplit)
	TEST (SplitDup, AvlSplitKeyDup)
	TEST (SplitDup, RbSplitKeyDup)
int	main (int argc, char **argv)

Detailed Description

Tests for Avl Rb Rk.

Definition in file avl-rb-rk.cc.

Typedef Documentation

AvlRkTest

using AvlRkTest = RankTreeTest<Avl_Tree_Rk<int> >

Definition at line 89 of file avl-rb-rk.cc.

RbRkTest

using RbRkTest = RankTreeTest<Rb_Tree_Rk<int> >

Definition at line 90 of file avl-rb-rk.cc.

Function Documentation

destroy_tree()

template<typename Tree >

void destroy_tree

(

Tree &

tree

)

Definition at line 520 of file avl-rb-rk.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::is_empty(), Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove().

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

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 1068 of file avl-rb-rk.cc.

References Aleph::maps().

rng()

static mt19937 rng ( 42  )

static

TEST() [1/32]

TEST	(	EdgeCases	,
		EmptyAvlTree
	)

Definition at line 356 of file avl-rb-rk.cc.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size().

TEST() [2/32]

TEST	(	EdgeCases	,
		EmptyRbTree
	)

Definition at line 369 of file avl-rb-rk.cc.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size().

TEST() [3/32]

TEST	(	EdgeCases	,
		SingleElementAvl
	)

Definition at line 384 of file avl-rb-rk.cc.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify().

TEST() [4/32]

TEST	(	EdgeCases	,
		SingleElementRb
	)

Definition at line 406 of file avl-rb-rk.cc.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::verify().

TEST() [5/32]

TEST	(	InsertDup	,
		AvlTree
	)

Definition at line 470 of file avl-rb-rk.cc.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify().

TEST() [6/32]

TEST	(	InsertDup	,
		RbTree
	)

Definition at line 492 of file avl-rb-rk.cc.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::verify().

TEST() [7/32]

TEST	(	JoinSplitAvl	,
		JoinExclusiveBasic
	)

Definition at line 528 of file avl-rb-rk.cc.

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

TEST() [8/32]

TEST	(	JoinSplitAvl	,
		JoinExclusiveEmptyLeft
	)

Definition at line 560 of file avl-rb-rk.cc.

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

TEST() [9/32]

TEST	(	JoinSplitAvl	,
		JoinExclusiveEmptyRight
	)

Definition at line 577 of file avl-rb-rk.cc.

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

TEST() [10/32]

TEST	(	JoinSplitAvl	,
		JoinThenSplit
	)

Definition at line 717 of file avl-rb-rk.cc.

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

TEST() [11/32]

TEST	(	JoinSplitAvl	,
		SplitKeyBasic
	)

Definition at line 594 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key().

TEST() [12/32]

TEST	(	JoinSplitAvl	,
		SplitKeyNotFound
	)

Definition at line 626 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key().

TEST() [13/32]

TEST	(	JoinSplitAvl	,
		SplitPosBasic
	)

Definition at line 652 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos().

TEST() [14/32]

TEST	(	JoinSplitAvl	,
		SplitPosEnd
	)

Definition at line 699 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::HTList::is_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos().

TEST() [15/32]

TEST	(	JoinSplitAvl	,
		SplitPosZero
	)

Definition at line 681 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::HTList::is_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos().

TEST() [16/32]

TEST	(	JoinSplitRb	,
		JoinExclusiveBasic
	)

Definition at line 745 of file avl-rb-rk.cc.

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

TEST() [17/32]

TEST	(	JoinSplitRb	,
		JoinExclusiveEmptyLeft
	)

Definition at line 775 of file avl-rb-rk.cc.

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

TEST() [18/32]

TEST	(	JoinSplitRb	,
		JoinExclusiveEmptyRight
	)

Definition at line 792 of file avl-rb-rk.cc.

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

TEST() [19/32]

TEST	(	JoinSplitRb	,
		JoinThenSplit
	)

Definition at line 924 of file avl-rb-rk.cc.

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

TEST() [20/32]

TEST	(	JoinSplitRb	,
		SplitKeyBasic
	)

Definition at line 809 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key().

TEST() [21/32]

TEST	(	JoinSplitRb	,
		SplitKeyNotFound
	)

Definition at line 839 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key().

TEST() [22/32]

TEST	(	JoinSplitRb	,
		SplitPosBasic
	)

Definition at line 861 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos().

TEST() [23/32]

TEST	(	JoinSplitRb	,
		SplitPosEnd
	)

Definition at line 906 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::HTList::is_empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos().

TEST() [24/32]

TEST	(	JoinSplitRb	,
		SplitPosZero
	)

Definition at line 888 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::HTList::is_empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos().

TEST() [25/32]

TEST	(	JoinSplitStress	,
		AvlLargeJoinSplit
	)

Definition at line 952 of file avl-rb-rk.cc.

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

TEST() [26/32]

TEST	(	JoinSplitStress	,
		RbLargeJoinSplit
	)

Definition at line 980 of file avl-rb-rk.cc.

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

TEST() [27/32]

TEST	(	SearchOrInsert	,
		AvlTree
	)

Definition at line 430 of file avl-rb-rk.cc.

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

TEST() [28/32]

TEST	(	SearchOrInsert	,
		RbTree
	)

Definition at line 449 of file avl-rb-rk.cc.

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

TEST() [29/32]

TEST	(	SplitDup	,
		AvlSplitKeyDup
	)

Definition at line 1010 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup().

TEST() [30/32]

TEST	(	SplitDup	,
		RbSplitKeyDup
	)

Definition at line 1040 of file avl-rb-rk.cc.

References destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), Aleph::HTList::size(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup().

TEST() [31/32]

TEST	(	StressTest	,
		MixedOperationsAvl
	)

Definition at line 264 of file avl-rb-rk.cc.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), N, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), rng, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify().

TEST() [32/32]

TEST	(	StressTest	,
		MixedOperationsRb
	)

Definition at line 309 of file avl-rb-rk.cc.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::maps(), N, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), rng, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::verify().

TEST_F() [1/12]

TEST_F	(	AvlRkTest	,
		InsertAndVerify
	)

Definition at line 94 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [2/12]

TEST_F	(	AvlRkTest	,
		PositionNotFound
	)

Definition at line 129 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [3/12]

TEST_F	(	AvlRkTest	,
		PositionOperations
	)

Definition at line 115 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [4/12]

TEST_F	(	AvlRkTest	,
		RemoveAndVerify
	)

Definition at line 138 of file avl-rb-rk.cc.

References Aleph::maps(), N, rng, and Aleph::shuffle().

TEST_F() [5/12]

TEST_F	(	AvlRkTest	,
		SelectAfterRemoval
	)

Definition at line 155 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [6/12]

TEST_F	(	AvlRkTest	,
		SelectOperations
	)

Definition at line 102 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [7/12]

TEST_F	(	RbRkTest	,
		InsertAndVerify
	)

Definition at line 179 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [8/12]

TEST_F	(	RbRkTest	,
		PositionNotFound
	)

Definition at line 214 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [9/12]

TEST_F	(	RbRkTest	,
		PositionOperations
	)

Definition at line 200 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [10/12]

TEST_F	(	RbRkTest	,
		RemoveAndVerify
	)

Definition at line 223 of file avl-rb-rk.cc.

References Aleph::maps(), N, rng, and Aleph::shuffle().

TEST_F() [11/12]

TEST_F	(	RbRkTest	,
		SelectAfterRemoval
	)

Definition at line 240 of file avl-rb-rk.cc.

References Aleph::maps(), and N.

TEST_F() [12/12]

TEST_F	(	RbRkTest	,
		SelectOperations
	)

Definition at line 187 of file avl-rb-rk.cc.

References Aleph::maps(), and N.