#ifndef __hash_t_hh__
#define __hash_t_hh__

#include "hash.hh"

#define template_line \
template <class Vector, class Key, class ReturnData, \
          class HashFunc, class EqualKey, \
          class IsNonExistent, class MakeNonExistent>
#define templates Vector, Key, ReturnData, HashFunc, EqualKey,\
                  IsNonExistent, MakeNonExistent
#define vht vector_hash_table<templates>

template_line
vht::table_iterator vht::find_item_v(const value_type &d) {
  size_type start = hash1v(d);
  size_type i = start;
  size_type h2 = hash2v(d);
  size_type c =  bucket_count();
  for (;;) {
    if (equal_to_(table_[i], d) || is_nonexistent_(table_[i]) ) break;
    i = (i + h2) % c;
    if (i == start) break;
  }
  return table_.begin() + i;
}

template_line
vht::table_iterator vht::find_item_k(const key_type &d) {
  size_type start = hash1k(d);
  size_type i = start;
  size_type h2 = hash2k(d);
  size_type c =  bucket_count();
  for (;;) {
    if (equal_to_(table_[i], d) || is_nonexistent_(table_[i]) ) break;
    i = (i + h2) % c;
    if (i == start) break;
  }
  return table_.begin() + i;
}

template_line
vht::const_table_iterator vht::find_item_k(const key_type &d) const {
  size_type start = hash1k(d);
  size_type i = start;
  size_type h2 = hash2k(d);
  size_type c =  bucket_count();
  for (;;) {
    if (equal_to_(table_[i], d) || is_nonexistent_(table_[i]) ) break;
    i = (i + h2) % c;
    if (i == start) break;
  }
  return table_.begin() + i;
}

template_line
void vht::nonexistent_table() {
  table_iterator table_end = table_.end();
  for (table_iterator i = table_.begin(); i != table_end; ++i) {
    make_nonexistent_(*i);
  }
}
  
template_line
pair<vht::iterator, bool> vht::insert(const vht::value_type &d) {
  table_iterator i = find_item_v(d);
  if (equal_to_(*i,d)) 
    return pair<iterator,bool>(iterator(i,this),false);

  if (load_factor() > .8) {
    resize(bucket_count()*1.5);
    return insert(d);
  } else {
    *i = d;
    ++size_;
  }
  return pair<iterator,bool>(iterator(i,this),true);
}

template_line
bool vht::count(const vht::key_type &d) const {
  const_table_iterator i = find_item_k(d);
  return equal_to_(*i,d);
}

template_line
vht::iterator vht::find(const vht::key_type &d) {
  table_iterator i = find_item_k(d);
  if (equal_to_(*i,d)) 
    return iterator(i,this);
  else
    return end();
}

template_line
vht::const_iterator vht::find(const vht::key_type &d) const {
  const_table_iterator i = find_item_k(d);
  if (equal_to_(*i,d)) 
    return const_iterator(i,this);
  else
    return end();
}

template_line
vht::size_type vht::erase(const vht::key_type &key) {
  table_iterator i = find_item_k(key);
  if (equal_to_(*i, key)) {
    erase(iterator(i,this));
    return 1;
  } else {
    return 0;
  }
}

template_line
void vht::erase(const vht::iterator &p) {
  table_iterator pos = p.pos;  // AER: gave access directly, instead of through a method
  make_nonexistent_(*pos);
  table_iterator table_end = table_.end();

  table_iterator e = pos;
  do {
    ++e;
    if (e == table_end) e = table_.begin();
  } while (!is_nonexistent_(*e));

  table_iterator should_be;
  while (pos != e) {
    if (is_nonexistent_(*pos)) {
      should_be = find_item_v(*pos);
      if (is_nonexistent_(*should_be)) {
	*should_be = *pos;
	make_nonexistent_(*pos);
      }
    }
    ++pos;
    if (pos == table_end) pos = table_.begin();
  }
  --size_;
}

template_line
void vht::swap(vht &other) {
  table_.swap(other.table_);
  size_type temp = size_;
  size_ = other.size_;
  other.size_ = temp;
}

template_line
void vht::resize(size_type i) {
  if (i < 7) {
    i = 7;
  } else {
    size_type j =  ((i - 3)/4)*4 + 3;
    if (j == i) 
      i = j;
    else
      i = j + 4;
    primes p(sqrt(i)+2);
    for (;;) {
      if (i > p.max_num())
	p.resize(sqrt(i)+2);
      if (p.is_prime(i) && p.is_prime(i-2))
	break;
      i += 4;
    }
  }
  vector_hash_table temp(i);
  iterator e = end();
  for (iterator i = begin(); i != e; ++i)
    temp.insert(*i);
  swap(temp);
}

template_line
void vht::recalc_size() {
  size_ = 0;
  for (iterator i = begin(); i != e; ++i, ++_size);
}

#undef template_line
#undef templates
#undef vht

#endif
