#ifndef cs2hashset_h_
#define cs2hashset_h_
// The set class as a hash table instead of a binary search tree.  The
// primary external difference between cs2set and cs2hashset is that
// the iterators do not step through the hashset in any meaningful
// order.  It is just the order imposed by the hash function.

#include <iostream>
#include <list>
#include <string>
#include <vector>

// The cs2hashset is templated over both the type of key and the type
// of the hash function, a function object.
template < typename KeyType, typename HashFunc >
class cs2hashset {
private:
  // HASH SET REPRESENTATION
  std::vector< std::list<KeyType> > m_table;  // actual table
  HashFunc m_hash;                            // hash function
  unsigned int m_size;                        // number of keys

  typedef typename std::list<KeyType>::iterator hash_list_itr;
public:

  // The iterator class is defined as a nested class and does not have
  // to be templated separately over the hash function object type.
  class iterator {
  public:
    friend class cs2hashset;   // allows access to private variables
  private:
    // ITERATOR REPRESENTATION
    cs2hashset* m_hs;          
    int m_index;               // current index in the hash table
    hash_list_itr m_list_itr;  // current iterator at the current index

  private:
    // private constructors for use by the cs2hashset only
    iterator(cs2hashset * hs) : m_hs(hs), m_index(-1) {}
    iterator(cs2hashset* hs, int index, hash_list_itr loc)
      : m_hs(hs), m_index(index), m_list_itr(loc) {}

  public:
    // Ordinary constructors & assignment operator
    iterator() : m_hs(0), m_index(-1)  {}
    iterator(iterator const& itr)
      : m_hs(itr.m_hs), m_index(itr.m_index), m_list_itr(itr.m_list_itr) {}
    iterator&  operator=(const iterator& old) {
      m_hs = old.m_hs;
      m_index = old.m_index; 
      m_list_itr = old.m_list_itr;
      return *this;
    }

    // The dereference operator need only worry about the current
    // list iterator, and does not need to check the current index.
    const KeyType& operator*() const { return *m_list_itr; }

    // The comparison operators must account for the list iterators
    // being unassigned at the end.
    friend bool operator== (const iterator& lft, const iterator& rgt)
    { return lft.m_hs == rgt.m_hs && lft.m_index == rgt.m_index && 
	(lft.m_index == -1 || lft.m_list_itr == rgt.m_list_itr); }
    friend bool operator!= (const iterator& lft, const iterator& rgt)
    { return lft.m_hs != rgt.m_hs || lft.m_index != rgt.m_index || 
	(lft.m_index != -1 && lft.m_list_itr != rgt.m_list_itr); }

    // increment and decrement
    iterator& operator++() { 
      this->next();
      return *this;
    }
    iterator operator++(int) {
      iterator temp(*this);
      this->next();
      return temp;
    }
    iterator & operator--() { 
      this->prev();
      return *this;
    }
    iterator operator--(int) {
      iterator temp(*this);
      this->prev();
      return temp;
    }

  private:
    // Find the next entry in the table
    void next() {
      ++ m_list_itr;  // next item in the list

      // If we are at the end of this list
      if (m_list_itr == m_hs->m_table[m_index].end()) {
        // Find the next non-empty list in the table
        for (++m_index; 
             m_index < int(m_hs->m_table.size()) && m_hs->m_table[m_index].empty();
             ++m_index) {}
        
        // If one is found, assign the m_list_itr to the start
        if (m_index != int(m_hs->m_table.size()))
          m_list_itr = m_hs->m_table[m_index].begin();
        
        // Otherwise, we are at the end
        else
          m_index = -1;
      }
    }

    // Find the previous entry in the table
    void prev() {
      // If we aren't at the start of the current list, just decrement
      // the list iterator
      if (m_list_itr != m_hs->m_table[m_index].begin())
	m_list_itr -- ;

      else {
        // Otherwise, back down the table until the previous
        // non-empty list in the table is found
        for (--m_index; m_index >= 0 && m_hs->m_table[m_index].empty(); --m_index) {}

        // Go to the last entry in the list.
        m_list_itr = m_hs->m_table[m_index].begin();
        hash_list_itr p = m_list_itr; ++p;
        for (; p != m_hs->m_table[m_index].end(); ++p, ++m_list_itr) {}
      }
    }
  };

  // =================================================================
  // HASH SET IMPLEMENTATION
  
  // Constructor for the table set just accepts the size of the table.
  // The default constructor for the hash function object is
  // implicitly used.
  cs2hashset(unsigned int init_size = 10) : m_table(init_size), m_size(0) {}
  
  // Copy constructor just uses the member function copy constructors.
  cs2hashset(const cs2hashset<KeyType, HashFunc>& old) 
    : m_table(old.m_table), m_size(old.m_size) {}

  ~cs2hashset() {}

  cs2hashset& operator=(const cs2hashset<KeyType,HashFunc>& old) {
    if (&old != this)
      *this = old;
  }

  unsigned int size() const { return m_size; }

  // Insert the key if it is not already there.
  std::pair< iterator, bool > insert(KeyType const& key) {
    const float LOAD_FRACTION_FOR_RESIZE = 1.25;

    if (m_size >= LOAD_FRACTION_FOR_RESIZE * m_table.size())
      this->resize_table(2*m_table.size()+1);

    // implemented in class

    //  Compute the hash value and then the table index
    unsigned int hash_value = m_hash(key);
    unsigned int index = hash_value % m_table.size();

    //  If the key is not already in the table
    hash_list_itr p = std::find( m_table[index].begin(), m_table[index].end(), key );
    if ( p == m_table[index].end() )
      {
	//  put it in front and construct an iterator
	m_table[index].push_front( key );
	iterator h_itr( this, index, m_table[index].begin() );
	m_size ++ ;
	return std::make_pair( h_itr, true );
      }
    else
      {
	// The key is already there so create an iterator and return false.
	iterator h_itr( this, index, p );
	return std::make_pair( h_itr, false );
      }
 
  }


  // Find the key, using hash function, indexing and list find
  iterator find(const KeyType& key) {
    unsigned int hash_value = m_hash(key);
    unsigned int index = hash_value % m_table.size();
    hash_list_itr p = std::find(m_table[index].begin(),
				 m_table[index].end(), key);
    if (p == m_table[index].end())
      return this->end();
    else
      return iterator(this, index, p);
  }


  // Erase the key 
  int erase(const KeyType& key) {
    // Find the key and use the erase iterator function.
    iterator p = find(key);
    if (p == end())
      return 0;
    else {
      erase(p);
      return 1;
    }
  }

  // Erase at the iterator
  void erase(iterator p) {
    m_table[ p.m_index ].erase(p.m_list_itr);
  }

  // Find the first entry in the table and create an associated iterator
  iterator begin() {
    // Implemented in class

    iterator p( this );
    for ( p.m_index = 0; p.m_index<int(this->m_table.size()); ++ p.m_index )
      {
	if ( !m_table[p.m_index].empty() )
	  {
	    hash_list_itr q = m_table[ p.m_index ].begin();
	    p.m_list_itr = q;
	    return p;
	  }
      }
    p.m_index = -1;
    return p;

  }

  // Create an end iterator.
  iterator end() {
    iterator p(this);
    p.m_index = -1;
    return p;
  }
  
  // A public print utility.
  void print(std::ostream & ostr) {
    for (unsigned int i=0; i<m_table.size(); ++i) {
      ostr << i << ": ";
      for (hash_list_itr p = m_table[i].begin(); p != m_table[i].end(); ++p)
        ostr << ' ' << *p;
      ostr << std::endl;
    }
  }

private:
  // resize the table with the same values but a 
  void resize_table(unsigned int new_size) {
    // Implemented in class

    std::vector< std::list<KeyType> > old_table = m_table;
    m_table.clear();
    m_table.resize( new_size );

    for ( unsigned int i=0; i<old_table.size(); ++i )
      for ( hash_list_itr p = old_table[i].begin(); p!=old_table[i].end(); ++p )
	{
	  unsigned int index = m_hash( *p ) % new_size;
	  m_table[index].push_front( *p );
	}

  }

};
#endif