/**
* Hash Table with open addressing, linear probing.
* http://e...content-available-to-author-only...a.org/wiki/Hash_table#Open_addressing
*
* INPUT: rows of the format:
* <command> <args>
* available commands:
* insert <string> <int>
* remove <string>
* get <string>
* print
* reset <int>
*
* Author: Erel Segal http://t...content-available-to-author-only...s.fm/rentabrain
* Date: 2010-10-13
*/
#include <string>
#include <iostream>
using namespace std;
template <typename T,typename K> struct HashTableNode {
K key;
T value;
bool isEmpty, isRemoved;
HashTableNode<T,K>() { isEmpty=true; isRemoved=false; }
HashTableNode<T,K>(K newKey, T newValue) { set(newKey,newValue); }
void set(K newKey, T newValue) {
key=newKey;
value=newValue;
isEmpty=isRemoved=false;
}
void remove() {
isRemoved=true;
}
};
/**
* A hash table with open addressing, linear probing.
* PARAMETERS:
* T - type of values stored in hash.
* K - type of keys by which the values are stored.
* hash - a hash function that gets a key and the table size m, and returns
* an integer in 0...m-1
*/
template <typename T, typename K, int HASH(K, int)> class HashTable {
HashTableNode<T,K>* myTable;
int mySize;
int hashFunction(K key, int baseHashValue, int trialNumber) {
return (baseHashValue + trialNumber) % mySize;
}
public:
void reset(int newSize) {
if (myTable) delete[] myTable;
myTable = new HashTableNode<T,K>[newSize];
mySize = newSize;
}
HashTable<T,K,HASH> (int newSize=10): myTable(NULL) { reset(newSize); }
~HashTable<T,K,HASH> () {
// if (myTable) delete[] myTable; // runtime error!
}
/**
* Look for the given key in the hash.
* If it exists - return a pointer to the matching value.
* Otherwise - return NULL.
*/
T* get (K key) {
int baseHashValue = HASH(key,mySize);
for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
int hashValue = hashFunction(key, baseHashValue, trialNumber);
if (myTable[hashValue].isEmpty) {
return NULL; // not found
}
if (myTable[hashValue].key==key) {
if (myTable[hashValue].isRemoved) {
return NULL; // found but deleted
} else {
return &myTable[hashValue].value;
}
}
}
return NULL; // not found
}
/**
* Insert the given value to the table, under the given key.
*/
void insert (K key, T value) {
int baseHashValue = HASH(key,mySize);
for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
int hashValue = hashFunction(key, baseHashValue, trialNumber);
if (myTable[hashValue].isEmpty || myTable[hashValue].isRemoved || myTable[hashValue].key==key) {
// found a place to insert:
myTable[hashValue].set(key,value);
return;
}
}
// could not find a place to insert:
throw string("Hash Table overflow");
}
/**
* Look for the given key in the hash.
* If it exists - remove it.
* Otherwise - return NULL.
*/
void remove (K key) {
int baseHashValue = HASH(key,mySize);
for (int trialNumber=0; trialNumber<mySize; ++trialNumber) {
int hashValue = hashFunction(key, baseHashValue, trialNumber);
if (myTable[hashValue].isEmpty) {
return; // not found
}
if (myTable[hashValue].key==key) {
myTable[hashValue].remove();
return;
}
}
}
friend ostream& operator<< (ostream& out, const HashTable<T,K,HASH> theHash) {
out << "{ ";
for (int i=0; i<theHash.mySize; ++i) {
if (!theHash.myTable[i].isEmpty && !theHash.myTable[i].isRemoved) {
out << " (" << i << ") "
<< theHash.myTable[i].key << " -> "
<< theHash.myTable[i].value << ", ";
}
}
out << " }";
return out;
}
}; // template class HashTable<T,K,HASH>
/**
* calculate a hash value for a string - convert the string to a number modulu the given base
*/
int string2number(string str, int modulu) {
int num=0;
for (size_t i=0; i<str.length(); ++i) {
num = (num*256 + str[i])%modulu;
}
return num;
}
int main() {
HashTable<int, string, &string2number> mapWordToNumber;
cout << mapWordToNumber << endl;
string command, word;
int number;
for (;;) {
cin >> command;
if (cin.eof()) return 0;
try {
if (command=="reset") {
cin >> number;
cout << command << " " << number << ":" << endl;
mapWordToNumber.reset(number);
} else if (command=="insert") {
cin >> word >> number;
cout << command << " " << word << " " << number << ":" << endl;
mapWordToNumber.insert(word,number);
} else if (command=="remove") {
cin >> word;
cout << command << " " << word << ":" << endl;
mapWordToNumber.remove(word);
} else if (command=="get") {
cin >> word;
cout << command << " " << word << ":";
int* value = mapWordToNumber.get(word);
if (value==NULL)
cout << "doesn't exist!";
else
cout << *value;
cout << endl;
} else if (command=="print") {
cout << mapWordToNumber << endl;
}
} catch (string error) {
cout << "ERROR: " << error << endl;
}
}
}