bin-node-xt.cc File Reference

Tests for Bin Node Xt. More...

#include <algorithm>
#include <random>
#include <set>
#include <stdexcept>
#include <vector>
#include <gtest/gtest.h>
#include <tpl_binNodeXt.H>
#include <tpl_binNodeUtils.H>

Include dependency graph for bin-node-xt.cc:

Go to the source code of this file.

Functions
	TEST (BinNodeXt, SplitKeyRecXtSplitsAndEmptiesRootWhenKeyAbsent)
	TEST (BinNodeXt, SplitKeyRecXtReturnsFalseWhenKeyPresentAndDoesNotCorrupt)
	TEST (BinNodeXt, SplitKeyDupRecXtSplitsAndEmptiesRoot)
	TEST (BinNodeXt, InsertRootXtMakesInsertedNodeRoot)
	TEST (BinNodeXt, InsertDupRootXtAllowsDuplicatesAndBecomesRoot)
	TEST (BinNodeXt, InsertByPosXtMaintainsRankButMayBreakBst)
	TEST (BinNodeXt, SearchOrInsertRootRecXtUsagePattern)
	TEST (BinNodeXt, ComparatorGreaterInsertFindRemove)
	TEST (BinNodeXt, OutOfRangeExceptions)
	TEST (BinNodeXt, SentinelCountIsZero)
	TEST (BinNodeXt, InsertByKeyMaintainsCountsAndBst)
	TEST (BinNodeXt, InsertRejectsDuplicates)
	TEST (BinNodeXt, InsertDupAllowsDuplicatesAndCounts)
	TEST (BinNodeXt, SearchOrInsertByKeyReturnsExistingOrInserted)
	TEST (BinNodeXt, SelectRecAndSelectNeAndSelectParent)
	TEST (BinNodeXt, InorderPositionReturnsRankOrMinusOne)
	TEST (BinNodeXt, FindPositionContract)
	TEST (BinNodeXt, SplitPosRecAndJoinExclusiveRoundtrip)
	TEST (BinNodeXt, RemoveByPosAndRemoveByKey)
	TEST (BinNodeXt, RotationsMaintainRankInvariant)
	TEST (BinNodeXt, Property_RandomInsertRemove_CountsAndOrder)

Detailed Description

Tests for Bin Node Xt.

Definition in file bin-node-xt.cc.

Function Documentation

TEST() [1/21]

TEST	(	BinNodeXt	,
		ComparatorGreaterInsertFindRemove
	)

Definition at line 256 of file bin-node-xt.cc.

References Aleph::check_rank_tree(), cmp(), Aleph::divide_and_conquer_partition_dp(), inorder_keys(), k, KEY, and root().

TEST() [2/21]

TEST	(	BinNodeXt	,
		FindPositionContract
	)

Definition at line 404 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::find_position(), Aleph::insert_by_key_xt(), k, KEY, and root().

TEST() [3/21]

TEST	(	BinNodeXt	,
		InorderPositionReturnsRankOrMinusOne
	)

Definition at line 386 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::inorder_position(), Aleph::insert_by_key_xt(), k, KEY, root(), and Aleph::select().

TEST() [4/21]

TEST	(	BinNodeXt	,
		InsertByKeyMaintainsCountsAndBst
	)

Definition at line 304 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), k, and root().

TEST() [5/21]

TEST	(	BinNodeXt	,
		InsertByPosXtMaintainsRankButMayBreakBst
	)

Definition at line 204 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), Aleph::insert_by_pos_xt(), k, KEY, root(), and Aleph::select().

TEST() [6/21]

TEST	(	BinNodeXt	,
		InsertDupAllowsDuplicatesAndCounts
	)

Definition at line 332 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::insert_dup_by_key_xt(), and root().

TEST() [7/21]

TEST	(	BinNodeXt	,
		InsertDupRootXtAllowsDuplicatesAndBecomesRoot
	)

Definition at line 190 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), Aleph::insert_dup_root_xt(), k, and root().

TEST() [8/21]

TEST	(	BinNodeXt	,
		InsertRejectsDuplicates
	)

Definition at line 317 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_by_key_xt(), and root().

TEST() [9/21]

TEST	(	BinNodeXt	,
		InsertRootXtMakesInsertedNodeRoot
	)

Definition at line 171 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), Aleph::insert_root_xt(), k, and root().

TEST() [10/21]

TEST	(	BinNodeXt	,
		OutOfRangeExceptions
	)

Definition at line 283 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::insert_by_key_xt(), k, Aleph::remove_by_pos_xt(), root(), Aleph::select(), Aleph::select_rec(), and Aleph::split_pos_rec().

TEST() [11/21]

TEST	(	BinNodeXt	,
		Property_RandomInsertRemove_CountsAndOrder
	)

Definition at line 502 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), k, Aleph::remove_by_key_xt(), rng, and root().

TEST() [12/21]

TEST	(	BinNodeXt	,
		RemoveByPosAndRemoveByKey
	)

Definition at line 455 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), k, KEY, Aleph::remove_by_key_xt(), Aleph::remove_by_pos_xt(), and root().

TEST() [13/21]

TEST	(	BinNodeXt	,
		RotationsMaintainRankInvariant
	)

Definition at line 481 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), inorder_keys(), LLINK, r, RLINK, Aleph::rotate_to_left_xt(), and Aleph::rotate_to_right_xt().

TEST() [14/21]

TEST	(	BinNodeXt	,
		SearchOrInsertByKeyReturnsExistingOrInserted
	)

Definition at line 345 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), KEY, root(), and Aleph::search_or_insert_by_key_xt().

TEST() [15/21]

TEST	(	BinNodeXt	,
		SearchOrInsertRootRecXtUsagePattern
	)

Definition at line 231 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), k, KEY, and root().

TEST() [16/21]

TEST	(	BinNodeXt	,
		SelectRecAndSelectNeAndSelectParent
	)

Definition at line 363 of file bin-node-xt.cc.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::insert_by_key_xt(), k, KEY, root(), Aleph::select(), Aleph::select_ne(), and Aleph::select_rec().

TEST() [17/21]

TEST	(	BinNodeXt	,
		SentinelCountIsZero
	)

Definition at line 299 of file bin-node-xt.cc.

References Aleph::COUNT(), and Aleph::divide_and_conquer_partition_dp().

TEST() [18/21]

TEST	(	BinNodeXt	,
		SplitKeyDupRecXtSplitsAndEmptiesRoot
	)

Definition at line 153 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_dup_by_key_xt(), k, l, r, root(), and Aleph::split_key_dup_rec_xt().

TEST() [19/21]

TEST	(	BinNodeXt	,
		SplitKeyRecXtReturnsFalseWhenKeyPresentAndDoesNotCorrupt
	)

Definition at line 138 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), k, l, r, root(), and Aleph::split_key_rec_xt().

TEST() [20/21]

TEST	(	BinNodeXt	,
		SplitKeyRecXtSplitsAndEmptiesRootWhenKeyAbsent
	)

Definition at line 120 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), k, l, r, root(), and Aleph::split_key_rec_xt().

TEST() [21/21]

TEST	(	BinNodeXt	,
		SplitPosRecAndJoinExclusiveRoundtrip
	)

Definition at line 430 of file bin-node-xt.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder_keys(), Aleph::insert_by_key_xt(), Aleph::join_exclusive_xt(), k, l, r, root(), and Aleph::split_pos_rec().