00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #ifndef HASH_MAP_H_
00026 #define HASH_MAP_H_
00027
00028
00029 #include <Core/Container/ArrayList.h>
00030
00031 namespace Lamp{
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 template <typename HashKey, typename ValueType>
00046 class HashMap{
00047 public:
00048
00049
00050
00051
00052
00053
00054 template <typename HashKey, typename ValueType>
00055 class HashData{
00056 public:
00057
00058 HashData() : value_(NULL){}
00059
00060
00061 HashKey key_;
00062
00063 ValueType value_;
00064 };
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074 explicit HashMap(int capacity = 16, float loadFactor = 0.75f) :
00075 capacity_(capacity), loadFactor_(loadFactor), count_(0){
00076 Assert(capacity_ > 0);
00077 maxSize_ = (int)(capacity_ * loadFactor_);
00078 array_ = new HashItem<HashKey, ValueType>[capacity_];
00079 }
00080
00081
00082
00083
00084 ~HashMap(){
00085 Assert(count_ == 0);
00086 delete[] array_;
00087 }
00088
00089
00090
00091
00092
00093 void cloneTo(HashMap* destination) const{
00094 Assert(destination->getCount() == 0);
00095 destination->loadFactor_ = loadFactor_;
00096 destination->setCapacity(capacity_);
00097 for(int i = 0; i < capacity_; i++){
00098 HashItem<HashKey, ValueType>* item = &array_[i];
00099
00100 if(item->value_ == NULL){ continue; }
00101 while(true){
00102 destination->put(item->key_, item->value_);
00103 item = item->next_;
00104 if(item == NULL){ break; }
00105 }
00106 }
00107 }
00108
00109
00110
00111
00112
00113
00114
00115
00116 int getCount() const{ return count_; }
00117
00118
00119
00120
00121
00122 bool isEmpty() const{ return (count_ == 0); }
00123
00124
00125
00126
00127
00128
00129 ValueType get(const HashKey& key) const{
00130
00131 u_int hashCode = key.getHashCode();
00132 HashItem<HashKey, ValueType>* item;
00133 item = &array_[hashCode % capacity_];
00134 if(item->value_ == NULL){ return NULL; }
00135 while(true){
00136 if(item->key_.equals(key)){ return item->value_; }
00137 item = item->next_;
00138 if(item == NULL){ return NULL; }
00139 }
00140 }
00141
00142
00143
00144
00145
00146 int getCapacity() const{ return capacity_; }
00147
00148
00149
00150
00151
00152 float getLoadFactor() const{ return loadFactor_; }
00153
00154
00155
00156
00157
00158 void toArray(ArrayList< HashData<HashKey, ValueType> >* arrayList) const{
00159 if(count_ == 0){ return; }
00160 arrayList->clear(count_);
00161 for(int i = 0; i < capacity_; i++){
00162 HashItem<HashKey, ValueType>* item = &array_[i];
00163 if(item->value_ == NULL){ continue; }
00164 while(true){
00165 HashData<HashKey, ValueType> data;
00166 data.key_ = item->key_;
00167 data.value_ = item->value_;
00168 arrayList->add(data);
00169 item = item->next_;
00170 if(item == NULL){ break; }
00171 }
00172 }
00173 }
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184 bool put(HashKey key, ValueType value){
00185 Assert(value != NULL);
00186 if(value == NULL){ return false; }
00187
00188 if(count_ + 1 > maxSize_){
00189 int newCapacity = capacity_ * 2;
00190 while(true){
00191 maxSize_ = (int)(newCapacity * loadFactor_);
00192 if(count_ + 1 <= maxSize_){ break; }
00193 newCapacity *= 2;
00194 }
00195 setCapacity(newCapacity);
00196 }
00197
00198 u_int hashCode = key.getHashCode();
00199
00200 HashItem<HashKey, ValueType>* item;
00201 item = &array_[hashCode % capacity_];
00202 if(item->value_ == NULL){
00203 item->key_ = key;
00204 item->value_ = value;
00205 count_++;
00206 return true;
00207 }
00208 while(true){
00209
00210 if(item->key_.equals(key)){ return false; }
00211
00212 if(item->next_ == NULL){
00213 HashItem<HashKey, ValueType>* newItem;
00214 newItem = new HashItem<HashKey, ValueType>(key, value);
00215 item->next_ = newItem;
00216 count_++;
00217 return true;
00218 }
00219 item = item->next_;
00220 }
00221 }
00222
00223
00224
00225
00226
00227
00228 ValueType remove(HashKey key){
00229
00230 u_int hashCode = key.getHashCode();
00231 HashItem<HashKey, ValueType>* item = &array_[hashCode % capacity_];
00232 if(item->value_ == NULL){ return NULL; }
00233
00234 ValueType returnValue = NULL;
00235 if(item->key_.equals(key)){
00236 returnValue = item->value_;
00237 if(item->next_ == NULL){
00238
00239 item->value_ = NULL;
00240 item->key_ = HashKey();
00241 }else{
00242
00243 HashItem<HashKey, ValueType>* nextItem = item->next_;
00244 *item = *nextItem;
00245 delete nextItem;
00246 }
00247 count_--;
00248 return returnValue;
00249 }
00250
00251 HashItem<HashKey, ValueType>* nextItem;
00252 while(true){
00253 nextItem = item->next_;
00254 if(nextItem == NULL){ return NULL; }
00255 if(nextItem->key_.equals(key)){
00256 returnValue = nextItem->value_;
00257 item->next_ = nextItem->next_;
00258 delete nextItem;
00259 count_--;
00260 return returnValue;
00261 }
00262 item = nextItem;
00263 }
00264 }
00265
00266
00267
00268
00269 void clear(){
00270 for(int i = 0; i < capacity_; i++){
00271 HashItem<HashKey, ValueType>* item = &array_[i];
00272 HashItem<HashKey, ValueType>* nextItem = item->next_;
00273
00274 if(item->value_ == NULL){ continue; }
00275 item->key_ = HashKey();
00276 item->value_ = NULL;
00277 item->next_ = NULL;
00278 count_--;
00279 while(true){
00280 item = nextItem;
00281 if(item == NULL){ break; }
00282 nextItem = item->next_;
00283 item->key_ = HashKey();
00284 item->value_ = NULL;
00285 item->next_ = NULL;
00286 count_--;
00287 delete item;
00288 }
00289 }
00290 }
00291
00292
00293
00294
00295
00296 void setCapacity(int capacity){
00297 HashMap<HashKey, ValueType*> hashMap(capacity, loadFactor_);
00298 int listSize = count_, listCounter = 0;
00299 HashKey* keyList = new HashKey[listSize];
00300 ValueType* valueList = new ValueType[listSize];
00301 for(int i = 0; i < capacity_; i++){
00302 HashItem<HashKey, ValueType>* item = &array_[i];
00303 if(item->value_ == NULL){ continue; }
00304 while(true){
00305 keyList[listCounter] = item->key_;
00306 valueList[listCounter] = item->value_;
00307 listCounter++;
00308 item = item->next_;
00309 if(item == NULL){ break; }
00310 }
00311 }
00312 clear();
00313 delete[] array_;
00314 capacity_ = capacity;
00315 maxSize_ = (int)(capacity_ * loadFactor_);
00316 array_ = new HashItem<HashKey, ValueType>[capacity_];
00317
00318 for(int i = 0;i < listSize;i++){ put(keyList[i], valueList[i]); }
00319 delete[] keyList;
00320 delete[] valueList;
00321 }
00322
00323
00324
00325
00326 void trim(){
00327 int newCapacity = 1, maxSize;
00328 while(true){
00329 maxSize = (int)(newCapacity * loadFactor_);
00330 if(count_ <= maxSize){ break; }
00331 newCapacity *= 2;
00332 }
00333 setCapacity(newCapacity);
00334 }
00335
00336
00337 #ifdef _DEBUG
00338
00339
00340
00341
00342 void debugPrint(bool detail){
00343 DebugOut("\nCapacity %d, LoadFactor %.2f MaxSize %d Size %d ",
00344 capacity_, loadFactor_, maxSize_, count_);
00345 if(detail){ DebugOut("\n"); }
00346 int allocCount = 0;
00347 for(int i = 0;i < capacity_;i++){
00348 HashItem<HashKey, ValueType>* item = &array_[i];
00349 int count = 0;
00350
00351 while(true){
00352 count++;
00353 if(count >= 2){ allocCount++; }
00354 if(detail){
00355 if(item->value_ != NULL){ DebugOut("*"); }
00356 }
00357 if(item->next_ == NULL){ break; }
00358 item = item->next_;
00359 }
00360 if(detail){ DebugOut("\n"); }
00361 }
00362 DebugOut("allocCount %d allocRate %.1f%%\n",
00363 allocCount, (float)allocCount / count_ * 100.f);
00364 }
00365 #endif
00366
00367 private:
00368
00369
00370 template <typename HashKey, typename ValueType>
00371 class HashItem{
00372 friend class HashMap;
00373 public:
00374
00375 HashItem() : key_(), value_(NULL), next_(NULL){}
00376
00377
00378 HashItem(HashKey key, ValueType value) :
00379 key_(), value_(value), next_(NULL){
00380 key_ = key;
00381 }
00382
00383
00384 HashItem& operator =(const HashItem& copy){
00385 key_ = copy.key_;
00386 value_ = copy.value_;
00387 next_ = copy.next_;
00388 return *this;
00389 }
00390
00391
00392 HashKey key_;
00393
00394 ValueType value_;
00395
00396 HashItem* next_;
00397 };
00398
00399
00400
00401 HashMap(const HashMap& copy);
00402
00403
00404 void operator =(const HashMap& copy);
00405
00406
00407
00408 int capacity_;
00409
00410 float loadFactor_;
00411
00412 int maxSize_;
00413
00414 int count_;
00415
00416 HashItem<HashKey, ValueType>* array_;
00417 };
00418
00419
00420 }
00421 #endif // End of HASH_MAP_H_
00422