template<typename T, typename Key = unsigned int>
class hash
{
struct node
{
Key _key;
T _data;
node *_next;
node(const Key &key, const T &x) : _key(key), _data(x), _next(NULL) { }
};
node **_head;
unsigned int _mod;
public:
hash(unsigned int mod = 13) : _mod(mod)
{
assert(mod);
_head = new node*[_mod];
memset(_head, 0, sizeof(node *) * _mod);
}
~hash()
{
clear();
delete[] _head;
}
void clear()
{
for(int i = 0; i < _mod; i++)
{
for(node *p; _head[i]; )
{
p = _head[i], _head[i] = _head[i]->_next;
delete p;
}
_head[i] = NULL;
}
}
void visit(void func(unsigned int, const Key &, const T &))
{
for(int i = 0; i < _mod; i++)
for(node *p = _head[i]; p; p = p->_next)
func(i + 1, p->_key, p->_data);
}
void push(const Key &key, const T &x)
{
unsigned int i = (unsigned int)key % _mod;
if(_head[i])
{
for(node *p = _head[i]; p && p->_key != key; p = p->_next)
{
if(!p->_next)
{
p->_next = new node(key, x);
break;
}
}
}
else
_head[i] = new node(key, x);
}
T * find(const Key &key)
{
unsigned int i = (unsigned int)key % _mod;
for(node *p = _head[i]; p; p = p->_next)
{
if(p->_key == key)
return &p->_data;
}
return NULL;
}
void pop(const Key &key)
{
unsigned int i = (unsigned int)key % _mod;
node *t = NULL, *pre = NULL;
if(_head[i])
{
if(_head[i]->_key == key)
t = _head[i], _head[i] = _head[i]->_next;
else
{
for(pre = _head[i], t = pre->_next; t; t = t->_next)
{
if(t->_key == key)
{
pre->_next = t->_next;
break;
}
}
}
}
if(t)
delete t;
}
void pop(const Key &key, T &data)
{
unsigned int i = (unsigned int)key % _mod;
node *t = NULL, *pre = NULL;
if(_head[i])
{
if(_head[i]->_key == key)
t = _head[i], _head[i] = _head[i]->_next;
else
{
for(pre = _head[i], t = pre->_next; t; t = t->_next)
{
if(t->_key == key)
{
pre->_next = t->_next;
break;
}
}
}
}
if(t)
{
data = t->_data;
delete t;
}
}
};