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-2010 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) const { 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) const { 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 

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Sun Oct 24 12:41:57 2010 by Doxygen (1.6.2)