Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
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::maps(), 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(), inorder(), Aleph::maps(), and root().

◆ TEST() [3/37]

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() [4/37]

TEST ( BinNodeUtils  ,
CheckBstRejectsGlobalViolation   
)

◆ TEST() [5/37]

TEST ( BinNodeUtils  ,
ComputeNodesInLevel   
)

◆ TEST() [6/37]

TEST ( BinNodeUtils  ,
FindMinMax   
)

◆ TEST() [7/37]

TEST ( BinNodeUtils  ,
FindSuccessorAndPredecessor   
)

◆ TEST() [8/37]

TEST ( BinNodeUtils  ,
ForEachTraversals   
)

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

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

◆ TEST() [9/37]

◆ TEST() [10/37]

TEST ( BinNodeUtils  ,
InsertDupInBstAllowsDuplicates   
)

◆ TEST() [11/37]

TEST ( BinNodeUtils  ,
InsertDupRootAlwaysInserts   
)

◆ TEST() [12/37]

TEST ( BinNodeUtils  ,
InsertInBstRejectsDuplicates   
)

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

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

◆ TEST() [13/37]

TEST ( BinNodeUtils  ,
InsertRootRecInsertsAndRotatesToRoot   
)

◆ TEST() [14/37]

TEST ( BinNodeUtils  ,
InsertRootRecRejectsDuplicate   
)

◆ TEST() [15/37]

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() [16/37]

TEST ( BinNodeUtils  ,
InternalPathLength   
)

◆ TEST() [17/37]

TEST ( BinNodeUtils  ,
JoinExclusiveEmptiesInputs   
)

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

References inorder(), Aleph::insert_in_bst(), and Aleph::maps().

◆ TEST() [18/37]

TEST ( BinNodeUtils  ,
JoinPreorderStoresDuplicates   
)

◆ TEST() [19/37]

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() [20/37]

TEST ( BinNodeUtils  ,
LoadTreeKeysInPrefixThrowsOnShortInput   
)

◆ TEST() [21/37]

TEST ( BinNodeUtils  ,
PrefixInfixSuffixLists   
)

◆ TEST() [22/37]

TEST ( BinNodeUtils  ,
PreorderToBstBuildsValidTree   
)

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

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

◆ TEST() [23/37]

TEST ( BinNodeUtils  ,
Property_InsertRemoveRandom_StableInvariants   
)

◆ TEST() [24/37]

TEST ( BinNodeUtils  ,
RemoveFromBstRespectsComparator   
)

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

References Aleph::check_bst(), KEY, Aleph::maps(), and root().

◆ TEST() [25/37]

TEST ( BinNodeUtils  ,
RemoveFromBstReturnsDetachedNode   
)

◆ TEST() [26/37]

TEST ( BinNodeUtils  ,
RotationsPreserveInorder   
)

◆ TEST() [27/37]

TEST ( BinNodeUtils  ,
SaveTreeInArrayEscapesKeys   
)

◆ TEST() [28/37]

TEST ( BinNodeUtils  ,
SaveTreeInArrayOfCharsLoadTreeFromArrayRoundtrip   
)

◆ TEST() [29/37]

TEST ( BinNodeUtils  ,
SaveTreeLoadTreeRoundtrip   
)

◆ TEST() [30/37]

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() [31/37]

TEST ( BinNodeUtils  ,
SearchParentReturnsNodeAndUpdatesParent   
)

◆ TEST() [32/37]

TEST ( BinNodeUtils  ,
SearchRankParent   
)

◆ TEST() [33/37]

TEST ( BinNodeUtils  ,
SplitKeyDupRecSplitsAndEmptiesRoot   
)

◆ TEST() [34/37]

TEST ( BinNodeUtils  ,
SplitKeyIterativeSplits   
)

◆ TEST() [35/37]

TEST ( BinNodeUtils  ,
SplitKeyRecOnlySplitsWhenKeyAbsent   
)

◆ TEST() [36/37]

TEST ( BinNodeUtils  ,
ThreadedTraversalsDoNotCorruptTree   
)

◆ TEST() [37/37]

TEST ( BinNodeUtils  ,
TreeToBitsAndBitsToTreeRoundtripShapeAndKeys   
)