splay-tree-rk.cc File Reference

Tests for Splay Tree Rk. More...

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

Include dependency graph for splay-tree-rk.cc:

Go to the source code of this file.

Functions
	TEST (SplayTreeRk, EmptyTreeProperties)
	TEST (SplayTreeRk, InsertSingleElement)
	TEST (SplayTreeRk, InsertMultipleElements)
	TEST (SplayTreeRk, InsertRejectsDuplicates)
	TEST (SplayTreeRk, InsertDupAllowsDuplicates)
	TEST (SplayTreeRk, SearchFindsExistingKey)
	TEST (SplayTreeRk, SearchReturnsNullForMissingKey)
	TEST (SplayTreeRk, SearchOrInsertBehavior)
	TEST (SplayTreeRk, RemoveExistingKey)
	TEST (SplayTreeRk, RemoveReturnsNullForMissingKey)
	TEST (SplayTreeRk, RemoveFromEmptyTree)
	TEST (SplayTreeRk, RemoveRootWithNoLeftChild)
	TEST (SplayTreeRk, RemoveAllElements)
	TEST (SplayTreeRk, SelectByPosition)
	TEST (SplayTreeRk, SelectOutOfRangeThrows)
	TEST (SplayTreeRk, PositionFindsCorrectRank)
	TEST (SplayTreeRk, PositionReturnsMinusOneForMissingKey)
	TEST (SplayTreeRk, PositionOnEmptyTree)
	TEST (SplayTreeRk, SplayBringsNodeToRoot)
	TEST (SplayTreeRk, CountsMaintainedAfterSplay)
	TEST (SplayTreeRk, SingleElementOperations)
	TEST (SplayTreeRk, InsertInDescendingOrder)
	TEST (SplayTreeRk, InsertInAscendingOrder)
	TEST (SplayTreeRk, CustomComparatorGreater)
	TEST (SplayTreeRk, StatefulComparatorAffectsEquality)
	TEST (SplayTreeRk, RandomInsertSearchRemove)
	TEST (SplayTreeRk, SelectAndPositionConsistency)
	TEST (SplayTreeRk, VerifyDetectsValidTree)
	TEST (SplayTreeRk, SwapTrees)
	TEST (SplayTreeRk, Stress_AscendingInsertion)
	TEST (SplayTreeRk, Stress_DescendingInsertion)
	TEST (SplayTreeRk, Stress_ZigzagInsertion)
	TEST (SplayTreeRk, Fuzz_LargeScaleRandomOps)
	TEST (SplayTreeRk, Stress_BulkInsertBulkRemove)
	TEST (SplayTreeRk, Stress_ManyDuplicates)
	TEST (SplayTreeRk, Stress_RankOperationsUnderLoad)
	TEST (SplayTreeRk, Stress_FrequentAccessPattern)

Detailed Description

Tests for Splay Tree Rk.

Definition in file splay-tree-rk.cc.

Function Documentation

TEST() [1/37]

TEST	(	SplayTreeRk	,
		CountsMaintainedAfterSplay
	)

Definition at line 457 of file splay-tree-rk.cc.

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

TEST() [2/37]

TEST	(	SplayTreeRk	,
		CustomComparatorGreater
	)

Definition at line 533 of file splay-tree-rk.cc.

References KEY, Aleph::LLINK(), Aleph::maps(), nodes, and Aleph::RLINK().

TEST() [3/37]

TEST	(	SplayTreeRk	,
		EmptyTreeProperties
	)

Definition at line 128 of file splay-tree-rk.cc.

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

TEST() [4/37]

TEST	(	SplayTreeRk	,
		Fuzz_LargeScaleRandomOps
	)

Definition at line 804 of file splay-tree-rk.cc.

References StlAlephIterator< SetName >::begin(), Aleph::DynList< T >::empty(), Aleph::DynList< T >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search(), Aleph::HTList::size(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size().

TEST() [5/37]

TEST	(	SplayTreeRk	,
		InsertDupAllowsDuplicates
	)

Definition at line 187 of file splay-tree-rk.cc.

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

TEST() [6/37]

TEST	(	SplayTreeRk	,
		InsertInAscendingOrder
	)

Definition at line 514 of file splay-tree-rk.cc.

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

TEST() [7/37]

TEST	(	SplayTreeRk	,
		InsertInDescendingOrder
	)

Definition at line 499 of file splay-tree-rk.cc.

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

TEST() [8/37]

TEST	(	SplayTreeRk	,
		InsertMultipleElements
	)

Definition at line 154 of file splay-tree-rk.cc.

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

TEST() [9/37]

TEST	(	SplayTreeRk	,
		InsertRejectsDuplicates
	)

Definition at line 172 of file splay-tree-rk.cc.

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

TEST() [10/37]

TEST	(	SplayTreeRk	,
		InsertSingleElement
	)

Definition at line 139 of file splay-tree-rk.cc.

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

TEST() [11/37]

TEST	(	SplayTreeRk	,
		PositionFindsCorrectRank
	)

Definition at line 384 of file splay-tree-rk.cc.

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

TEST() [12/37]

TEST	(	SplayTreeRk	,
		PositionOnEmptyTree
	)

Definition at line 419 of file splay-tree-rk.cc.

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

TEST() [13/37]

TEST	(	SplayTreeRk	,
		PositionReturnsMinusOneForMissingKey
	)

Definition at line 406 of file splay-tree-rk.cc.

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

TEST() [14/37]

TEST	(	SplayTreeRk	,
		RandomInsertSearchRemove
	)

Definition at line 588 of file splay-tree-rk.cc.

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

TEST() [15/37]

TEST	(	SplayTreeRk	,
		RemoveAllElements
	)

Definition at line 327 of file splay-tree-rk.cc.

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

TEST() [16/37]

TEST	(	SplayTreeRk	,
		RemoveExistingKey
	)

Definition at line 261 of file splay-tree-rk.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::getRoot(), inorder_keys(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size().

TEST() [17/37]

TEST	(	SplayTreeRk	,
		RemoveFromEmptyTree
	)

Definition at line 298 of file splay-tree-rk.cc.

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

TEST() [18/37]

TEST	(	SplayTreeRk	,
		RemoveReturnsNullForMissingKey
	)

Definition at line 283 of file splay-tree-rk.cc.

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

TEST() [19/37]

TEST	(	SplayTreeRk	,
		RemoveRootWithNoLeftChild
	)

Definition at line 306 of file splay-tree-rk.cc.

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

TEST() [20/37]

TEST	(	SplayTreeRk	,
		SearchFindsExistingKey
	)

Definition at line 202 of file splay-tree-rk.cc.

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

TEST() [21/37]

TEST	(	SplayTreeRk	,
		SearchOrInsertBehavior
	)

Definition at line 236 of file splay-tree-rk.cc.

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

TEST() [22/37]

TEST	(	SplayTreeRk	,
		SearchReturnsNullForMissingKey
	)

Definition at line 220 of file splay-tree-rk.cc.

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

TEST() [23/37]

TEST	(	SplayTreeRk	,
		SelectAndPositionConsistency
	)

Definition at line 659 of file splay-tree-rk.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::DynList< T >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position(), rng, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select(), and Aleph::HTList::size().

TEST() [24/37]

TEST	(	SplayTreeRk	,
		SelectByPosition
	)

Definition at line 353 of file splay-tree-rk.cc.

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

TEST() [25/37]

TEST	(	SplayTreeRk	,
		SelectOutOfRangeThrows
	)

Definition at line 372 of file splay-tree-rk.cc.

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

TEST() [26/37]

TEST	(	SplayTreeRk	,
		SingleElementOperations
	)

Definition at line 480 of file splay-tree-rk.cc.

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

TEST() [27/37]

TEST	(	SplayTreeRk	,
		SplayBringsNodeToRoot
	)

Definition at line 433 of file splay-tree-rk.cc.

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

TEST() [28/37]

TEST	(	SplayTreeRk	,
		StatefulComparatorAffectsEquality
	)

Definition at line 567 of file splay-tree-rk.cc.

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

TEST() [29/37]

TEST	(	SplayTreeRk	,
		Stress_AscendingInsertion
	)

Definition at line 749 of file splay-tree-rk.cc.

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

TEST() [30/37]

TEST	(	SplayTreeRk	,
		Stress_BulkInsertBulkRemove
	)

Definition at line 860 of file splay-tree-rk.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::is_empty(), Aleph::maps(), N, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size().

TEST() [31/37]

TEST	(	SplayTreeRk	,
		Stress_DescendingInsertion
	)

Definition at line 775 of file splay-tree-rk.cc.

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

TEST() [32/37]

TEST	(	SplayTreeRk	,
		Stress_FrequentAccessPattern
	)

Definition at line 970 of file splay-tree-rk.cc.

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

TEST() [33/37]

TEST	(	SplayTreeRk	,
		Stress_ManyDuplicates
	)

Definition at line 891 of file splay-tree-rk.cc.

References Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::is_empty(), KEY, Aleph::maps(), N, Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::remove(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select(), and Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::size().

TEST() [34/37]

TEST	(	SplayTreeRk	,
		Stress_RankOperationsUnderLoad
	)

Definition at line 931 of file splay-tree-rk.cc.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::DynList< T >::insert(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::position(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::select(), and Aleph::HTList::size().

TEST() [35/37]

TEST	(	SplayTreeRk	,
		Stress_ZigzagInsertion
	)

Definition at line 788 of file splay-tree-rk.cc.

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

TEST() [36/37]

TEST	(	SplayTreeRk	,
		SwapTrees
	)

Definition at line 722 of file splay-tree-rk.cc.

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

TEST() [37/37]

TEST	(	SplayTreeRk	,
		VerifyDetectsValidTree
	)

Definition at line 699 of file splay-tree-rk.cc.

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