#ifndef __PerfectHash__h
#define __PerfectHash__h

#include "HashTable.h"
#include "MyTime.h"

//
// An Almost Perfect Hash Table
//
class PerfectHash : public HashTable {
protected:
  int    N;                             // Size of hash table
  int    s;                             // Size of hash header
  int    first;                         // First free block in data section

// Having these as separate arrays is not cache coherent
  int    *Hp, *Hi, *Hr;                 // Arrays for header information
  Key    *Dk;                           // Arrays for data information
  Object *Dd;

// Used for statistical tracking
  int    insertions,                    // Number of insertions
         collisions,                    // Number of times insertion had collision
         moves,                         // Number of moves involved during collisions
         guesses;                       // Number of times m value is guessed during collision
  MyTime freeslottime;                  // Largest entry in data table used

// Internal functions
  int    H(int m, int i, int k);        // Hash function H(m,i,k)
  int    FreeSlots(int amount);         // Find first block of free slots

public:
  PerfectHash(int size);
  void   Insert(Key key, Object data);
  Object Search(Key key);
  void   PrintStats();
};

#endif // ifdef __PerfectHash__