/************************************************************************
 * File:    table.cpp                                                   *
 *                                                                      *
 * Purpose: Implements tables via hashing.  Start file for CSCI 3510    *
 *          programming assignment.                                     *
 *                                                                      *
 * Author:  Karl Abrahamson                                             *
 *                                                                      *
 * Date:    September 18, 2005                                          *
 ************************************************************************/

#include <cstring>
#include <cstdlib>
#include "table.h"
using namespace std;

//--------------------------------------------------------------//
// REMARK. The annotation PRIVATE indicates that a definition   //
// is not exported; the linker is not even told that it exists. //
// It is the same as the C++ keyword 'static'.                  //
//--------------------------------------------------------------//

#undef PRIVATE
#define PRIVATE static

//**************************************************************//
//                      dupstr                                  //
//**************************************************************//
// dupstr(s) returns a copy of null-terminated string s, in the //
// heap.                                                        //
//**************************************************************//

PRIVATE char* dupstr(char* s)
{
  char* d = new char[strlen(s) + 1];
  strcpy(d, s);
  return d;
}

//**************************************************************//
//                      equalKeys                               //
//**************************************************************//
// equalKeys(k1,k2) is 1 if keys k1 and k2 are the same, and    //
// is 0 if they are different.  				//
//**************************************************************//

PRIVATE int equalKeys(char* k1, char* k2)
{
  return strcmp(k1, k2) == 0;
}


//**************************************************************//
//                      hash                                    //
//**************************************************************//
// hash(key) is the hash value associated with key.             //
//**************************************************************//

PRIVATE long hash(char* key)
{
  //------------------------------------------------------------//
  // This hash function is computed by breaking the string into //
  // four-byte segments, and exclusive-oring the segments       //
  // together.                                                  //
  //------------------------------------------------------------//

  long   h;   // Accumulates hash value.
  long   b;   // Accumulates four bytes of the string.
  char*  s;   // Scans through the string.
  char   c;   // Holds *s, the current character.
  int    i;

  if(key == NULL) return 0;

  h = 0;
  s = key;
  c = *s;

  while(c != 0) 
  {
    //----------------------------------------------------------//
    // Shift four bytes of s into b, but stop at the end of s.  //
    // Then exclusive-or into h.                                //
    //                                                          //
    // Note: x << k is x shifted left by k bits.                //
    //       x ^ y is bitwise the exclusive-or of x and y.      //
    //                                                          //
    // The bytes are taken to be 7 bits.                        //
    //----------------------------------------------------------//

    b = 0;
    i = 0;
    while(i < 4 && c != 0) 
    {
      b = (b << 7) + c;
      c = *(++s);
      i++;
    }
    h = h ^ b;
  }

  return h;
}


//**************************************************************//
//                      hashLocate                              //
//**************************************************************//
// hashLocate(t,key) returns a pointer to the cell in table t   //
// that holds the given key.  If key is not in table t, then    //
// the location that the key should occupy, if it is inserted,  //
// is returned.                                                 //
//                                                              //
//			IMPORTANT NOTE				//
//								//
// It is important to hashLocate that the table have at least   //
// one empty cell.  Otherwise, hashLocate will get into an      //
// infinite loop when searching for something that is not in    //
// the table.                                                   //
//**************************************************************//

PRIVATE HashCellType* hashLocate(HashTableType& tbl, char* key)
{
  HashCellType* cells = tbl.cells;          // The cell array.
  int           size  = HASH_TABLE_SIZE;    // The size of array cells.
  int           currentIndex;               // Possible result index.
  HashCellType* currentCell;                // Possible result pointer.
  
  currentIndex = hash(key) % size;
  currentCell  = cells + currentIndex;

  while(currentCell->key != NULL) 
  {
    //-----------------------------------------------------//
    // If the key is found, return a pointer to this cell. //
    //-----------------------------------------------------//

    if(equalKeys(key, currentCell->key)) return currentCell;

    //----------------------------------------------------------//
    // Move to the next cell, wrapping around if at the end of  //
    // the table.                                               //
    //----------------------------------------------------------//

    currentIndex++;
    if(currentIndex >= size) currentIndex -= size;
    currentCell = cells + currentIndex;
  }

  //---------------------------------------------------------
  // If we get out of the loop, currentCell points to an empty
  // cell where this cell would be inserted, if an insertion
  // is being done.  Return that pointer.
  //---------------------------------------------------------

  return currentCell;
}


//**************************************************************//
//                      hashInsert                              //
//**************************************************************//
// hashInsert(t,key,val) inserts the given key, with associated //
// value val, into table t.                                     //
//                                                              //
// If key is already present in the table, then hashInsert      //
// replaces the value associated with key by val.               //
//                                                              //
// If there is no more room in the table, then hashInsert does  //
// not do the insertion -- it leaves the table unchanged.       //
//**************************************************************//

void hashInsert(HashTableType& tbl, char* key, char* val)
{
  //------------------------------------------------------------//
  // If an insertion would overload the table, just give up,    //
  // and do not do the insertion.  Note that we cannot use      //
  // all of the cells in the table, since hashLocate requires   //
  // that there be at least one empty cell.                     //
  //------------------------------------------------------------//

  if(hashFull(tbl)) return;

  //---------------------------------------//
  // Locate the place to do the insertion. //
  //---------------------------------------//

  HashCellType* insertionPoint = hashLocate(tbl, key);

  //------------------------------------------------------------//
  // If the insertion cell is empty, then install both the      //
  // key and the value.  If the insertion cell is occupied,     //
  // then we are modifying an entry; delete the value and       //
  // change it to the new value.                                //
  //------------------------------------------------------------//

  if(insertionPoint->key == NULL) 
  {
    insertionPoint->key = dupstr(key);
    tbl.load++;
  }
  else 
  {
    delete[] (insertionPoint->val);
  }
  insertionPoint->val = dupstr(val);
}


//**************************************************************//
//                      hashLookup                              //
//**************************************************************//
// If key is in table t, then hashLookup(t,key,val) sets val    //
// to the value associated with key in table t, and returns 1.  //
//                                                              //
// If key is NOT in table t, then hashLookup(t,key,val) returns //
// 0, and does not alter val.                                   //
//**************************************************************//

int hashLookup(HashTableType& tbl, char* key, char*& val)
{
  HashCellType* lookupPoint = hashLocate(tbl, key);

  if(lookupPoint->key != NULL) 
  {
    val = lookupPoint->val;
    return 1;
  }
  else 
  {
    return 0;
  }
}


//**************************************************************//
//                      hashFull                                //
//**************************************************************//
// hashFull(t) returns 1 if table t cannot accept any more      //
// insertions, and 0 if table t can accept more insertions.     //
// If hashFull(t) returns 1, then further insertions into t     //
// will be ignored.                                             //
//**************************************************************//

int hashFull(HashTableType& tbl)
{
  return tbl.load == HASH_TABLE_SIZE - 1;
}


//**************************************************************//
//                      hashMakeEmpty                           //
//**************************************************************//
// hashMakeEmpty(t) removes all items from table t.             //
//**************************************************************//

void hashMakeEmpty(HashTableType& tbl)
{
  int i;

  tbl.load = 0;

  for(i = 0; i < HASH_TABLE_SIZE; i++) 
  {
    //-------------------------------------------------------//
    // If the i-th cell is occupied, then delete its key and //
    // value, and set it to an empty cell by setting its key //
    // to NULL.					             //
    //-------------------------------------------------------//

    HashCellType* thisCell = tbl.cells + i;
    if(thisCell->key != NULL) 
    {
      delete[] (thisCell->key);
      delete[] (thisCell->val);
      thisCell->key = NULL;
    }
  }
}