const int DefaultSize = 100;
enum KindofStatus {Active, Empty, Deleted};
template<class E, class K>
class HashTable
{
public:
HashTable(int d, int sz = DefaultSize);
~HashTable() {delete []ht_; delete []info;}
HashTable<E, K>& operator = (const HashTable<E, K>& rhs);
bool Search(const K k1, const E& el) const;
bool Insert(const E& el);
bool Remove(const K k1, const E& el);
void makeEmpty();
private:
int divitor_;
int current_size_;
int table_size_;
E* ht_;
KindofStatus* info;
int find_pos(const K k1) const;
int operator == (E& el) {return *this == el;}
int operator != (E& el) {return *this != el;}
};
template<class E, class K>
int HashTable<E, K>::find_pos(const K k1) const
{
int i = k1%divitor_;
int j = i;
do
{
if(info[j] == Empty || info[j] == Active && ht_[j] == k1)
return j;
j = (j + 1) % table_size_;
}while(j !=i);
return j;
}
template<class E, class K>
bool HashTable<E, K>::Search(const K k1, const E& el) const
{
int i = find_pos(k1);
if(info[i] != Active || ht_[i] != k1)
return false;
el = ht_[i];
return true;
}
template<class E, class K>
void HashTable<E, K>::makeEmpty()
{
for(int i=0; i<table_size_; i++)
{
info[i] = Empty;
current_size_ = 0;
}
}
template<class E, class K>
bool HashTable<E, K>::Insert(const E& el)
{
K k1 = el; // overload
int i = find_pos(k1);
if(info[i] != Active)
{
ht_[i] = el;
current_size_ ++;
info[i]++;
return true;
}
if(info[i] == Active && ht_[i] == k1)
{
cout<<"this key has been contained"<<endl;
return false;
}
cout<<"the table is full and can not be insert!"<<endl;
return false;
}
template<class E, class K>
HashTable<E, K>& HashTable<E, K>::operator = (const HashTable<E, K>& rhs)
{
if( *this != rhs)
{
delete []ht_;
delete []info;
table_size_ = rhs.table_size_;
divitor_ = rhs.divitor_;
current_size_ = rhs.current_size_;
ht_ = new E[table_size_];
info = new KindofStatus[table_size_];
for(int i=0; i<table_size_; i++)
{
ht_[i] = rhs.ht_[i];
info[i] = rhs.info[i];
}
}
return *this;
}
template<class E, class K>
bool HashTable<E, K>::Remove(const K k1, const E& el)
{
int i = find_pos(k1);
if(info[i] == Active && ht_[i] == k1)
{
info[i] = Deleted;
current_size_--;
return true;
}
return false;
}