avl.cc File Reference

Tests for Avl. More...

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

Include dependency graph for avl.cc:

Go to the source code of this file.

Functions
	TEST (AvlTree, InsertSearchVerifyAndIteratorOrder)
	TEST (AvlTree, InsertRejectsDuplicatesAndSearchOrInsertReturnsExisting)
	TEST (AvlTree, DuplicateAtIntermediateLevel)
	TEST (AvlTree, DuplicateAfterOnlyLeftDescents)
	TEST (AvlTree, DuplicateDeepInTree)
	TEST (AvlTree, InsertDupAllowsDuplicates)
	TEST (AvlTree, RemoveMissingReturnsNull)
	TEST (AvlTree, RemoveReturnsDetachedNode)
	TEST (AvlTree, Property_RandomInsertRemove_StableInvariants)
	TEST (AvlTree, Rotations_LL_RR_LR_RL)
	TEST (AvlTree, Property_OracleSet_MatchesInorder)
	TEST (AvlTree, WorksWithCustomComparator)
	TEST (AvlTree, Stress_AscendingInsertion)
	TEST (AvlTree, Stress_DescendingInsertion)
	TEST (AvlTree, Stress_ZigzagInsertion)
	TEST (AvlTree, Fuzz_LargeScaleRandomOps)
	TEST (AvlTree, Stress_BulkInsertBulkRemove)
	TEST (AvlTree, Stress_ManyDuplicates)
	TEST (AvlTree, Stress_AlternatingInsertRemove)
	TEST (AvlTree, Stress_StringKeys)

Detailed Description

Tests for Avl.

Definition in file avl.cc.

Function Documentation

TEST() [1/20]

TEST	(	AvlTree	,
		DuplicateAfterOnlyLeftDescents
	)

Definition at line 175 of file avl.cc.

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

TEST() [2/20]

TEST	(	AvlTree	,
		DuplicateAtIntermediateLevel
	)

Definition at line 138 of file avl.cc.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_or_insert(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [3/20]

TEST	(	AvlTree	,
		DuplicateDeepInTree
	)

Definition at line 200 of file avl.cc.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [4/20]

TEST	(	AvlTree	,
		Fuzz_LargeScaleRandomOps
	)

Definition at line 490 of file avl.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::DynList< T >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), rng, Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [5/20]

TEST	(	AvlTree	,
		InsertDupAllowsDuplicates
	)

Definition at line 230 of file avl.cc.

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

TEST() [6/20]

TEST	(	AvlTree	,
		InsertRejectsDuplicatesAndSearchOrInsertReturnsExisting
	)

Definition at line 117 of file avl.cc.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search_or_insert(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [7/20]

TEST	(	AvlTree	,
		InsertSearchVerifyAndIteratorOrder
	)

Definition at line 92 of file avl.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), is_avl(), KEY, Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [8/20]

TEST	(	AvlTree	,
		Property_OracleSet_MatchesInorder
	)

Definition at line 357 of file avl.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::DynList< T >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), rng, and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [9/20]

TEST	(	AvlTree	,
		Property_RandomInsertRemove_StableInvariants
	)

Definition at line 274 of file avl.cc.

References Aleph::DynList< T >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), rng, and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [10/20]

TEST	(	AvlTree	,
		RemoveMissingReturnsNull
	)

Definition at line 243 of file avl.cc.

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

TEST() [11/20]

TEST	(	AvlTree	,
		RemoveReturnsDetachedNode
	)

Definition at line 254 of file avl.cc.

References DIFF, Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), Aleph::RLINK(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [12/20]

TEST	(	AvlTree	,
		Rotations_LL_RR_LR_RL
	)

Definition at line 314 of file avl.cc.

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

TEST() [13/20]

TEST	(	AvlTree	,
		Stress_AlternatingInsertRemove
	)

Definition at line 629 of file avl.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), inorder_keys(), Aleph::DynList< T >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), rng, and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [14/20]

TEST	(	AvlTree	,
		Stress_AscendingInsertion
	)

Definition at line 432 of file avl.cc.

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

TEST() [15/20]

TEST	(	AvlTree	,
		Stress_BulkInsertBulkRemove
	)

Definition at line 564 of file avl.cc.

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

TEST() [16/20]

TEST	(	AvlTree	,
		Stress_DescendingInsertion
	)

Definition at line 451 of file avl.cc.

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

TEST() [17/20]

TEST	(	AvlTree	,
		Stress_ManyDuplicates
	)

Definition at line 601 of file avl.cc.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::maps(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [18/20]

TEST	(	AvlTree	,
		Stress_StringKeys
	)

Definition at line 676 of file avl.cc.

References Aleph::DynList< T >::insert(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), random_string(), rng, Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::search(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().

TEST() [19/20]

TEST	(	AvlTree	,
		Stress_ZigzagInsertion
	)

Definition at line 469 of file avl.cc.

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

TEST() [20/20]

TEST	(	AvlTree	,
		WorksWithCustomComparator
	)

Definition at line 401 of file avl.cc.

References Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::remove(), and Aleph::Gen_Avl_Tree< NodeType, Key, Compare >::verify().