// HashStringToIntTable.C
//
// Written 19 Feb 1996 by Max Hailperin <max@gac.edu>.
//
// This provides a hash-table implementation of StringToIntTable,
// a class of string to integer location mappings; see StringToIntTable.h.
//
// The table is represented as a "dynamically growable" array of pointers to
// "has buckets", each of which is the first in a linked list.  The "growth"
//  is actually done by making twice as big a table and copying the existing
//  entries into the new table, then freeing up the old table's space.
//
// The StringToIntTableRep::grow() member function is left as an exercise.
// Some notes on it:
//   1) The size should double and hence the lgSize, which is the base 2 log
//      of the size, should increase by 1.
//   2) The existing Buckets should be reused, they simply need linking into
//      new chains in the new table.

#include "StringToIntTable.h"
#include <string.h>
#include <assert.h>
#include <limits.h>

static class Bucket{
public:
  Bucket(const char *indexString, int initialValue, Bucket *nextBucket);
  ~Bucket();
  char *string;
  int intLocation;
  Bucket *next;
};

class StringToIntTableRep{
public:
  StringToIntTableRep(int initialValue);
  ~StringToIntTableRep();
  int &operator[](const char *string);
private:
  int initVal;
  unsigned size;
  unsigned lgSize;
  unsigned count;
  Bucket **table;
  void grow();
  Bucket *&findSlot(const char *s); // finds head of appropriate bucket chain
};

static const unsigned lgInitialSize = 8;
static const unsigned initialSize = (1 << lgInitialSize);
static const unsigned long goldenMultiplier = 2654435769UL;
                                              // floor(2^31 * (sqrt(5)-1)) 

Bucket::Bucket(const char *indexString, int initialValue, Bucket *nextBucket){
  string = new char[strlen(indexString)+1];
  strcpy(string, indexString);
  intLocation = initialValue;
  next = nextBucket;
}

Bucket::~Bucket(){
  delete [] string;
  delete next;
}

StringToIntTableRep::StringToIntTableRep(int initialValue){
  initVal = initialValue;
  size = initialSize;
  lgSize = lgInitialSize;
  count = 0;
  table = new Bucket*[size];
  for(int i = 0; i < size; i++)
    table[i] = 0;
}

StringToIntTableRep::~StringToIntTableRep(){
  for(int i = 0; i < size; i++)
    delete table[i];
}

int& StringToIntTableRep::operator[](const char *s){
  Bucket*& bp = findSlot(s);
  for(Bucket* b = bp; b != 0; b = b->next)
    if(strcmp(b->string, s) == 0)
      return b->intLocation;
  Bucket* newBucket = new Bucket(s, initVal, bp);
  bp = newBucket;
  if(++count > size)
    grow();
  return newBucket->intLocation;
}

Bucket*& StringToIntTableRep::findSlot(const char *s){
  /* use hashing to find the right bucket chain */
  const char *p;
  unsigned long h = 0, g;
  for(p = s; *p; p++){  /* this loop does the hashpjw computation */
    h = (h << 4) + *p;  /* see Aho, Sethi, and Ullman p. 436 */
    if((g = h&0xf0000000) != 0)
      h ^= (g | (g >> 24));
  }
  h *= goldenMultiplier; /* these two lines do division hashing by */
  h >>= 32 - lgSize;    /* golden ratio method; see Knuth vol. 3 */
  assert(h < size);
  return table[h];
}

StringToIntTable::StringToIntTable(int initialValue){
  assert(sizeof(unsigned long) * CHAR_BIT == 32);  // check assumption of 32-bitness
  rep = new StringToIntTableRep(initialValue);
}

StringToIntTable::~StringToIntTable(){
  delete rep;
}

int& StringToIntTable::operator[](const char *s){
  return(*rep)[s];
}