#ifndef HASHTABLE_H_
#define HASHTABLE_H_ 1
// Oldham, Jeffrey D.
// 2000Apr18
// CS1321

// A Hash Table Implementation

// We implement an open-chained hash table storing keys only, no
// values.

// We implement the hash table using a vector of vectors of keyTypes.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <math.h>		// has sqrt()
#include <utility>		// has pair()
#include "URL.h"
#include <assert.h>
#include <limits.h>		// has UCHAR_MAX

class hashTable {
public:
  typedef URL keyType;
  typedef pair<bool,keyType> insertPair;

  // constructor
  hashTable(void) {
    table[0].resize(64);	// arbitrary initial size
    table[1].resize(64);
    whichTable = 0;
    nuItems = 0;
    goldenRatio = (sqrt(5) - 1.0) / 2.0;
    return;
  }

  // Ensure the given key is in the hash table.
  // Return a pair <true,whatever> iff the key was not previously
  // present.  Return a pair <false,matching key> if a matching key is 
  // found.
  insertPair insert(const keyType & key) {
    sizePosition p = hash(key);
    assert(p < table[whichTable].size());
    vk::iterator i =
      find(table[whichTable][p].begin(), table[whichTable][p].end(), key);
    if (i == table[whichTable][p].end()) {
      table[whichTable][p].push_back(key);
      resize(true /* increment */);
      return insertPair(true,key /* ignored */);
    }
    else
      return insertPair(false, *i);
  }

  // Query if the given key is in the hash table, returning true if
  // present.
  bool query(const keyType & key) const {
    sizePosition p = hash(key);
    assert(p < table[whichTable].size());
    return
      find(table[whichTable][p].begin(), table[whichTable][p].end(), key) !=
      table[whichTable][p].end();
  }

  // Ensure the given key is not in the hash table.
  // Return true iff the key was previously present.
  bool remove(const keyType & key) {
    sizePosition p = hash(key);
    assert(p < table[whichTable].size());
    vk::iterator i =
      find(table[whichTable][p].begin(), table[whichTable][p].end(), key);
    if (i == table[whichTable][p].end())
      return false;
    else {
      table[whichTable][p].erase(i);
      resize(false /* decrement */);
      return true;
    }
  }

  // Print the hash table's contents.
  friend
  ostream& operator<<(ostream& out, const hashTable & h) {
    for (vvk::const_iterator i = h.table[h.whichTable].begin();
	 i != h.table[h.whichTable].end();
	 ++i)
      copy(i->begin(), i->end(), ostream_iterator<keyType>(out, "\n"));
    return out;
  }

private:
  typedef vector<vector< keyType > > vvk;
  typedef vector< keyType > vk;
  typedef vk::size_type sizePosition; // position within a vector
  vector<vector< keyType > > table[2]; // stores values
  unsigned int whichTable;
	// strategy: table[whichTable] will contain the current data.
	// "Resizing" the table will actually just copy the data to
	// the other vector.

  // Convert a key into a vector position.
  // input <- key
  //	      table's size (if 0, the function will use the current
  //	      table's size)
  sizePosition hash(const keyType & key, sizePosition tableSize = 0) const {
    if (tableSize == 0)
      tableSize = table[whichTable].size();
    string URLcontents = key.getContents(); // unclear why needed
#ifdef DEBUG
    sizePosition s =
      static_cast<sizePosition>(floor(tableSize *
				      stringToFraction(URLcontents.begin(),
						       URLcontents.end(),
						       goldenRatio)));
    cout << "hash(" << key << ") yielded " << s << ".\n";
    return s;
#else
    return
      static_cast<sizePosition>(floor(tableSize *
				      stringToFraction(URLcontents.begin(),
						       URLcontents.end(),
						       goldenRatio)));
#endif // DEBUG
  }

  // Return the fractional portion of a double.
  static double fraction(const double d) {
    assert(d >= 0.0);
    double answer = d - floor(d);
    assert(answer < 1.0);
    return answer;
  }

  // Compute fractional portion of the product of the base-256 value
  // of the (backwards) string and the golden ratio.
  static double stringToFraction(string::const_iterator pos,
				 string::const_iterator ending,
				 const double irrational) {
    if (pos == ending)
      return 0.0;
    else
      return fraction(fraction(static_cast<unsigned int>(*pos) * irrational) +
		      (UCHAR_MAX+1) *
		      stringToFraction(++pos, ending, irrational));
  }

  sizePosition nuItems;		// number of items in the hash table
  double goldenRatio;

  // Resize the vector to the given factor of its original size if
  // necessary.  Also update the number of items in the table.
  // We use the strategy of "switching" to the other vector if we need 
  // to resize.
  // input <- boolean true if table's contents increased, else false
  void resize(bool incrementP) {
    if (incrementP) ++nuItems; else --nuItems;
    if (2 * nuItems <= table[whichTable].size() && 
	table[whichTable].size() <= 8 * nuItems)
      return;			// no table size change

    // Change the table's size.
    sizePosition newSize;
    if (2 * nuItems > table[whichTable].size())
      newSize = table[whichTable].size() * 2;
    else
      newSize = max(table[whichTable].size() / 2, 1u);

    whichTable = 1 - whichTable;
    table[whichTable].clear();
    table[whichTable].resize(newSize);
#ifdef DEBUG
    cout << "Resize hash table from size " << table[1-whichTable].size() <<
      " to " << table[whichTable].size() << ".\n";
#endif // DEBUG
    for (vvk::const_iterator i = table[1-whichTable].begin();
	 i != table[1-whichTable].end();
	 ++i)
      for (vk::const_iterator j = i->begin();
	   j != i->end();
	   ++j) {
	table[whichTable][hash(*j, newSize)].push_back(*j);
      }

    return;
  }
};

#endif // HASHTABLE_H_