lib-src/trees/qa.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <assert.h>
  26 #include <stdio.h>
  27 #include <AD/trees/avl.h>
  28 #include <AD/trees/splay.h>
  29 #include <AD/trees/leftist.h>
  30 #include <AD/trees/pagoda.h>
  31
  32 typedef const char * string;
  33
  34 void print_tree (BinaryTree<string,string>& tree, Ix i)
  35 {  if (i == 0) { printf("."); return; }
  36    printf("%s(",tree.key(i));
  37    print_tree(tree,tree.left(i));
  38    printf(",");
  39    print_tree(tree,tree.right(i));
  40    printf(")");
  41 }
  42
  43 int main()
  44 {  AVLTree<string,string> avl;
  45    SplayTree<string,string> splay;
  46    LeftistTree<string,string> leftist;
  47    Pagoda<string,string> pagoda;
  48
  49    static struct { string first, last; } authors[] =
  50    {  { "Edgar",    "Doctorow"   },
  51       { "James",    "Joyce"      },
  52       { "Vladimir", "Nabokov"    },
  53       { "Pablo",    "Neruda",    },
  54       { "William",  "Faulkner",  },
  55       { "Ernest",   "Hemingway"  },
  56       { "Gabriel",  "Garcia Marquez" },
  57       { "Isabel",   "Allende" },
  58       { "Thomas",   "Pynchon" },
  59       { "Kurt",     "Vonnegurt" },
  60       { "Ken",      "Casey" },
  61       { "Norman",   "Mailer" },
  62    };
  63
  64    static struct { string first, last; } old_authors[] =
  65    {  { "William", "Shakespear" },
  66       { "Edgar",   "Poe" },
  67       { "Thomas",  "Jefferson" }
  68    };
  69
  70    int size = sizeof(authors)/sizeof(authors[0]);
  71    int i, n;
  72    Ix ix, iy; int count;
  73
  74
  75    for (i = 0; i < sizeof(old_authors)/sizeof(old_authors[0]); i++) {
  76       avl.insert(old_authors[i].first, old_authors[i].last);
  77       assert(avl.contains(old_authors[i].first));
  78       assert(avl.avl_balanced());
  79       splay.insert(old_authors[i].first, old_authors[i].last);
  80       assert(splay.contains(old_authors[i].first));
  81    }
  82
  83    for (i = 0; i < size; i++) {
  84       avl.insert(authors[i].first, authors[i].last);
  85       assert(avl.contains(authors[i].first));
  86       assert(avl.avl_balanced());
  87       splay.insert(authors[i].first, authors[i].last);
  88       assert(splay.contains(authors[i].first));
  89    }
  90
  91    printf( "AVL tree: size = %d\n", avl.size());
  92    for (count = 0, ix = avl.first(); ix; ix = avl.next(ix), count++)
  93       printf("[%s %s] ", avl.key(ix), avl.value(ix));
  94    printf("\n");
  95    assert(count == size);
  96
  97    for (count = 0, ix = avl.last(); ix; ix = avl.prev(ix), count++);
  98    assert(count == size);
  99
 100    printf( "Splay tree: size = %d\n", splay.size());
 101    for (count = 0, ix = splay.first(); ix; ix = splay.next(ix), count++)
 102       printf("[%s %s] ", splay.key(ix), splay.value(ix));
 103    printf("\n");
 104    assert(count == size);
 105
 106    for (count = 0, ix = splay.last(); ix; ix = splay.prev(ix), count++);
 107    assert(count == size);
 108
 109    for (i = 0; i < size; i++) {
 110       assert(avl.remove(authors[i].first));
 111       assert(avl.lookup(authors[i].first) == 0);
 112       assert(avl.avl_balanced());
 113       for (count = 0, ix = avl.first(); ix; ix = avl.next(ix), count++);
 114       assert(count == size - i - 1);
 115       for (count = 0, ix = avl.last(); ix; ix = avl.prev(ix), count++);
 116       assert(count == size - i - 1);
 117    }
 118    assert(avl.size() == 0);
 119
 120    for (i = 0; i < size; i++) {
 121       assert(splay.remove(authors[i].first));
 122       assert(splay.lookup(authors[i].first) == 0);
 123       for (count = 0, ix = splay.first(); ix; ix = splay.next(ix), count++);
 124       assert(count == size - i - 1);
 125       for (count = 0, ix = splay.last(); ix; ix = splay.prev(ix), count++);
 126       assert(count == size - i - 1);
 127    }
 128    assert(splay.size() == 0);
 129
 130    for (i = 0; i < size; i++)
 131       leftist.insert(authors[i].first,authors[i].last);
 132    assert(leftist.size() == size);
 133
 134    for (i = 0; i < size; i++)
 135       pagoda.insert(authors[i].first,authors[i].last);
 136    assert(pagoda.size() == size);
 137
 138    while (! leftist.isEmpty()) {
 139       ix = leftist.min();
 140       printf("[%s %s] ",leftist.key(ix),leftist.value(ix));
 141       assert(leftist.delete_min());
 142    }
 143    printf("\n");
 144    assert(leftist.size() == 0);
 145
 146    while (! pagoda.isEmpty()) {
 147       ix = pagoda.min();
 148       printf("[%s %s] ",pagoda.key(ix),pagoda.value(ix));
 149       assert(pagoda.delete_min());
 150    }
 151    printf("\n");
 152    assert(pagoda.size() == 0);
 153
 154    printf("OK\n");
 155    return 0;
 156 }