00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
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
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
00070
00071 void clone(ArrayList& destination) const{
00072 delete[] destination.array_;
00073 destination.capacity_ = capacity_;
00074 destination.array_ = new Type[capacity_];
00075
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
00086
00087 int getCount() const{ return count_; }
00088
00089
00090
00091
00092
00093 bool isEmpty() const{ return (count_ == 0); }
00094
00095
00096
00097
00098
00099
00100 Type& get(int index) const{
00101 Assert(index >= 0);
00102 Assert(index < count_);
00103 return array_[index];
00104 }
00105
00106
00107
00108
00109
00110
00111 Type& operator [](int index) const{
00112 Assert(index >= 0);
00113 Assert(index < count_);
00114 return array_[index];
00115 }
00116
00117
00118
00119
00120
00121 int getCapacity() const{ return capacity_; }
00122
00123
00124
00125
00126
00127
00128
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
00142
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
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
00167
00168
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
00179
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
00196
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
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
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
00252
00253
00254
00255
00256
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
00267
00268
00269
00270
00271
00272
00273
00274
00275
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
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 }
00313 #endif // End of ARRAY_LIST_H_
00314