/************************************************************************
 * File:    table.h                                                     *
 *                                                                      *
 * Purpose: Implements tables.  Start file for CSCI 3510                *
 *          programming assignment.                                     *
 *                                                                      *
 * Author:  Karl Abrahamson                                             *
 *                                                                      *
 * Date:    January 27, 1998                                            *
 ************************************************************************/

#ifndef TABLE_H
#define TABLE_H

#include <stdio.h>

//--------------------------------------------------------------//
// This header file describes hash tables as provided by        //
// table.cc.  See that file for a discussion of tables.         //
//--------------------------------------------------------------//

//--------------------------------------------------------------//
// HASH_TABLE_SIZE is one larger than the maximum number of     //
// keys that can be stored in the hash table.                   //
//--------------------------------------------------------------//

#define HASH_TABLE_SIZE 100

//------------------------------------------------------//
// HashKeyType is the type of the keys.                 //
// HashValType is the type of the associated values.    //
//------------------------------------------------------//

typedef char*     HashKeyType;
typedef char*     HashValueType;

//------------------------------------------------------//
// NullKey is a key that is not used for real keys,     //
// and can be used to indicate an empty cell.           //
//------------------------------------------------------//

#define NullKey NULL

struct HashCellType {
  HashKeyType   key;
  HashValueType val;
};

typedef HashCellType* HashCellPtrType;

struct HashTableType {
  int             load;
  HashCellPtrType cells;

  // When a table is created, allocate memory for it, and
  // set all of the key fields to NullKey.

  HashTableType()
  {
    int i;

    load  = 0;
    cells = new HashCellType[HASH_TABLE_SIZE];
    for(i = 0; i < HASH_TABLE_SIZE; i++) {
      cells[i].key = NullKey;
    }
  }
};

//--------------------------------------------------------------//
//              Function Prototypes                             //
//--------------------------------------------------------------//

//--------------------------------------------------------------//
// 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, HashKeyType key, HashValueType val);

//--------------------------------------------------------------//
// 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, HashKeyType key, HashValueType& val);

//--------------------------------------------------------------//
// hashFull(t) returns 1 if table t is full (and hence cannot   //
// accept any more insertions), and 0 if table t is not full.   //
//--------------------------------------------------------------//

int hashFull(HashTableType& tbl);

//--------------------------------------------------------------//
// hashEmpty(t) removes all items from table t.                 //
//--------------------------------------------------------------//

void hashEmpty(HashTableType& tbl);

#endif // defined TABLE_H