Irrlicht 3D Engine
 
Loading...
Searching...
No Matches
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
12namespace irr
13{
14namespace core
15{
16
17
19template <class T>
20class list
21{
22private:
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
34public:
35 class ConstIterator;
36
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 #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
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
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
258 {
259 return Iterator(First);
260 }
261
262
264
266 {
267 return ConstIterator(First);
268 }
269
270
272
274 {
275 return Iterator(0);
276 }
277
278
280
282 {
283 return ConstIterator(0);
284 }
285
286
288
290 {
291 return Iterator(Last);
292 }
293
294
296
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
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
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
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
402private:
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
Axis aligned bounding box in 3d dimensional space.
Definition aabbox3d.h:22
void construct(T *ptr, const T &e)
Construct an element.
void destruct(T *ptr)
Destruct an element.
void deallocate(T *ptr)
Deallocate memory for an array of objects.
T * allocate(size_t cnt)
Allocate memory for an array of objects.
List iterator for const access.
Definition irrList.h:88
ConstIterator & operator++()
Definition irrList.h:94
ConstIterator & operator-=(s32 num)
Definition irrList.h:113
ConstIterator & operator--()
Definition irrList.h:95
bool operator!=(const ConstIterator &other) const
Definition irrList.h:117
ConstIterator & operator=(const Iterator &iterator)
Definition irrList.h:124
ConstIterator operator-(s32 num) const
Definition irrList.h:114
bool operator==(const ConstIterator &other) const
Definition irrList.h:116
ConstIterator & operator+=(s32 num)
Definition irrList.h:99
ConstIterator operator+(s32 num) const
Definition irrList.h:112
ConstIterator(const Iterator &iter)
Definition irrList.h:92
List iterator.
Definition irrList.h:39
Iterator operator+(s32 num) const
Definition irrList.h:61
Iterator & operator--()
Definition irrList.h:44
bool operator==(const Iterator &other) const
Definition irrList.h:65
Iterator & operator-=(s32 num)
Definition irrList.h:62
Iterator operator-(s32 num) const
Definition irrList.h:63
bool operator!=(const Iterator &other) const
Definition irrList.h:66
Iterator & operator++()
Definition irrList.h:43
Iterator & operator+=(s32 num)
Definition irrList.h:48
Doubly linked list template.
Definition irrList.h:21
void push_back(const T &element)
Adds an element at the end of the list.
Definition irrList.h:213
list(const list< T > &other)
Copy constructor.
Definition irrList.h:141
void insert_before(const Iterator &it, const T &element)
Inserts an element before an element.
Definition irrList.h:332
u32 size() const
Returns amount of elements in list.
Definition irrList.h:175
Iterator erase(Iterator &it)
Erases an element.
Definition irrList.h:354
void operator=(const list< T > &other)
Assignment operator.
Definition irrList.h:155
u32 getSize() const
Definition irrList.h:179
~list()
Destructor.
Definition irrList.h:148
ConstIterator end() const
Gets end node.
Definition irrList.h:281
Iterator getLast()
Gets last element.
Definition irrList.h:289
ConstIterator getLast() const
Gets last element.
Definition irrList.h:297
void swap(list< T > &other)
Swap the content of this list container with the content of another list.
Definition irrList.h:393
ConstIterator begin() const
Gets first node.
Definition irrList.h:265
bool empty() const
Checks for empty list.
Definition irrList.h:205
void insert_after(const Iterator &it, const T &element)
Inserts an element after an element.
Definition irrList.h:308
list()
Default constructor for empty list.
Definition irrList.h:136
Iterator end()
Gets end node.
Definition irrList.h:273
void clear()
Clears the list, deletes all elements in the list.
Definition irrList.h:187
Iterator begin()
Gets first node.
Definition irrList.h:257
void push_front(const T &element)
Adds an element at the begin of the list.
Definition irrList.h:234
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition irrMath.h:177
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
unsigned int u32
32 bit unsigned variable.
Definition irrTypes.h:58
signed int s32
32 bit signed variable.
Definition irrTypes.h:66