bin-node-utils.cc File Reference

Tests for Bin Node Utils. More...

#include <algorithm>
#include <cctype>
#include <random>
#include <sstream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>
#include <gtest/gtest.h>
#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>
#include <tpl_dynArray.H>

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

Go to the source code of this file.

Functions
	TEST (BinNodeUtils, PrefixInfixSuffixLists)
	TEST (BinNodeUtils, ForEachTraversals)
	TEST (BinNodeUtils, ComputeNodesInLevel)
	TEST (BinNodeUtils, InternalPathLength)
	TEST (BinNodeUtils, BuildTreeFromPreorderAndInorder)
	TEST (BinNodeUtils, BuildTreeFromPostorderAndInorder)
	TEST (BinNodeUtils, SaveTreeLoadTreeRoundtrip)
	TEST (BinNodeUtils, LoadTreeKeysInPrefixThrowsOnShortInput)
	TEST (BinNodeUtils, SaveTreeInArrayOfCharsLoadTreeFromArrayRoundtrip)
	TEST (BinNodeUtils, SaveTreeInArrayEscapesKeys)
	TEST (BinNodeUtils, ThreadedTraversalsDoNotCorruptTree)
	TEST (BinNodeUtils, InsertInBstRejectsDuplicates)
	TEST (BinNodeUtils, InsertDupInBstAllowsDuplicates)
	TEST (BinNodeUtils, CheckBstRejectsGlobalViolation)
	TEST (BinNodeUtils, SearchOrInsertInBst)
	TEST (BinNodeUtils, RemoveFromBstReturnsDetachedNode)
	TEST (BinNodeUtils, JoinExclusiveEmptiesInputs)
	TEST (BinNodeUtils, JoinPreorderStoresDuplicates)
	TEST (BinNodeUtils, JoinStoresDuplicates)
	TEST (BinNodeUtils, SplitKeyRecOnlySplitsWhenKeyAbsent)
	TEST (BinNodeUtils, SplitKeyDupRecSplitsAndEmptiesRoot)
	TEST (BinNodeUtils, SplitKeyIterativeSplits)
	TEST (BinNodeUtils, InfixIteratorTraversesInSortedOrder)
	TEST (BinNodeUtils, RotationsPreserveInorder)
	TEST (BinNodeUtils, FindMinMax)
	TEST (BinNodeUtils, FindSuccessorAndPredecessor)
	TEST (BinNodeUtils, SearchParentReturnsNodeAndUpdatesParent)
	TEST (BinNodeUtils, SearchRankParent)
	TEST (BinNodeUtils, InsertRootRecInsertsAndRotatesToRoot)
	TEST (BinNodeUtils, InsertRootRecRejectsDuplicate)
	TEST (BinNodeUtils, InsertRootRequiresKeyAbsent)
	TEST (BinNodeUtils, InsertDupRootAlwaysInserts)
	TEST (BinNodeUtils, RemoveFromBstRespectsComparator)
	TEST (BinNodeUtils, TreeToBitsAndBitsToTreeRoundtripShapeAndKeys)
	TEST (BinNodeUtils, BitsToTreeThrowsOnInvalidBits)
	TEST (BinNodeUtils, PreorderToBstBuildsValidTree)
	TEST (BinNodeUtils, Property_InsertRemoveRandom_StableInvariants)

Detailed Description

Tests for Bin Node Utils.

Definition in file bin-node-utils.cc.

Function Documentation

TEST() [1/37]

TEST	(	BinNodeUtils	,
		BitsToTreeThrowsOnInvalidBits
	)

Definition at line 878 of file bin-node-utils.cc.

References Aleph::bits_to_tree(), Aleph::divide_and_conquer_partition_dp(), and Aleph::BitArray::push().

TEST() [2/37]

TEST	(	BinNodeUtils	,
		BuildTreeFromPostorderAndInorder
	)

Definition at line 321 of file bin-node-utils.cc.

References Aleph::check_bst(), delete_tree(), Aleph::divide_and_conquer_partition_dp(), inorder, and root().

TEST() [3/37]

TEST	(	BinNodeUtils	,
		BuildTreeFromPreorderAndInorder
	)

Definition at line 308 of file bin-node-utils.cc.

References Aleph::check_bst(), delete_tree(), Aleph::divide_and_conquer_partition_dp(), inorder, and root().

TEST() [4/37]

TEST	(	BinNodeUtils	,
		CheckBstRejectsGlobalViolation
	)

Definition at line 501 of file bin-node-utils.cc.

References Aleph::check_bst(), Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, and root().

TEST() [5/37]

TEST	(	BinNodeUtils	,
		ComputeNodesInLevel
	)

Definition at line 278 of file bin-node-utils.cc.

References Aleph::compute_nodes_in_level(), Aleph::divide_and_conquer_partition_dp(), l1, l2, LLINK, RLINK, and root().

TEST() [6/37]

TEST	(	BinNodeUtils	,
		FindMinMax
	)

Definition at line 703 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::find_max(), Aleph::find_min(), Aleph::insert_in_bst(), k, KEY, and root().

TEST() [7/37]

TEST	(	BinNodeUtils	,
		FindSuccessorAndPredecessor
	)

Definition at line 714 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::find_predecessor(), Aleph::find_successor(), Aleph::insert_in_bst(), k, KEY, pred, root(), and Aleph::searchInBinTree().

TEST() [8/37]

TEST	(	BinNodeUtils	,
		ForEachTraversals
	)

Definition at line 261 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, RLINK, and root().

TEST() [9/37]

TEST	(	BinNodeUtils	,
		InfixIteratorTraversesInSortedOrder
	)

Definition at line 666 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::BinNodeInfixIterator< Node >::get_curr_ne(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::insert_in_bst(), k, KEY, Aleph::BinNodeInfixIterator< Node >::next_ne(), and root().

TEST() [10/37]

TEST	(	BinNodeUtils	,
		InsertDupInBstAllowsDuplicates
	)

Definition at line 488 of file bin-node-utils.cc.

References Aleph::check_bst(), Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_dup_in_bst(), and root().

TEST() [11/37]

TEST	(	BinNodeUtils	,
		InsertDupRootAlwaysInserts
	)

Definition at line 816 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_dup_root(), Aleph::insert_in_bst(), k, and root().

TEST() [12/37]

TEST	(	BinNodeUtils	,
		InsertInBstRejectsDuplicates
	)

Definition at line 473 of file bin-node-utils.cc.

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

TEST() [13/37]

TEST	(	BinNodeUtils	,
		InsertRootRecInsertsAndRotatesToRoot
	)

Definition at line 771 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_in_bst(), Aleph::insert_root_rec(), k, KEY, and root().

TEST() [14/37]

TEST	(	BinNodeUtils	,
		InsertRootRecRejectsDuplicate
	)

Definition at line 787 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), Aleph::insert_root_rec(), k, and root().

TEST() [15/37]

TEST	(	BinNodeUtils	,
		InsertRootRequiresKeyAbsent
	)

Definition at line 800 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_in_bst(), Aleph::insert_root(), k, KEY, and root().

TEST() [16/37]

TEST	(	BinNodeUtils	,
		InternalPathLength
	)

Definition at line 298 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::internal_path_length(), LLINK, RLINK, and root().

TEST() [17/37]

TEST	(	BinNodeUtils	,
		JoinExclusiveEmptiesInputs
	)

Definition at line 548 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), and k.

TEST() [18/37]

TEST	(	BinNodeUtils	,
		JoinPreorderStoresDuplicates
	)

Definition at line 567 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), Aleph::join_preorder(), and k.

TEST() [19/37]

TEST	(	BinNodeUtils	,
		JoinStoresDuplicates
	)

Definition at line 587 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), Aleph::join(), and k.

TEST() [20/37]

TEST	(	BinNodeUtils	,
		LoadTreeKeysInPrefixThrowsOnShortInput
	)

Definition at line 350 of file bin-node-utils.cc.

References delete_tree(), Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::load_tree_keys_in_prefix(), and root().

TEST() [21/37]

TEST	(	BinNodeUtils	,
		PrefixInfixSuffixLists
	)

Definition at line 245 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::in_nodes(), Aleph::infix(), LLINK, Aleph::prefix(), RLINK, root(), and Aleph::suffix().

TEST() [22/37]

TEST	(	BinNodeUtils	,
		PreorderToBstBuildsValidTree
	)

Definition at line 887 of file bin-node-utils.cc.

References delete_tree(), Aleph::divide_and_conquer_partition_dp(), inorder, and root().

TEST() [23/37]

TEST	(	BinNodeUtils	,
		Property_InsertRemoveRandom_StableInvariants
	)

Definition at line 905 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_in_bst(), k, KEY, Aleph::remove_from_bst(), rng, and root().

TEST() [24/37]

TEST	(	BinNodeUtils	,
		RemoveFromBstRespectsComparator
	)

Definition at line 828 of file bin-node-utils.cc.

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

TEST() [25/37]

TEST	(	BinNodeUtils	,
		RemoveFromBstReturnsDetachedNode
	)

Definition at line 528 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_in_bst(), k, KEY, LLINK, Aleph::remove_from_bst(), RLINK, and root().

TEST() [26/37]

TEST	(	BinNodeUtils	,
		RotationsPreserveInorder
	)

Definition at line 685 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, LLINK, r, RLINK, Aleph::rotate_to_left(), and Aleph::rotate_to_right().

TEST() [27/37]

TEST	(	BinNodeUtils	,
		SaveTreeInArrayEscapesKeys
	)

Definition at line 394 of file bin-node-utils.cc.

References delete_tree(), Aleph::divide_and_conquer_partition_dp(), Aleph::BinNode< Key >::get_key(), inorder, KEY, keys, LLINK, RLINK, root(), and Aleph::tree_to_bits().

TEST() [28/37]

TEST	(	BinNodeUtils	,
		SaveTreeInArrayOfCharsLoadTreeFromArrayRoundtrip
	)

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

References Aleph::check_bst(), delete_tree(), Aleph::divide_and_conquer_partition_dp(), inorder, keys, LLINK, RLINK, root(), and Aleph::tree_to_bits().

TEST() [29/37]

TEST	(	BinNodeUtils	,
		SaveTreeLoadTreeRoundtrip
	)

Definition at line 334 of file bin-node-utils.cc.

References Aleph::check_bst(), delete_tree(), Aleph::divide_and_conquer_partition_dp(), inorder, LLINK, RLINK, root(), and Aleph::save_tree().

TEST() [30/37]

TEST	(	BinNodeUtils	,
		SearchOrInsertInBst
	)

Definition at line 512 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), KEY, root(), and Aleph::search_or_insert_in_bst().

TEST() [31/37]

TEST	(	BinNodeUtils	,
		SearchParentReturnsNodeAndUpdatesParent
	)

Definition at line 736 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_in_bst(), k, KEY, Aleph::BinNode< Key >::reset(), RLINK, root(), and Aleph::search_parent().

TEST() [32/37]

TEST	(	BinNodeUtils	,
		SearchRankParent
	)

Definition at line 755 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::insert_in_bst(), k, KEY, root(), and Aleph::search_rank_parent().

TEST() [33/37]

TEST	(	BinNodeUtils	,
		SplitKeyDupRecSplitsAndEmptiesRoot
	)

Definition at line 626 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), k, l, r, root(), and Aleph::split_key_dup_rec().

TEST() [34/37]

TEST	(	BinNodeUtils	,
		SplitKeyIterativeSplits
	)

Definition at line 646 of file bin-node-utils.cc.

References Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), k, l, r, root(), and Aleph::split_key().

TEST() [35/37]

TEST	(	BinNodeUtils	,
		SplitKeyRecOnlySplitsWhenKeyAbsent
	)

Definition at line 607 of file bin-node-utils.cc.

References Aleph::check_bst(), Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::insert_in_bst(), k, l, r, root(), and Aleph::split_key_rec().

TEST() [36/37]

TEST	(	BinNodeUtils	,
		ThreadedTraversalsDoNotCorruptTree
	)

Definition at line 442 of file bin-node-utils.cc.

References Aleph::check_bst(), Aleph::divide_and_conquer_partition_dp(), inorder, Aleph::inOrderThreaded(), LLINK, Aleph::preOrderThreaded(), RLINK, root(), Aleph::size(), and Aleph::tree_to_bits().

TEST() [37/37]

TEST	(	BinNodeUtils	,
		TreeToBitsAndBitsToTreeRoundtripShapeAndKeys
	)

Definition at line 850 of file bin-node-utils.cc.

References delete_tree(), Aleph::divide_and_conquer_partition_dp(), inorder, keys, LLINK, RLINK, root(), Aleph::BitArray::size(), Aleph::size(), and Aleph::tree_to_bits().