hashtabletest.cpp

Go to the documentation of this file.

#include <cmath>
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

#include <aclock.h>
#include <bucketlink.h>
#include <hashtable.h>
#include <hashtable2.h>
#include <hashtabletest.h>
#include <print.h>
#include <stringhash.h>
#include <stringpairhash.h>
#include <typedefs.h>


string hashtabletest::doc[] = 
{
  "",
  "Basic interactive looking up a dictionary test.",
  "Unit test: Inserting and retrieving integers.",
  "Unit test: hash table same size as data, inserting and retriving integers and timing.",
  "Unit test: hashtable2 random integer insert and retrieving.",
  "Iterating through hash table code - prelude to hashtableiterator.",
  "hashtableiterator - iterating though a hashtable container. ",
  "Iteratively remove elements from a hash table.",
  "Write to a hash element, changing it."
};


void hashtabletest::test01()
{
  cout << "Testing Hash Table for Strings" << endl;

  string dict[] = { "abc", "nogo", "python" };

  cout << "The dictionary is: ";
  cout << print(dict,dict+3) << endl;

  uintc n(sizeof(dict)/sizeof(string));

  vector< bucketlink<string> > v(n);
  for (uint i=0; i<n; ++i)
    v[i] = bucketlink<string>(&dict[i]);

  uintc hashtablesize(70);
  stringhash h(32,8);
  hashtable<string,stringhash&> H(hashtablesize,h);

  for (uint i=0; i<n; ++i)
    H.insert( & v[i] );

  bucketlink<string> * cp;

  string k;
  for ( ; k!="exit"; )
  {
    cout << "Look to see if string is in the hash table" << endl;
    cout << "Enter \"exit\" to terminate." << endl;
    cout << "Enter string k: ";
    cin >> k;

    if (k=="exit")
      return;

    cp = H.insertInverse(k);
    if (cp==0)
      cout << "not found" << endl;
    else
      cout << "found" << endl;
    cout << SHOW(H.contains(k)) << endl;
  }
}


int hashtabletest::test02unit()
{
  cout << "Testing Hash Table" << endl << endl;

  cout << "Testing if all inserted integers in hash table " << endl;
  cout << "  can be retrieved." << endl;  
  cout << endl;

  int p = 1003;
  int t;
  uint kmax = 7;

  vector<int> v;
  vector< bucketlink<int> > bv;
  uint sz = 4000;

  cout << "Inserting " << sz << " numbers into the hash table." << endl;

  for (uint i=0; i<sz; ++i)
  {
    t = i;

    for (uint k=0; k<kmax; ++k)
    {
      t *= i;
      t = t % p;
    }
    v.push_back(t); 
  }

  hashfunction01 h(8);
  hashtable<int,hashfunction01&> H(60,h);

  for (uint i=0; i<sz; ++i)
  {
    bv.push_back( bucketlink<int>(&v[i]) );
    H.insert( & bv[i] );
  }


  cout << "Testing if the inserted numbers are in the hash table." << endl;

  for (uint i=0; i<sz; ++i)
  {
    if (H.insertInverse( v[i] ) != 0)
      cout << v[i] << " ";
    assert( H.insertInverse( v[i] ) != 0 );
    if (H.insertInverse(v[i])==0)
      return 1;
  }
  cout << endl;

  cout << "success" << endl;

  return 0;
}


boolc hashtabletest::insertandretrievetest
(
  uintc n, 
  uintc hashtablesize
)
{
  int t;
  uint kmax = 7;

  vector<int> v(n);
  vector< bucketlink<int> > bv(n);
  uint sz = n;

  // Make some data to be hashed.
  // Put this data in vector v.
  for (uint i=0; i<sz; ++i)
  {
    t = i;

    for (uint k=0; k<kmax; ++k)
    {
      t *= i;
      t = t % n;
    }
    v[i] = t;
  }

  cout << sz;

  hashfunction01 h(8);
  hashtable<int,hashfunction01&> H(hashtablesize,h);

  aclock c;
  c.measure();

  for (uint i=0; i<sz; ++i)
  {
    bv[i] = bucketlink<int>(&v[i]);
    H.insert( & bv[i] );
  }

  c.measure();
  cout << "  " << c.diff_s();


  bucketlink<int> * cp;

  c.measure();
  for (uint i=0; i<sz; ++i)
  {
    cp = H.insertInverse( v[i] );
    assert( cp != 0 );
    if (cp==0)
      return false;
  }
  c.measure();
  cout << "  " << c.diff_s() << endl;

  return true;
}

int hashtabletest::test03unit()
{
  cout << "Testing Hash Table" << endl;
  cout << "same size of table as data" << endl;
  cout << endl;
  cout << "Testing Hash Table" << endl << endl;

  cout << "Testing if all inserted integers in hash table " << endl;
  cout << "  can be retrieved and timing." << endl;  
  cout << endl;

  uint u=1000;
  for (uint k=0; k<12; ++k)
  {
    if ( insertandretrievetest(u,u) == false)
      return 1;

    u *= 2;
  }
  cout << "success" << endl;
  return 0;
}

int hashtabletest::test04unit()
{

  uintc vsz(10);
  vector<int> v(vsz);

  for (uint i=0; i<vsz; ++i)
    v[i]=rand();

  cout << "Inserting " << vsz << " random integers." << endl;

  hashfunction01 hfn(8);
  hashtable2<int,hashfunction01> h(60,hfn);
  h.insert(&v[0],&v[0]+vsz);

  cout << "Testing if they are in the hashtable2 container." << endl;

  for (uint i=0; i<vsz; ++i)
  {
    cout << SHOW(v[i]) << " ";
    assert( h.contains(v[i]) == true );
    if (h.contains(v[i])!=true)
      return 1;
  }
  cout << endl;
  
  cout << "success" << endl;
  return 0;
}


void hashtabletest::test05()
{

  typedef stringpair<int> spi;
  spi wi[] = 
  { 
    spi("cat",87), spi("sam",840), spi("troghe",92), spi("tx67",89), 
    spi("zsh",11)
  };
  uintc N=5;
  vector<spi> vi(wi,wi+5);
  typedef bucketlink<spi> bl;
  vector<bl> bv(N);

  
  typedef stringpairhash<int> sphi;
  sphi sph;
  hashtable<spi,sphi&> h1(N*2,sph);

  for (uint i=0; i<N; ++i)
  {
    bv[i] = bl(&vi[i]);
    h1.insert(&bv[i]);
  }

  for (uint i=0; i<h1.bucketsize; ++i)
  {
    if (h1.vb[i]==0)
      continue;

    bl* x = h1.vb[i];
    for ( ;x!=0; x=x->next )
      cout << x->data->id << endl;
  }
}


void hashtabletest::test06()
{

  typedef stringpair<int> spi;
  spi wi[] = 
  { 
    spi("cat",87), spi("sam",840), spi("troghe",92), spi("tx67",89), 
    spi("zsh",11)
  };
  uintc N=5;
  vector<spi> vi(wi,wi+N);
  typedef bucketlink<spi> bl;
  vector<bl> bv(N);

  typedef stringpairhash<int> sphi;
  sphi sph;
  hashtable<spi,sphi&> h1(N*2,sph);

  for (uint i=0; i<N; ++i)
  {
    bv[i] = bl(&vi[i]);
    h1.insert(&bv[i]);
  }

  hashtableiterator< hashtable<spi,sphi&> > hi(h1);

  for (hi.reset(); !hi; ++hi)
    cout << hi()->data->id << endl;
}


void hashtabletest::test07()
{
  cout << "Testing Hash Table for Strings" << endl;

  string dict[] = 
  { 
    "abc", "nogo", "python", "moon", "zelda", 
    "release", "light", "matrix" 
  };
  uintc N(sizeof(dict)/sizeof(string));

  cout << "The dictionary is: " << endl;
  cout << print(dict,dict+N) << endl;

  vector< bucketlink<string> > vi(N);
  for (uint i=0; i<N; ++i)
    vi[i] = bucketlink<string>(&dict[i]);

  uintc hashtablesize(70);
  stringhash h(32,8);
  hashtable<string,stringhash&> H(hashtablesize,h);

  for (uint i=0; i<N; ++i)
    H.insert( & vi[i] );

//  bucketlink<string> * cp;

  bool res;

  string k;
  for ( ; k!="exit"; )
  {
    cout << "Delete a string in the hash table" << endl;
    cout << "Enter \"exit\" to terminate." << endl;
    cout << "Enter string k: ";
    cin >> k;

    if (k=="exit")
      break;

    res = H.remove(k);
    cout << SHOW(res) << endl;
    cout << SHOW(H.contains(k)) << endl;
  }

  cout << "The dictionary now is: " << endl;
  hashtableiterator< hashtable<string,stringhash&> > hi(H);
  for (hi.reset(); !hi; ++hi)
    cout << hi()->data->c_str() << " ";
  cout << endl;
}


void hashtabletest::test08()
{
  typedef stringpair<int> spi;
  spi wi[] = 
  { 
    spi("cat",87), spi("sam",840), spi("troghe",92), spi("tx67",89), 
    spi("zsh",11), spi("grey",111), spi("drow",192)
  };
  uintc N=7;
  vector<spi> vi(wi,wi+N);
  typedef bucketlink<spi> bl;
  vector<bl> bv(N);

  typedef stringpairhash<int> sphi;
  sphi sph;
  typedef hashtable<spi,sphi&> htable;
  htable h1(N*2,sph);

  for (uint i=0; i<N; ++i)
  {
    bv[i] = bl(&vi[i]);
    h1.insert(&bv[i]);
  }

  hashtableiterator< htable > hi(h1);

  for (hi.reset(); !hi; ++hi)
    cout << hi()->data->id << ":" << hi()->data->data << " "; 
  cout << endl;

  cout << "Write over the cat element, setting its data to 0." << endl;

  htable::blink x;
  x = h1.insertInverse( stringpair<int>("cat",0) );  
  if (x)
  {
    cout << x->data->id << ":" << x->data->data << endl;
    x->data->data = 0;
  }

  for (hi.reset(); !hi; ++hi)
    cout << hi()->data->id << ":" << hi()->data->data << " "; 
  cout << endl;
}