#ifndef MYSet_H
#define MYSet_H

#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
#include <typeinfo>
using namespace std;

int DEFAULT_INITIAL_CAPACITY = 4;
float DEFAULT_MAX_LOAD_FACTOR = 0.75f; 
unsigned MAXIMUM_CAPACITY = 1 << 30; 

template<typename K>
class MySet
{
public:
  MySet();
  MySet(int initialCapacity);
  MySet(int initialCapacity, float loadFactorThreshold);

  int getSize() const;
  bool isEmpty() const;
  bool contains(K key) const;
  bool add(K key);
  bool remove(K key);
  void clear();
  vector<K> getKeys() const;
  string toString() const;

private:
  int size; 
  float loadFactorThreshold; 
  int capacity; 

  // Hash table is an array with each cell as a vector
  vector<K>* table;

  int hash(int hashCode) const;
  unsigned hashCode(K key) const;
  int supplementalHash(int h) const; 
  int trimToPowerOf2(int initialCapacity);
  void rehash();
  void removeKeys();
};

template<typename K>
MySet<K>::MySet()
{
  capacity = DEFAULT_INITIAL_CAPACITY;
  table = new vector<K>[capacity];
  loadFactorThreshold = DEFAULT_MAX_LOAD_FACTOR;
  size = 0;
}

template<typename K>
MySet<K>::MySet(int initialCapacity)
{
  capacity = initialCapacity;
  table = new vector<K>[capacity];
  loadFactorThreshold = DEFAULT_MAX_LOAD_FACTOR;
  size = 0;
}

template<typename K>
MySet<K>::MySet(int initialCapacity, float loadFactorThreshold) 
{ 
  if (initialCapacity > MAXIMUM_CAPACITY)
    capacity = MAXIMUM_CAPACITY;
  else
    capacity = trimToPowerOf2(initialCapacity);
    
  this->loadFactorThreshold = loadFactorThreshold;    
  table = new vector<K>[capacity];
  size = 0;
}

template<typename K>
bool MySet<K>::add(K key)
{
  if (contains(key)) return false; // key is already in the set
  
  // Check load factor
  if (size >= capacity * loadFactorThreshold) 
  {
    if (capacity == MAXIMUM_CAPACITY)
      throw runtime_error("Exceeding maximum capacity");
      
    rehash();
  }
    
  int bucketIndex = hash(hashCode(key));

  // Add a new entry (key, value) to hashTable[index]
  table[bucketIndex].push_back(key);

  size++; // Increase size

  return true;
} 

template<typename K>
bool MySet<K>::isEmpty() const
{
  return size == 0;
}

template<typename K>
bool MySet<K>::contains(K key) const
{    
  int bucketIndex = hash(hashCode(key));

  for (K& e: table[bucketIndex])
    if (e == key) 
      return true;
    
  return false;
}
  
template<typename K>
bool MySet<K>::remove(K key) 
{
  int bucketIndex = hash(hashCode(key));
    
  // Remove the first entry that matches the key from a bucket
  if (table[bucketIndex].size() > 0) 
  {
    for (auto p = table[bucketIndex].begin(); 
        p != table[bucketIndex].end(); p++)
      if (*p == key) 
      {
        table[bucketIndex].erase(p);
        size--; // Decrease size
        return true; // Remove just one entry that matches the key
      }
  } 

  return false;
}

template<typename K>
void MySet<K>::clear() 
{
  size = 0;
  removeKeys();
}

template<typename K>
vector<K> MySet<K>::getKeys() const
{
  vector<K> v;
    
  for (int i = 0; i < capacity; i++) 
  {
    for (K& e: table[i])
      v.push_back(e); 
  }
    
  return v;
}

template<typename K>
void MySet<K>::removeKeys() 
{
  for (int i = 0; i < capacity; i++) 
  {
    table[i].clear();
  }
}

template<typename K>
string MySet<K>::toString() const
{
  stringstream ss;
  ss << "[";
    
  for (int i = 0; i < capacity; i++) 
  {
    for (K& e: table[i])
      ss << e << " ";
  }
    
  ss << "]";
  return ss.str();
}

template<typename K>
unsigned MySet<K>::hashCode(K key) const
{ 
  return typeid(key).hash_code();
}

template<typename K>
int MySet<K>::hash(int hashCode) const
{
  return supplementalHash(hashCode) & (capacity - 1);
}
  
template<typename K>
int MySet<K>::supplementalHash(int h) const
{
  h ^= (h >> 20) ^ (h >> 12);
  return h ^ (h >> 7) ^ (h >> 4);
}

template<typename K>
int MySet<K>::trimToPowerOf2(int initialCapacity) 
{
  int capacity = 1;
  while (capacity < initialCapacity) {
    capacity <<= 1;
  }
    
  return capacity;
}

template<typename K>
void MySet<K>::rehash() 
{
  vector<K> set = getKeys(); // Get entries
  capacity <<= 1; // Double capacity   
  delete[] table; // Delete old hash table
  table = new vector<K>[capacity]; // Create a new hash table
  size = 0; // Reset size to 0
    
  for (K& e: set) 
    add(e); // Store to new table
}

template<typename K>
int MySet<K>::getSize() const
{
  return size;
}

#endif