tests/qa3.cc

   1 //  Test hash table stuff
   2
   3 #include <assert.h>
   4 #include <stdio.h>
   5 #include <AD/hash/chash.h>   // coalesced hashing hash table
   6 #include <AD/hash/dchash.h>  // direct chaining hash table
   7 #include <AD/hash/dhash.h>   // double hashing hash table
   8 #include <AD/hash/lhash.h>   // linear probing hash table
   9 #include <AD/hash/ohash.h>   // ordered hashing hash table
  10 #include <AD/hash/chash2.h>   // coalesced hashing hash table
  11 #include <AD/hash/dchash2.h>  // direct chaining hash table
  12 #include <AD/hash/dhash2.h>   // double hashing hash table
  13 #include <AD/hash/lhash2.h>   // linear probing hash table
  14 #include <AD/hash/ohash2.h>   // ordered hashing hash table
  15
  16 typedef const char * string;
  17
  18 int main()
  19 {
  20    CHashTable<string,string>  a(10);
  21    DCHashTable<string,string> b(10,2);
  22    DHashTable<string,string>  c(10);
  23    LHashTable<string,string>  d(10);
  24    OHashTable<string,string>  e(10);
  25
  26    static struct { string first, last; } authors[] =
  27    {  { "Edgar",    "Doctorow"   },
  28       { "James",    "Joyce"      },
  29       { "Vladimir", "Nabokov"    },
  30       { "Pablo",    "Neruda",    },
  31       { "William",  "Faulkner",  },
  32       { "Ernest",   "Hemingway"  },
  33       { "Gabriel",  "Garcia Marquez" },
  34       { "Isabel",   "Allende" },
  35       { "Thomas",   "Pynchon" },
  36       { "Kurt",     "Vonnegurt" },
  37       { "Ken",      "Casey" },
  38       { "Norman",   "Mailer" },
  39    };
  40
  41    static struct { string first, last; } old_authors[] =
  42    {  { "William", "Shakespear" },
  43       { "Edgar",   "Poe" },
  44       { "Thomas",  "Jefferson" }
  45    };
  46
  47    int size = sizeof(authors)/sizeof(authors[0]);
  48    int i, n;
  49
  50    for (i = 0; i < sizeof(old_authors)/sizeof(old_authors[0]); i++) {
  51       a.insert(old_authors[i].first, old_authors[i].last);
  52       b.insert(old_authors[i].first, old_authors[i].last);
  53       c.insert(old_authors[i].first, old_authors[i].last);
  54       d.insert(old_authors[i].first, old_authors[i].last);
  55       e.insert(old_authors[i].first, old_authors[i].last);
  56    }
  57
  58    for (i = 0; i < sizeof(authors)/sizeof(authors[0]); i++) {
  59       a.insert(authors[i].first, authors[i].last);
  60       b.insert(authors[i].first, authors[i].last);
  61       c.insert(authors[i].first, authors[i].last);
  62       d.insert(authors[i].first, authors[i].last);
  63       e.insert(authors[i].first, authors[i].last);
  64    }
  65
  66    Ix ix;
  67    printf("[Coalesced hashing (size = %d, capacity = %d)]\n", a.size(), a.capacity());
  68    for (n = 0, ix = a.first(); ix; ix = a.next(ix), n++) {
  69       printf("Name %s %s\n", a.key(ix), a.value(ix));
  70       assert(a.lookup(a.key(ix)));
  71    }
  72    assert(a.size() == n);
  73
  74    printf("[Direct chaining (size = %d, capacity = %d)]\n", e.size(), e.capacity());
  75    for (n = 0, ix = b.first(); ix; ix = b.next(ix), n++) {
  76       printf("Name %s %s\n", b.key(ix), b.value(ix));
  77       assert(b.lookup(b.key(ix)));
  78    }
  79    assert(b.size() == n);
  80
  81    printf("[Double hashing (size = %d, capacity = %d)]\n", a.size(), a.capacity());
  82    for (n = 0, ix = c.first(); ix; ix = c.next(ix), n++) {
  83       printf("Name %s %s\n", c.key(ix), c.value(ix));
  84       assert(c.lookup(c.key(ix)));
  85    }
  86    assert(c.size() == n);
  87
  88    printf("[Linear hashing (size = %d, capacity = %d)]\n", b.size(), b.capacity());
  89    for (n = 0, ix = d.first(); ix; ix = d.next(ix), n++) {
  90       printf("Name %s %s\n", d.key(ix), d.value(ix));
  91       assert(d.lookup(d.key(ix)));
  92    }
  93    assert(d.size() == n);
  94
  95    printf("[Ordered hashing (size = %d, capacity = %d)]\n", c.size(), c.capacity());
  96    for (n = 0, ix = e.first(); ix; ix = e.next(ix), n++) {
  97       printf("Name %s %s\n", e.key(ix), e.value(ix));
  98       assert(e.lookup(e.key(ix)));
  99    }
 100    assert(e.size() == n);
 101
 102    assert(a.size() == size);
 103    assert(b.size() == size);
 104    assert(c.size() == size);
 105    assert(d.size() == size);
 106    assert(e.size() == size);
 107
 108    printf("OK\n");
 109    return 0;
 110 }