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

Deque.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 DEQUE_H_
00026 #define DEQUE_H_
00027 
00028 namespace Lamp{
00029 
00030 //------------------------------------------------------------------------------
00031 /**
00032  * デック
00033  *
00034  * このクラスは継承しないで下さい。
00035  */
00036 template <typename Type>
00037 class Deque{
00038 public:
00039     //--------------------------------------------------------------------------
00040     // 構築、破棄
00041     //--------------------------------------------------------------------------
00042     /**
00043      * コンストラクタ
00044      */
00045     Deque(){
00046         capacity_ = defaultCapacity_;
00047         array_ = new Type[capacity_];
00048         front_ = count_ = 0;
00049     }
00050 
00051     /**
00052      * コンストラクタ
00053      * @param capacity 初期キャパシティ。2の累乗が好ましい。
00054      */
00055     explicit Deque(int capacity){
00056         Assert(capacity > 0);
00057         capacity_ = capacity;
00058         array_ = new Type[capacity_];
00059         front_ = count_ = 0;
00060     }
00061 
00062     /**
00063      * デストラクタ
00064      */
00065     ~Deque(){ delete[] array_; }
00066 
00067     /**
00068      * クローン
00069      * @param destination クローン先デック
00070      */
00071     void clone(Deque& destination) const{
00072         delete[] destination.array_;
00073         destination.capacity_ = capacity_;
00074         destination.array_ = new Type[capacity_];
00075         destination.front_ = front_;
00076         destination.count_ = count_;
00077         // 文字列クラス等を正しくコピーするにはmemcpyでは駄目
00078         for(int i = 0; i < count_; i++){
00079             int index = (i + front_) % capacity_;
00080             destination.array_[index] = array_[index];
00081         }
00082     }
00083 
00084     //--------------------------------------------------------------------------
00085     // 情報の取得
00086     //--------------------------------------------------------------------------
00087     /**
00088      * 要素数の取得
00089      * @return 要素数
00090      */
00091     int getCount() const{ return count_; }
00092 
00093     /**
00094      * 空かどうか
00095      * @return 空ならtrueを返す
00096      */
00097     bool isEmpty() const{ return (count_ == 0); }
00098 
00099     /**
00100      * 要素の取得
00101      * @param index 取得する要素のインデックス
00102      * @return 要素
00103      */
00104     Type& get(int index) const{
00105         Assert(index >= 0);
00106         Assert(index < count_);
00107         return array_[(front_ + index) % capacity_];
00108     }
00109 
00110     /**
00111      * 要素の取得
00112      * @param index 取得する要素のインデックス
00113      * @return 要素
00114      */
00115     Type& operator [](int index) const{
00116         Assert(index >= 0);
00117         Assert(index < count_);
00118         return array_[(front_ + index) % capacity_];
00119     }
00120 
00121     /**
00122      * キャパシティの取得
00123      * @return キャパシティ
00124      */
00125     int getCapacity() const{ return capacity_; }
00126 
00127     /**
00128      * 前からの値の検索
00129      *
00130      * デックの前から値を検索し、発見できればそのインデックスを返します。
00131      * @param searchValue 検索する値
00132      * @return 値のインデックス。値が無ければ-1を返す。
00133      */
00134     int indexOf(const Type& searchValue) const{
00135         for(int i = 0; i < count_; i++){
00136             if(array_[(front_ + i) % capacity_] == searchValue){ return i; }
00137         }
00138         return -1;
00139     }
00140 
00141     /**
00142      * 後からの値の検索
00143      *
00144      * デックの後ろから値を検索し、発見できればそのインデックスを返します。
00145      * @param searchValue 検索する値
00146      * @return 値のインデックス。値が無ければ-1を返す。
00147      */
00148     int lastIndexOf(const Type& searchValue) const{
00149         for(int i = count_ - 1; i >= 0; i--){
00150             if(array_[(front_ + i) % capacity_] == searchValue){ return i; }
00151         }
00152         return -1;
00153     }
00154 
00155     //--------------------------------------------------------------------------
00156     // デックの変更
00157     //--------------------------------------------------------------------------
00158     /**
00159      * 先頭への要素の追加
00160      * @param value 要素
00161      */
00162     void pushFront(const Type& value){
00163         if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
00164         front_--;
00165         if(front_ < 0){ front_ += capacity_; }
00166         array_[front_] = value;
00167         count_++;
00168     }
00169 
00170     /**
00171      * 末尾への要素の追加
00172      * @param value 要素
00173      */
00174     void pushBack(const Type& value){
00175         if((count_ + 1) > capacity_){ resize(capacity_ * 2); }
00176         array_[(front_ + count_) % capacity_] = value;
00177         count_++;
00178     }
00179 
00180     /**
00181      * 先頭からの要素の削除
00182      * @return 削除した要素
00183      */
00184     Type popFront(){
00185         Assert(count_ > 0);
00186         int resultIndex = front_;
00187         front_ = (front_ + 1) % capacity_;
00188         count_--;
00189         return array_[resultIndex];
00190     }
00191 
00192     /**
00193      * 末尾からの要素の削除
00194      * @return 削除した要素
00195      */
00196     Type popBack(){
00197         Assert(count_ > 0);
00198         int resultIndex = (front_ + count_ - 1) % capacity_;
00199         count_--;
00200         return array_[resultIndex];
00201     }
00202 
00203     /**
00204      * 要素の設定
00205      * @param index 要素を設定するインデックス
00206      * @param value 要素
00207      */
00208     void set(int index, const Type& value) const{
00209         Assert(index >= 0);
00210         Assert(index < count_);
00211         array_[(front_ + index) % capacity_] = value;
00212     }
00213 
00214     /**
00215      * 要素の削除
00216      * @param index 削除する要素のインデックス
00217      * @return デックから削除した要素
00218      */
00219     Type remove(int index){
00220         Assert(index >= 0);
00221         Assert(index < count_);
00222         Assert(count_ > 0);
00223         Type result = array_[(front_ + index) % capacity_];
00224         count_--;
00225         if(index < (count_ / 2)){
00226             // 前を詰める
00227             for(int i = index - 1; i >= 0; i--){
00228                 int source = (front_ + i) % capacity_;
00229                 int destination = (source + 1) % capacity_;
00230                 array_[destination] = array_[source];
00231             }
00232             // 前インデックスもずらす
00233             front_ = (front_ + 1) % capacity_;
00234         }else{
00235             // 後を詰める
00236             for(int i = index; i < count_; i++){
00237                 int destination = (front_ + i) % capacity_;
00238                 int source = (destination + 1) % capacity_;
00239                 array_[destination] = array_[source];
00240             }
00241         }
00242         return result;
00243     }
00244 
00245     /**
00246      * 値による要素の削除
00247      *
00248      * デックの後ろから削除する値を検索し、同じ要素があれば削除します。
00249      * @param removeValue 削除する要素の値
00250      * @return 削除したインデックス。-1なら該当する要素無し。
00251      */
00252     int removeByValue(const Type& removeValue){
00253         int index = lastIndexOf(removeValue);
00254         if(index == -1){ return index; }
00255         remove(index);
00256         return index;
00257     }
00258 
00259     /**
00260      * 全要素を削除
00261      */
00262     void clear(){ front_ = count_ = 0; }
00263 
00264     /**
00265      * 全要素を削除
00266      * @param capacity クリア後のキャパシティ
00267      */
00268     void clear(int capacity){
00269         Assert(capacity >= 0);
00270         if(capacity <= 0){ capacity = 1; }
00271         delete[] array_;
00272         capacity_ = capacity;
00273         array_ = new Type[capacity_];
00274         front_ = count_ = 0;
00275     }
00276 
00277     /**
00278      * キャパシティの設定
00279      * @param newCapacity 新しいキャパシティ
00280      */
00281     void setCapacity(int newCapacity){
00282         Assert(newCapacity >= count_);
00283         resize(newCapacity);
00284     }
00285 
00286     /**
00287      * トリム
00288      *
00289      * 現在のサイズに合わせて使用メモリを最小にします。
00290      */
00291     void trim(){
00292         if(count_ == 0){ resize(1);}
00293         else{ resize(count_); }
00294     }
00295 
00296     //--------------------------------------------------------------------------
00297     // ソートとサーチ
00298     //--------------------------------------------------------------------------
00299     /**
00300      * ソート
00301      *
00302      * クイックソートでデックをソートします。<br>
00303      * compareの返り値を以下のようにすると昇順にソートされます。<br>
00304      * 第一引数が第二引数より大きいときは1以上<br>
00305      * 第一引数と大に引数が同じ場合は0<br>
00306      * 第一引数が第二引数より小さいときは-1以下
00307      * @param compare 比較関数。
00308      */
00309     void sort( int(*compare)(const Type*, const Type*) ){
00310         // 一塊にする
00311         if((front_ + count_) > capacity_){
00312             if(count_ != capacity_){
00313                 // 隙間を詰める
00314                 int destination = (front_ + count_) % capacity_;
00315                 for(int i = front_; i < capacity_; i++, destination++){
00316                     array_[destination] = array_[i];
00317                 }
00318 
00319             }
00320             front_ = 0;
00321         }
00322         qsort(array_ + front_, count_, sizeof(Type),
00323             (int(*)(const void*, const void*))compare);
00324     }
00325 
00326     /**
00327      * サーチ
00328      *
00329      * バイナリサーチでデックを検索します。<br>
00330      * デックは昇順にソートされている必要があります。<br>
00331      * 要素が見つからなかった場合はNULLを返します。
00332      * compareは以下のような返り値を返してください。<br>
00333      * 第一引数が第二引数より大きいときは1以上<br>
00334      * 第一引数と大に引数が同じ場合は0<br>
00335      * 第一引数が第二引数より小さいときは-1以下
00336      * @param key 検索する値
00337      * @param compare 比較関数
00338      * @return 検索結果、見つからなければNULL
00339      */
00340     Type* search(Type key, int(*compare)(const Type*, const Type*) ){
00341         return (Type*)bsearch(&key, array_ + front_, count_, sizeof(Type),
00342             (int(*)(const void*, const void*))compare);
00343     }
00344 
00345 private:
00346     // リサイズ
00347     void resize(int newCapacity){
00348         Assert(newCapacity > 0);
00349         Type* newArray = new Type[newCapacity];
00350         // 文字列クラス等を正しくコピーするにはmemcpyでは駄目
00351         for(int i = 0; i < count_; i++){
00352             int index = i + front_;
00353             int source = index % capacity_;
00354             int destination = index % newCapacity;
00355             newArray[destination] = array_[source];
00356         }
00357         delete[] array_;
00358         array_ = newArray;
00359         capacity_ = newCapacity;
00360     }
00361 
00362     // コピーコンストラクタの隠蔽
00363     Deque(const Deque& copy);
00364 
00365     // 代入コピーの隠蔽
00366     void operator =(const Deque& copy);
00367 
00368     // 配列
00369     Type* array_;
00370     // 前インデックス
00371     int front_;
00372     // 要素数
00373     int count_;
00374     // キャパシティ
00375     int capacity_;
00376     // デフォルトキャパシティ
00377     static const int defaultCapacity_ = 16;
00378 
00379 };
00380 
00381 //------------------------------------------------------------------------------
00382 } // End of namespace Lamp
00383 #endif // End of DEQUE_H_
00384 //------------------------------------------------------------------------------

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