// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

#include "dictionary.h"

#include "hashdict.h"

// Search for the record with Key K
template <class Key, class Elem, class Comp, class getKey>
bool hashdict<Key, Elem, Comp, getKey>::
hashSearch(const Key& K, Elem& e) const {
  int home;              // Home position for K
  int pos = home = h(K); // Initial posit on probe sequence
  for (int i = 1;
       !Comp::eq(K, getKey::key(HT[pos])) &&
       !Comp::eq(EMPTYKEY, getKey::key(HT[pos])); i++)
    pos = (home + p(K, i)) % M;  // Next on probe sequence
  if (Comp::eq(K, getKey::key(HT[pos]))) {  // Found it
    e = HT[pos];
    return true;
  }
  else return false;      // K not in hash table
}

// Insert e into hash table HT
template <class Key, class Elem, class Comp, class getKey>
bool hashdict<Key, Elem, Comp, getKey>::
hashInsert(const Elem& e) {
  int home;                      // Home position for e
  int pos = home = h(getKey::key(e)); // Init probe sequence
  for (int i=1; !(Comp::eq(EMPTYKEY,
                             getKey::key(HT[pos]))); i++) {
    pos = (home + p(getKey::key(e), i)) % M; // probe
    if (Comp::eq(getKey::key(e), getKey::key(HT[pos])))
      return false;                          // Duplicate
  }
  HT[pos] = e;                   // Insert e
  return true;
}