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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/*:*
*: File: ./src/hmap.h
*:
*: yChat; Homepage: www.yChat.org; Version 0.5.6-BASIC
*:
*: Copyright (C) 2003, 2004 Paul C. Buetow, Volker Richter
*: Copyright (C) 2005 EXA Digital Solutions GbR
*:
*: This program is free software; you can redistribute it and/or
*: modify it under the terms of the GNU General Public License
*: as published by the Free Software Foundation; either version 2
*: of the License, or (at your option) any later version.
*:
*: This program is distributed in the hope that it will be useful,
*: but WITHOUT ANY WARRANTY; without even the implied warranty of
*: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
*: GNU General Public License for more details.
*:
*: You should have received a copy of the GNU General Public License
*: along with this program; if not, write to the Free Software
*: Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*:*/
#pragma warning(disable:4786)
#ifndef hmap_h
#define hmap_h
#include <vector>
#include "incl.h"
using namespace std;
// void add_elem( obj_type x, key_type k ) --> Insert x
// void del_elem( key_type k ) --> Remove x
// obj_type get_elem( key_type k ) --> Return item that matches x
// void make_empty( ) --> Remove all items
template <class obj_type, class key_type>
class hmap
{
private:
enum entry_type
{
ACTIVE, EMPTY, DELETED
};
struct hash_entry
{
obj_type element;
key_type key;
entry_type info;
hash_entry( const obj_type &e = obj_type( ), const key_type &k = key_type( ), entry_type i = EMPTY ) : element( e ), key( k ), info( i )
{ }
}
;
int occupied;
virtual bool isActive( int currentPos ) const;
virtual void rehash( );
virtual bool isPrime ( int n ) const;
virtual int nextPrime( int n ) const;
double maxOccupiedPercentage;
protected:
int lookups;
unsigned int hash( const string &key ) const;
vector<hash_entry> array;
public:
hmap( double moc );
virtual int findPos ( const key_type &k );
virtual void make_empty( );
virtual void add_elem ( const obj_type &x, const key_type &k );
virtual void del_elem ( const key_type &k );
virtual obj_type get_elem ( const key_type &k );
virtual void run_func( void (*func)(obj_type) );
virtual void run_func( void (*func)(obj_type, void*), void* v_arg );
// inline:
void getSize()
{
int size = 0;
for( int j = 0; j < array.size( ); j++ )
if (array[ j ].info == ACTIVE)
size++;
return size;
};
int getLookups()
{
return lookups;
};
int getCapacity()
{
return array.size();
};
double getLambda()
{
return static_cast<double>(getSize())/static_cast<double>(getCapacity());
}
obj_type& operator[]( key_type &k )
{
return get_elem( k );
}
};
template <class obj_type, class key_type>
class linearhmap : public hmap<obj_type, key_type>
{
public:
linearhmap(double moc) : hmap<obj_type, key_type>(moc)
{}
;
virtual int findPos( const key_type &k )
{
int collisionNum = 0;
int currentPos = hash( k ) % hmap<obj_type, key_type>::array.size( );
hmap<obj_type, key_type>::lookups++;
while( hmap<obj_type, key_type>::array[ currentPos ].info != hmap<obj_type, key_type>::EMPTY &&
hmap<obj_type, key_type>::array[ currentPos ].key != k )
{
hmap<obj_type, key_type>::lookups ++;
currentPos++;
if( currentPos >= hmap<obj_type, key_type>::array.size( ) )
currentPos -= hmap<obj_type, key_type>::array.size( );
}
return currentPos;
}
};
#include "hmap.cpp"
#endif
|
