avl-rb-rk.cc File Reference

Tests for Avl Rb Rk. More...

#include <gtest/gtest.h>
#include <numeric>
#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 90 of file avl-rb-rk.cc.

RbRkTest

using RbRkTest = RankTreeTest<Rb_Tree_Rk<int> >

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

Function Documentation

destroy_tree()

template<typename Tree >

void destroy_tree

(

Tree &

tree

)

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

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

Referenced by Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::export_to_tree_node(), Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::export_to_tree_node(), 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 1069 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching().

rng()

static mt19937 rng ( 42  )

static

TEST() [1/32]

TEST	(	EdgeCases	,
		EmptyAvlTree
	)

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

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 370 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 385 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 407 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 471 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 493 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 529 of file avl-rb-rk.cc.

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

TEST() [8/32]

TEST	(	JoinSplitAvl	,
		JoinExclusiveEmptyLeft
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive().

TEST() [9/32]

TEST	(	JoinSplitAvl	,
		JoinExclusiveEmptyRight
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive().

TEST() [10/32]

TEST	(	JoinSplitAvl	,
		JoinThenSplit
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive().

TEST() [11/32]

TEST	(	JoinSplitAvl	,
		SplitKeyBasic
	)

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

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

TEST() [12/32]

TEST	(	JoinSplitAvl	,
		SplitKeyNotFound
	)

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

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

TEST() [13/32]

TEST	(	JoinSplitAvl	,
		SplitPosBasic
	)

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

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

TEST() [14/32]

TEST	(	JoinSplitAvl	,
		SplitPosEnd
	)

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

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

TEST() [15/32]

TEST	(	JoinSplitAvl	,
		SplitPosZero
	)

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

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

TEST() [16/32]

TEST	(	JoinSplitRb	,
		JoinExclusiveBasic
	)

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

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

TEST() [17/32]

TEST	(	JoinSplitRb	,
		JoinExclusiveEmptyLeft
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive().

TEST() [18/32]

TEST	(	JoinSplitRb	,
		JoinExclusiveEmptyRight
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive().

TEST() [19/32]

TEST	(	JoinSplitRb	,
		JoinThenSplit
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive().

TEST() [20/32]

TEST	(	JoinSplitRb	,
		SplitKeyBasic
	)

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

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

TEST() [21/32]

TEST	(	JoinSplitRb	,
		SplitKeyNotFound
	)

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

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

TEST() [22/32]

TEST	(	JoinSplitRb	,
		SplitPosBasic
	)

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

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

TEST() [23/32]

TEST	(	JoinSplitRb	,
		SplitPosEnd
	)

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

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

TEST() [24/32]

TEST	(	JoinSplitRb	,
		SplitPosZero
	)

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

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

TEST() [25/32]

TEST	(	JoinSplitStress	,
		AvlLargeJoinSplit
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), and N.

TEST() [26/32]

TEST	(	JoinSplitStress	,
		RbLargeJoinSplit
	)

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

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), and N.

TEST() [27/32]

TEST	(	SearchOrInsert	,
		AvlTree
	)

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

References Aleph::blossom_maximum_cardinality_matching(), 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 450 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), 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 1011 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 1041 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), destroy_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), 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 265 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), 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(), 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 310 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), 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(), 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 95 of file avl-rb-rk.cc.

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [2/12]

TEST_F	(	AvlRkTest	,
		PositionNotFound
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [3/12]

TEST_F	(	AvlRkTest	,
		PositionOperations
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [4/12]

TEST_F	(	AvlRkTest	,
		RemoveAndVerify
	)

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

References Aleph::blossom_maximum_cardinality_matching(), keys, N, rng, and Aleph::shuffle().

TEST_F() [5/12]

TEST_F	(	AvlRkTest	,
		SelectAfterRemoval
	)

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

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

TEST_F() [6/12]

TEST_F	(	AvlRkTest	,
		SelectOperations
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [7/12]

TEST_F	(	RbRkTest	,
		InsertAndVerify
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [8/12]

TEST_F	(	RbRkTest	,
		PositionNotFound
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [9/12]

TEST_F	(	RbRkTest	,
		PositionOperations
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.

TEST_F() [10/12]

TEST_F	(	RbRkTest	,
		RemoveAndVerify
	)

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

References Aleph::blossom_maximum_cardinality_matching(), keys, N, rng, and Aleph::shuffle().

TEST_F() [11/12]

TEST_F	(	RbRkTest	,
		SelectAfterRemoval
	)

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

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

TEST_F() [12/12]

TEST_F	(	RbRkTest	,
		SelectOperations
	)

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

References Aleph::blossom_maximum_cardinality_matching(), and N.