treap_test.cc File Reference

Tests for Treap (tpl_treap.H) More...

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

Include dependency graph for treap_test.cc:

Go to the source code of this file.

Classes
class	TreapTest

Functions
	TEST_F (TreapTest, EmptyTreeIsEmpty)
	TEST_F (TreapTest, InsertIncreasesSize)
	TEST_F (TreapTest, SearchFindsInsertedKeys)
	TEST_F (TreapTest, RemoveDecreasesSize)
	TEST_F (TreapTest, RemoveNonExistentReturnsNull)
	TEST_F (TreapTest, SingleInsertMaintainsTreapProperties)
	TEST_F (TreapTest, MultipleInsertsMaintainTreapProperties)
	TEST_F (TreapTest, SequentialInsertsMaintainTreapProperties)
	TEST_F (TreapTest, ReverseInsertsMaintainTreapProperties)
	TEST_F (TreapTest, RemoveMaintainsTreapProperties)
	TEST_F (TreapTest, InorderTraversalIsSorted)
	TEST_F (TreapTest, MinAndMaxFromInorder)
	TEST_F (TreapTest, PrioritiesAreAssigned)
	TEST_F (TreapTest, HeapPropertyOnPriorities)
	TEST_F (TreapTest, SameSeedProducesSameStructure)
	TEST_F (TreapTest, RandomInsertsMaintainTreapProperties)
	TEST_F (TreapTest, RandomInsertsAndRemovesMaintainTreapProperties)
	TEST_F (TreapTest, LargeSequentialInserts)
int	main (int argc, char **argv)

Detailed Description

Tests for Treap (tpl_treap.H)

Tests the Treap (randomized BST) implementation including:

• Basic operations (insert, search, remove)
• Heap property verification (priorities)
• BST property verification (keys)
• Reproducibility with seed

Definition in file treap_test.cc.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 452 of file treap_test.cc.

References Aleph::maps().

TEST_F() [1/18]

TEST_F	(	TreapTest	,
		EmptyTreeIsEmpty
	)

Definition at line 199 of file treap_test.cc.

References Aleph::maps().

TEST_F() [2/18]

TEST_F	(	TreapTest	,
		HeapPropertyOnPriorities
	)

Definition at line 336 of file treap_test.cc.

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

TEST_F() [3/18]

TEST_F	(	TreapTest	,
		InorderTraversalIsSorted
	)

Definition at line 301 of file treap_test.cc.

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

TEST_F() [4/18]

TEST_F	(	TreapTest	,
		InsertIncreasesSize
	)

Definition at line 204 of file treap_test.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), and Aleph::maps().

TEST_F() [5/18]

TEST_F	(	TreapTest	,
		LargeSequentialInserts
	)

Definition at line 434 of file treap_test.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search().

TEST_F() [6/18]

TEST_F	(	TreapTest	,
		MinAndMaxFromInorder
	)

Definition at line 311 of file treap_test.cc.

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

TEST_F() [7/18]

TEST_F	(	TreapTest	,
		MultipleInsertsMaintainTreapProperties
	)

Definition at line 261 of file treap_test.cc.

References Aleph::maps().

TEST_F() [8/18]

TEST_F	(	TreapTest	,
		PrioritiesAreAssigned
	)

Definition at line 325 of file treap_test.cc.

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

TEST_F() [9/18]

TEST_F	(	TreapTest	,
		RandomInsertsAndRemovesMaintainTreapProperties
	)

Definition at line 399 of file treap_test.cc.

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

TEST_F() [10/18]

TEST_F	(	TreapTest	,
		RandomInsertsMaintainTreapProperties
	)

Definition at line 382 of file treap_test.cc.

References Aleph::DynList< T >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), rng, and Aleph::HTList::size().

TEST_F() [11/18]

TEST_F	(	TreapTest	,
		RemoveDecreasesSize
	)

Definition at line 228 of file treap_test.cc.

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

TEST_F() [12/18]

TEST_F	(	TreapTest	,
		RemoveMaintainsTreapProperties
	)

Definition at line 285 of file treap_test.cc.

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

TEST_F() [13/18]

TEST_F	(	TreapTest	,
		RemoveNonExistentReturnsNull
	)

Definition at line 242 of file treap_test.cc.

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

TEST_F() [14/18]

TEST_F	(	TreapTest	,
		ReverseInsertsMaintainTreapProperties
	)

Definition at line 276 of file treap_test.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), and Aleph::maps().

TEST_F() [15/18]

TEST_F	(	TreapTest	,
		SameSeedProducesSameStructure
	)

Definition at line 348 of file treap_test.cc.

References inorder_keys(), Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::PRIO().

TEST_F() [16/18]

TEST_F	(	TreapTest	,
		SearchFindsInsertedKeys
	)

Definition at line 215 of file treap_test.cc.

References Aleph::maps(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search().

TEST_F() [17/18]

TEST_F	(	TreapTest	,
		SequentialInsertsMaintainTreapProperties
	)

Definition at line 267 of file treap_test.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), and Aleph::maps().

TEST_F() [18/18]

TEST_F	(	TreapTest	,
		SingleInsertMaintainsTreapProperties
	)

Definition at line 255 of file treap_test.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), and Aleph::maps().