-
Notifications
You must be signed in to change notification settings - Fork 1
/
hash.h
96 lines (69 loc) · 1.92 KB
/
hash.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/***********************************************************************
* hash.h
* Simple hash table
* Maurizio Palesi [[email protected]]
***********************************************************************
*/
#ifndef __HASH_H__
#define __HASH_H__
#include <cassert>
#include <vector>
using namespace std;
template <class T>
class Hash
{
public:
vector<vector<T> > vhash;
//----------------------------------------------------------------------
Hash(int _size)
{
vhash.resize(_size);
}
//----------------------------------------------------------------------
virtual bool equal(T &t1, T &t2) = 0;
//----------------------------------------------------------------------
virtual unsigned int T2Index(T &t) = 0;
//----------------------------------------------------------------------
void addT(T &t)
{
unsigned int index = T2Index(t);
assert( index < vhash.size() );
vhash[index].push_back(t);
}
//----------------------------------------------------------------------
T * searchT(T &t)
{
unsigned int index = T2Index(t);
assert( index < vhash.size() );
bool found = false;
unsigned int s = vhash[index].size();
unsigned int i = 0;
while (i<s && !found)
{
if (equal(vhash[index][i], t))
found = true;
else
i++;
}
return found ? &(vhash[index][i]) : NULL;
}
//----------------------------------------------------------------------
unsigned int avgLen()
{
unsigned int len = 0;
for (int i=0; i<vhash.size(); i++)
len += vhash[i].size();
return (len/vhash.size());
}
//----------------------------------------------------------------------
unsigned int maxLen()
{
unsigned int max = 0;
for (int i=0; i<vhash.size(); i++)
if (max < vhash[i].size())
max = vhash[i].size();
return max;
}
//----------------------------------------------------------------------
};
#endif