#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;
}
};