//[c]dictionary.cpp - a simple hashtable class
//[c]
//[l]:	Header File:dictionary.h
//[c]
//[of]:	Includes
//[c]
#include <stdio.h>
//[c]
#include "dictionary.h"
//[cf]
//[of]:	Constants
//[c]
#define default_size   10
#define max(x, y) (((x)>(y))?(x):(y))
//[cf]
//[of]:	Private
//[c]
//[of]:	increaseTally()
//[c]increase the counter of items
//[c]grow the array if more than 75% of slots are used
//[c]
void Dictionary::increaseTally()
{
  tally++;

  if( 4*tally>3*size ) resize(size*3/2);
}
//[cf]
//[of]:	decreaseTally()
//[c]decrease the counter of items
//[c]reduce the array if less than 30% of slots are used
//[c]
void Dictionary::decreaseTally()
{
  tally--;

  if( 3*tally<size ) resize(max(default_size, 2*size/3));
}
//[cf]
//[of]:	resize(size)
//[c]Resize the list of associations
//[c]
void Dictionary::resize(int s)
{
  int i;
  int c = 0;
  Association* a = new Association[s];
  for(i=0; i<s; i++) a[i].key = NULL;

  for(i=0; i<size; i++)
  {
    if( notEmpty(i) )
    {
      int count = 1;
      int location = ((unsigned int)hash(key(i))) % s;
      while( a[location].key!=NULL )
      {
        location++;
        if( location==s ) location=0;
        count++;
      }
      a[location].key   = key(i);
      a[location].value = value(i);
      c = max(count, c);
    }
  }

  delete associations;

  collisions   = c;
  associations = a;
  size         = s;
}
//[cf]
//[of]:	fillUp(current)
//[c]Fix collisions after freeing a slot
//[c]
void Dictionary::fillUp(int current)
{
  while( notEmpty(current) )
  {
    int best = slot(key(current));
    int count = 0;

    if( current!=best )
      while( notEmpty(best) ) { best++; if( best==size ) best=0; count++; }

    if( current!=best )
    {
      setKey   (best, key(current));
      setValue (best, value(current));
      clear(current);

      collisions = max(count, collisions);
    }

    current++; if( current==size ) current=0;
  }
}
//[cf]
//[c]
//[of]:	setKey(index, key)
//[c]
void Dictionary::setKey(int i, void* k)
{
  associations[i].key = k;
}
//[cf]
//[of]:	setValue(index, value)
//[c]
void Dictionary::setValue(int i, void* v)
{
  associations[i].value = v;
}
//[cf]
//[of]:	clear(index)
//[c]
void Dictionary::clear(int i)
{
  associations[i].key = NULL;
}
//[cf]
//[cf]
//[c]
//[c]Initialize - Release
//[c]
//[of]:	Dictionary()
//[c]Initializes a new hastable
//[c]
Dictionary::Dictionary()
{
  collisions   = 0;
  tally        = 0;
  size         = default_size;
  associations = new Association[default_size];

  for(int i=0; i<size; i++) clear(i);
}
//[cf]
//[of]:	~Dictionary()
//[c]Deletes an hashtable
//[c]
Dictionary::~Dictionary()
{
  // it is the responsibility of the sub-class to free the keys and values
  delete associations;
}
//[cf]
//[c]
//[c]Testing
//[c]
//[of]:	isEmpty() const
//[c]Returns true if the hashtable is empty
//[c]
bool Dictionary::isEmpty () const 
{
  return tally==0;
}
//[cf]
//[of]:	notEmpty() const
//[c]Returns true if the hashtable contains one or more elements
//[c]
bool Dictionary::notEmpty() const 
{ 
  return tally!=0; 
}
//[cf]
//[c]
//[c]Direct Accessors
//[c]
//[of]:	getSize() const
//[c]Returns the total number of slots currently allocated.
//[c]
//[c]	Use this method to enumerate all slots in conjunction with
//[c]	isEmpty() to keep only non empty slots.
//[c]
int Dictionary::getSize() const 
{ 
  return size; 
}
//[cf]
//[c]
//[of]:	key(index) const
//[c]
void* Dictionary::key(int i) const
{
  return associations[i].key;
}
//[cf]
//[of]:	value((index) const
//[c]
void* Dictionary::value(int i) const
{
  return associations[i].value;
}
//[cf]
//[of]:	isEmpty(index) const
//[c]Returns true if the slot is not used
//[c]
bool Dictionary::isEmpty(int i) const
{
  return associations[i].key == NULL;
}
//[cf]
//[of]:	notEmpty(index) const
//[c]Returns true if the slot is used
//[c]
bool Dictionary::notEmpty(int i) const
{
  return associations[i].key != NULL;
}
//[cf]
//[c]
//[c]Accessing
//[c]
//[of]:	value(key) const
//[c]Returns the value for the given key
//[c]
//[c]	Note: there must be at least one free slot.
//[c]
void* Dictionary::value(void* k) const
{
  int location = slot(k);
  int count    = collisions;

  while( count>0 && notEmpty(location) )
  {
    if( match(key(location), k) ) return value(location);

    location++;
    if( location==size ) location = 0;
    count--;
  }

  return NULL;
}
//[cf]
//[c]
//[c]Adding - Removing
//[c]
//[of]:	add(key, value)
//[c]Puts a value
//[c]
//[c]	There must be at least one free slot.
//[c]	If there were already a value at this slot, the old value is returned.
//[c]	In such a case, the returned value, and the passed key are no more
//[c]	referenced by the dictionary, it is the responsibility of the sub-class
//[c]	to free them.
//[c]
void* Dictionary::add(void* k, void* v)
{
  int location = slot(k);
  int count    = 1;

  while( true )
  {
    if( notEmpty(location) )
    {
      if( match(k, key(location)) )
      {
        void* old = value(location);
        setValue(location, v);
        return old;
      }
      else
      {
        location++;
        if( location==size ) location = 0;
        count++;
      }
    }
    else
    {
      setKey   (location, k);
      setValue (location, v);
      collisions = max(count, collisions);
      increaseTally();
      return NULL;
    }
  }

  // never happens, but make compilers happy
  return NULL;
}
//[cf]
//[of]:	remove (key)
//[c]Removes an item
//[c]
//[c]	Returns the item for the given key or nil if not found.
//[c]
void Dictionary::remove(void* k)
{
  int location = slot(k);
  int count    = collisions;

  while( count>0 && notEmpty(location) )
  {
    if( match(k, key(location)) )
    {
      clear(location);
      location++;
      if( location==size ) location=0;
      fillUp(location);  // useless if we are going to resize
      decreaseTally();
      return;
    }

    location++;
    if( location==size ) location=0;
    count--;
  }

  return;
}
//[cf]