tests/qa5.cc

   1 //  Test tree stuff
   2
   3 #include <assert.h>
   4 #include <stdio.h>
   5 #include <AD/trees/avl.h>
   6 #include <AD/trees/splay.h>
   7 #include <AD/trees/leftist.h>
   8 #include <AD/trees/pagoda.h>
   9
  10 typedef const char * string;
  11
  12 void print_tree (BinaryTree<string,string>& tree, Ix i)
  13 {  if (i == 0) { printf("."); return; }
  14    printf("%s(",tree.key(i));
  15    print_tree(tree,tree.left(i));
  16    printf(",");
  17    print_tree(tree,tree.right(i));
  18    printf(")");
  19 }
  20
  21 int main()
  22 {  AVLTree<string,string> avl;
  23    SplayTree<string,string> splay;
  24    LeftistTree<string,string> leftist;
  25    Pagoda<string,string> pagoda;
  26
  27    static struct { string first, last; } authors[] =
  28    {  { "Edgar",    "Doctorow"   },
  29       { "James",    "Joyce"      },
  30       { "Vladimir", "Nabokov"    },
  31       { "Pablo",    "Neruda",    },
  32       { "William",  "Faulkner",  },
  33       { "Ernest",   "Hemingway"  },
  34       { "Gabriel",  "Garcia Marquez" },
  35       { "Isabel",   "Allende" },
  36       { "Thomas",   "Pynchon" },
  37       { "Kurt",     "Vonnegurt" },
  38       { "Ken",      "Casey" },
  39       { "Norman",   "Mailer" },
  40    };
  41
  42    static struct { string first, last; } old_authors[] =
  43    {  { "William", "Shakespear" },
  44       { "Edgar",   "Poe" },
  45       { "Thomas",  "Jefferson" }
  46    };
  47
  48    int size = sizeof(authors)/sizeof(authors[0]);
  49    int i, n;
  50    Ix ix, iy; int count;
  51
  52
  53    for (i = 0; i < sizeof(old_authors)/sizeof(old_authors[0]); i++) {
  54       avl.insert(old_authors[i].first, old_authors[i].last);
  55       assert(avl.contains(old_authors[i].first));
  56       assert(avl.avl_balanced());
  57       splay.insert(old_authors[i].first, old_authors[i].last);
  58       assert(splay.contains(old_authors[i].first));
  59    }
  60
  61    for (i = 0; i < size; i++) {
  62       avl.insert(authors[i].first, authors[i].last);
  63       assert(avl.contains(authors[i].first));
  64       assert(avl.avl_balanced());
  65       splay.insert(authors[i].first, authors[i].last);
  66       assert(splay.contains(authors[i].first));
  67    }
  68
  69    printf( "AVL tree: size = %d\n", avl.size());
  70    for (count = 0, ix = avl.first(); ix; ix = avl.next(ix), count++)
  71       printf("[%s %s] ", avl.key(ix), avl.value(ix));
  72    printf("\n");
  73    assert(count == size);
  74
  75    for (count = 0, ix = avl.last(); ix; ix = avl.prev(ix), count++);
  76    assert(count == size);
  77
  78    printf( "Splay tree: size = %d\n", splay.size());
  79    for (count = 0, ix = splay.first(); ix; ix = splay.next(ix), count++)
  80       printf("[%s %s] ", splay.key(ix), splay.value(ix));
  81    printf("\n");
  82    assert(count == size);
  83
  84    for (count = 0, ix = splay.last(); ix; ix = splay.prev(ix), count++);
  85    assert(count == size);
  86
  87    for (i = 0; i < size; i++) {
  88       assert(avl.remove(authors[i].first));
  89       assert(avl.lookup(authors[i].first) == 0);
  90       assert(avl.avl_balanced());
  91       for (count = 0, ix = avl.first(); ix; ix = avl.next(ix), count++);
  92       assert(count == size - i - 1);
  93       for (count = 0, ix = avl.last(); ix; ix = avl.prev(ix), count++);
  94       assert(count == size - i - 1);
  95    }
  96    assert(avl.size() == 0);
  97
  98    for (i = 0; i < size; i++) {
  99       assert(splay.remove(authors[i].first));
 100       assert(splay.lookup(authors[i].first) == 0);
 101       for (count = 0, ix = splay.first(); ix; ix = splay.next(ix), count++);
 102       assert(count == size - i - 1);
 103       for (count = 0, ix = splay.last(); ix; ix = splay.prev(ix), count++);
 104       assert(count == size - i - 1);
 105    }
 106    assert(splay.size() == 0);
 107
 108    for (i = 0; i < size; i++)
 109       leftist.insert(authors[i].first,authors[i].last);
 110    assert(leftist.size() == size);
 111
 112    for (i = 0; i < size; i++)
 113       pagoda.insert(authors[i].first,authors[i].last);
 114    assert(pagoda.size() == size);
 115
 116    while (! leftist.is_empty()) {
 117       ix = leftist.min();
 118       printf("[%s %s] ",leftist.key(ix),leftist.value(ix));
 119       assert(leftist.delete_min());
 120    }
 121    printf("\n");
 122    assert(leftist.size() == 0);
 123
 124    while (! pagoda.is_empty()) {
 125       ix = pagoda.min();
 126       printf("[%s %s] ",pagoda.key(ix),pagoda.value(ix));
 127       assert(pagoda.delete_min());
 128    }
 129    printf("\n");
 130    assert(pagoda.size() == 0);
 131
 132    printf("OK\n");
 133    return 0;
 134 }