#ifndef HASHTABLE_MANAGER_STDKEYS_H
#define HASHTABLE_MANAGER_STDKEYS_H

#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <numeric>
#ifdef QE //#ifdef added by Ajith John on 24 July 2013
#include <set>
#endif //#ifdef added by Ajith John on 24 July 2013 ends here

using namespace std;


//the hashtable manager has no way of comparing the values stored. It can compare only keys, since the keys are standard.
//The keys generated by the client must be unique....

typedef unsigned long long int t_index;

/**
 * Define some primes.
 * Primes are the heart of hash functions. Various hash functions use various primes from this list.
 *
 * IMPORTANT: Size of the hashtable MUST be a prime
 */
#define PRIME0 1201
#define PRIME1 9901
#define PRIME2 93719

/**
 * This class represents the Status of HashTable operations.
 * It provides public method success(), that should be used to check the status of a operation on HashTable.
 * It also provides getValue() method which returns the Value associated with the result of operation. If the success() method returns a false, then the value contains invalid content.
 *
 * This class is outside the t_HashTable class in order to allow its instantiation by clients of hashtable.
 */
template <class t_Value>
class t_HTStatusValue
{
 private:
  t_Value m_value;
  bool m_isSuccess;
 public:
  bool success(){ return m_isSuccess;}
  t_Value getValue(){ return m_value;}
  t_HTStatusValue (bool status_to_update, t_Value v):m_isSuccess(status_to_update), m_value(v){}
};


template<typename Key, typename Value>
class HashTableIterator;







/*
 * This class depicts the whole hashtable
 *
 * The HashTable public API
 *
 * Create A HashTable:
 * t_HashTable <t_Key, t_Value> hashtable_object

 * Insertion:
 * t_HTStatusValue<t_Value> result = hashtable_insert(key, value);
 * Return Value:
 * On Success, result.success()=true; result.getValue()=the value just inserted
 * On Failure, result.success()=false; result.getValue()=an invalid value
 *
 *
 * Deletion:
 * t_HTStatusValue<t_Value> result = hashtable_delete(key);
 * On Success, result.success()=true; result.getValue()=the deleted value associated with the key
 * On Failure, result.success()=false; result.getValue()= an invalid value
 *
 *
 * Search:
 * t_HTStatusValue<t_Value> result = hashtable_search(t_Key key)
 * On Success, result.success()=true; result.getValue()=the value associated with the key being searched
 * On Failure, result.success()=false; result.getValue()=an invalid value
 *
 * 
 */


template <class t_Key, class t_Value>
  class t_HashTable
{

 private:
  //Define necessary inner classes
  //These classes form components of the hashtable
     public:
  class t_HashTableEntry
  {
  /**
   * The individual entry of a hashtable. Each entry stores key and value.
   * A linked list of t_HashTableEntry is used to resolve the hash collisions, therefore contains a pointer t_HashTableEntry* next
   */
  private:
    t_Key m_key;
    t_Value m_value;        //The Value to store in the table
  protected:
      
    t_HashTableEntry(const t_HashTableEntry &e):
    first(m_key), second(m_value), m_key(e.m_key), m_value(e.m_value){}
    t_HashTableEntry& operator=(const t_HashTableEntry& e)
    {m_key = e.m_key; m_value = e.m_value; return *this;}
    
  public:
      const t_Key& first;
      t_Value& second;
    t_HashTableEntry *m_next; //use it to form linked list in case of collisions
    t_Key getKey();
    t_Value getValue();
    
    t_HashTableEntry();
    t_HashTableEntry (const t_Value& value_of_entry, const t_Key& key_of_entry);
    
    void printHashTableEntry();
    //to gain access to m_key and m_value which can be accessed by constant references instead of temporaries
  template<typename Key, typename Value>
  friend class HashTableIterator;
  template<typename Key, typename Value>
  friend class t_HashTable;
  };



  private:



  /**
   * We need a linked list of t_HashTableEntry in order to take care of
   * collision while hashing. 
   * t_HashTableEntryListHeader is the type of the header of such a linked list.
   * It contains a pointer t_HashTableEntry * next, that points to the list.
   * An array of t_HashTableEntryListHeader (of length SIZE) forms the hashtable.
   */
  class t_HashTableEntryListHeader
  {
  public:
    t_HashTableEntry *m_next;
    t_HashTableEntryListHeader();
  
  };

 private:

  static const int m_SIZE = PRIME2; //This is static in order to initialize it



  //In general, class attributes cannot be initialized!!!

  vector <t_HashTableEntryListHeader> m_Buckets;


  int m_nKeysStored;     //This field contains the actual number of keys stored
  int m_nCollisions;  //Current count of the number of collisions over the entire hashtable
  int m_nBucketsUsed;    //Number of buckets used. Different from number of keys stored.



  /**
   * Hash functions for standard key types.
   */
  t_index Hash(const string& string_to_hash);
#ifdef KEEP_INT_HASH
  t_index Hash(int integer_to_hash);
#endif
  t_index Hash(unsigned long long);
  
  bool CompareKeys(const string& key1, const string& key2);
  bool CompareKeys(const int key1, const int key2);

  bool insertEntryInList(const t_index& index,const t_Value& value_to_insert, const t_Key& key);

  bool freeDynamicallyAllocatedMemory();

  //Public API of the hashtable
 public:

  /**
   * Constructor for the hashtable
   * The vector of buckets is initially empty. The vector is resized to m_SIZE to create m_SIZE number of buckets.
   *
   *
   *
   */
  t_HashTable();
  t_HashTable(int size);
  ~t_HashTable();
  bool clear();
  t_HTStatusValue<t_Value> hashtable_insert(const t_Key& key, const t_Value& val);
 

  /**
   *The deletion of a value takes a reference to key. However, we cannot delete it directly. Need to search...
   *
   **/

  t_HTStatusValue<t_Value> hashtable_delete(const t_Key& key);
  t_HTStatusValue<t_Value> hashtable_search(const t_Key& key);
   
  /**
   * This function prints the hashtable, but only when standard values are used. Not otherwise.
   *
   *
   */

  void printHashTableKeys();
  /* Statistics collecting functions */

  int getMaximumSizeOfHashTable();

  float getLoadFactor();

  int getStoredKeysCount();
  int getCountOfCollisions();
  vector<unsigned> getCollisionCounts()const;
  
  unsigned int getAverageCollisionsPerBucket()
  {
      unsigned sum=0;
      vector<unsigned> coll = getCollisionCounts();
      sum = std::accumulate(coll.begin(), coll.end(), sum);
      return sum/coll.size();
  }
  
  unsigned getMaxNumberOfCollisionsPerBucket()
  {
      vector<unsigned> coll = getCollisionCounts();
      return *std::max_element(coll.begin(), coll.end());
  }
  
  unsigned getMedianOfNumberOfCollisionsPerBucket()
  {
      vector<unsigned> coll = getCollisionCounts();
      std::partial_sort(coll.begin(), coll.begin()+coll.size()/2+1, coll.end());
      return coll.at(coll.size()/2);
  }

  int getNumberOfBucketsUsed();
  
  template<typename Key, typename Value>
  friend class HashTableIterator;

  
  t_Value& operator[](const t_Key& key);
  typedef HashTableIterator<t_Key, t_Value> iterator;
  typedef t_HashTableEntry value_type;
  iterator find(const t_Key& key);
  iterator begin(){return HashTableIterator<t_Key,t_Value>(*this);}
  iterator end(){return HashTableIterator<t_Key,t_Value>(*this, -1,0,true);}
  unsigned size(){return getStoredKeysCount();}
  bool empty(){ return size() == 0;}
};

template<typename Key, typename Value>
class HashTableIterator
{
    protected:
        t_HashTable<Key, Value> *hash;
         int currentBucketIndex;
         typedef typename t_HashTable<Key, Value>::t_HashTableEntry* pEntry;
        typename t_HashTable<Key, Value>::t_HashTableEntry* currentEntry;
        bool isEnd;
    public:
        typedef typename t_HashTable<Key, Value>::t_HashTableEntry value_type;
        
        HashTableIterator(t_HashTable<Key,Value> &h, int cbe=-1, typename t_HashTable<Key, Value>::t_HashTableEntry* p=0,bool ie=false):
        hash(&h), currentBucketIndex(cbe),currentEntry(p), isEnd(ie)
        { if(!isEnd && cbe==-1 && p==0)gotoFirst();}
        
        bool operator==(HashTableIterator &hti)
        {
            if(isEnd && hti.isEnd)
                return true;
            return hash == hti.hash && currentBucketIndex == hti.currentBucketIndex &&
                    currentEntry == hti.currentEntry;
        }
        
        bool gotoFirst(){
            currentBucketIndex = -1;
            currentEntry = NULL;
            isEnd = false;
            return gotoNext();
        }
        bool gotoNext()
        {
            if(isEnd)
                return false;
            if(currentEntry!=NULL)
            {
                currentEntry = currentEntry->m_next;
                if(currentEntry!=NULL)
                    return true;
            }
            for(int i=currentBucketIndex+1;i<hash->m_Buckets.size(); ++i)
            {
                if(hash->m_Buckets[i].m_next != NULL)
                {
                    currentBucketIndex = i;
                    currentEntry = hash->m_Buckets[i].m_next;
                    return true;
                }
            }
            isEnd = true;
            return false;
        }
        
        HashTableIterator<Key,Value>& operator++(){ gotoNext(); return *this;}
        value_type& operator*(){ return getPair();}
        operator void*(){ return isValid()?currentEntry:NULL;}
        
        bool isValid(){ return !isEnd && currentEntry!=NULL;}
        value_type& getPair(){ 
            assert(isValid());
            return *currentEntry;
        }
        
        const Key& getKey(){ assert(isValid()); return currentEntry->m_key;}
        const Value& getValue(){ assert(isValid()); return currentEntry->m_value;}
        value_type* operator->(){ return currentEntry;}
};
#endif