testLinHash.C

Go to the documentation of this file.

 
/* Aleph-w
 
     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9c
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2018 Leandro Rabindranath Leon 
 
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
 
  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.
 
  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
 
# include <iostream>
# include <string>
# include <ctime>
# include <cstdlib>
# include <aleph.H>
# include <tpl_linHash.H>
 
/* TODO:
   1-. Test del() del iterador
 
*/
 
# include <cassert>
using namespace std;
 
# include <cassert>
using namespace Aleph;
 
struct Entry : public LinearHashTableVtl<unsigned long>::Bucket
{
  unsigned long val;
 
  Entry(unsigned long k, unsigned long v) 
    : LinearHashTableVtl<unsigned long>::Bucket(k), val( v )
    {
      /* EMPTY */
    }
};
 
void print_stats( LinearHashTableVtl<unsigned long> & table)
{
  cout << "Capacity  = " << table.capacity() << endl
       << "size       = " << table.size() << endl
       << "busy slots = " << table.busy_slots() << endl
       << "expansions = " << table.expansions() << endl
       << "alpha      = " << 1.0*table.size()/table.capacity() << endl;
}
 
int main(int argc, char *argv[])
{ 
  const unsigned long numNodes = 10000;
 
  unsigned long  i, n = numNodes;
 
  unsigned long  value;
 
  unsigned int t = std::time(NULL);
 
  try 
    {
      if (argc > 1)
  n = std::stoul(argv[1]);
 
      if (argc > 2)
  t = std::stoul(argv[2]);
    }
  catch (...)
    {
      // ignore
    }
 
  if (n <= 0)
    {
      cout << "n must be positive" << endl;
      return 1;
    }
 
  DynArray<unsigned int> keys(n);
 
  cout << "testDynamicHash " << n << " " << t << endl;
 
  srand(t);
 
  LinearHashTableVtl<unsigned long> table;
  Entry* bucket;
 
  print_stats(table);
 
  cout << "Inserting..." << endl;
 
  for (i = 0; i < n; i++)
    {
      do
  {
    value = keys[i] = (unsigned long)  (10*n*(rand() /(RAND_MAX + 1.0)));
  }
      while (table.search(value) != NULL);    
 
      cout << value << " ";
 
      bucket = new Entry (keys[i], i);
      table.insert(bucket);
    }
 
  cout << endl;
 
  table.print();
  
  print_stats(table);
 
  cout << endl << "Searching..." << endl;
 
  for (i = 0; i < n; i++)
    {
      value = keys[i];
      bucket = static_cast<Entry*>(table.search(value));
      if (bucket == NULL)
  {
    cout << endl << "Error key " << keys[i] << " not found" <<  endl;
    abort();
  }
    }
 
  cout << "Testing iterator" << endl;
 
  {
    long count = 0;
    for (LinearHashTableVtl<unsigned long>::Iterator it(table); it.has_curr();
   it.next(), ++count)
      cout << it.get_curr()->get_key() << " ";
    if (count != table.size())
      AH_ERROR("Test not passed count = %ld != %ld", count, table.size());
  }
  
  cout << endl << "testing deleting ..." << endl;
 
  try
    {
      for (i = 0; i < n; i++)
  {
    value = keys[i];
    bucket = static_cast<Entry*>(table.search(value));
    if (bucket != NULL)
      {
        table.remove(bucket);
        delete bucket;
      }
    else
      AH_ERROR("%u th key %u not found\n", (int) i, (int) keys[i]);
  }
      print_stats(table);
    }
  catch (exception& exc)
    {
      cout << exc.what() << " exception has been thrown" << endl;       
    }
  catch (...)
    {
      cout << " unknown exception has been thrown" << endl; 
    }
 
  assert(table.size() == 0);  
}