s.hanson
May 3rd, 2008, 01:46 AM
This is a snippet from a hash table program I am writing. It uses inheritance, where HashTable is abstract base, OpenAddressing is abstract and LinearProbeHash inherits from OpenAddressing
#include <vector>
#include <string>
using namespace std;
enum Status { EMPTY, USED, FREE };
///////////////////////////////////////////////////////////////
// HASH TABLE CLASS - ABSTRACT BASE //
///////////////////////////////////////////////////////////////
template <typename Object>
class HashTable
{
public:
struct HashElement// Storage "Bucket" for a hash element
{
int key;
Object el;
Status status;
HashElement(const int& k=0, const Object& e=NULL, Status st=EMPTY)
: key(k),el(e), status(st) {}
};
typedef HashElement* ElemPtr;
protected:
virtual ElemPtr finder(const int& k) = 0;
virtual ElemPtr inserter(const int& k, const Object& e) = 0;
virtual int hash1(const int& k) { return (k % N); }
int sz, N;
public:
virtual void removeElement(int k) = 0;
virtual ElemPtr find(int k) { return finder(k); }
};
///////////////////////////////////////////////////////////////
//OPEN-ADDRESSING CLASS - ABSTRACT BASE //
///////////////////////////////////////////////////////////////
template <typename Object>
class OpenAddressing : public HashTable<Object>
{
public:
void removeElement(int k)
{
ElemPtr temp = finder(k);
*temp = this->HashElement(FREE);
this->sz--;
}
protected:
ElemPtr HashArray;
virtual int hash2(const int& k, const int& i) = 0; // hash function
ElemPtr inserter(const int& k, const Object& e)
{
int i = 0;
int insertLoc = this->hash1(k); //starts insert at hash value of key
int startPoint = insertLoc; //keeps track of initial insert location
while (HashArray[insertLoc].status == USED)
{
this->collisions++; //keep track of collisions for testing
i++;
insertLoc = hash2(k,i);
if ( insertLoc == startPoint) //loop has gone all the way around the table
{
cerr << "Table Full!\n";
return NULL;
}
}
HashArray[insertLoc] = HashElement(k,e,USED);
this->sz++;
return &HashArray[insertLoc];
}
ElemPtr finder(const int& k)
{
int loc = this->hash1(k);
int startPoint = loc;
bool found = true;
int i=0;
while (HashArray[loc].key != k)
{
i++;
this->collisions++;
loc = hash2(k,i);
if (HashArray[loc].status == EMPTY || startPoint == loc)
{
found = false;
break;
}
}
if (found == false)
{
cerr << "Couldn't find element with key: " << k << endl;
return NULL;
}
else
// cout << "\nIterations to find " << k << "\t << i << endl;
return &HashArray[loc];
}
};
///////////////////////////////////////////////////////////////
// LINEAR PROBING CLASS - ABSTRACT BASE //
///////////////////////////////////////////////////////////////
template <typename Object>
class LinearProbeHash : public OpenAddressing<Object>
{
public:
LinearProbeHash(int capacity=107)
{
this->sz = 0;
this->N = capacity;
this->collisions = 0;
this->HashArray = new HashElement[this->N];
}
protected:
virtual int hash2(const int& k, const int& i)
{
return ((this->hash1(k)+i) % this->N);
}
};
I cannot figure this out. I get this error at several places:
Hash.h:55: error: ‘ElemPtr’ does not name a type
Hash.h:55: note: (perhaps ‘typename HashTable<Object>::ElemPtr’ was intended)
Does anyone know what I might be doing wrong. I have never done any serious implementation of templates with inheritance.
#include <vector>
#include <string>
using namespace std;
enum Status { EMPTY, USED, FREE };
///////////////////////////////////////////////////////////////
// HASH TABLE CLASS - ABSTRACT BASE //
///////////////////////////////////////////////////////////////
template <typename Object>
class HashTable
{
public:
struct HashElement// Storage "Bucket" for a hash element
{
int key;
Object el;
Status status;
HashElement(const int& k=0, const Object& e=NULL, Status st=EMPTY)
: key(k),el(e), status(st) {}
};
typedef HashElement* ElemPtr;
protected:
virtual ElemPtr finder(const int& k) = 0;
virtual ElemPtr inserter(const int& k, const Object& e) = 0;
virtual int hash1(const int& k) { return (k % N); }
int sz, N;
public:
virtual void removeElement(int k) = 0;
virtual ElemPtr find(int k) { return finder(k); }
};
///////////////////////////////////////////////////////////////
//OPEN-ADDRESSING CLASS - ABSTRACT BASE //
///////////////////////////////////////////////////////////////
template <typename Object>
class OpenAddressing : public HashTable<Object>
{
public:
void removeElement(int k)
{
ElemPtr temp = finder(k);
*temp = this->HashElement(FREE);
this->sz--;
}
protected:
ElemPtr HashArray;
virtual int hash2(const int& k, const int& i) = 0; // hash function
ElemPtr inserter(const int& k, const Object& e)
{
int i = 0;
int insertLoc = this->hash1(k); //starts insert at hash value of key
int startPoint = insertLoc; //keeps track of initial insert location
while (HashArray[insertLoc].status == USED)
{
this->collisions++; //keep track of collisions for testing
i++;
insertLoc = hash2(k,i);
if ( insertLoc == startPoint) //loop has gone all the way around the table
{
cerr << "Table Full!\n";
return NULL;
}
}
HashArray[insertLoc] = HashElement(k,e,USED);
this->sz++;
return &HashArray[insertLoc];
}
ElemPtr finder(const int& k)
{
int loc = this->hash1(k);
int startPoint = loc;
bool found = true;
int i=0;
while (HashArray[loc].key != k)
{
i++;
this->collisions++;
loc = hash2(k,i);
if (HashArray[loc].status == EMPTY || startPoint == loc)
{
found = false;
break;
}
}
if (found == false)
{
cerr << "Couldn't find element with key: " << k << endl;
return NULL;
}
else
// cout << "\nIterations to find " << k << "\t << i << endl;
return &HashArray[loc];
}
};
///////////////////////////////////////////////////////////////
// LINEAR PROBING CLASS - ABSTRACT BASE //
///////////////////////////////////////////////////////////////
template <typename Object>
class LinearProbeHash : public OpenAddressing<Object>
{
public:
LinearProbeHash(int capacity=107)
{
this->sz = 0;
this->N = capacity;
this->collisions = 0;
this->HashArray = new HashElement[this->N];
}
protected:
virtual int hash2(const int& k, const int& i)
{
return ((this->hash1(k)+i) % this->N);
}
};
I cannot figure this out. I get this error at several places:
Hash.h:55: error: ‘ElemPtr’ does not name a type
Hash.h:55: note: (perhaps ‘typename HashTable<Object>::ElemPtr’ was intended)
Does anyone know what I might be doing wrong. I have never done any serious implementation of templates with inheritance.