Code:
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stdexcept>
using std::setw;
using std::string;
using std::cin;
using std::cout;
using std::cerr;
template < class KeyType, class ValueType >
struct element
{
element *next;
ValueType value;
KeyType key;
};
template < class KeyType, class ValueType >
class HashMap
{
public:
typedef int (*hashfunc) ( KeyType key );
HashMap( hashfunc h, int buckets );
~HashMap( );
bool Insert ( KeyType key, ValueType value);
bool Remove ( KeyType key );
bool Replace ( KeyType key, ValueType value);
ValueType Find ( KeyType key ) const;
bool Has ( KeyType key ) const;
template < class K, class V >
friend ostream& operator<< ( ostream& o, const HashMap < K, V > & hm);
void PrintBucket ( KeyType key ) const;
private:
element <KeyType, ValueType> *bucket;
int numbuckets;
};
template <class KeyType, class ValueType>
HashMap<KeyType, ValueType>::HashMap(hashfunc h, int _numbuckets)
{
numbuckets=_numbuckets;
if (numbuckets <= 0)
{
string s1 = "HashMap Constructor";
throw HashMapException(s1);
}
typedef element<KeyType,ValueType>* elp;
element<KeyType,ValueType> **buckets;
buckets = new elp[numbuckets];
for ( int i = 0; i <= numbuckets; i++ )
{
buckets[i] = NULL;
}
hashfunc d = h;
}
template <class KeyType, class ValueType>
HashMap<KeyType, ValueType>::~HashMap( )
{
for ( int i = 0; i <= numbuckets; i++)
{
buckets[i] = NULL;
}
delete [] buckets;
}
template <class KeyType, class ValueType>
bool HashMap<KeyType, ValueType>::Insert ( KeyType key, ValueType value)
{
//What is this for?
//HashMap node<KeyType, ValueType>(hashfunc, numbuckets);
element<KeyType,ValueType> *newptr = new element<KeyType,ValueType>;
if (newptr == NULL)
{
return false;
}
newptr -> data = value;
newptr -> next = buckets[hashfunc(key)];
buckets[hashfunc(key)] = newptr;
return true;
}
template <class KeyType, class ValueType>
bool HashMap<KeyType, ValueType>::Remove ( KeyType key )
{
element<KeyType,ValueType> *front;
element<KeyType,ValueType> *back;
front = buckets[hashfunc(key)];
back = front;
if (front -> key == key)
{
delete front;
return true;
}
while (front != NULL)
{
if (front -> key == key)
{
back -> next = front -> next;
delete front;
return true;
}
front = front -> next;
}
return false;
}
template <class KeyType, class ValueType>
bool HashMap<KeyType, ValueType>::Replace ( KeyType key, ValueType value)
{
element<KeyType,ValueType> *runner = buckets[hashfunc(key)];
while (runner != NULL)
{
if (runner -> key == key)
{
runner -> value = value;
return true;
runner = runner -> next;
}
return false;
}
}
template <class KeyType, class ValueType>
ValueType HashMap<KeyType, ValueType>::Find ( KeyType key ) const
{
element<KeyType,KeyType> *runner = buckets[hashfunc(key)];
while (runner != NULL)
{
if (runner -> key == key)
{
return runner -> value;
}
runner = runner -> next;
}
string s1 = "Find";
throw HashMapException (s1);
}
template <class KeyType, class ValueType>
bool HashMap<KeyType, ValueType>::Has ( KeyType key ) const
{
element<KeyType,ValueType> *runner = buckets[hashfunc(key)];
while (runner != NULL)
{
if (runner -> key == key)
{
return true;
}
runner = runner -> next;
}
return false;
}
template < class K, class V >
ostream& operator<< ( ostream& o, const HashMap < K, V > & hm)
{
for (int i = 0; i < buckets; i++)
{
bucket[i].PrintBucket(hm->key);
}
}
template <class KeyType, class ValueType>
void HashMap<KeyType, ValueType>::PrintBucket ( KeyType key ) const
{
int bucketnum = hashfunc(key);
element<KeyType,ValueType> *runner = bucket[hashfunc(key)];
if (runner == NULL)
{
cout << "Bucket " << bucketnum << " is empty" << endl;
return;
}
cout << "Bucket " << bucketnum << " contains: " << endl;
while (runner != NULL)
{
if (runner -> key == key)
{
cout << "(" << runner -> key << ", " << runner -> value << endl;
return;
}
runner = runner -> next;
}
string s1 = "PrintBucket";
throw HashMapException (s1);
}
int main()
{
return 0;
}