|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
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>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) | |
Tests for Bin Node Utils.
Definition in file bin-node-utils.cc.
| TEST | ( | BinNodeUtils | , |
| BitsToTreeThrowsOnInvalidBits | |||
| ) |
Definition at line 878 of file bin-node-utils.cc.
References Aleph::bits_to_tree(), Aleph::maps(), and Aleph::BitArray::push().
| TEST | ( | BinNodeUtils | , |
| BuildTreeFromPostorderAndInorder | |||
| ) |
Definition at line 321 of file bin-node-utils.cc.
References Aleph::check_bst(), delete_tree(), inorder(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| BuildTreeFromPreorderAndInorder | |||
| ) |
Definition at line 308 of file bin-node-utils.cc.
References Aleph::check_bst(), delete_tree(), inorder(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| CheckBstRejectsGlobalViolation | |||
| ) |
Definition at line 501 of file bin-node-utils.cc.
References Aleph::check_bst(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().
| TEST | ( | BinNodeUtils | , |
| ComputeNodesInLevel | |||
| ) |
Definition at line 278 of file bin-node-utils.cc.
References Aleph::compute_nodes_in_level(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().
| TEST | ( | BinNodeUtils | , |
| FindMinMax | |||
| ) |
Definition at line 703 of file bin-node-utils.cc.
References Aleph::find_max(), Aleph::find_min(), Aleph::insert_in_bst(), KEY, Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| FindSuccessorAndPredecessor | |||
| ) |
Definition at line 714 of file bin-node-utils.cc.
References Aleph::find_predecessor(), Aleph::find_successor(), Aleph::insert_in_bst(), KEY, Aleph::maps(), pred, root(), and Aleph::searchInBinTree().
| TEST | ( | BinNodeUtils | , |
| ForEachTraversals | |||
| ) |
Definition at line 261 of file bin-node-utils.cc.
References KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().
| TEST | ( | BinNodeUtils | , |
| InfixIteratorTraversesInSortedOrder | |||
| ) |
Definition at line 666 of file bin-node-utils.cc.
References Aleph::BinNodeInfixIterator< Node >::get_curr_ne(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::insert_in_bst(), KEY, Aleph::maps(), Aleph::BinNodeInfixIterator< Node >::next_ne(), and root().
| TEST | ( | BinNodeUtils | , |
| InsertDupInBstAllowsDuplicates | |||
| ) |
Definition at line 488 of file bin-node-utils.cc.
References Aleph::check_bst(), inorder(), Aleph::insert_dup_in_bst(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| InsertDupRootAlwaysInserts | |||
| ) |
Definition at line 816 of file bin-node-utils.cc.
References Aleph::insert_dup_root(), Aleph::insert_in_bst(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| InsertInBstRejectsDuplicates | |||
| ) |
Definition at line 473 of file bin-node-utils.cc.
References Aleph::insert_in_bst(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| InsertRootRecInsertsAndRotatesToRoot | |||
| ) |
Definition at line 771 of file bin-node-utils.cc.
References Aleph::insert_in_bst(), Aleph::insert_root_rec(), KEY, Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| InsertRootRecRejectsDuplicate | |||
| ) |
Definition at line 787 of file bin-node-utils.cc.
References inorder(), Aleph::insert_in_bst(), Aleph::insert_root_rec(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| InsertRootRequiresKeyAbsent | |||
| ) |
Definition at line 800 of file bin-node-utils.cc.
References Aleph::insert_in_bst(), Aleph::insert_root(), KEY, Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| InternalPathLength | |||
| ) |
Definition at line 298 of file bin-node-utils.cc.
References Aleph::internal_path_length(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), and root().
| TEST | ( | BinNodeUtils | , |
| JoinExclusiveEmptiesInputs | |||
| ) |
Definition at line 548 of file bin-node-utils.cc.
References inorder(), Aleph::insert_in_bst(), and Aleph::maps().
| TEST | ( | BinNodeUtils | , |
| JoinPreorderStoresDuplicates | |||
| ) |
Definition at line 567 of file bin-node-utils.cc.
References inorder(), Aleph::insert_in_bst(), Aleph::join_preorder(), and Aleph::maps().
| TEST | ( | BinNodeUtils | , |
| JoinStoresDuplicates | |||
| ) |
Definition at line 587 of file bin-node-utils.cc.
References inorder(), Aleph::insert_in_bst(), Aleph::join(), and Aleph::maps().
| TEST | ( | BinNodeUtils | , |
| LoadTreeKeysInPrefixThrowsOnShortInput | |||
| ) |
Definition at line 350 of file bin-node-utils.cc.
References delete_tree(), Aleph::LLINK(), Aleph::load_tree_keys_in_prefix(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| PrefixInfixSuffixLists | |||
| ) |
Definition at line 245 of file bin-node-utils.cc.
References Aleph::in_nodes(), Aleph::infix(), Aleph::LLINK(), Aleph::maps(), Aleph::prefix(), Aleph::RLINK(), root(), and Aleph::suffix().
| TEST | ( | BinNodeUtils | , |
| PreorderToBstBuildsValidTree | |||
| ) |
Definition at line 887 of file bin-node-utils.cc.
References delete_tree(), inorder(), Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| Property_InsertRemoveRandom_StableInvariants | |||
| ) |
Definition at line 905 of file bin-node-utils.cc.
References Aleph::DynList< T >::insert(), Aleph::insert_in_bst(), KEY, Aleph::maps(), Aleph::remove_from_bst(), rng, and root().
| TEST | ( | BinNodeUtils | , |
| RemoveFromBstRespectsComparator | |||
| ) |
Definition at line 828 of file bin-node-utils.cc.
References Aleph::check_bst(), KEY, Aleph::maps(), and root().
| TEST | ( | BinNodeUtils | , |
| RemoveFromBstReturnsDetachedNode | |||
| ) |
Definition at line 528 of file bin-node-utils.cc.
References Aleph::insert_in_bst(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::remove_from_bst(), Aleph::RLINK(), and root().
| TEST | ( | BinNodeUtils | , |
| RotationsPreserveInorder | |||
| ) |
Definition at line 685 of file bin-node-utils.cc.
References inorder(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), Aleph::rotate_to_left(), and Aleph::rotate_to_right().
| TEST | ( | BinNodeUtils | , |
| SaveTreeInArrayEscapesKeys | |||
| ) |
Definition at line 394 of file bin-node-utils.cc.
References delete_tree(), Aleph::DynList< T >::empty(), Aleph::BinNode< Key >::get_key(), inorder(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::tree_to_bits().
| TEST | ( | BinNodeUtils | , |
| SaveTreeInArrayOfCharsLoadTreeFromArrayRoundtrip | |||
| ) |
Definition at line 363 of file bin-node-utils.cc.
References Aleph::check_bst(), delete_tree(), Aleph::DynList< T >::empty(), inorder(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::tree_to_bits().
| TEST | ( | BinNodeUtils | , |
| SaveTreeLoadTreeRoundtrip | |||
| ) |
Definition at line 334 of file bin-node-utils.cc.
References Aleph::check_bst(), delete_tree(), inorder(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), and Aleph::save_tree().
| TEST | ( | BinNodeUtils | , |
| SearchOrInsertInBst | |||
| ) |
Definition at line 512 of file bin-node-utils.cc.
References KEY, Aleph::maps(), root(), and Aleph::search_or_insert_in_bst().
| TEST | ( | BinNodeUtils | , |
| SearchParentReturnsNodeAndUpdatesParent | |||
| ) |
Definition at line 736 of file bin-node-utils.cc.
References Aleph::insert_in_bst(), KEY, Aleph::maps(), Aleph::BinNode< Key >::reset(), Aleph::RLINK(), root(), and Aleph::search_parent().
| TEST | ( | BinNodeUtils | , |
| SearchRankParent | |||
| ) |
Definition at line 755 of file bin-node-utils.cc.
References Aleph::insert_in_bst(), KEY, Aleph::maps(), root(), and Aleph::search_rank_parent().
| TEST | ( | BinNodeUtils | , |
| SplitKeyDupRecSplitsAndEmptiesRoot | |||
| ) |
Definition at line 626 of file bin-node-utils.cc.
References inorder(), Aleph::insert_in_bst(), l, Aleph::maps(), root(), and Aleph::split_key_dup_rec().
| TEST | ( | BinNodeUtils | , |
| SplitKeyIterativeSplits | |||
| ) |
Definition at line 646 of file bin-node-utils.cc.
References inorder(), Aleph::insert_in_bst(), l, Aleph::maps(), root(), and Aleph::split_key().
| TEST | ( | BinNodeUtils | , |
| SplitKeyRecOnlySplitsWhenKeyAbsent | |||
| ) |
Definition at line 607 of file bin-node-utils.cc.
References Aleph::check_bst(), inorder(), Aleph::insert_in_bst(), l, Aleph::maps(), root(), and Aleph::split_key_rec().
| TEST | ( | BinNodeUtils | , |
| ThreadedTraversalsDoNotCorruptTree | |||
| ) |
Definition at line 442 of file bin-node-utils.cc.
References Aleph::check_bst(), inorder(), Aleph::inOrderThreaded(), Aleph::LLINK(), Aleph::maps(), Aleph::preOrderThreaded(), Aleph::RLINK(), root(), Aleph::HTList::size(), Aleph::size(), and Aleph::tree_to_bits().
| TEST | ( | BinNodeUtils | , |
| TreeToBitsAndBitsToTreeRoundtripShapeAndKeys | |||
| ) |
Definition at line 850 of file bin-node-utils.cc.
References delete_tree(), inorder(), Aleph::LLINK(), Aleph::maps(), Aleph::RLINK(), root(), Aleph::BitArray::size(), Aleph::size(), and Aleph::tree_to_bits().