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