00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 const int InitialBuckets = 4;
00017 const int ResizeRatio = 3;
00018 const int IncreaseSizeBy = 4;
00019
00020 #include "copyright.h"
00021
00022
00023
00024
00025
00026
00027
00028 template <class Key, class T>
00029 HashTable<Key,T>::HashTable(Key (*get)(T x), unsigned (*hFunc)(Key x))
00030 {
00031 numItems = 0;
00032 InitBuckets(InitialBuckets);
00033 getKey = get;
00034 hash = hFunc;
00035 }
00036
00037
00038
00039
00040
00041
00042
00043 template <class Key, class T>
00044 void
00045 HashTable<Key,T>::InitBuckets(int sz)
00046 {
00047 numBuckets = sz;
00048 buckets = new Bucket[numBuckets];
00049 for (int i = 0; i < sz; i++) {
00050 buckets[i] = new List<T>;
00051 }
00052 }
00053
00054
00055
00056
00057
00058
00059 template <class Key, class T>
00060 HashTable<Key,T>::~HashTable()
00061 {
00062 ASSERT(IsEmpty());
00063 DeleteBuckets(buckets, numBuckets);
00064 }
00065
00066
00067
00068
00069
00070
00071
00072 template <class Key, class T>
00073 void
00074 HashTable<Key,T>::DeleteBuckets(List<T> **table, int sz)
00075 {
00076 for (int i = 0; i < sz; i++) {
00077 delete table[i];
00078 }
00079 delete [] table;
00080 }
00081
00082
00083
00084
00085
00086
00087 template <class Key, class T>
00088 int
00089 HashTable<Key, T>::HashValue(Key key) const
00090 {
00091 int result = (*hash)(key) % numBuckets;
00092 ASSERT(result >= 0 && result < numBuckets);
00093 return result;
00094 }
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108 template <class Key, class T>
00109 void
00110 HashTable<Key,T>::Insert(T item)
00111 {
00112 Key key = getKey(item);
00113
00114 ASSERT(!IsInTable(key));
00115
00116 if ((numItems / numBuckets) >= ResizeRatio) {
00117 ReHash();
00118 }
00119
00120 buckets[HashValue(key)]->Append(item);
00121 numItems++;
00122
00123 ASSERT(IsInTable(key));
00124 }
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134 template <class Key, class T>
00135 void
00136 HashTable<Key,T>::ReHash()
00137 {
00138 Bucket *oldTable = buckets;
00139 int oldSize = numBuckets;
00140 T item;
00141
00142 SanityCheck();
00143 InitBuckets(numBuckets * IncreaseSizeBy);
00144
00145 for (int i = 0; i < oldSize; i++) {
00146 while (!oldTable[i]->IsEmpty()) {
00147 item = oldTable[i]->RemoveFront();
00148 buckets[HashValue(getKey(item))]->Append(item);
00149 }
00150 }
00151 DeleteBuckets(oldTable, oldSize);
00152 SanityCheck();
00153 }
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 template <class Key, class T>
00167 bool
00168 HashTable<Key,T>::FindInBucket(int bucket,
00169 Key key, T *itemPtr) const
00170 {
00171 ListIterator<T> iterator(buckets[bucket]);
00172
00173 for (; !iterator.IsDone(); iterator.Next()) {
00174 if (key == getKey(iterator.Item())) {
00175 *itemPtr = iterator.Item();
00176 return TRUE;
00177 }
00178 }
00179 *itemPtr = NULL;
00180 return FALSE;
00181 }
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191 template <class Key, class T>
00192 bool
00193 HashTable<Key,T>::Find(Key key, T *itemPtr) const
00194 {
00195 int bucket = HashValue(key);
00196
00197 return FindInBucket(bucket, key, itemPtr);
00198 }
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208 template <class Key, class T>
00209 T
00210 HashTable<Key,T>::Remove(Key key)
00211 {
00212 int bucket = HashValue(key);
00213 T item;
00214 bool found = FindInBucket(bucket, key, &item);
00215
00216 ASSERT(found);
00217
00218 buckets[bucket]->Remove(item);
00219 numItems--;
00220
00221 ASSERT(!IsInTable(key));
00222 return item;
00223 }
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233 template <class Key,class T>
00234 void
00235 HashTable<Key,T>::Apply(void (*func)(T)) const
00236 {
00237 for (int bucket = 0; bucket < numBuckets; bucket++) {
00238 buckets[bucket]->Apply(func);
00239 }
00240 }
00241
00242
00243
00244
00245
00246
00247
00248
00249 template <class Key,class T>
00250 int
00251 HashTable<Key,T>::FindNextFullBucket(int bucket) const
00252 {
00253 for (; bucket < numBuckets; bucket++) {
00254 if (!buckets[bucket]->IsEmpty()) {
00255 break;
00256 }
00257 }
00258 return bucket;
00259 }
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270 template <class Key, class T>
00271 void
00272 HashTable<Key,T>::SanityCheck() const
00273 {
00274 int numFound = 0;
00275 ListIterator<T> *iterator;
00276
00277 for (int i = 0; i < numBuckets; i++) {
00278 buckets[i]->SanityCheck();
00279 numFound += buckets[i]->NumInList();
00280 iterator = new ListIterator<T>(buckets[i]);
00281 for (; !iterator->IsDone(); iterator->Next()) {
00282 ASSERT(i == HashValue(getKey(iterator->Item())));
00283 }
00284 delete iterator;
00285 }
00286 ASSERT(numItems == numFound);
00287
00288 }
00289
00290
00291
00292
00293
00294
00295 template <class Key, class T>
00296 void
00297 HashTable<Key,T>::SelfTest(T *p, int numEntries)
00298 {
00299 int i;
00300 HashIterator<Key, T> *iterator = new HashIterator<Key,T>(this);
00301
00302 SanityCheck();
00303 ASSERT(IsEmpty());
00304 for (; !iterator->IsDone(); iterator->Next()) {
00305 ASSERTNOTREACHED();
00306 }
00307 delete iterator;
00308
00309 for (i = 0; i < numEntries; i++) {
00310 Insert(p[i]);
00311 ASSERT(IsInTable(getKey(p[i])));
00312 ASSERT(!IsEmpty());
00313 }
00314
00315
00316 for (i = 0; i < numEntries; i++) {
00317 ASSERT(Remove(getKey(p[i])) == p[i]);
00318 }
00319
00320 ASSERT(IsEmpty());
00321 SanityCheck();
00322 }
00323
00324
00325
00326
00327
00328
00329
00330
00331 template <class Key, class T>
00332 HashIterator<Key,T>::HashIterator(HashTable<Key,T> *tbl)
00333 {
00334 table = tbl;
00335 bucket = table->FindNextFullBucket(0);
00336 bucketIter = NULL;
00337 if (bucket < table->numBuckets) {
00338 bucketIter = new ListIterator<T>(table->buckets[bucket]);
00339 }
00340 }
00341
00342
00343
00344
00345
00346
00347 template <class Key,class T>
00348 void
00349 HashIterator<Key,T>::Next()
00350 {
00351 bucketIter->Next();
00352 if (bucketIter->IsDone()) {
00353 delete bucketIter;
00354 bucketIter = NULL;
00355 bucket = table->FindNextFullBucket(++bucket);
00356 if (bucket < table->numBuckets) {
00357 bucketIter = new ListIterator<T>(table->buckets[bucket]);
00358 }
00359 }
00360 }