AbstractHashTable.h

/*  _________________________________________________________________________
 *
 *  UTILIB: A utility library for developing portable C++ codes.
 *  Copyright (c) 2001, Sandia National Laboratories.
 *  This software is distributed under the GNU Lesser General Public License.
 *  For more information, see the README file in the top UTILIB directory.
 *  _________________________________________________________________________
 */

//
// AbstractHashTable.h
//
#ifndef __AbstractHashTable_h
#define __AbstractHashTable_h

#ifdef __GNUC__
#pragma interface
#endif

#ifdef NON_ANSI
#include <iostream.h>
#else
#include <iostream>
using namespace std;
#endif

#ifndef ANSI_HDRS
#include <string.h>
#include <stdio.h>
#else
#include <cstring>
#include <cstdio>
#endif

#include "_math.h"
#include "LinkedList.h"
#include "BasicArray.h"
#include "hash_fn.h"
#include "compare.h"

//
// Externs of a list of primes that are good for hash tables
//
extern int              utilib_num_primes;
extern unsigned long    utilib_prime_list[];


template <class T, class KEY>
class AbstractHashTable
{ 
public:
  typedef size_t size_type;
  typedef ListItem<T*>* hash_element;
  
public:

  explicit AbstractHashTable(const char* nameBuff = "Unnamed");
  explicit AbstractHashTable(size_type initial_size, 
                                        const char* nameBuff = "Unnamed");
  virtual ~AbstractHashTable()
                {
                clear();
                ListItem<T*>::delete_unused();
                }

  bool      empty() const {return (data.len() == 0);}
  operator bool()   const {return (data.len() != 0);}
  int      size()  const {return data.len();}

  virtual T* find(KEY& key) const;

  virtual T* first() const
                {
                if (data.len() == 0) return ((T*)0);
                return data.head()->data(); 
                }

  virtual void add(KEY& key)
                {insert(&key);}
  virtual void add(KEY& key, T*& item)
                {item = insert(&key);}
  virtual void remove(KEY& key, bool& status)
                {
                T* tmp = find(key);
                if (tmp) extract(tmp,status);
                else     status = false;
                }
  virtual void remove(T*& item, bool& status)
                {
                if (!item)
                   status = false;
                else {
                   extract(item,status);
                   item = NULL;
                   }
                }
  virtual void remove(T*& item, KEY& key, bool& status)
                {
                if (!item)
                   status = false;
                else {
                   key = item->key();
                   extract(item,status);
                   item = NULL;
                   }
                }

  virtual T* next(T* item);

  int      write(ostream& os) const;
  int      read(istream& is);
  void clear(); 

  void     statistics(ostream& os);

  bool& ignore_duplicates()
                {return ignore_duplicates_flag;}

  bool using_prime_ht;
  void set_hash_fn(size_type (*hashfn)(const KEY&,size_type))
                {curr_hashfn = hashfn;}
  size_type (*curr_hashfn)(const KEY&,size_type);

 protected:

  virtual size_type hash(KEY& key, size_type table_size) const
        {
        if (curr_hashfn)
           return (*curr_hashfn)(key,table_size);
        else
           return hash_fn(key,table_size);
        }
  virtual T* insert(KEY* key);
  void    insert(T* item, const bool resize_OK=true);

  virtual void    extract(T* item, bool& status);
  void resize(const int newsize=-1);

  LinkedList<T*> data;
  BasicArray<ListItem<T*>*> table;
  BasicArray<int> bucket_size;

  double max_load;
  bool ignore_duplicates_flag;
        
};



template <class T, class KEY>
inline ostream& operator<<(ostream& output, const AbstractHashTable<T,KEY>& 
                                        table)
{ table.write(output); return(output); }
 


template <class T, class KEY>
inline istream& operator>>(istream& input, AbstractHashTable<T,KEY>& table)
{ table.read(input); return(input); }



template <class T, class KEY>
AbstractHashTable<T,KEY>::AbstractHashTable(const char* /*nameBuff*/):
  using_prime_ht(true),
  curr_hashfn(0),
  table(utilib_prime_list[0]),
  bucket_size(utilib_prime_list[0]),
  max_load(3.0),
  ignore_duplicates_flag(true)
{ bucket_size=0; table = (ListItem<T*>*)NULL; }



template <class T, class KEY>
AbstractHashTable<T,KEY>::AbstractHashTable(size_type initial_size, 
                                                const char* /*nameBuff*/) :
  using_prime_ht(true),
  curr_hashfn(0),
  table(initial_size),
  bucket_size(initial_size),
  max_load(3.0),
  ignore_duplicates_flag(true)
{ bucket_size=0; table = (ListItem<T*>*)NULL; }



template <class T, class KEY>
T* AbstractHashTable<T,KEY>::find(KEY& key) const
{
size_type index = hash(key, table.size());
if (bucket_size[index] == 0)
   return ((T*)NULL);

hash_element curr = table[index];

int i=0;
for (; curr && (i<bucket_size[index]); i++) {
  if (curr->data()->compare(key) == 0)
     break;
  curr = data.next(curr);
  }

if ((curr == NULL) || (i == bucket_size[index]))
   return NULL;
return curr->data();
}



//
// This code is virtually identical to 'find', only we return the 
// hash table item for the 'next' element in the 'data' linked list.
//
template <class T, class KEY>
T* AbstractHashTable<T,KEY>::next(T* item)
{
size_type index = hash(item->key(),table.size());
if (bucket_size[index] == 0)
   return ((T*)NULL);

hash_element curr = table[index];

int i=0;
for (; i<bucket_size[index]; i++) {
  if (item->compare(curr->data()->key()) == 0)
     break;
  curr = data.next(curr);
  }

curr = data.next(curr);
if (curr == NULL)
   return NULL;
return curr->data();
}



template <class T, class KEY>
T* AbstractHashTable<T,KEY>::insert(KEY* key)
{
T* item = new T(key);
if (!item)
   ErrAbort("AbstractHashTable<T,KEY>::insert - memory error.");
insert(item);
return item;
}


template <class T, class KEY>
void AbstractHashTable<T,KEY>::insert(T* item, const bool resize_OK)
{
bool resize_flag=false;
size_type index;
if ( !(ignore_duplicates_flag && (find(item->key()) != NULL)) ) {
   index = hash(item->key(),table.size());
   table[index] = data.insert(item, table[index]);
   bucket_size[index]++;
   }
if (resize_OK == false) return;
if ( (resize_flag == true) || 
     (max_load < (((double)data.size())/((double)table.size()))) )
   resize();
}



template <class T, class KEY>
void AbstractHashTable<T,KEY>::extract(T* item, bool& status)
{
hash_element curr;
status = false;

if ((curr = data.find(item)) != NULL) {
   size_type index = hash(item->key(),table.size());
   if (curr == table[index]) {
      if (bucket_size[index] > 1)
         table[index] = data.next(table[index]);
      else
         table[index] = NULL;
      }
   data.remove(curr);
   bucket_size[index]--;
   status = true;
   delete item;
   }
}



template <class T, class KEY>
void AbstractHashTable<T,KEY>::statistics(ostream& os)
{
os << "Hash table size is " << table.size() << endl;
os << "Total number of objects is " << data.size() << endl;
os << "Table load is " << (((double)data.size())/table.size()) << endl;
os << "Largest bucket contains " << max(bucket_size) << " objects" << endl;
os << "Largest bucket is #" << argmax(bucket_size) << endl;
os << "Hash table histogram:" << endl;
char str[128];
sprintf(str,"%10s %10s %10s %10s", "size", "buckets", "objects", "sum-pct");
os << str << endl;

size_type buckets = table.len();
int tnbuckets=0;
for (int j=0; j<16; j++) {
  int nbuckets=0;
  int nobjs=0;
  for (size_type i=0; i < buckets; i++) {
    if (bucket_size[i] == j) {
       nbuckets++;
       nobjs += j;
       }
  }
  tnbuckets+=nobjs;
  sprintf(str,"%10d %10d %10d %10d", j, nbuckets, nobjs, (int)((100.0*tnbuckets)/data.len()) );
  os << str << endl;
  }
{
int nbuckets=0;
int nobjs=0;
for (size_type i=0; i < buckets; i++) {
  if (bucket_size[i] >= 16) {
     nbuckets++;
     nobjs += bucket_size[i];
     }
  }
tnbuckets+=nobjs;
sprintf(str,"%10s %10d %10d %10d", ">15", nbuckets, nobjs, (int)((100.0*tnbuckets)/data.len()) );
os << str << endl;
}
}



template <class T, class KEY>
void AbstractHashTable<T,KEY>::clear()
{
bucket_size = 0;
while (data) {
  T* tmp = data.head()->data();
  delete tmp;
  data.remove(data.head());
  }
table = (ListItem<T*>*)NULL;
}


template <class T, class KEY>
void AbstractHashTable<T,KEY>::resize(const int newsize)
{
int tmp = newsize;
bool flag=true;

while (flag) {
   if (tmp == -1) {
      if (using_prime_ht) {
         int i=0;
         while (i < utilib_num_primes) {
           if (utilib_prime_list[i] > table.size())
              break;
           i++;
           }
         if (utilib_prime_list[i] <= table.size())
            ErrAbort("AbstractHashTable<T,KEY>::resize -- Cannot automatically resize the hashtable any larger.");
         tmp = utilib_prime_list[i];
         }
      else {
         tmp = table.size()*2;
         }
      }
      
   table.resize(tmp);
   table = (ListItem<T*>*)NULL;
   bucket_size.resize(tmp);
   bucket_size = 0;
   
   int ndata = data.size();
   for (int i=0; i<ndata; i++) {
     T* tmp_item=NULL;
     data.remove(tmp_item);
     if (data.size() != (ndata-1))
        ErrAbort("Bug here - First.");
     insert(tmp_item,false);
     if (data.size() != ndata)
        ErrAbort("Bug here - Second.");
     }

   //
   // We might need to loop until the table is big enough, so
   // we set the flag variable for now...
   //
   flag = false;
   }
}


template <class T, class KEY>
int AbstractHashTable<T,KEY>::write(ostream& os) const
{
os << data.size() << endl;

hash_element curr = data.head();
while (curr) {
  curr->data()->write(os);
  os << endl;
  curr = data.next(curr);
  }
  
return OK;
}



//
// BUGGY!!!
//
template <class T, class KEY>
int AbstractHashTable<T,KEY>::read(istream& is)
{
clear();
size_type Size;
is >> Size;
for (size_type i=0; i<Size; i++) {
  T* item;
  item->read(is);
  insert(item);
  }

return OK;
}


#endif