Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials

# irrList.h

Go to the documentation of this file.

    00001 // Copyright (C) 2002-2009 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
    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                 //First = 0; handled by loop
    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                 // suggest changing this to a const Iterator& and
    00350                 // working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?)
    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 } // end namespace core
    00392 }// end namespace irr
    00393
    00394 #endif
    00395

| The Irrlicht Engine Documentation © 2003-2009 by Nikolaus Gebhardt. Generated on Sun Jan 10 09:24:04 2010 by Doxygen (1.5.6)