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

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