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

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