#ifndef hash_set_h_
#define hash_set_h_

//  File:     hash_set.h
//  Purpose:  Implement the basic function of the set class as a hash
//      table instead of a binary search tree.  This version differs
//      from that of lecture in that the table is a vector of
//      pointers, each being the start of a linked list.  Memory is
//      explicitly allocated and deallocated here instead of
//      implicitly through the list class.  While this makes more work
//      in some functions, it saves substantial allocation cost.

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

template < typename KeyType, typename HashFunc >
class hash_set {
private:

  //  The node type for the doubly-linked lists.  Note that the
  //  hash_value is cached, so that it does not need to be recomputed.
  class HashNode {
  public:
    HashNode( const KeyType& in_key, unsigned int in_hash ) 
      : key(in_key), hash_value(in_hash), next(0), prev(0) {}
    HashNode( ) : next(0), prev(0) {}
    KeyType key;
    unsigned int hash_value;
    HashNode* next; 
    HashNode* prev;
  };

private:
  //  Here are the actual member variables. 

  std::vector< HashNode* > m_table;  //  actual table
  HashFunc m_hash;                   //  hash function
  unsigned int m_size;               //  number of keys stored in the table

public:

  //  Start with the iterator class.  This is defined as a nested
  //  class so that it does not have to be templated separately over
  //  the hash function object type.

  class iterator {
  public:
    friend class hash_set;   // allows access to private variables
  private:
    hash_set* m_hs;          //  pointer to the hash_set object
    int m_index;             //  current index in the hash table
    HashNode* m_list_ptr;    //  ptr to current node in list at the current index

  private:

    //  private constructors for use by the hash_set only
    iterator( hash_set * hs )
      : m_hs(hs), m_index(-1), m_list_ptr(0)
    {}

    iterator( hash_set* hs, int index, HashNode* ptr )
      : m_hs(hs), m_index(index), m_list_ptr(ptr)
    {}

  public:

    //  Two ordinary constructors
    iterator() : m_hs(0), m_index(-1), m_list_ptr(0)  {}

    iterator( iterator const& itr )
      : m_hs(itr.m_hs), m_index(itr.m_index), m_list_ptr(itr.m_list_ptr)
    {}

    iterator&  operator=( const iterator& old )
    {
      m_hs = old.m_hs;
      m_index = old.m_index;
      m_list_ptr = old.m_list_ptr;
      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_ptr->key;
    }

    //  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_list_ptr == rgt.m_list_ptr; }
  
    friend bool operator!= ( const iterator& lft, const iterator& rgt )
    { return lft.m_hs != rgt.m_hs || lft.m_index != rgt.m_index || 
	lft.m_list_ptr != rgt.m_list_ptr; }

    //  pre-increment
    iterator& operator++( ) 
    { 
      this->next();
      return *this;
    }

    //  post-increment is indicated by the dummy int argument
    iterator operator++( int ) 
    {
      iterator temp( *this );
      this->next();
      return temp;
    }

  private:
    //  Find the next entry in the table
    void next()
    {
      //  Checkpoint 2

    }
  };

  /////////////////////////////////
  //  On to the actual hash set  //
  /////////////////////////////////

  //  Constructor for the table set just accepts the size of the
  //  table.  The default constructor for the hash function object is
  //  implicitly used.
  hash_set( unsigned int init_size = 10 )
    : m_table(init_size,0), m_size(0) {}

  
  //  Copy constructor just uses the member function copy
  //  constructors.
  hash_set( const hash_set<KeyType, HashFunc>& old ) 
    : m_size( old.size() )
  {
    this->copy(old);
  }

  ~hash_set()
  {
    this->destroy();
  }

  hash_set& operator=( const hash_set<KeyType,HashFunc>& old )
  {
    if ( this != &old )
      {
	this->destroy();
	this->copy(old);
      }
    return *this;
  }

  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;

    //  Resize if necessary.
    if ( m_size >= LOAD_FRACTION_FOR_RESIZE * m_table.size() )
      this->resize_table( 2*m_table.size()+1 );  // making the new and old sizes relatively prime breaks up clusters

    //  Checkpoint 1
  }


  //  Find the key, using hash function computation, indexing and list
  //  find.
  iterator find( const KeyType& key )
  {
    unsigned int hash_value = m_hash(key);
    unsigned int index = hash_value % m_table.size();
    for ( HashNode* ptr = m_table[index]; ptr; ptr = ptr->next )
      {
	if ( ptr->key == key )
	  return iterator( this, index, ptr );
      }
    return end();
  }


  // 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_size --;
    
    //  Checkpoint 3

  }


  //  Find the first entry in the table and create an associated
  //  iterator.
  iterator begin()
  {
    //  Checkpoint 2


  }
  

  //  Create an end iterator.
  iterator end()
  {
    return iterator( this, -1, 0 );
  }

  
  //  A public print utility.
  void print( std::ostream & ostr )
  {
    for ( unsigned int i=0; i<m_table.size(); ++i )
      {
	ostr << i << ": ";
	for ( HashNode* p = m_table[i]; p; p=p->next )
	  ostr << ' ' << p->key;
	ostr << std::endl;
      }
  }

private:
  void copy( const hash_set<KeyType, HashFunc>& old ) 
  {
    m_table.resize( old.m_table.size(), 0 );
    for ( unsigned int i=0; i<m_table.size(); ++i )
      if ( old.m_table[i] )
	{
	  HashNode* old_p = old.m_table[i];
	  m_table[i] = new HashNode( old_p->key, old_p->hash_value );
	  HashNode* p = m_table[i];
	  old_p = old_p->next;

	  while ( old_p )
	    {
	      p->next = new HashNode( old_p->key, old_p->hash_value );
	      p->next->prev = p;
	      p = p->next;
	      old_p = old_p->next;
	    }
	}
  }

  void destroy()
  {
    for ( unsigned int i=0; i<m_table.size(); ++i )
      {
	HashNode* p = m_table[i];
	while ( p )
	  {
	    HashNode* q = p;
	    p = p->next;
	    delete q;
	  }
      }
  }


  //  resize the table with the same values but a 
  void resize_table( unsigned int new_size )
  {
    //  Checkpoint 3
  }
};
	   
#endif