include string include iostream include iterator include sstream inclu

#include <string>
#include <iostream>
#include <iterator>
#include <sstream>
#include <stdexcept>

template <typename Key, typename Value>
class AbstractHashTable {
	public:
		AbstractHashTable() {
		}

		virtual void clear() = 0;
		virtual Value& get(const Key& key) = 0;
		virtual void add(Key &key, Value value) = 0;
		virtual void remove(const Key &key) = 0;
		virtual ~AbstractHashTable() { }
};

template <typename Key, typename Value>
class HashTable : public AbstractHashTable<Key, Value> {
	public:
		virtual void clear() { }
		virtual Value& get(const Key& key) { }
		virtual void add(Key &key, Value& value) { }
		virtual void remove(const Key &key) { }
		virtual ~HashTable() { }
};

template <typename Value>
class HashTable<std::string, Value> : public AbstractHashTable<std::string, Value> {
	private:
		int elements;
		int allocatedSize;

		class pair {
			public:
				pair(std::string& key, Value value)
					: key(key), value(value) { }
				std::string& key;
				Value value;
		}* *_store;

	public:
		class iterator : public std::iterator<std::input_iterator_tag, Value> {
			private:
				pair* *store;
				int idx;
				int size;
			public:
				iterator(int idx, pair* *store, int size)
					: idx(idx), store(store), size(size) { }

				bool operator==(const iterator& o) {
						return store == o.store && idx == o.idx && size == o.size;
				}

				bool operator!=(const iterator& o) {
						return !(*this == o);
				}

				pair* operator*(void) {
						if (idx != size) {
								return store[idx];
						} else {
								std::stringstream s;
								s << "Invalid idx " << idx;
								throw std::invalid_argument(s.str());
						}
				}

				iterator& operator++(void) {
						++idx;
						while (idx < size && 0 == store[idx]) {
							++idx;
						}
						return *this;
				}

				iterator operator++(int) {
						iterator t = *this;
						++*this;
						return t;
				}
		};

		HashTable() : AbstractHashTable<std::string, Value>() {
			elements = 0;
			allocatedSize = 2; //4096;
			_store = new pair*[allocatedSize];
		}

		void clear() {
			for (int i = 0; i < allocatedSize; ++i) {
				if (0 != _store[i]) {
					delete _store[i];
					_store[i] = 0;
				}
			}
		}

		Value& get(const std::string& key) {
			int idx = hash(key);
			return _store[idx]->value;
		}

		void add(std::string& key, Value value) {
			if (getSize() == getElements()) {
				expand();
			}

			int idx = hash(key);
			if (0 != _store[idx]) {
				expand();
				idx = hash(key);
			}

			_store[idx] = new pair(key, value);
			elements++;
#if 0
			std::cout << "{ ";
			for (int i = 0; i < allocatedSize; ++i) {
				std::cout << _store[i] << (_store[i] ? _store[i]->value : -1) << ", ";
			}
			std::cout << "}" << std::endl;
#endif
		}

		void remove(const std::string& key) {
			int idx = hash(key);
			delete _store[idx];
			_store[idx] = 0;
			elements--;
		}

		int getSize() {
			return allocatedSize;
		}

		int getElements() {
			return elements;
		}

		bool isEmpty() {
			return 0 == elements;
		}

		~HashTable() {
			delete [] _store;
		}

		iterator begin() {
			return iterator(0, _store, allocatedSize);
		}

		iterator end() {
			return iterator(allocatedSize, _store, allocatedSize);
		}

	private:
		int _hash(const std::string& key) {
			double a = .6180339887;
			int m = allocatedSize;
			unsigned int k = 0, k_pos = 0;
			double b;

			const char *s = key.c_str();
			for (int i = 0; s[i]; ++i) {
				unsigned char c = s[i];
				int j = 7;
				while (j >= 0 && ((c >> j) & 1) ^ 1) { // skip leading zeroes
					--j;
				}
				while (j >= 0) {
					k |= (((c >> j) & 1) << k_pos);
					k_pos++;
					if (k_pos >= 8*sizeof(int)) {
						break;
					}
					--j;
				}
				if (k_pos >= 8*sizeof(int)) {
					break;
				}
			}

			b = k * a;
			b -= (int) b;

			return (int) (m*b);
		}

		int fix_hash(int idx, const std::string& key, pair* *store, int size) {
			int j = idx;
			int i = 0;
			while (i != size) {
				if (0 == store[j] || store[j]->key == key) {
					break;
				}
				i++;
				j = (j + i) % size;
			}
			return j;
		}

		int hash(const std::string& key) {
			return fix_hash(_hash(key), key, _store, allocatedSize);
		}

		void expand() {
			allocatedSize *= 2;
			pair* *newStore = new pair*[allocatedSize];
			for (int i = 0; i < allocatedSize/2; ++i) {
				if (0 == _store[i]) continue;
				int idx = _hash(_store[i]->key);
				idx = fix_hash(idx, _store[i]->key, newStore, allocatedSize);
				newStore[idx] = _store[i];
			}
			delete [] _store;
			_store = newStore;
		}
};