#ifndef _HASH_MAP
#define _HASH_MAP

#include <vector>
#include <string>
using namespace std;

int operator % (const string & text, int max) {
	int code = 0;
	for (int i = 0; i < text.size(); ++ i) {
		int code1 = text[i];
		code1 = code1 << (i * 8 % 24);
		code = code ^ code1;
	}
	return code % max;
}

class NoSuchKeyException {};

template <typename K, typename V>
class HashTable
{
private:
		
	class Entry
	{
	public:
		K key;
		V value;
		bool isInUse;
		
		Entry() {
			isInUse = false;
		}
	};
	
	Entry * entries;
	
	int capacity;
	int count;
	
	void initialize(int capacity2) {
		count = 0;
		capacity = capacity2;
		entries = new Entry[capacity];
	}
	
	void assign(const HashTable & map2) {
		count = map2.count;
		capacity = map2.capacity;
		entries = new Entry[capacity];
		for (int i = 0; i < capacity; ++ i) {
			entries[i] = map2.entries[i];
		}
	}
	
public:
	
	HashTable() {
		initialize(2);
	}
	
	~HashTable() {
		delete [] entries;
	}
	
	HashTable(const HashTable & map2) {
		assign(map2);
	}
	
	HashTable & operator = (const HashTable & map2) {
		delete [] entries;
		assign(map2);
		return (*this);
	}
	
	void clear() {
		delete [] entries;
		initialize(2);
	}
	
private:
	
	int hashIndex(const K & key) const {
		return key % capacity;
	}
	
	int find(const K & key) const {
		int index = hashIndex(key);
		while (true) {
			if (! entries[index].isInUse) {
				return index;
			}
			if (entries[index].key == key) {
				return index;
			}
			index = (index + 1) % capacity;
		}
	}
	
	void resize(int capacity2) {
		Entry * entries0 = entries;
		int capacity0 = capacity;
		initialize(capacity2);
		for (int i = 0; i < capacity0; ++ i) {
			if (entries0[i].isInUse) {
				put(entries0[i].key, entries0[i].value);
			}
		}
		delete [] entries0;
	}
	
public:
	
	void put(const K & key, const V & value) {
		int index = find(key);
		entries[index].value = value;
		if (entries[index].isInUse) return;
		
		entries[index].isInUse = true;
		entries[index].key = key;
		
		++ count;
		if (count > capacity / 2) {
			resize(capacity * 2);
		}
	}
	
	V get(const K & key) const {
		int index = find(key);
		if (! entries[index].isInUse) {
			throw NoSuchKeyException();
		}
		return entries[index].value;
	}
	
	bool remove(const K & key) {
		int index = find(key);
		if (! entries[index].isInUse) return false;
		fillNotInUseEntry(index);
		
		-- count;
		if (count < capacity / 4) {
			resize(capacity / 2);
		}
		return true;
	}
	
private:
	
	void fillNotInUseEntry(int index) {
		int next = index;
		while (true) {
			next = (next + 1) % capacity;
			if (! entries[next].isInUse) {
				entries[index].isInUse = false;
				return;
			}
			int index0 = hashIndex(entries[next].key);
			if (index < next) {
				if (index0 > index &&
					index0 <= next) continue;
			}
			else {
				if (index0 > index ||
					index0 <= next) continue;
			}
			entries[index] = entries[next];
			index = next;
		}
	}
	
public:
	
	bool containsKey(const K & key) const {
		int index = find(key);
		return (entries[index].isInUse);
	}
	
	int size() const {
		return count;
	}

	vector<K> getKeys() const {
		vector<K> vec;
		for (int i = 0; i < capacity; ++ i) {
			if (entries[i].isInUse) {
				vec.push_back(entries[i].key);
			}
		}
		return vec;
	}
	
};

#endif