// Abstract AVL Tree Template Test Suite.
// This code is in the public domain.
// Version: 1.5 Author: Walt Karas
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "avl_tree.h"
// Check to make sure double inclusion OK.
#include "avl_tree.h"
void bail(const char *note)
{
printf("%s\n", note);
exit(1);
}
// Mask of highest bit in an unsigned int.
const unsigned HIGH_BIT = (~(((unsigned) (~ 0)) >> 1));
// Node array and "shadow" node array.
struct
{
signed char bf;
int val;
unsigned gt, lt;
}
arr[401], arr2[400];
// Class to pass to template as abstractor parameter.
class abstr
{
public:
// Handles are indexes into the "arr" array. If a handle has been
// "accessed", it has its high bit set. (The handle has to have been
// accessed in order to alter the node's values, or compare its key.)
typedef unsigned handle;
typedef unsigned size;
typedef int key;
static handle get_less(handle h, bool access)
{
if (!(h & HIGH_BIT))
bail("get_less");
handle child = arr[h & ~HIGH_BIT].lt;
if (access)
child |= HIGH_BIT;
return(child);
}
static void set_less(handle h, handle lh)
{
if (!(h & HIGH_BIT))
{
printf("%x %x\n", h, lh);
bail("set_less");
}
if (lh != ~0)
lh &= ~HIGH_BIT;
arr[h & ~HIGH_BIT].lt = lh;
}
static handle get_greater(handle h, bool access)
{
if (!(h & HIGH_BIT))
bail("get_greater");
handle child = arr[h & ~HIGH_BIT].gt;
if (access)
child |= HIGH_BIT;
return(child);
}
static void set_greater(handle h, handle gh)
{
if (!(h & HIGH_BIT))
bail("set_greater");
if (gh != ~0)
gh &= ~HIGH_BIT;
arr[h & ~HIGH_BIT].gt = gh;
}
static int get_balance_factor(handle h)
{
if (!(h & HIGH_BIT))
bail("get_balance_factor");
return(arr[h & ~HIGH_BIT].bf);
}
static void set_balance_factor(handle h, int bf)
{
if (!(h & HIGH_BIT))
bail("set_balance_factor");
arr[h & ~HIGH_BIT].bf = bf;
}
static int compare_key_node(key k, handle h)
{
if (!(h & HIGH_BIT))
bail("compare_key_node");
return(k - arr[h & ~HIGH_BIT].val);
}
static int compare_node_node(handle h1, handle h2)
{
if (!(h1 & HIGH_BIT))
bail("compare_node_node - h1");
if (!(h2 & HIGH_BIT))
bail("compare_node_node - h2");
return(arr[h1 & ~HIGH_BIT].val - arr[h2 & ~HIGH_BIT].val);
}
static handle null(void) { return(~0); }
static bool read_error(void) { return(false); }
};
// AVL tree with public root for testing purposes.
class t_avl_tree : public abstract_container::avl_tree
{
public:
handle &pub_root;
t_avl_tree(void) : pub_root(abs.root) { }
};
t_avl_tree tree;
typedef t_avl_tree::iter iter;
// Verifies that a tree is a valid AVL Balanced Binary Search Tree.
// Returns depth. Don't use on an empty tree.
int verify_tree(unsigned subroot = tree.pub_root & ~HIGH_BIT)
{
int l_depth, g_depth;
unsigned h;
if (arr[subroot].lt == ~0)
l_depth = 0;
else
{
h = arr[subroot].lt & ~HIGH_BIT;
if (arr[subroot].val <= arr[h].val)
{
printf("not less: %u %d %d %d\n",
subroot, arr[subroot].val, h, arr[h].val);
bail("verify_tree");
}
l_depth = verify_tree(h);
}
if (arr[subroot].gt == ~0)
g_depth = 0;
else
{
h = arr[subroot].gt & ~HIGH_BIT;
if (arr[subroot].val >= arr[h].val)
{
printf("not greater: %u %d %d %d\n",
subroot, arr[subroot].val, h, arr[h].val);
bail("verify_tree");
}
g_depth = verify_tree(h);
}
if (arr[subroot].bf != (g_depth - l_depth))
{
printf("bad bf: n=%u bf=%d gd=%d ld=%d\n",
subroot, arr[subroot].bf, g_depth, l_depth);
bail("verify_tree");
}
return((g_depth > l_depth ? g_depth : l_depth) + 1);
}
void check_empty(void)
{
if (tree.pub_root != ~0)
bail("not empty");
}
void insert(unsigned h)
{
unsigned rh = tree.insert(h | HIGH_BIT);
if (rh == ~0)
bail("insert null");
rh &= ~HIGH_BIT;
if (arr[h].val != arr[rh].val)
{
printf("bad - %u %u\n", h, rh);
bail("insert");
}
}
void remove(int k, bool should_be_null = false)
{
unsigned rh = tree.remove(k);
if (rh == ~0)
{
if (!should_be_null)
{
printf("null key=%d\n", k);
bail("remove");
}
}
else
{
if (should_be_null)
{
printf("not null key=%d rh=%u\n", k, rh);
bail("remove");
}
rh &= ~HIGH_BIT;
if (arr[rh].val != k)
{
printf("wrong key=%d rh=%u [rh].val=%d\n", k, rh, arr[rh].val);
bail("remove");
}
// Mark balance factor of node to indicate it's not in the tree.
arr[rh].bf = 123;
}
}
unsigned max_elems;
// Prior to starting a test, mark all the nodes to be used in the test
// with a bad balance factor. This makes it easy to tell which nodes
// are in the tree and which aren't.
void mark_bf(void)
{
unsigned i = max_elems;
while (i)
{
i--;
arr[i].bf = 123;
}
}
void search_test(int key, abstract_container::search_type st, unsigned rh)
{
if (tree.search(key, st) != (rh | HIGH_BIT))
{
printf("%d %x %u\n", key, (unsigned) st, rh);
bail("search_test");
}
iter it;
it.start_iter(tree, key, st);
if (*it != (rh | HIGH_BIT))
{
printf("%d %x %x %x\n", key, (unsigned) st, rh, *it);
bail("search_test - iter");
}
if ((st == abstract_container::EQUAL) && (rh != ~0))
{
unsigned h = *it;
iter it2 = it;
it++;
it2--;
if (*it != tree.search(key, abstract_container::GREATER))
{
printf("%d %x %x %x\n", key, (unsigned) st, h, *it);
bail("search_test - iter ++");
}
if (*it2 != tree.search(key, abstract_container::LESS))
{
printf("%d %x %x %x\n", key, (unsigned) st, h, *it2);
bail("search_test - iter --");
}
}
return;
}
void search_test(unsigned h)
{
if (arr[h].bf == 123)
{
search_test(2 * h, abstract_container::EQUAL, ~0);
// Test subst function.
arr[400].val = 2 * h;
if (tree.subst(400 | HIGH_BIT) != ~0)
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst not there");
}
}
else
{
search_test(2 * h, abstract_container::EQUAL, h);
search_test(2 * h, abstract_container::LESS_EQUAL, h);
search_test(2 * h, abstract_container::GREATER_EQUAL, h);
search_test(2 * h + 1, abstract_container::EQUAL, ~0);
search_test(2 * h + 1, abstract_container::LESS, h);
search_test(2 * h + 1, abstract_container::LESS_EQUAL, h);
search_test(2 * h - 1, abstract_container::EQUAL, ~0);
search_test(2 * h - 1, abstract_container::GREATER, h);
search_test(2 * h - 1, abstract_container::GREATER_EQUAL, h);
// Test subst function.
arr[400].val = 2 * h - 1;
if (tree.subst(400 | HIGH_BIT) != ~0)
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst low");
}
arr[400].val = 2 * h;
if (tree.subst(400 | HIGH_BIT) != (h | HIGH_BIT))
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst in");
}
verify_tree();
if (tree.subst(h | HIGH_BIT) != (400 | HIGH_BIT))
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst out");
}
arr[400].val = 2 * h + 1;
if (tree.subst(400 | HIGH_BIT) != ~0)
{
printf("max_elems=%u h=%x\n", max_elems, h);
bail("subst high");
}
}
}
void search_all(void)
{
unsigned h = max_elems, min = ~0, max = ~0;
while (h)
{
h--;
search_test(h);
if (arr[h].bf != 123)
{
if (max == ~0)
max = h;
min = h;
}
}
h = tree.search_least();
if (h != (min | HIGH_BIT))
{
printf("%x %x\n", h, min);
bail("search_all least");
}
h = tree.search_greatest();
if (h != (max | HIGH_BIT))
{
printf("%x %x\n", h, max);
bail("search_all greatest");
}
iter it;
// Test forward iteration through entire tree.
it.start_iter_least(tree);
if (*it != (min | HIGH_BIT))
{
printf("%x %x\n", h, min);
bail("search_all least - iter");
}
while (*it != (max | HIGH_BIT))
{
h = *it;
it++;
if (*it != tree.search(2 * h, abstract_container::GREATER))
{
printf("%x %x\n", h, *it);
bail("search_all increment - iter");
}
}
it++;
if (*it != ~0)
bail("search_all increment - end");
// Test backward iteration through entire tree.
it.start_iter_greatest(tree);
if (*it != (max | HIGH_BIT))
{
printf("%x %x\n", h, max);
bail("search_all greatest - iter");
}
while (*it != (min | HIGH_BIT))
{
h = *it;
it--;
if (*it != tree.search(2 * h, abstract_container::LESS))
{
printf("%x %x\n", h, *it);
bail("search_all increment - iter");
}
}
it--;
if (*it != ~0)
bail("search_all increment - end");
}
void dump(unsigned subroot, unsigned depth)
{
if (arr[subroot].lt != ~0)
dump(arr[subroot].lt, depth + 1);
printf("%u(%u, %d) ", subroot, depth, arr[subroot].bf);
if (arr[subroot].gt != ~0)
dump(arr[subroot].gt, depth + 1);
}
void dump(void)
{
dump(tree.pub_root & ~HIGH_BIT, 0);
putchar('\n');
}
// Create a tree with the nodes whose handles go from 0 to max_elems - 1.
// Insert step and remove step parameters must be relatively prime to
// max_elems.
void big_test(unsigned in_step, unsigned rm_step)
{
unsigned in = 0, rm = 0;
printf("inserting\n");
do
{
insert(in);
verify_tree();
in += in_step;
in %= max_elems;
}
while (in != 0);
search_all();
printf("removing\n");
for ( ; ; )
{
remove(rm * 2);
rm += rm_step;
rm %= max_elems;
if (rm == 0)
break;
verify_tree();
}
check_empty();
}
// Iterate through all the possible topologies of AVL trees with a
// certain depth. The trees are created in the "shadow" node array,
// then copied into the main node array.
class possible_trees
{
private:
// 1-base depth.
unsigned depth_;
// Subtree description structure. size is number of nodes in subtree.
struct sub { unsigned root, size; };
sub t;
// Create "first" subtree of a given depth with the node whose handle
// is "start" as the node with the minimum key in the tree. balance
// factors of nodes with children are all -1 in the first subtree.
sub first(unsigned start, unsigned depth)
{
sub s;
if (depth == 0)
{
s.size = 0;
s.root = ~0;
}
else if (depth == 1)
{
arr2[start].bf = 0;
arr2[start].lt = ~0;
arr2[start].gt = ~0;
s.size = 1;
s.root = start;
}
else
{
s = first(start, depth - 1);
start += s.size;
arr2[start].bf = -1;
arr2[start].lt = s.root;
sub s2 = first(start + 1, depth - 2);
arr2[start].gt = s2.root;
s.root = start;
s.size += s2.size + 1;
}
return(s);
}
// If there is no "next" subtree, returns a subtree description with
// a size of zero.
sub next(unsigned start, unsigned subroot, unsigned depth)
{
sub s;
if (depth < 2)
// For a subtree of depth 1 (1 node), the first topology is the
// only topology, so no next.
s.size = 0;
else
{
// Get next greater subtree.
s = next(subroot + 1, arr2[subroot].gt,
depth - (arr2[subroot].bf == -1 ? 2 : 1));
if (s.size != 0)
{
arr2[subroot].gt = s.root;
s.size += subroot - start + 1;
s.root = subroot;
}
else
{
// No next greater subtree. Get next less subtree, and
// start over with first greater subtree.
int bf = arr2[subroot].bf;
s = next(start, arr2[subroot].lt, depth - (bf == 1 ? 2 : 1));
if (s.size == 0)
{
// No next less subtree.
if (bf == 1)
// No next balance factor.
return(s);
// Go to next balance factor, then start iteration
// all over with first less and first greater subtrees.
bf++;
s = first(start, depth - (bf == 1 ? 2 : 1));
}
start += s.size;
arr2[start].lt = s.root;
s.root = start;
sub s2 = first(s.root + 1, depth - (bf == -1 ? 2 : 1));
arr2[s.root].gt = s2.root;
arr2[s.root].bf = bf;
s.size += s2.size + 1;
}
}
return(s);
}
void dump(unsigned subroot, unsigned depth)
{
if (arr2[subroot].lt != ~0)
dump(arr2[subroot].lt, depth + 1);
printf("%u(%u, %d) ", subroot, depth, arr2[subroot].bf);
if (arr2[subroot].gt != ~0)
dump(arr2[subroot].gt, depth + 1);
}
public:
// Copy from shadow node array to main node array and set tree root.
void place(void)
{
memcpy(arr, arr2, t.size * sizeof(arr[0]));
tree.pub_root = t.root | HIGH_BIT;
}
void first(unsigned d) { depth_ = d; t = first(0, depth_); }
bool next(void)
{
if (t.size == 0)
bail("possible_trees::next");
t = next(0, t.root, depth_);
return(t.size > 0);
}
void dump(void) { dump(t.root, 0); putchar('\n'); }
possible_trees(void) { t.size = 0; }
};
possible_trees pt;
// Tests for each tree in the iteration.
void one_tree(void)
{
pt.place();
unsigned h = tree.search_least();
while (h != ~0)
{
arr[400].val = 2 * h - 1;
insert(400);
verify_tree();
pt.place();
arr[400].val = 2 * h + 1;
insert(400);
verify_tree();
pt.place();
remove(2 * h);
verify_tree();
pt.place();
h = tree.search(2 * h, abstract_container::GREATER);
}
}
void all_trees(unsigned depth)
{
pt.first(depth);
do
one_tree();
while (pt.next());
}
// Array of handles in order by node key.
unsigned h_arr[400];
// Test the build member function template by building tress with from 1
// to 400 nodes.
void build_test(void)
{
unsigned i;
tree.build(h_arr, 0);
check_empty();
for (i = 0; i < 400; i++)
{
h_arr[i] = i | HIGH_BIT;
tree.build(h_arr, i + 1);
verify_tree();
}
}
int main()
{
unsigned i;
printf(
"Empty member optimization is%s working\n",
sizeof(abstract_container::avl_tree) == sizeof(unsigned) ?
"" : " NOT");
for (i = 0; i < 400; i++)
arr2[i].val = i * 2;
memcpy(arr, arr2, sizeof(arr));
max_elems = 3;
mark_bf();
printf("0 nodes\n");
check_empty();
search_all();
printf("1 node\n");
insert(1);
insert(1);
verify_tree();
search_all();
remove(2);
remove(2, true);
check_empty();
printf("2 nodes less slant\n");
insert(2);
insert(2);
insert(1);
insert(1);
verify_tree();
search_all();
remove(2);
remove(2, true);
insert(1);
verify_tree();
remove(4);
remove(4, true);
verify_tree();
remove(2);
check_empty();
printf("2 nodes greater slant\n");
insert(1);
insert(1);
insert(2);
insert(2);
verify_tree();
search_all();
remove(4);
remove(4, true);
insert(2);
verify_tree();
remove(2);
remove(2, true);
verify_tree();
remove(4);
check_empty();
max_elems = 400;
printf("%u nodes\n", max_elems);
mark_bf();
big_test(3, 7);
big_test(13, 7);
printf("all trees depth 3\n");
all_trees(3);
printf("all trees depth 4\n");
all_trees(4);
printf("all trees depth 5\n");
all_trees(5);
printf("build test\n");
build_test();
printf("SUCCESS!\n");
return(0);
}
(
geocities.com/wkaras)