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