#include <iostream>

template <typename K, typename V>
class ExtendibleHash {
public:
	// constructor
	ExtendibleHash(size_t size);
	// helper function to generate hash addressing
	size_t HashKey(const K &key);
	// helper function to get global & local depth
	int GetGlobalDepth() const;
	int GetLocalDepth(int bucket_id) const;
	int GetNumBuckets() const;
	// lookup and modifier
	bool Find(const K &key, V &value);
	bool Remove(const K &key);
	void Insert(const K &key, const V &value);

	// add your own member variables here
	int size; // size of each bucket: how many records
	int num;  // total number of buckets
	int globalDepth;

	struct Record
	{
		K *kptr;
		V *vptr;
	};

	struct Bucket
	{
		int localDepth;
		int counter;
		Record *recordArray;
	};

	Bucket **addressTable; // address table to link to all buckets
};

template <typename K, typename V>
ExtendibleHash<K, V>::ExtendibleHash(size_t _size) {
	size = _size;

	// initialize address table with depth 1
	globalDepth = 1;
	num = 2;
	addressTable = (Bucket **)malloc(2 * sizeof(Bucket *));
	for (int i = 0; i < num; ++i)
	{
		Bucket *b = (Bucket *)malloc(sizeof(Bucket));
		b->localDepth = 1;
		b->counter = 0;
		b->recordArray = (Record *)malloc(size * sizeof(Record));
		addressTable[i] = b;
	}
}

/*
 * helper function to calculate the hashing address of input key
 */
template <typename K, typename V>
size_t ExtendibleHash<K, V>::HashKey(const K &key) {
	int m = ~(0xffffffff << globalDepth); // mask the bits
	long v = 0, b = 1, p = 1000000007;    // to calculate polynomial
	uintptr_t a = (uintptr_t)(&key);      // address[0] for key object
	int size = sizeof(K);                 // byte size of key

	// iterate over all bytes of K
	for (int i = 0; i < size; ++i)
	{
		// when one pointer moves 1 step(+1)
		// the corresponding bits moves 1 char(8bit)
		unsigned char t = *(reinterpret_cast<unsigned char*>(i + a));
		v = ((t * b) % p + v) % p;
		b = (b * 31) % p;
	}
	return (size_t)v & m;
}

/*
 * helper function to return global depth of hash table
 * NOTE: you must implement this function in order to pass test
 */
template <typename K, typename V>
int ExtendibleHash<K, V>::GetGlobalDepth() const {
	return globalDepth;
}

/*
 * helper function to return local depth of one specific bucket
 * NOTE: you must implement this function in order to pass test
 */
template <typename K, typename V>
int ExtendibleHash<K, V>::GetLocalDepth(int bucket_id) const {
	return addressTable[bucket_id]->localDepth;
}

/*
 * helper function to return current number of bucket in hash table
 */
template <typename K, typename V>
int ExtendibleHash<K, V>::GetNumBuckets() const {
	return num;
}

/*
 * lookup function to find value associate with input key
 */
template <typename K, typename V>
bool ExtendibleHash<K, V>::Find(const K &key, V &value) {
	return false;
}

/*
 * delete <key,value> entry in hash table
 * Shrink & Combination is not required for this project
 */
template <typename K, typename V>
bool ExtendibleHash<K, V>::Remove(const K &key) {
	return false;
}

/*
 * insert <key,value> entry in hash table
 * Split & Redistribute bucket when there is overflow and if necessary increase
 * global depth
 */
template <typename K, typename V>
void ExtendibleHash<K, V>::Insert(const K &key, const V &value) {
	size_t hid = HashKey(key);

	// bucket to be inserted
	Bucket *b = addressTable[hid];

	if (b->counter < size)
	{
		// inserting without splitting
		b->recordArray[b->counter].kptr = (K *)&key;
		b->recordArray[b->counter].vptr = (V *)&value;
		b->counter += 1;
	}
	else
	{
		int _globalDepth = globalDepth;
		int _localDepth = b->localDepth;

		if (_localDepth + 1 > _globalDepth)
		{
			// expend and update addressTable
			globalDepth = globalDepth + 1;
			Bucket **_addressTable = (Bucket **)malloc((1 << globalDepth) * sizeof(Bucket *));

			// copy the original addressTable
			for (int i = 0; i < (1 << _globalDepth); ++i)
			{
				_addressTable[i] = addressTable[i];
				_addressTable[i | (1 << _globalDepth)] = addressTable[i];
			}

			// update pointer
			Bucket **p = addressTable;
			addressTable = _addressTable;
			free(p);
		}
		// else, do not update addressTable

		// splitting without expending
		// initialization
		Bucket *b0 = (Bucket *)malloc(sizeof(Bucket));
		b0->localDepth = _localDepth + 1;
		b0->counter = 0;
		b0->recordArray = (Record *)malloc(size * sizeof(Record));

		Bucket *b1 = (Bucket *)malloc(sizeof(Bucket));
		b1->counter = 0;
		b1->localDepth = _localDepth + 1;
		b1->recordArray = (Record *)malloc(size * sizeof(Record));

		// hashkey has been updated since globalDepth IS updated
		if (((HashKey(key) >> _localDepth) & 0x1) == 0)
		{
			b0->recordArray[b0->counter].kptr = (K *)&key;
			b0->recordArray[b0->counter].vptr = (V *)&value;
			b0->counter++;
		}
		else
		{
			b1->recordArray[b1->counter].kptr = (K *)&key;
			b1->recordArray[b1->counter].vptr = (V *)&value;
			b1->counter++;
		}

		// split bucket b
		for (int i = 0; i < size; ++i)
		{
			K _key = *(b->recordArray[i].kptr);
			if (((HashKey(_key) >> _localDepth) & 0x1) == 0)
			{
				b0->recordArray[b0->counter].kptr = b->recordArray[i].kptr;
				b0->recordArray[b0->counter].vptr = b->recordArray[i].vptr;
				b0->counter++;
			}
			else
			{
				b1->recordArray[b1->counter].kptr = b->recordArray[i].kptr;
				b1->recordArray[b1->counter].vptr = b->recordArray[i].vptr;
				b1->counter++;
			}
		}

		// update
		num++;
		free(b->recordArray);
		free(addressTable[hid]); // delete b

		int _hid = hid ^ (1 << _localDepth);
		if (((hid >> _localDepth) & 0x1) == 0)
		{
			addressTable[hid] = b0;
			addressTable[_hid] = b1;
		}
		else
		{
			addressTable[hid] = b1;
			addressTable[_hid] = b0;
		}
	}
}

template class ExtendibleHash<int, std::string>;
template class ExtendibleHash<int, int>;

int main()
{
	ExtendibleHash<int, std::string> *test =
		new ExtendibleHash<int, std::string>(2);

	// insert several key/value pairs
	test->Insert(1, "a");
	test->Insert(2, "b");
	test->Insert(3, "c");
	test->Insert(4, "d");
	test->Insert(5, "e");
	test->Insert(6, "f");
	test->Insert(7, "g");
	test->Insert(8, "h");
	test->Insert(9, "i");
}