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 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
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
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
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
00090
00091 int getCount() const{ return count_; }
00092
00093
00094
00095
00096
00097 bool isEmpty() const{ return (count_ == 0); }
00098
00099
00100
00101
00102
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
00113
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
00124
00125 int getCapacity() const{ return capacity_; }
00126
00127
00128
00129
00130
00131
00132
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
00146
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
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
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
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
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
00206
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
00217
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
00250
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
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
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
00303
00304
00305
00306
00307
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
00330
00331
00332
00333
00334
00335
00336
00337
00338
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
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 }
00383 #endif // End of DEQUE_H_
00384