C:/Active/libraries/cxutils/2.0/include/cxutils/circulararray.h
Go to the documentation of this file.
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 00026 00027 00028 00029 00030 00031 00032 00033 00034 00035 00036 00037 00038 00039 00040 00041 00042 #ifndef __CXUTILS_CIRCULAR_ARRAY_H 00043 #define __CXUTILS_CIRCULAR_ARRAY_H 00044 00045 #include <stdlib.h> 00046 #include <assert.h> 00047 00048 namespace CxUtils 00049 { 00064 template <class T> 00065 class CircularArray 00066 { 00067 public: 00075 class iterator 00076 { 00077 friend class CircularArray; 00078 public: 00079 iterator() : mpArray(0), mIndex(0) {} 00080 iterator(const iterator& itr) : mpArray(itr.mpArray), mIndex(itr.mIndex) {} 00081 ~iterator() {} 00082 T& operator->() 00083 { 00084 return *(*this); 00085 } 00086 T& operator*() 00087 { 00088 int pos = 0; 00089 pos = ((int)(mpArray->mPosition)) - ((int)(mpArray->mElements)) + mIndex; 00090 if(pos < 0) 00091 { 00092 pos += (int)mpArray->mReserved; 00093 } 00094 return mpArray->mpArray[pos]; 00095 } 00096 iterator& operator=(const iterator& itr) 00097 { 00098 mpArray = itr.mpArray; 00099 mIndex = itr.mIndex; 00100 return *this; 00101 } 00102 iterator& operator++(int) 00103 { 00104 ++mIndex; 00105 return *this; 00106 } 00107 iterator& operator++() 00108 { 00109 mIndex++; 00110 return *this; 00111 } 00112 bool operator!=(const iterator& itr) const 00113 { 00114 if(mpArray == itr.mpArray && mIndex < itr.mIndex) 00115 { 00116 return true; 00117 } 00118 return false; 00119 } 00120 private: 00121 CircularArray<T>* mpArray; 00122 unsigned int mIndex; 00123 }; 00131 class reverse_iterator 00132 { 00133 friend class CircularArray; 00134 public: 00135 reverse_iterator() : mpArray(0), mIndex(0) {} 00136 reverse_iterator(const reverse_iterator& itr) : mpArray(itr.mpArray), mIndex(itr.mIndex) {} 00137 ~reverse_iterator() {} 00138 T& operator->() 00139 { 00140 return *(*this); 00141 } 00142 T& operator*() 00143 { 00144 int pos = 0; 00145 pos = ((int)(mpArray->mPosition)) - ((int)(mIndex)) - 1; 00146 if(pos < 0) 00147 { 00148 pos += (int)mpArray->mReserved; 00149 } 00150 return mpArray->mpArray[pos]; 00151 } 00152 reverse_iterator& operator=(const iterator& itr) 00153 { 00154 mpArray = itr.mpArray; 00155 mIndex = itr.mIndex; 00156 return *this; 00157 } 00158 reverse_iterator& operator++(int) 00159 { 00160 ++mIndex; 00161 return *this; 00162 } 00163 reverse_iterator& operator++() 00164 { 00165 mIndex++; 00166 return *this; 00167 } 00168 bool operator!=(const iterator& itr) 00169 { 00170 if(mpArray == itr.mpArray && mIndex < itr.mIndex) 00171 { 00172 return true; 00173 } 00174 return false; 00175 } 00176 private: 00177 CircularArray<T>* mpArray; 00178 unsigned int mIndex; 00179 }; 00187 class const_iterator 00188 { 00189 friend class CircularArray; 00190 public: 00191 const_iterator() : mpArray(0), mIndex(0) {} 00192 const_iterator(const const_iterator& itr) : mpArray(itr.mpArray), mIndex(itr.mIndex) {} 00193 ~const_iterator() {} 00194 const T& operator->() const 00195 { 00196 return *(*this); 00197 } 00198 const T& operator*() const 00199 { 00200 int pos = 0; 00201 pos = ((int)(mpArray->mPosition)) - ((int)(mpArray->mElements)) + mIndex; 00202 if(pos < 0) 00203 { 00204 pos += (int)mpArray->mReserved; 00205 } 00206 return mpArray->mpArray[pos]; 00207 } 00208 const_iterator& operator=(const iterator& itr) 00209 { 00210 mpArray = itr.mpArray; 00211 mIndex = itr.mIndex; 00212 return *this; 00213 } 00214 const_iterator& operator=(const const_iterator& itr) 00215 { 00216 mpArray = itr.mpArray; 00217 mIndex = itr.mIndex; 00218 return *this; 00219 } 00220 const_iterator& operator++(int) 00221 { 00222 ++mIndex; 00223 return *this; 00224 } 00225 const_iterator& operator++() 00226 { 00227 mIndex++; 00228 return *this; 00229 } 00230 bool operator!=(const iterator& itr) 00231 { 00232 if(mpArray == itr.mpArray && mIndex < itr.mIndex) 00233 { 00234 return true; 00235 } 00236 return false; 00237 } 00238 bool operator!=(const const_iterator& itr) 00239 { 00240 if(mpArray == itr.mpArray && mIndex < itr.mIndex) 00241 { 00242 return true; 00243 } 00244 return false; 00245 } 00246 private: 00247 CircularArray<T>* mpArray; 00248 unsigned int mIndex; 00249 }; 00257 class const_reverse_iterator 00258 { 00259 friend class CircularArray; 00260 public: 00261 const_reverse_iterator() : mpArray(0), mIndex(0) {} 00262 const_reverse_iterator(const const_reverse_iterator& itr) : mpArray(itr.mpArray), mIndex(itr.mIndex) {} 00263 ~const_reverse_iterator() {} 00264 const T& operator->() const 00265 { 00266 return *(*this); 00267 } 00268 const T& operator*() const 00269 { 00270 int pos = 0; 00271 pos = ((int)(mpArray->mPosition)) - ((int)(mIndex)) - 1; 00272 if(pos < 0) 00273 { 00274 pos += (int)mpArray->mReserved; 00275 } 00276 return mpArray->mpArray[pos]; 00277 } 00278 const_reverse_iterator& operator=(const const_iterator& itr) 00279 { 00280 mpArray = itr.mpArray; 00281 mIndex = itr.mIndex; 00282 return *this; 00283 } 00284 const_reverse_iterator& operator++(int) 00285 { 00286 ++mIndex; 00287 return *this; 00288 } 00289 const_reverse_iterator& operator++() 00290 { 00291 mIndex++; 00292 return *this; 00293 } 00294 bool operator!=(const const_iterator& itr) 00295 { 00296 if(mpArray == itr.mpArray && mIndex < itr.mIndex) 00297 { 00298 return true; 00299 } 00300 return false; 00301 } 00302 private: 00303 CircularArray<T>* mpArray; 00304 unsigned int mIndex; 00305 }; 00306 CircularArray(const unsigned int size = 5); 00307 CircularArray(const CircularArray<T> &another); 00308 ~CircularArray(); 00309 iterator begin() 00310 { 00311 iterator itr; 00312 itr.mpArray = (CircularArray<T> *)this; 00313 itr.mIndex = 0; 00314 return itr; 00315 } 00316 const_iterator begin() const 00317 { 00318 const_iterator itr; 00319 itr.mpArray = (CircularArray<T> *)this; 00320 itr.mIndex = 0; 00321 return itr; 00322 } 00323 iterator rbegin() 00324 { 00325 return begin(); 00326 } 00327 const_iterator rbegin() const 00328 { 00329 return begin(); 00330 } 00331 iterator end() 00332 { 00333 iterator itr; 00334 itr.mpArray = (CircularArray<T> *)this; 00335 itr.mIndex = mElements; 00336 return itr; 00337 } 00338 const_iterator end() const 00339 { 00340 const_iterator itr; 00341 itr.mpArray = (CircularArray<T> *)this; 00342 itr.mIndex = mElements; 00343 return itr; 00344 } 00345 iterator rend() 00346 { 00347 return end(); 00348 } 00349 const_iterator rend() const 00350 { 00351 return end(); 00352 } 00353 unsigned int GetFrontIndex() const { return mPosition; } 00354 void Clear(); 00355 void Destroy(); 00356 unsigned int Reserve(const unsigned int size); 00357 unsigned int Resize(const unsigned int size); 00358 unsigned int PushBack(const T &data); 00359 bool PopFront(T* data); 00360 bool PopBack(T* data); 00361 unsigned int Reserved() const; 00362 unsigned int Size() const; 00363 CircularArray<T> &operator=(const CircularArray<T> &another); 00364 protected: 00365 unsigned int mElements; 00366 unsigned int mReserved; 00367 unsigned int mPosition; 00368 T *mpArray; 00369 }; 00370 00378 template <class T> 00379 CircularArray<T>::CircularArray(const unsigned int size) : mElements(0), 00380 mReserved(0), 00381 mPosition(0), 00382 mpArray(0) 00383 { 00384 Reserve(size); 00385 } 00386 00392 template <class T> 00393 CircularArray<T>::CircularArray(const CircularArray<T> &another) : mElements(0), 00394 mReserved(0), 00395 mPosition(0), 00396 mpArray(0) 00397 { 00398 *this = another; 00399 } 00400 00406 template<class T> 00407 CircularArray<T>::~CircularArray() 00408 { 00409 Destroy(); 00410 } 00411 00412 00418 template<class T> 00419 void CircularArray<T>::Clear() 00420 { 00421 mPosition = mElements = 0; 00422 } 00423 00429 template<class T> 00430 void CircularArray<T>::Destroy() 00431 { 00432 if(mpArray) 00433 delete[] mpArray; 00434 00435 mpArray = NULL; 00436 mElements = mReserved = mPosition = 0; 00437 } 00438 00448 template<class T> 00449 unsigned int CircularArray<T>::Reserve(const unsigned int size) 00450 { 00451 T *ptr = NULL; 00452 // Delete old data 00453 Destroy(); 00454 00455 ptr = new T[size]; 00456 assert(ptr); 00457 00458 mpArray = ptr; 00459 mReserved = size; 00460 mPosition = mElements = 0; 00461 00462 return 1; 00463 } 00464 00476 template<class T> 00477 unsigned int CircularArray<T>::Resize(const unsigned int size) 00478 { 00479 if(size == mReserved) 00480 return 1; 00481 00482 T *ptr = new T[size]; 00483 assert(ptr); 00484 00485 if(mElements < size) 00486 { 00487 //CircularArray<T> myT; 00488 //myT.Resize(1); 00489 00490 typename CircularArray<T>::iterator itr; 00491 unsigned int i = 0; 00492 for(itr = this->begin(); itr != this->end(); itr++) 00493 { 00494 ptr[i++] = *itr; 00495 } 00496 mPosition = mElements; 00497 } 00498 else 00499 { 00500 mElements = mPosition = 0; 00501 } 00502 00503 if(mpArray) 00504 delete[] mpArray; 00505 00506 mpArray = ptr; 00507 mReserved = size; 00508 00509 return 1; 00510 } 00511 00521 template<class T> 00522 unsigned int CircularArray<T>::PushBack(const T &data) 00523 { 00524 if(!mpArray) 00525 return 0; 00526 // Add data to current position. 00527 mpArray[mPosition] = data; 00528 // Update write position in circular array. 00529 mPosition++; 00530 // Check for wrap around. 00531 if(mPosition >= mReserved) 00532 mPosition = 0; 00533 // Increase number of elements up to max. 00534 if(mElements < mReserved) 00535 mElements++; 00536 00537 return mElements; 00538 } 00539 00550 template<class T> 00551 bool CircularArray<T>::PopFront(T* data = NULL) 00552 { 00553 if(!mpArray) 00554 return false; 00555 00556 if(mElements > 0) 00557 { 00558 if(data) 00559 { 00560 int pos = ((int)(mPosition)) - ((int)(mElements)); 00561 if(pos < 0) 00562 { 00563 pos += (int)mReserved; 00564 } 00565 *data = mpArray[pos]; 00566 } 00567 00568 mElements--; 00569 00570 return true; 00571 } 00572 return false; 00573 } 00574 00575 00586 template<class T> 00587 bool CircularArray<T>::PopBack(T* data = NULL) 00588 { 00589 if(!mpArray) 00590 return false; 00591 00592 if(mElements > 0) 00593 { 00594 if(data) 00595 { 00596 int pos = ((int)(mPosition)) - 1; 00597 if(pos < 0) 00598 { 00599 pos += (int)mReserved; 00600 } 00601 *data = mpArray[pos]; 00602 } 00603 00604 mElements--; 00605 mPosition--; 00606 if(mPosition < 0) 00607 { 00608 mPosition += mReserved; 00609 } 00610 return true; 00611 } 00612 return false; 00613 } 00614 00615 00621 template<class T> 00622 unsigned int CircularArray<T>::Reserved() const { return mReserved; } 00623 00629 template<class T> 00630 unsigned int CircularArray<T>::Size() const { return mElements; } 00631 00637 template<class T> 00638 CircularArray<T> &CircularArray<T>::operator=(const CircularArray<T> &another) 00639 { 00640 if(this != &another) 00641 { 00642 if(mReserved != another.mReserved) 00643 { 00644 Reserve(another.mReserved); 00645 } 00646 Clear(); 00647 typename CircularArray<T>::const_iterator itr; 00648 for(itr = another.begin(); itr != another.end(); itr++) 00649 { 00650 PushBack(*itr); 00651 } 00652 } 00653 00654 return *this; 00655 } 00656 } 00657 00658 #endif 00659 00660 /* End of File */
