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 //------------------------------------------------------------------------------