#ifndef __hash_hh__
#define __hash_hh__

#include <iterator>
#include <functional>
#include <utility>

#include "prime.hh"

//
// This hash table is implemnted as a Open Address Hash Table
// which uses a Vector like object to store its data.  So
// it might even be considered an adapter
//

////////////////////////////////////////////////////////
//                                                    //
//          Vector Hash Table Interator               //
//                                                    //
////////////////////////////////////////////////////////

template <class HashTable, class ReturnData, class Iterator>
class vht_iterator : public bidirectional_iterator
                     <
                       ReturnData,
                       typename HashTable::difference_type
                     >
{
  friend bool operator==<> (const vht_iterator&, const vht_iterator&);
  friend bool operator!=<> (const vht_iterator&, const vht_iterator&);
public: // AER: made public, instead of private
  Iterator  pos;
  HashTable *hash_table; 
  typedef typename HashTable::value_type value_type;
public:
  Iterator table_iterator() const {return pos;}
public:
  vht_iterator(Iterator p, HashTable *ht) : pos(p), hash_table(ht) {}
  vht_iterator(Iterator p, HashTable *ht, bool) 
    : pos(p), hash_table(ht) 
    {
      while (pos != hash_table->table().end()
	     && hash_table->is_nonexistent_func()(*pos) )
	++pos;
    }

  ReturnData& operator* () {return *pos;}
  const ReturnData& operator* () const {return *pos;}

  vht_iterator& operator++ () {
    ++pos;
    for (;;) {
      if (pos == hash_table->table().end()) break;
      if (!(hash_table->is_nonexistent_func())(*pos)) break;
      ++pos;
    }
    return *this;
  }
  vht_iterator operator++ (int) {
    vht_iterator temp = *this; 
    operator++();
    return temp;
  }

  vht_iterator& operator-- () {
      --pos;
    for (;;) {
      if (pos < hash_table->table().begin()) break;
      if (!(hash_table->is_nonexistent_func())(*pos)) break;
      --pos;
    }
    return *this;
  }
  vht_iterator operator-- (int) {
    vht_iterator temp = *this; 
    operator--();
    return temp;
  }
};

template <class T, class R, class I>
  inline
  bool operator== (const vht_iterator<T,R,I> &rhs, const vht_iterator<T,R,I> &lhs)
{
  return rhs.pos == lhs.pos;
}
		 
template <class T, class R, class I>
  inline
  bool operator!= (const vht_iterator<T,R,I> &rhs, const vht_iterator<T,R,I> &lhs)
{
  return rhs.pos != lhs.pos;
}

////////////////////////////////////////////////////////
//                                                    //
//                Vector Hash Table                   //
//                                                    //
////////////////////////////////////////////////////////

#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
class vector_hash_table {
public:
  typedef Vector                           vector_type;
  typedef typename Vector::value_type      value_type;
  typedef typename Vector::size_type       size_type;
  typedef typename Vector::difference_type difference_type;

  typedef typename Vector::pointer         pointer;
  typedef typename Vector::reference       reference;
  typedef typename Vector::const_reference const_reference;

  typedef Key                              key_type;
  typedef HashFunc                         hasher;
  typedef EqualKey                         key_equal;
  typedef IsNonExistent                    is_nonexistent;
  typedef MakeNonExistent                  make_nonexistent;
private:
    IsNonExistent is_nonexistent_;
  MakeNonExistent make_nonexistent_;
  HashFunc    hash;
  EqualKey    equal_to_;
public:
  const is_nonexistent& is_nonexistent_func() const {return is_nonexistent_;}
  const make_nonexistent& make_nonexistent_func() const {return make_nonexistent_;}
  const hasher&       hash_funct() const  {return hash;}
  const key_equal&    key_eq() const      {return equal_to_;}
public:
  typedef Vector table_type;
  // These public functions are very danguages and should be used with
  // great care as the modofy the internal structure of the object

        table_type& table()       {return table_;}
  const table_type& table() const {return table_;}
  void recalc_size();
  void set_size(size_type s) {size_  = s;} 

private:
  Vector      table_;
  size_type   size_;

  typedef typename Vector::iterator       table_iterator;
  typedef typename Vector::const_iterator const_table_iterator;
  
  size_type hash1k(const key_type &d) const {return hash(d) % bucket_count();}
  size_type hash1v(const value_type &d) const {return hash(d) % bucket_count();}
  size_type hash2k(const key_type &d) const 
    {return 1 + (hash(d) % (bucket_count() - 2));}
  size_type hash2v(const value_type &d) const 
    {return 1 + (hash(d) % (bucket_count() - 2));}

public:
  typedef vht_iterator<vector_hash_table, ReturnData, table_iterator>       iterator;
  typedef vht_iterator<const vector_hash_table, const ReturnData, const_table_iterator>
                                                                       const_iterator;
  typedef 
    reverse_bidirectional_iterator<iterator, ReturnData, 
                                   ReturnData&, difference_type> 
    reverse_iterator;
  typedef
    reverse_bidirectional_iterator<const_iterator, const ReturnData,
                                   const ReturnData&, difference_type> 
    const_reverse_iterator;

private:
  table_iterator find_item_v(const value_type &d);
  const_table_iterator find_item_k(const key_type &d) const;
  table_iterator find_item_k(const key_type &d);
  void nonexistent_table();
  
public:
  vector_hash_table() : table_(7), size_(0) 
    {nonexistent_table();}
  vector_hash_table(size_type i) 
    : table_(i < 7 ? 7 : i), size_(0) {nonexistent_table();}
  
 
  iterator begin() {return iterator(table_.begin(), this, 1);}
  iterator end()   {return iterator(table_.end(), this);}
  const_iterator begin() const {return const_iterator(table_.begin(), this, 1);}
  const_iterator end()   const {return const_iterator(table_.end(), this);}

  reverse_iterator rbegin() {return reverse_iterator(end());}
  reverse_iterator rend()   {return reverse_iterator(begin());}
  const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
  const_reverse_iterator rend()   const {return const_reverse_iterator(begin());}

  pair<iterator, bool> insert(const value_type &);
  bool count(const key_type &) const;

        iterator find(const key_type&);
  const_iterator find(const key_type&) const;
  
  size_type erase(const key_type &key);
  void erase(const iterator &p);
  
  size_type size() const {return size_;}
  bool      empty() const {return !size_;}

  void swap(vector_hash_table &);
  void resize(size_type);
  size_type bucket_count() const {return table_.size();}
  double load_factor() const {return static_cast<double>(size())/bucket_count();}
};

#undef template_line
#undef templates

////////////////////////////////////////////////////////
//                                                    //
//             Pair Adapter Functions                 //
//                                                    //
////////////////////////////////////////////////////////

template <class Pair, class EqualTo>
class pair_equal_to_with_key {
  EqualTo  equal_to_;
public:
  typedef bool                      result_type;
  typedef Pair                      pair_type;
  typedef typename Pair::first_type key_type;
  typedef EqualTo                   key_equal;

  pair_equal_to_with_key() {}
  pair_equal_to_with_key(const EqualTo &et) : equal_to_(et) {}
  
  bool operator() (const pair_type& rhs, const pair_type& lhs) const 
    {return equal_to_(rhs.first,lhs.first);}
  bool operator() (const pair_type& rhs, const key_type& lhs) const
    {return equal_to_(rhs.first,lhs);}
  bool operator() (const key_type& rhs, const pair_type& lhs) const
    {return equal_to_(rhs,lhs.first);}
};


template <class Pair, class Func>
class unary_on_first {
  Func func;
public:
  typedef Pair                         pair_type;
  typedef Func                         func_type;
  typedef typename Func::result_type   result_type;
  typedef typename Func::argument_type argument_type;

  unary_on_first() {}
  unary_on_first(const Func &f) : func(f) {}

  result_type operator() (argument_type p) const {return func(p);}
  result_type operator() (pair_type p)     const {return func(p.first);}
};

template <class Pair1, class Pair2, class Func>
class binary_on_first {
  Func func;

public:

  typedef Pair1                               first_pair_type;
  typedef Pair2                               second_pair_type;
  typedef Func                                func_type;
  typedef typename Func::result_type          result_type;
  typedef typename Func::first_argument_type  first_argument_type;
  typedef typename Func::second_argument_type second_argument_type;

  binary_on_first() {}
  binary_on_first(const Func &f) : func(f) {}

  result_type operator() (first_argument_type p1, second_argument_type p2) const
    {return func(p1,p2);}
  result_type operator() (first_pair_type p1, second_argument_type p2) const
    {return func(p1.first,p2);}
  result_type operator() (first_argument_type p1, second_pair_type p2) const
    {return func(p1,p2.first);}
  result_type operator() (first_pair_type p1, second_pair_type p2) const
    {return func(p1.first,p2.first);}
};

////////////////////////////////////////////////////////
//                                                    //
//                  vector_hash_set                   //
//                                                    //
////////////////////////////////////////////////////////


#define htable  vector_hash_table \
  < Vector, Value, const Value, \
    HashFunc, EqualKey, \
    IsNonExistent, MakeNonExistent \
  >

template <class Value, class HashFunc, 
          class IsNonExistent, class MakeNonExistent,
          class EqualKey = equal_to<Value>, 
          class Vector = vector<Value> >
class vector_hash_set : public htable
{
private:
  typedef htable derived;
public:
  vector_hash_set() : derived() {}
  vector_hash_set(size_type i) : derived(i) {}
};


////////////////////////////////////////////////////////
//                                                    //
//                  vector_hash_map                   //
//                                                    //
////////////////////////////////////////////////////////


#define ppair pair<Key, Data>
#define cpair pair<const Key, Data>

#undef  htable
#define htable  vector_hash_table \
  <Vector, Key, ppair, \
   unary_on_first<const ppair&, HashFunc>,\
   pair_equal_to_with_key<ppair, EqualKey>,\
   unary_on_first<const ppair&, IsNonExistent>, \
   unary_on_first<ppair, MakeNonExistent> \
  >

template <class Key, class Data, class HashFunc, 
          class IsNonExistent, class MakeNonExistent,
          class EqualKey = equal_to< Key >, 
          class Vector = vector< ppair >
         >
class vector_hash_map : public htable
{
private:
  typedef htable derived;
public:
  vector_hash_map() : derived() {}
  vector_hash_map(size_type i) : derived(i) {}
  typedef Data data_type;
  data_type& operator[] (const key_type& k) 
    {return (*((insert(typename vector_hash_map::value_type(k, data_type()))).first)).second;}
};

#undef ppair
#undef cpair
#undef htable

#endif
