 |
+
+
+
+ Irrlicht 3D Engine
+
+
+
+ |
+
+
+
+
+
+
+
+
+
+
+ 
+
+ |
+
+
+
00001 // Copyright (C) 2002-2012 Nikolaus Gebhardt +00002 // This file is part of the "Irrlicht Engine". +00003 // For conditions of distribution and use, see copyright notice in irrlicht.h +00004 +00005 #ifndef __IRR_LIST_H_INCLUDED__ +00006 #define __IRR_LIST_H_INCLUDED__ +00007 +00008 #include "irrTypes.h" +00009 #include "irrAllocator.h" +00010 #include "irrMath.h" +00011 +00012 namespace irr +00013 { +00014 namespace core +00015 { +00016 +00017 +00019 template <class T> +00020 class list +00021 { +00022 private: +00023 +00025 struct SKListNode +00026 { +00027 SKListNode(const T& e) : Next(0), Prev(0), Element(e) {} +00028 +00029 SKListNode* Next; +00030 SKListNode* Prev; +00031 T Element; +00032 }; +00033 +00034 public: +00035 class ConstIterator; +00036 +00038 class Iterator +00039 { +00040 public: +00041 Iterator() : Current(0) {} +00042 +00043 Iterator& operator ++() { Current = Current->Next; return *this; } +00044 Iterator& operator --() { Current = Current->Prev; return *this; } +00045 Iterator operator ++(s32) { Iterator tmp = *this; Current = Current->Next; return tmp; } +00046 Iterator operator --(s32) { Iterator tmp = *this; Current = Current->Prev; return tmp; } +00047 +00048 Iterator& operator +=(s32 num) +00049 { +00050 if(num > 0) +00051 { +00052 while (num-- && this->Current != 0) ++(*this); +00053 } +00054 else +00055 { +00056 while(num++ && this->Current != 0) --(*this); +00057 } +00058 return *this; +00059 } +00060 +00061 Iterator operator + (s32 num) const { Iterator tmp = *this; return tmp += num; } +00062 Iterator& operator -=(s32 num) { return (*this)+=(-num); } +00063 Iterator operator - (s32 num) const { return (*this)+ (-num); } +00064 +00065 bool operator ==(const Iterator& other) const { return Current == other.Current; } +00066 bool operator !=(const Iterator& other) const { return Current != other.Current; } +00067 bool operator ==(const ConstIterator& other) const { return Current == other.Current; } +00068 bool operator !=(const ConstIterator& other) const { return Current != other.Current; } +00069 +00070 #if defined (_MSC_VER) && (_MSC_VER < 1300) +00071 #pragma warning(disable:4284) // infix notation problem when using iterator operator -> +00072 #endif +00073 +00074 T & operator * () { return Current->Element; } +00075 T * operator ->() { return &Current->Element; } +00076 +00077 private: +00078 explicit Iterator(SKListNode* begin) : Current(begin) {} +00079 +00080 SKListNode* Current; +00081 +00082 friend class list<T>; +00083 friend class ConstIterator; +00084 }; +00085 +00087 class ConstIterator +00088 { +00089 public: +00090 +00091 ConstIterator() : Current(0) {} +00092 ConstIterator(const Iterator& iter) : Current(iter.Current) {} +00093 +00094 ConstIterator& operator ++() { Current = Current->Next; return *this; } +00095 ConstIterator& operator --() { Current = Current->Prev; return *this; } +00096 ConstIterator operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; } +00097 ConstIterator operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; } +00098 +00099 ConstIterator& operator +=(s32 num) +00100 { +00101 if(num > 0) +00102 { +00103 while(num-- && this->Current != 0) ++(*this); +00104 } +00105 else +00106 { +00107 while(num++ && this->Current != 0) --(*this); +00108 } +00109 return *this; +00110 } +00111 +00112 ConstIterator operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; } +00113 ConstIterator& operator -=(s32 num) { return (*this)+=(-num); } +00114 ConstIterator operator - (s32 num) const { return (*this)+ (-num); } +00115 +00116 bool operator ==(const ConstIterator& other) const { return Current == other.Current; } +00117 bool operator !=(const ConstIterator& other) const { return Current != other.Current; } +00118 bool operator ==(const Iterator& other) const { return Current == other.Current; } +00119 bool operator !=(const Iterator& other) const { return Current != other.Current; } +00120 +00121 const T & operator * () { return Current->Element; } +00122 const T * operator ->() { return &Current->Element; } +00123 +00124 ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; } +00125 +00126 private: +00127 explicit ConstIterator(SKListNode* begin) : Current(begin) {} +00128 +00129 SKListNode* Current; +00130 +00131 friend class Iterator; +00132 friend class list<T>; +00133 }; +00134 +00136 list() +00137 : First(0), Last(0), Size(0) {} +00138 +00139 +00141 list(const list<T>& other) : First(0), Last(0), Size(0) +00142 { +00143 *this = other; +00144 } +00145 +00146 +00148 ~list() +00149 { +00150 clear(); +00151 } +00152 +00153 +00155 void operator=(const list<T>& other) +00156 { +00157 if(&other == this) +00158 { +00159 return; +00160 } +00161 +00162 clear(); +00163 +00164 SKListNode* node = other.First; +00165 while(node) +00166 { +00167 push_back(node->Element); +00168 node = node->Next; +00169 } +00170 } +00171 +00172 +00174 +00175 u32 size() const +00176 { +00177 return Size; +00178 } +00179 u32 getSize() const +00180 { +00181 return Size; +00182 } +00183 +00184 +00186 +00187 void clear() +00188 { +00189 while(First) +00190 { +00191 SKListNode * next = First->Next; +00192 allocator.destruct(First); +00193 allocator.deallocate(First); +00194 First = next; +00195 } +00196 +00197 //First = 0; handled by loop +00198 Last = 0; +00199 Size = 0; +00200 } +00201 +00202 +00204 +00205 bool empty() const +00206 { +00207 return (First == 0); +00208 } +00209 +00210 +00212 +00213 void push_back(const T& element) +00214 { +00215 SKListNode* node = allocator.allocate(1); +00216 allocator.construct(node, element); +00217 +00218 ++Size; +00219 +00220 if (First == 0) +00221 First = node; +00222 +00223 node->Prev = Last; +00224 +00225 if (Last != 0) +00226 Last->Next = node; +00227 +00228 Last = node; +00229 } +00230 +00231 +00233 +00234 void push_front(const T& element) +00235 { +00236 SKListNode* node = allocator.allocate(1); +00237 allocator.construct(node, element); +00238 +00239 ++Size; +00240 +00241 if (First == 0) +00242 { +00243 Last = node; +00244 First = node; +00245 } +00246 else +00247 { +00248 node->Next = First; +00249 First->Prev = node; +00250 First = node; +00251 } +00252 } +00253 +00254 +00256 +00257 Iterator begin() +00258 { +00259 return Iterator(First); +00260 } +00261 +00262 +00264 +00265 ConstIterator begin() const +00266 { +00267 return ConstIterator(First); +00268 } +00269 +00270 +00272 +00273 Iterator end() +00274 { +00275 return Iterator(0); +00276 } +00277 +00278 +00280 +00281 ConstIterator end() const +00282 { +00283 return ConstIterator(0); +00284 } +00285 +00286 +00288 +00289 Iterator getLast() +00290 { +00291 return Iterator(Last); +00292 } +00293 +00294 +00296 +00297 ConstIterator getLast() const +00298 { +00299 return ConstIterator(Last); +00300 } +00301 +00302 +00304 +00308 void insert_after(const Iterator& it, const T& element) +00309 { +00310 SKListNode* node = allocator.allocate(1); +00311 allocator.construct(node, element); +00312 +00313 node->Next = it.Current->Next; +00314 +00315 if (it.Current->Next) +00316 it.Current->Next->Prev = node; +00317 +00318 node->Prev = it.Current; +00319 it.Current->Next = node; +00320 ++Size; +00321 +00322 if (it.Current == Last) +00323 Last = node; +00324 } +00325 +00326 +00328 +00332 void insert_before(const Iterator& it, const T& element) +00333 { +00334 SKListNode* node = allocator.allocate(1); +00335 allocator.construct(node, element); +00336 +00337 node->Prev = it.Current->Prev; +00338 +00339 if (it.Current->Prev) +00340 it.Current->Prev->Next = node; +00341 +00342 node->Next = it.Current; +00343 it.Current->Prev = node; +00344 ++Size; +00345 +00346 if (it.Current == First) +00347 First = node; +00348 } +00349 +00350 +00352 +00354 Iterator erase(Iterator& it) +00355 { +00356 // suggest changing this to a const Iterator& and +00357 // working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?) +00358 +00359 Iterator returnIterator(it); +00360 ++returnIterator; +00361 +00362 if(it.Current == First) +00363 { +00364 First = it.Current->Next; +00365 } +00366 else +00367 { +00368 it.Current->Prev->Next = it.Current->Next; +00369 } +00370 +00371 if(it.Current == Last) +00372 { +00373 Last = it.Current->Prev; +00374 } +00375 else +00376 { +00377 it.Current->Next->Prev = it.Current->Prev; +00378 } +00379 +00380 allocator.destruct(it.Current); +00381 allocator.deallocate(it.Current); +00382 it.Current = 0; +00383 --Size; +00384 +00385 return returnIterator; +00386 } +00387 +00389 +00393 void swap(list<T>& other) +00394 { +00395 core::swap(First, other.First); +00396 core::swap(Last, other.Last); +00397 core::swap(Size, other.Size); +00398 core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation +00399 } +00400 +00401 +00402 private: +00403 +00404 SKListNode* First; +00405 SKListNode* Last; +00406 u32 Size; +00407 irrAllocator<SKListNode> allocator; +00408 +00409 }; +00410 +00411 +00412 } // end namespace core +00413 }// end namespace irr +00414 +00415 #endif +00416 +