//假设我们要在 hashtable 中存的 key 和 value 都是数字
 
#include <iostream>
#include <assert.h>
using namespace std;
 
#define MIN_LOAD_FACTOR_THREHOLD 0.25
#define MAX_LOAD_FACTOR_THREHOLD (MIN_LOAD_FACTOR_THREHOLD * 2)
#define MIN_TABLE_SIZE 10
#define MAX_TABLE_SIZE 100
 
 
class Entry {
private:
  int key;
  int value;
public:
  Entry (int key, int value);
  int getKey ();
  int getValue ();
};
 
Entry::Entry (int key, int value) {
  this->key = key;
  this->value = value;
}
 
int Entry::getKey () {
  return this->key;
}
 
int Entry::getValue () {
  return this->value;
}
 
class Hashtable {
private:
  int size;
  Entry **table;
  //已占用的位置个数
  int occupiedSize;
  //负载率临界值
  float minLoadFactorThreshold;
  float maxLoadFactorThreshold;
  int maxTableSize;
  int minTableSize;
  static Entry * deleteEntry;
  void resize(double factor);
 
public:
  Hashtable (int size);
  int get (int key);
  void put (int key, int value);
  int hash (int key);
  int getSize ();
  int getOccupiedSize ();
  void remove (int key);
  ~Hashtable ();
};
 
Entry * Hashtable::deleteEntry = new Entry(-1, -1);
 
Hashtable::Hashtable (int size) {
  assert(size > 0);
  this->size = size;
  occupiedSize = 0;
  minTableSize = MIN_TABLE_SIZE;
  maxTableSize = MAX_TABLE_SIZE;
  minLoadFactorThreshold = MIN_LOAD_FACTOR_THREHOLD;
  maxLoadFactorThreshold = MAX_LOAD_FACTOR_THREHOLD;
  table = new Entry* [size];
  for (int i = 0; i < size; i++) {
    table[i] = NULL;
  }
}
 
void Hashtable::put (int key, int value) {
  int hash = this->hash(key);
  int count = 0;
  while(table[hash] != NULL) {
    //全部位置遍历后，如果仍然没有空位，返回；
    if (count >= size) {
      cout << "The hashtable is full, failed to add {key:" << key << " value:" << value << "}" << endl;
      return;
    }
    hash = (hash + 1) % size;
    count ++;
  }
  table[hash] = new Entry(key, value);
  occupiedSize ++;
  float currentLoadFactor = (float)occupiedSize / (float)size;
  if( currentLoadFactor > maxLoadFactorThreshold && size * 2 < maxTableSize) {
    resize(2);
  }
}
 
int Hashtable::get (int key) {
  int hash = this->hash(key);
  int count = 0;
  while(table[hash] != NULL) {
    if(table[hash]->getKey() == key) {
      return table[hash]->getValue();
    }
    //全部位置遍历后，仍然没有找到对应的key，返回-1
    if (count >= size) {
      return -1;
    }
    hash = (hash + 1) % size;
    count ++;
  }
 
  return -1;
}
 
int Hashtable::hash (int key) {
  return key % size;
}
int Hashtable::getSize () {
  return size;
}
int Hashtable::getOccupiedSize () {
  return occupiedSize;
}
 
void Hashtable::resize (double factor) {
  int oldSize = size;
  Entry ** oldTable = table;
  size = (int) oldSize * factor;
  table = new Entry* [size];
  occupiedSize = 0;
 
  for (int i = 0; i < size; i++) {
    table[i] = NULL;
  }
 
 
  for (int i = 0; i < oldSize; i++) {
    if (NULL != oldTable[i] &&  oldTable[i] != deleteEntry) {
      put(oldTable[i]->getKey(), oldTable[i]->getValue());
    }
  }
 
  delete[] oldTable;
 
}
 
void Hashtable::remove (int key) {
  int hash = this->hash(key);
  int count = 0;
  while(table[hash] != NULL) {
    if(table[hash]->getKey() == key) {
      delete table[hash];
      table[hash] = deleteEntry;
      occupiedSize --;
      // cout << "remove and occupiedSize: " << occupiedSize <<  endl;
      float currentLoadFactor = (float)occupiedSize / (float)size;
      if( currentLoadFactor < minLoadFactorThreshold && size / 2 > minTableSize) {
        resize(0.5);
      }
 
    }
    //全部位置遍历后，仍然没有找到对应的key
    if (count >= size) {
      cout << "没有找到你要删除的 key: " << key << endl;
      return;
    }
    hash = (hash + 1) % size;
    count ++;
  }
}
 
Hashtable::~Hashtable () {
  for (int i = 0; i < size; i++) {
    if(table[i]) {
      delete table[i];
    }
  }
  delete [] table;
}
 
int main () {
  Hashtable * table10 = new Hashtable(10);
  table10->put(1, 100);
  table10->put(2, 200);
  table10->put(3, 300);
  assert(table10->get(1) == 100);
  assert(table10->get(2) == 200);
  assert(table10->get(3) == 300);
  assert(table10->getSize() == 10);
  assert(table10->getOccupiedSize() == 3);
 
 
  //测试当负载率大于maxLoadFactorThreshold，要扩大 size * 2
  Hashtable * table2 = new Hashtable(2);
  table2->put(1, 100);
  table2->put(2, 200);
  table2->put(3, 300);
  assert(table2->get(1) == 100);
  assert(table2->get(2) == 200);
  assert(table2->get(3) == 300);
  assert(table2->getSize() == 8);
  assert(table2->getOccupiedSize() == 3);
 
 
  //测试删除和最小删除值
  Hashtable * table11 = new Hashtable(11);
  table11->put(1, 100);
  table11->put(2, 200);
  table11->put(3, 300);
  table11->put(4, 400);
  table11->put(5, 500);
  table11->put(6, 600);
  table11->put(7, 700);
  table11->put(8, 800);
  table11->put(9, 900);
  table11->put(10, 1000);
  table11->put(11, 1100);
  table11->put(12, 1200);
  assert(table11->get(8) == 800);
  assert(table11->getSize() == 44);
  assert(table11->getOccupiedSize() == 12);
  table11->remove(8);
  assert(table11->get(8) == -1);
  table11->remove(7);
  // 10 / 44 = 0.2 0.2 < 0.25 所以要压缩
  assert(table11->getSize() == 22);
  assert(table11->getOccupiedSize() == 10);
  table11->remove(6);
  table11->remove(5);
  table11->remove(4);
  table11->remove(3);
  table11->remove(2);
  // 5 / 22 = 0.2 0.2 < 0.25 所以要压缩
  assert(table11->getSize() == 11);
  assert(table11->getOccupiedSize() == 5);
  table11->remove(1);
  table11->remove(9);
  table11->remove(10);
  // 2 / 11 = 0.18 0.18 < 0.25 但是 11/2 < 10 ，所以不压缩
  assert(table11->getSize() == 11);
  assert(table11->getOccupiedSize() == 2);
 
  cout << "The tests run successfully." << endl;
 
}