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 
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  T & operator * () { return Current->Element; }
71  T * operator ->() { return &Current->Element; }
72 
73  private:
74  explicit Iterator(SKListNode* begin) : Current(begin) {}
75 
76  SKListNode* Current;
77 
78  friend class list<T>;
79  friend class ConstIterator;
80  };
81 
84  {
85  public:
86 
87  ConstIterator() : Current(0) {}
88  ConstIterator(const Iterator& iter) : Current(iter.Current) {}
89 
90  ConstIterator& operator ++() { Current = Current->Next; return *this; }
91  ConstIterator& operator --() { Current = Current->Prev; return *this; }
92  ConstIterator operator ++(s32) { ConstIterator tmp = *this; Current = Current->Next; return tmp; }
93  ConstIterator operator --(s32) { ConstIterator tmp = *this; Current = Current->Prev; return tmp; }
94 
96  {
97  if(num > 0)
98  {
99  while(num-- && this->Current != 0) ++(*this);
100  }
101  else
102  {
103  while(num++ && this->Current != 0) --(*this);
104  }
105  return *this;
106  }
107 
108  ConstIterator operator + (s32 num) const { ConstIterator tmp = *this; return tmp += num; }
109  ConstIterator& operator -=(s32 num) { return (*this)+=(-num); }
110  ConstIterator operator - (s32 num) const { return (*this)+ (-num); }
111 
112  bool operator ==(const ConstIterator& other) const { return Current == other.Current; }
113  bool operator !=(const ConstIterator& other) const { return Current != other.Current; }
114  bool operator ==(const Iterator& other) const { return Current == other.Current; }
115  bool operator !=(const Iterator& other) const { return Current != other.Current; }
116 
117  const T & operator * () { return Current->Element; }
118  const T * operator ->() { return &Current->Element; }
119 
120  ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }
121 
122  private:
123  explicit ConstIterator(SKListNode* begin) : Current(begin) {}
124 
125  SKListNode* Current;
126 
127  friend class Iterator;
128  friend class list<T>;
129  };
130 
133  : First(0), Last(0), Size(0) {}
134 
135 
137  list(const list<T>& other) : First(0), Last(0), Size(0)
138  {
139  *this = other;
140  }
141 
142 
145  {
146  clear();
147  }
148 
149 
151  void operator=(const list<T>& other)
152  {
153  if(&other == this)
154  {
155  return;
156  }
157 
158  clear();
159 
160  SKListNode* node = other.First;
161  while(node)
162  {
163  push_back(node->Element);
164  node = node->Next;
165  }
166  }
167 
168 
170 
171  u32 size() const
172  {
173  return Size;
174  }
175  u32 getSize() const
176  {
177  return Size;
178  }
179 
180 
182 
183  void clear()
184  {
185  while(First)
186  {
187  SKListNode * next = First->Next;
188  allocator.destruct(First);
189  allocator.deallocate(First);
190  First = next;
191  }
192 
193  //First = 0; handled by loop
194  Last = 0;
195  Size = 0;
196  }
197 
198 
200 
201  bool empty() const
202  {
203  return (First == 0);
204  }
205 
206 
208 
209  void push_back(const T& element)
210  {
211  SKListNode* node = allocator.allocate(1);
212  allocator.construct(node, element);
213 
214  ++Size;
215 
216  if (First == 0)
217  First = node;
218 
219  node->Prev = Last;
220 
221  if (Last != 0)
222  Last->Next = node;
223 
224  Last = node;
225  }
226 
227 
229 
230  void push_front(const T& element)
231  {
232  SKListNode* node = allocator.allocate(1);
233  allocator.construct(node, element);
234 
235  ++Size;
236 
237  if (First == 0)
238  {
239  Last = node;
240  First = node;
241  }
242  else
243  {
244  node->Next = First;
245  First->Prev = node;
246  First = node;
247  }
248  }
249 
250 
252 
253  Iterator begin()
254  {
255  return Iterator(First);
256  }
257 
258 
260 
261  ConstIterator begin() const
262  {
263  return ConstIterator(First);
264  }
265 
266 
268 
269  Iterator end()
270  {
271  return Iterator(0);
272  }
273 
274 
276 
277  ConstIterator end() const
278  {
279  return ConstIterator(0);
280  }
281 
282 
284 
285  Iterator getLast()
286  {
287  return Iterator(Last);
288  }
289 
290 
292 
293  ConstIterator getLast() const
294  {
295  return ConstIterator(Last);
296  }
297 
298 
300 
304  void insert_after(const Iterator& it, const T& element)
305  {
306  SKListNode* node = allocator.allocate(1);
307  allocator.construct(node, element);
308 
309  node->Next = it.Current->Next;
310 
311  if (it.Current->Next)
312  it.Current->Next->Prev = node;
313 
314  node->Prev = it.Current;
315  it.Current->Next = node;
316  ++Size;
317 
318  if (it.Current == Last)
319  Last = node;
320  }
321 
322 
324 
328  void insert_before(const Iterator& it, const T& element)
329  {
330  SKListNode* node = allocator.allocate(1);
331  allocator.construct(node, element);
332 
333  node->Prev = it.Current->Prev;
334 
335  if (it.Current->Prev)
336  it.Current->Prev->Next = node;
337 
338  node->Next = it.Current;
339  it.Current->Prev = node;
340  ++Size;
341 
342  if (it.Current == First)
343  First = node;
344  }
345 
346 
348 
350  Iterator erase(Iterator& it)
351  {
352  // suggest changing this to a const Iterator& and
353  // working around line: it.Current = 0 (possibly with a mutable, or just let it be garbage?)
354 
355  Iterator returnIterator(it);
356  ++returnIterator;
357 
358  if(it.Current == First)
359  {
360  First = it.Current->Next;
361  }
362  else
363  {
364  it.Current->Prev->Next = it.Current->Next;
365  }
366 
367  if(it.Current == Last)
368  {
369  Last = it.Current->Prev;
370  }
371  else
372  {
373  it.Current->Next->Prev = it.Current->Prev;
374  }
375 
376  allocator.destruct(it.Current);
377  allocator.deallocate(it.Current);
378  it.Current = 0;
379  --Size;
380 
381  return returnIterator;
382  }
383 
385 
389  void swap(list<T>& other)
390  {
391  core::swap(First, other.First);
392  core::swap(Last, other.Last);
393  core::swap(Size, other.Size);
394  core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
395  }
396 
397  typedef T value_type;
398  typedef u32 size_type;
399 
400 private:
401 
402  SKListNode* First;
403  SKListNode* Last;
404  u32 Size;
405  irrAllocator<SKListNode> allocator;
406 
407 };
408 
409 
410 } // end namespace core
411 }// end namespace irr
412 
413 #endif
414 
bool operator !=(const Iterator &other) const
Definition: irrList.h:115
ConstIterator operator+(s32 num) const
Definition: irrList.h:108
void insert_after(const Iterator &it, const T &element)
Inserts an element after an element.
Definition: irrList.h:304
u32 size() const
Returns amount of elements in list.
Definition: irrList.h:171
Iterator & operator -=(s32 num)
Definition: irrList.h:62
ConstIterator & operator -=(s32 num)
Definition: irrList.h:109
ConstIterator(const Iterator &iter)
Definition: irrList.h:88
Iterator getLast()
Gets last element.
Definition: irrList.h:285
~list()
Destructor.
Definition: irrList.h:144
Iterator & operator+=(s32 num)
Definition: irrList.h:48
ConstIterator & operator --()
Definition: irrList.h:91
bool operator !=(const ConstIterator &other) const
Definition: irrList.h:113
void destruct(T *ptr)
Destruct an element.
Definition: irrAllocator.h:51
Iterator operator+(s32 num) const
Definition: irrList.h:61
u32 getSize() const
Definition: irrList.h:175
Everything in the Irrlicht Engine can be found in this namespace.
Definition: aabbox3d.h:12
Iterator operator --(s32)
Definition: irrList.h:46
ConstIterator end() const
Gets end node.
Definition: irrList.h:277
bool operator !=(const Iterator &other) const
Definition: irrList.h:66
Doubly linked list template.
Definition: irrList.h:20
List iterator for const access.
Definition: irrList.h:83
bool operator==(const Iterator &other) const
Definition: irrList.h:65
list(const list< T > &other)
Copy constructor.
Definition: irrList.h:137
signed int s32
32 bit signed variable.
Definition: irrTypes.h:70
Iterator & operator --()
Definition: irrList.h:44
Iterator & operator++()
Definition: irrList.h:43
void push_back(const T &element)
Adds an element at the end of the list.
Definition: irrList.h:209
unsigned int u32
32 bit unsigned variable.
Definition: irrTypes.h:62
void push_front(const T &element)
Adds an element at the begin of the list.
Definition: irrList.h:230
void operator=(const list< T > &other)
Assignment operator.
Definition: irrList.h:151
bool operator==(const ConstIterator &other) const
Definition: irrList.h:112
T * allocate(size_t cnt)
Allocate memory for an array of objects.
Definition: irrAllocator.h:33
void swap(list< T > &other)
Swap the content of this list container with the content of another list.
Definition: irrList.h:389
Iterator operator -(s32 num) const
Definition: irrList.h:63
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition: irrMath.h:178
ConstIterator begin() const
Gets first node.
Definition: irrList.h:261
void clear()
Clears the list, deletes all elements in the list.
Definition: irrList.h:183
ConstIterator & operator++()
Definition: irrList.h:90
Iterator erase(Iterator &it)
Erases an element.
Definition: irrList.h:350
void construct(T *ptr, const T &e)
Construct an element.
Definition: irrAllocator.h:45
ConstIterator & operator+=(s32 num)
Definition: irrList.h:95
ConstIterator & operator=(const Iterator &iterator)
Definition: irrList.h:120
bool operator !=(const ConstIterator &other) const
Definition: irrList.h:68
Iterator end()
Gets end node.
Definition: irrList.h:269
ConstIterator operator --(s32)
Definition: irrList.h:93
void deallocate(T *ptr)
Deallocate memory for an array of objects.
Definition: irrAllocator.h:39
bool empty() const
Checks for empty list.
Definition: irrList.h:201
Iterator begin()
Gets first node.
Definition: irrList.h:253
void insert_before(const Iterator &it, const T &element)
Inserts an element before an element.
Definition: irrList.h:328
ConstIterator getLast() const
Gets last element.
Definition: irrList.h:293
list()
Default constructor for empty list.
Definition: irrList.h:132
List iterator.
Definition: irrList.h:38
ConstIterator operator -(s32 num) const
Definition: irrList.h:110