00001
00002
00003
00004
00005 #ifndef __IRR_LIST_H_INCLUDED__
00006 #define __IRR_LIST_H_INCLUDED__
00007
00008 #include "irrTypes.h"
00009 #include "irrAllocator.h"
00010
00011 namespace irr
00012 {
00013 namespace core
00014 {
00015
00016
00018 template <class T>
00019 class list
00020 {
00021 private:
00022
00024 struct SKListNode
00025 {
00026 SKListNode(const T& e) : Next(0), Prev(0), Element(e) {}
00027
00028 SKListNode* Next;
00029 SKListNode* Prev;
00030 T Element;
00031 };
00032
00033 public:
00034 class ConstIterator;
00035
00037 class Iterator
00038 {
00039 public:
00040 Iterator() : Current(0) {}
00041
00042 Iterator& operator ++() { Current = Current->Next; return *this; }
00043 Iterator& operator --() { Current = Current->Prev; return *this; }
00044 Iterator operator ++(s32) { Iterator tmp = *this; Current = Current->Next; return tmp; }
00045 Iterator operator --(s32) { Iterator tmp = *this; Current = Current->Prev; return tmp; }
00046
00047 Iterator& operator +=(s32 num)
00048 {
00049 if(num > 0)
00050 {
00051 while (num-- && this->Current != 0) ++(*this);
00052 }
00053 else
00054 {
00055 while(num++ && this->Current != 0) --(*this);
00056 }
00057 return *this;
00058 }
00059
00060 Iterator operator + (s32 num) const { Iterator tmp = *this; return tmp += num; }
00061 Iterator& operator -=(s32 num) const { return (*this)+=(-num); }
00062 Iterator operator - (s32 num) const { return (*this)+ (-num); }
00063
00064 bool operator ==(const Iterator& other) const { return Current == other.Current; }
00065 bool operator !=(const Iterator& other) const { return Current != other.Current; }
00066 bool operator ==(const ConstIterator& other) const { return Current == other.Current; }
00067 bool operator !=(const ConstIterator& other) const { return Current != other.Current; }
00068
00069 #if defined (_MSC_VER) && (_MSC_VER < 1300)
00070 #pragma warning(disable:4284) // infix notation problem when using iterator operator ->
00071 #endif
00072
00073 T & operator * () { return Current->Element; }
00074 T * operator ->() { return &Current->Element; }
00075
00076 private:
00077 Iterator(SKListNode* begin) : Current(begin) {}
00078
00079 SKListNode* Current;
00080
00081 friend class list<T>;
00082 };
00083
00085 class ConstIterator
00086 {
00087 public:
00088
00089 ConstIterator() : Current(0) {}
00090
00091 ConstIterator& operator ++() { Current = Current->Next; return *this; }
00092 ConstIterator& operator --() { Current = Current->Prev; return *this; }
00093 ConstIterator operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; }
00094 ConstIterator operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; }
00095
00096 ConstIterator& operator +=(s32 num)
00097 {
00098 if(num > 0)
00099 {
00100 while(num-- && this->Current != 0) ++(*this);
00101 }
00102 else
00103 {
00104 while(num++ && this->Current != 0) --(*this);
00105 }
00106 return *this;
00107 }
00108
00109 ConstIterator operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; }
00110 ConstIterator& operator -=(s32 num) const { return (*this)+=(-num); }
00111 ConstIterator operator - (s32 num) const { return (*this)+ (-num); }
00112
00113 bool operator ==(const ConstIterator& other) const { return Current == other.Current; }
00114 bool operator !=(const ConstIterator& other) const { return Current != other.Current; }
00115 bool operator ==(const Iterator& other) const { return Current == other.Current; }
00116 bool operator !=(const Iterator& other) const { return Current != other.Current; }
00117
00118 const T & operator * () { return Current->Element; }
00119 const T * operator ->() { return &Current->Element; }
00120
00121 ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }
00122
00123 private:
00124 ConstIterator(SKListNode* begin) : Current(begin) {}
00125
00126 SKListNode* Current;
00127
00128 friend class Iterator;
00129 friend class list<T>;
00130 };
00131
00133 list()
00134 : First(0), Last(0), Size(0) {}
00135
00136
00138 list(const list<T>& other) : First(0), Last(0), Size(0)
00139 {
00140 *this = other;
00141 }
00142
00143
00145 ~list()
00146 {
00147 clear();
00148 }
00149
00150
00152 void operator=(const list<T>& other)
00153 {
00154 if(&other == this)
00155 {
00156 return;
00157 }
00158
00159 clear();
00160
00161 SKListNode* node = other.First;
00162 while(node)
00163 {
00164 push_back(node->Element);
00165 node = node->Next;
00166 }
00167 }
00168
00169
00171
00172 u32 getSize() const
00173 {
00174 return Size;
00175 }
00176
00177
00179
00180 void clear()
00181 {
00182 while(First)
00183 {
00184 SKListNode * next = First->Next;
00185 allocator.destruct(First);
00186 allocator.deallocate(First);
00187 First = next;
00188 }
00189
00190
00191 Last = 0;
00192 Size = 0;
00193 }
00194
00195
00197
00198 bool empty() const
00199 {
00200 return (First == 0);
00201 }
00202
00203
00205
00206 void push_back(const T& element)
00207 {
00208 SKListNode* node = allocator.allocate(1);
00209 allocator.construct(node, element);
00210
00211 ++Size;
00212
00213 if (First == 0)
00214 First = node;
00215
00216 node->Prev = Last;
00217
00218 if (Last != 0)
00219 Last->Next = node;
00220
00221 Last = node;
00222 }
00223
00224
00226
00227 void push_front(const T& element)
00228 {
00229 SKListNode* node = allocator.allocate(1);
00230 allocator.construct(node, element);
00231
00232 ++Size;
00233
00234 if (First == 0)
00235 {
00236 Last = node;
00237 First = node;
00238 }
00239 else
00240 {
00241 node->Next = First;
00242 First->Prev = node;
00243 First = node;
00244 }
00245 }
00246
00247
00249
00250 Iterator begin()
00251 {
00252 return Iterator(First);
00253 }
00254
00255
00257
00258 ConstIterator begin() const
00259 {
00260 return ConstIterator(First);
00261 }
00262
00263
00265
00266 Iterator end()
00267 {
00268 return Iterator(0);
00269 }
00270
00271
00273
00274 ConstIterator end() const
00275 {
00276 return ConstIterator(0);
00277 }
00278
00279
00281
00282 Iterator getLast()
00283 {
00284 return Iterator(Last);
00285 }
00286
00287
00289
00290 ConstIterator getLast() const
00291 {
00292 return ConstIterator(Last);
00293 }
00294
00295
00297
00301 void insert_after(const Iterator& it, const T& element)
00302 {
00303 SKListNode* node = allocator.allocate(1);
00304 allocator.construct(node, element);
00305
00306 node->Next = it.Current->Next;
00307
00308 if (it.Current->Next)
00309 it.Current->Next->Prev = node;
00310
00311 node->Prev = it.Current;
00312 it.Current->Next = node;
00313 ++Size;
00314
00315 if (it.Current == Last)
00316 Last = node;
00317 }
00318
00319
00321
00325 void insert_before(const Iterator& it, const T& element)
00326 {
00327 SKListNode* node = allocator.allocate(1);
00328 allocator.construct(node, element);
00329
00330 node->Prev = it.Current->Prev;
00331
00332 if (it.Current->Prev)
00333 it.Current->Prev->Next = node;
00334
00335 node->Next = it.Current;
00336 it.Current->Prev = node;
00337 ++Size;
00338
00339 if (it.Current == First)
00340 First = node;
00341 }
00342
00343
00345
00347 Iterator erase(Iterator& it)
00348 {
00349
00350
00351
00352 Iterator returnIterator(it);
00353 ++returnIterator;
00354
00355 if(it.Current == First)
00356 {
00357 First = it.Current->Next;
00358 }
00359 else
00360 {
00361 it.Current->Prev->Next = it.Current->Next;
00362 }
00363
00364 if(it.Current == Last)
00365 {
00366 Last = it.Current->Prev;
00367 }
00368 else
00369 {
00370 it.Current->Next->Prev = it.Current->Prev;
00371 }
00372
00373 allocator.destruct(it.Current);
00374 allocator.deallocate(it.Current);
00375 it.Current = 0;
00376 --Size;
00377
00378 return returnIterator;
00379 }
00380
00381 private:
00382
00383 irrAllocator<SKListNode> allocator;
00384 SKListNode* First;
00385 SKListNode* Last;
00386 u32 Size;
00387
00388 };
00389
00390
00391 }
00392 }
00393
00394 #endif
00395