include/irrList.h

   1 // Copyright (C) 2002-2012 Nikolaus Gebhardt\r
   2 // This file is part of the "Irrlicht Engine".\r
   3 // For conditions of distribution and use, see copyright notice in irrlicht.h\r
   4 \r
   5 #ifndef __IRR_LIST_H_INCLUDED__\r
   6 #define __IRR_LIST_H_INCLUDED__\r
   7 \r
   8 #include "irrTypes.h"\r
   9 #include "irrAllocator.h"\r
  10 #include "irrMath.h"\r
  11 \r
  12 namespace irr\r
  13 {\r
  14 namespace core\r
  15 {\r
  16 \r
  17 \r
  18 //! Doubly linked list template.\r
  19 template <class T>\r
  20 class list\r
  21 {\r
  22 private:\r
  23 \r
  24         //! List element node with pointer to previous and next element in the list.\r
  25         struct SKListNode\r
  26         {\r
  27                 SKListNode(const T& e) : Next(0), Prev(0), Element(e) {}\r
  28 \r
  29                 SKListNode* Next;\r
  30                 SKListNode* Prev;\r
  31                 T Element;\r
  32         };\r
  33 \r
  34 public:\r
  35         class ConstIterator;\r
  36 \r
  37         //! List iterator.\r
  38         class Iterator\r
  39         {\r
  40         public:\r
  41                 Iterator() : Current(0) {}\r
  42 \r
  43                 Iterator& operator ++()    { Current = Current->Next; return *this; }\r
  44                 Iterator& operator --()    { Current = Current->Prev; return *this; }\r
  45                 Iterator  operator ++(s32) { Iterator tmp = *this; Current = Current->Next; return tmp; }\r
  46                 Iterator  operator --(s32) { Iterator tmp = *this; Current = Current->Prev; return tmp; }\r
  47 \r
  48                 Iterator& operator +=(s32 num)\r
  49                 {\r
  50                         if(num > 0)\r
  51                         {\r
  52                                 while (num-- && this->Current != 0) ++(*this);\r
  53                         }\r
  54                         else\r
  55                         {\r
  56                                 while(num++ && this->Current != 0) --(*this);\r
  57                         }\r
  58                         return *this;\r
  59                 }\r
  60 \r
  61                 Iterator  operator + (s32 num) const { Iterator tmp = *this; return tmp += num; }\r
  62                 Iterator& operator -=(s32 num) { return (*this)+=(-num); }\r
  63                 Iterator  operator - (s32 num) const { return (*this)+ (-num); }\r
  64 \r
  65                 bool operator ==(const Iterator&      other) const { return Current == other.Current; }\r
  66                 bool operator !=(const Iterator&      other) const { return Current != other.Current; }\r
  67                 bool operator ==(const ConstIterator& other) const { return Current == other.Current; }\r
  68                 bool operator !=(const ConstIterator& other) const { return Current != other.Current; }\r
  69 \r
  70                 T & operator * () { return Current->Element; }\r
  71                 T * operator ->() { return &Current->Element; }\r
  72 \r
  73         private:\r
  74                 explicit Iterator(SKListNode* begin) : Current(begin) {}\r
  75 \r
  76                 SKListNode* Current;\r
  77 \r
  78                 friend class list<T>;\r
  79                 friend class ConstIterator;\r
  80         };\r
  81 \r
  82         //! List iterator for const access.\r
  83         class ConstIterator\r
  84         {\r
  85         public:\r
  86 \r
  87                 ConstIterator() : Current(0) {}\r
  88                 ConstIterator(const Iterator& iter) : Current(iter.Current)  {}\r
  89 \r
  90                 ConstIterator& operator ++()    { Current = Current->Next; return *this; }\r
  91                 ConstIterator& operator --()    { Current = Current->Prev; return *this; }\r
  92                 ConstIterator  operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; }\r
  93                 ConstIterator  operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; }\r
  94 \r
  95                 ConstIterator& operator +=(s32 num)\r
  96                 {\r
  97                         if(num > 0)\r
  98                         {\r
  99                                 while(num-- && this->Current != 0) ++(*this);\r
 100                         }\r
 101                         else\r
 102                         {\r
 103                                 while(num++ && this->Current != 0) --(*this);\r
 104                         }\r
 105                         return *this;\r
 106                 }\r
 107 \r
 108                 ConstIterator  operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; }\r
 109                 ConstIterator& operator -=(s32 num) { return (*this)+=(-num); }\r
 110                 ConstIterator  operator - (s32 num) const { return (*this)+ (-num); }\r
 111 \r
 112                 bool operator ==(const ConstIterator& other) const { return Current == other.Current; }\r
 113                 bool operator !=(const ConstIterator& other) const { return Current != other.Current; }\r
 114                 bool operator ==(const Iterator&      other) const { return Current == other.Current; }\r
 115                 bool operator !=(const Iterator&      other) const { return Current != other.Current; }\r
 116 \r
 117                 const T & operator * () { return Current->Element; }\r
 118                 const T * operator ->() { return &Current->Element; }\r
 119 \r
 120                 ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }\r
 121 \r
 122         private:\r
 123                 explicit ConstIterator(SKListNode* begin) : Current(begin) {}\r
 124 \r
 125                 SKListNode* Current;\r
 126 \r
 127                 friend class Iterator;\r
 128                 friend class list<T>;\r
 129         };\r
 130 \r
 131         //! Default constructor for empty list.\r
 132         list()\r
 133                 : First(0), Last(0), Size(0) {}\r
 134 \r
 135 \r
 136         //! Copy constructor.\r
 137         list(const list<T>& other) : First(0), Last(0), Size(0)\r
 138         {\r
 139                 *this = other;\r
 140         }\r
 141 \r
 142 \r
 143         //! Destructor\r
 144         ~list()\r
 145         {\r
 146                 clear();\r
 147         }\r
 148 \r
 149 \r
 150         //! Assignment operator\r
 151         void operator=(const list<T>& other)\r
 152         {\r
 153                 if(&other == this)\r
 154                 {\r
 155                         return;\r
 156                 }\r
 157 \r
 158                 clear();\r
 159 \r
 160                 SKListNode* node = other.First;\r
 161                 while(node)\r
 162                 {\r
 163                         push_back(node->Element);\r
 164                         node = node->Next;\r
 165                 }\r
 166         }\r
 167 \r
 168 \r
 169         //! Returns amount of elements in list.\r
 170         /** \return Amount of elements in the list. */\r
 171         u32 size() const\r
 172         {\r
 173                 return Size;\r
 174         }\r
 175         u32 getSize() const\r
 176         {\r
 177                 return Size;\r
 178         }\r
 179 \r
 180 \r
 181         //! Clears the list, deletes all elements in the list.\r
 182         /** All existing iterators of this list will be invalid. */\r
 183         void clear()\r
 184         {\r
 185                 while(First)\r
 186                 {\r
 187                         SKListNode * next = First->Next;\r
 188                         allocator.destruct(First);\r
 189                         allocator.deallocate(First);\r
 190                         First = next;\r
 191                 }\r
 192 \r
 193                 //First = 0; handled by loop\r
 194                 Last = 0;\r
 195                 Size = 0;\r
 196         }\r
 197 \r
 198 \r
 199         //! Checks for empty list.\r
 200         /** \return True if the list is empty and false if not. */\r
 201         bool empty() const\r
 202         {\r
 203                 return (First == 0);\r
 204         }\r
 205 \r
 206 \r
 207         //! Adds an element at the end of the list.\r
 208         /** \param element Element to add to the list. */\r
 209         void push_back(const T& element)\r
 210         {\r
 211                 SKListNode* node = allocator.allocate(1);\r
 212                 allocator.construct(node, element);\r
 213 \r
 214                 ++Size;\r
 215 \r
 216                 if (First == 0)\r
 217                         First = node;\r
 218 \r
 219                 node->Prev = Last;\r
 220 \r
 221                 if (Last != 0)\r
 222                         Last->Next = node;\r
 223 \r
 224                 Last = node;\r
 225         }\r
 226 \r
 227 \r
 228         //! Adds an element at the begin of the list.\r
 229         /** \param element: Element to add to the list. */\r
 230         void push_front(const T& element)\r
 231         {\r
 232                 SKListNode* node = allocator.allocate(1);\r
 233                 allocator.construct(node, element);\r
 234 \r
 235                 ++Size;\r
 236 \r
 237                 if (First == 0)\r
 238                 {\r
 239                         Last = node;\r
 240                         First = node;\r
 241                 }\r
 242                 else\r
 243                 {\r
 244                         node->Next = First;\r
 245                         First->Prev = node;\r
 246                         First = node;\r
 247                 }\r
 248         }\r
 249 \r
 250 \r
 251         //! Gets first node.\r
 252         /** \return A list iterator pointing to the beginning of the list. */\r
 253         Iterator begin()\r
 254         {\r
 255                 return Iterator(First);\r
 256         }\r
 257 \r
 258 \r
 259         //! Gets first node.\r
 260         /** \return A const list iterator pointing to the beginning of the list. */\r
 261         ConstIterator begin() const\r
 262         {\r
 263                 return ConstIterator(First);\r
 264         }\r
 265 \r
 266 \r
 267         //! Gets end node.\r
 268         /** \return List iterator pointing to null. */\r
 269         Iterator end()\r
 270         {\r
 271                 return Iterator(0);\r
 272         }\r
 273 \r
 274 \r
 275         //! Gets end node.\r
 276         /** \return Const list iterator pointing to null. */\r
 277         ConstIterator end() const\r
 278         {\r
 279                 return ConstIterator(0);\r
 280         }\r
 281 \r
 282 \r
 283         //! Gets last element.\r
 284         /** \return List iterator pointing to the last element of the list. */\r
 285         Iterator getLast()\r
 286         {\r
 287                 return Iterator(Last);\r
 288         }\r
 289 \r
 290 \r
 291         //! Gets last element.\r
 292         /** \return Const list iterator pointing to the last element of the list. */\r
 293         ConstIterator getLast() const\r
 294         {\r
 295                 return ConstIterator(Last);\r
 296         }\r
 297 \r
 298 \r
 299         //! Inserts an element after an element.\r
 300         /** \param it Iterator pointing to element after which the new element\r
 301         should be inserted.\r
 302         \param element The new element to be inserted into the list.\r
 303         */\r
 304         void insert_after(const Iterator& it, const T& element)\r
 305         {\r
 306                 SKListNode* node = allocator.allocate(1);\r
 307                 allocator.construct(node, element);\r
 308 \r
 309                 node->Next = it.Current->Next;\r
 310 \r
 311                 if (it.Current->Next)\r
 312                         it.Current->Next->Prev = node;\r
 313 \r
 314                 node->Prev = it.Current;\r
 315                 it.Current->Next = node;\r
 316                 ++Size;\r
 317 \r
 318                 if (it.Current == Last)\r
 319                         Last = node;\r
 320         }\r
 321 \r
 322 \r
 323         //! Inserts an element before an element.\r
 324         /** \param it Iterator pointing to element before which the new element\r
 325         should be inserted.\r
 326         \param element The new element to be inserted into the list.\r
 327         */\r
 328         void insert_before(const Iterator& it, const T& element)\r
 329         {\r
 330                 SKListNode* node = allocator.allocate(1);\r
 331                 allocator.construct(node, element);\r
 332 \r
 333                 node->Prev = it.Current->Prev;\r
 334 \r
 335                 if (it.Current->Prev)\r
 336                         it.Current->Prev->Next = node;\r
 337 \r
 338                 node->Next = it.Current;\r
 339                 it.Current->Prev = node;\r
 340                 ++Size;\r
 341 \r
 342                 if (it.Current == First)\r
 343                         First = node;\r
 344         }\r
 345 \r
 346 \r
 347         //! Erases an element.\r
 348         /** \param it Iterator pointing to the element which shall be erased.\r
 349         \return Iterator pointing to next element. */\r
 350         Iterator erase(Iterator& it)\r
 351         {\r
 352                 // suggest changing this to a const Iterator& and\r
 353                 // working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?)\r
 354 \r
 355                 Iterator returnIterator(it);\r
 356                 ++returnIterator;\r
 357 \r
 358                 if(it.Current == First)\r
 359                 {\r
 360                         First = it.Current->Next;\r
 361                 }\r
 362                 else\r
 363                 {\r
 364                         it.Current->Prev->Next = it.Current->Next;\r
 365                 }\r
 366 \r
 367                 if(it.Current == Last)\r
 368                 {\r
 369                         Last = it.Current->Prev;\r
 370                 }\r
 371                 else\r
 372                 {\r
 373                         it.Current->Next->Prev = it.Current->Prev;\r
 374                 }\r
 375 \r
 376                 allocator.destruct(it.Current);\r
 377                 allocator.deallocate(it.Current);\r
 378                 it.Current = 0;\r
 379                 --Size;\r
 380 \r
 381                 return returnIterator;\r
 382         }\r
 383 \r
 384         //! Swap the content of this list container with the content of another list\r
 385         /** Afterward this object will contain the content of the other object and the other\r
 386         object will contain the content of this object. Iterators will afterward be valid for\r
 387         the swapped object.\r
 388         \param other Swap content with this object */\r
 389         void swap(list<T>& other)\r
 390         {\r
 391                 core::swap(First, other.First);\r
 392                 core::swap(Last, other.Last);\r
 393                 core::swap(Size, other.Size);\r
 394                 core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation\r
 395         }\r
 396 \r
 397         typedef T value_type;\r
 398         typedef u32 size_type;\r
 399 \r
 400 private:\r
 401 \r
 402         SKListNode* First;\r
 403         SKListNode* Last;\r
 404         u32 Size;\r
 405         irrAllocator<SKListNode> allocator;\r
 406 \r
 407 };\r
 408 \r
 409 \r
 410 } // end namespace core\r
 411 }// end namespace irr\r
 412 \r
 413 #endif\r
 414 \r