test_bt.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 463 行 · 第 1/2 页

//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Updated: JAM 08/19/92 -- modernized template syntax, remove macro hacks

#include <cool/String.h>
#include <cool/Binary_Node.h>
#include <cool/Binary_Node.C>
#include <cool/Binary_Tree.h>
#include <cool/Binary_Tree.C>
#include <cool/test.h>

void test_int_remove(CoolBinary_Tree<int>&);

void test_int_put () {  
  CoolBinary_Tree<int> b0;

  TEST ("b0.put(10)", b0.put(10), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 0);
  TEST ("b0.put(7)", b0.put(7), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  TEST ("b0.put(15)", b0.put(15), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  TEST ("b0.put(8)", b0.put(8), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  TEST ("b0.put(2)", b0.put(2), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  TEST ("b0.put(12)", b0.put(12), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  TEST ("b0.put(4)", b0.put(4), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  TEST ("b0.put(6)", b0.put(6), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 4);
  TEST ("b0.put(5)", b0.put(5), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 5);
  TEST ("b0.put(14)", b0.put(14), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 5);
  TEST ("b0.put(11)", b0.put(11), TRUE);
  TEST ("b0.tree_depth()", b0.tree_depth(), 5);
  TEST ("b0.count()", b0.count(), 11);

  TEST ("b0.find(5),b0.node()->is_leaf()", 
        (b0.find(5),b0.node()->is_leaf()), TRUE);
  TEST ("b0.find(8),b0.node()->is_leaf()",
        (b0.find(8),b0.node()->is_leaf()), TRUE);
  TEST ("b0.find(11),b0.node()->is_leaf()",
        (b0.find(11),b0.node()->is_leaf()), TRUE);
  TEST ("b0.find(14),b0.node()->is_leaf()",
        (b0.find(14),b0.node()->is_leaf()), TRUE);
  TEST ("b0.find(10),b0.node() == b0.get_root()",
        (b0.find(10),b0.node() == b0.get_root()), TRUE);
  test_int_remove (b0);
}

void test_int_remove (CoolBinary_Tree<int>& b0) {
  CoolBinary_Node<int>* n0;
    
  TEST ("b0.remove(7)", b0.remove(7), TRUE);
  TEST ("b0.find(7)", b0.find(7), FALSE);
  TEST ("b0.count()", b0.count(), 10);
  TEST ("b0.tree_depth()", b0.tree_depth(), 4);
  TEST ("b0.find(6)", b0.find(6), TRUE);
  TEST ("(b0.node() == b0.get_root()->get_ltree())",
         (b0.node() == b0.get_root()->get_ltree()), TRUE);
  TEST ("b0.find(5)",b0.find(5),TRUE);
  n0 = b0.node();
  TEST ("(n0 == (b0.find(4),b0.node()->get_rtree()))",
         (n0 == (b0.find(4),b0.node()->get_rtree())), TRUE);
  TEST ("b0.find(8)",b0.find(8),TRUE);
  n0 = b0.node();
  TEST ("(n0 == (b0.find(6),b0.node()->get_rtree()))",
         (n0 == (b0.find(6),b0.node()->get_rtree())), TRUE);

  TEST ("b0.remove(12)", b0.remove(12), TRUE);
  TEST ("b0.find(12)", b0.find(12), FALSE);
  TEST ("b0.count()", b0.count(), 9);
  TEST ("b0.tree_depth()", b0.tree_depth(), 4);
  TEST ("b0.find(11)",b0.find(11), TRUE);
  n0 = b0.node();
  TEST ("(n0 == (b0.find(15),b0.node()->get_ltree()))",
         (n0 == (b0.find(15),b0.node()->get_ltree())), TRUE);
  TEST ("b0.find(14)",b0.find(14), TRUE);
  n0 = b0.node();
  TEST ("(n0 == (b0.find(11),b0.node()->get_rtree()))",
         (n0 == (b0.find(11),b0.node()->get_rtree())), TRUE);


  TEST ("b0.remove(10)", b0.remove(10), TRUE);
  TEST ("b0.count()", b0.count(), 8);
  TEST ("b0.tree_depth()", b0.tree_depth(), 4);
  TEST ("b0.find(10)", b0.find(10), FALSE);
  TEST ("b0.get_root() == (b0.find(8),b0.node())",
        b0.get_root() == (b0.find(8),b0.node()), TRUE)
  TEST ("b0.find(6)",b0.find(6), TRUE);
  n0 = b0.node();
  TEST ("(n0 == (b0.find(8),b0.node()->get_ltree()))",
         (n0 == (b0.find(8),b0.node()->get_ltree())), TRUE);

  TEST ("b0.remove(5)", b0.remove(5), TRUE);
  TEST ("b0.count()", b0.count(), 7);
  TEST ("b0.tree_depth()", b0.tree_depth(), 3);

  TEST ("b0.remove(2)", b0.remove(2), TRUE);
  TEST ("b0.count()", b0.count(), 6);
  TEST ("b0.tree_depth()", b0.tree_depth(), 3);
  TEST ("b0.find(4)",b0.find(4), TRUE);
  n0 = b0.node();
  TEST ("(n0 == (b0.find(6),b0.node()->get_ltree()))",
         (n0 == (b0.find(6),b0.node()->get_ltree())), TRUE);

  TEST ("b0.remove(15)", b0.remove(15), TRUE);
  TEST ("b0.count()", b0.count(), 5);
  TEST ("b0.find(11)",b0.find(11), TRUE);
  TEST ("((b0.node())==(b0.get_root()->get_rtree()))",
         ((b0.node())==(b0.get_root()->get_rtree())), TRUE);

  TEST ("b0.remove(14)", b0.remove(14), TRUE);
  TEST ("b0.count()", b0.count(), 4);
  TEST ("b0.tree_depth()", b0.tree_depth(), 2);
  TEST ("b0.find(11),b0.node()->is_leaf()",
        (b0.find(11),b0.node()->is_leaf()), TRUE);

  TEST ("b0.remove(8)", b0.remove(8), TRUE);
  TEST ("b0.count()", b0.count(), 3);
  TEST ("b0.tree_depth()", b0.tree_depth(), 1);
  TEST ("b0.get_root()==(b0.find(6),b0.node())",
        (b0.get_root()==(b0.find(6),b0.node())), TRUE);
  TEST ("b0.find(4)",b0.find(4), TRUE);
  n0 = b0.node();
  TEST ("(n0==(b0.find(6),b0.node()->get_ltree()))",
         (n0==(b0.find(6),b0.node()->get_ltree())), TRUE);

  TEST ("b0.remove(11)", b0.remove(11), TRUE);
  TEST ("b0.count()", b0.count(), 2);
  TEST ("b0.tree_depth()", b0.tree_depth(), 1);

  TEST ("b0.remove(6)", b0.remove(6), TRUE);
  TEST ("b0.count()", b0.count(), 1);
  TEST ("b0.tree_depth()", b0.tree_depth(), 0);
  TEST ("b0.get_root()==(b0.find(4),b0.node())",
        (b0.get_root()==(b0.find(4),b0.node())), TRUE);
  TEST ("b0.get_root()->is_leaf()",
        (b0.get_root()->is_leaf()), TRUE);

  TEST ("b0.remove(4)", b0.remove(4), TRUE);
  TEST ("b0.count()", b0.count(), 0);
  TEST ("b0.tree_depth()", b0.tree_depth(), 0);
  TEST ("b0.get_root()==NULL", (b0.get_root()==NULL), TRUE);

}

void test_int () {  
  CoolBinary_Tree<int> b0;

  TEST ("CoolBinary_Tree<int> b0", b0.count(), 0);
  TEST ("b0.put(1)", b0.put(1), TRUE);
  TEST ("b0.count()", b0.count(), 1);
  TEST ("b0.find(1)", b0.find(1), TRUE);
  TEST ("b0.value()", b0.value(), 1);
  TEST ("b0.remove()", b0.remove(), TRUE);
  TEST ("b0.count()", b0.count(), 0);
  TEST ("b0.put(4)", b0.put(4), TRUE);
  TEST ("b0.count()", b0.count(), 1);
  TEST ("b0.put(8)", b0.put(8), TRUE);
  TEST ("b0.count()", b0.count(), 2);
  TEST ("b0.put(3)", b0.put(3), TRUE);
  TEST ("b0.count()", b0.count(), 3);
  TEST ("b0.put(1)", b0.put(1), TRUE);
  TEST ("b0.count()", b0.count(), 4);
  TEST ("b0.put(2)", b0.put(2), TRUE);
  TEST ("b0.count()", b0.count(), 5);
  TEST ("b0.put(6)", b0.put(6), TRUE);
  TEST ("b0.count()", b0.count(), 6);
  TEST ("b0.find(2)", b0.find(2), TRUE);
  TEST ("b0.value()", b0.value(), 2);
  TEST ("b0.reset()", (b0.reset(), 1), 1);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 1);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 2);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 3);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 4);
  TEST ("b0.prev()", b0.prev(), TRUE);
  TEST ("b0.value()", b0.value(), 3);
  TEST ("b0.prev()", b0.prev(), TRUE);
  TEST ("b0.value()", b0.value(), 2);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 3);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 4);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 6);
  TEST ("b0.next()", b0.next(), TRUE);
  TEST ("b0.value()", b0.value(), 8);
  TEST ("b0.count()", b0.count(), 6);
  TEST ("b0.find(99)", b0.find(99), FALSE);
  CoolBinary_Tree<int> b1(b0);
  TEST ("CoolBinary_Tree<int> b1(b0)", b1.count(), 6);
  TEST ("b1.remove(3)", b1.remove(3), TRUE);
  TEST ("b1.count()", b1.count(), 5);
  TEST ("b1.find(3)", b1.find(3), FALSE);
  TEST ("b0.balance()", (b0.balance(), b0.count()), 6);
  TEST ("b0.remove(3)", b0.remove(3), TRUE);
  TEST ("b0.count()", b0.count(), 5);
  TEST ("b0.find(3)", b0.find(3), FALSE);
  TEST ("b0.put(-3)", b0.put(-3), TRUE);
  TEST ("b0.count()", b0.count(), 6);
  TEST ("b0.put(18)", b0.put(18), TRUE);
  TEST ("b0.count()", b0.count(), 7);
  TEST ("b0.put(13)", b0.put(13), TRUE);
  TEST ("b0.count()", b0.count(), 8);
  TEST ("b0.put(1)", b0.put(1), FALSE);
  TEST ("b0.count()", b0.count(), 8);
  TEST ("b0.put(5)", b0.put(5), TRUE);
  TEST ("b0.count()", b0.count(), 9);
  TEST ("b0.put(17)", b0.put(17), TRUE);
  TEST ("b0.count()", b0.count(), 10);
  TEST ("b0.put(3)", b0.put(3), TRUE);
  TEST ("b0.count()", b0.count(), 11);
  TEST ("b0.balance()", (b0.balance(), b0.count()), 11);
  TEST ("b0.find(3)", b0.find(3), TRUE);
  TEST ("b0.find(8)", b0.find(8), TRUE);