Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound Members | File Members

HashMap.h

Go to the documentation of this file.
00001 //------------------------------------------------------------------------------
00002 // Lamp : Open source game middleware
00003 // Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
00004 //
00005 // This library is free software; you can redistribute it and/or
00006 // modify it under the terms of the GNU Lesser General Public
00007 // License as published by the Free Software Foundation; either
00008 // version 2.1 of the License, or (at your option) any later version.
00009 //
00010 // This library is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013 // Lesser General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU Lesser General Public
00016 // License along with this library; if not, write to the Free Software
00017 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00018 //------------------------------------------------------------------------------
00019 
00020 /** @file
00021  * ハッシュマップヘッダ
00022  * @author Junpee
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  * HashKeyは以下の4つのメソッドを実装している必要があります。<br>
00039  * HashKey();<br>
00040  * HashKey& operator =(const HashKey& copy);<br>
00041  * bool equals(const HashKey& compare) const;<br>
00042  * u_int getHashCode() const;<br>
00043  * ValueTypeは通常はポインタ型を指定して下さい。
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      * @param capacity 初期容量
00072      * @param loadFactor 負荷係数
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      * @param destination クローン先ハッシュマップ
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      * @return 要素数
00115      */
00116     int getCount() const{ return count_; }
00117 
00118     /**
00119      * 空かどうか
00120      * @return 空ならtrueを返す
00121      */
00122     bool isEmpty() const{ return (count_ == 0); }
00123 
00124     /**
00125      * 要素の取得
00126      * @param key 取得する要素のキー
00127      * @return 要素。該当するキーが無ければNULL。
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      * @return 容量
00145      */
00146     int getCapacity() const{ return capacity_; }
00147 
00148     /**
00149      * 負荷係数の取得
00150      * @return 負荷係数
00151      */
00152     float getLoadFactor() const{ return loadFactor_; }
00153 
00154     /**
00155      * 配列の取得
00156      * @param arrayList [out]データを格納するArrayList
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      * @param key ハッシュキー。同じキーは登録不可。
00181      * @param value 格納する値。NULLは不可。
00182      * @return 成功すればture、すでに同じ要素があればfalseを返し、値は追加されない。
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      * @param key ハッシュキー
00226      * @return 削除された値。見つからなければNULL
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                 // 1番目の要素だけを削除
00239                 item->value_ = NULL;
00240                 item->key_ = HashKey();
00241             }else{
00242                 // 2番目の要素を1番目に代入して削除
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      * @param capacity 設定するキャパシティ
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      * @param detail 詳細出力
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 } // End of namespace Lamp
00421 #endif // End of HASH_MAP_H_
00422 //------------------------------------------------------------------------------

Generated on Wed Mar 16 10:29:31 2005 for Lamp by doxygen 1.3.2