Line data Source code
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 :
18 : //! Doubly linked list template.
19 : template <class T>
20 : class list
21 : {
22 : private:
23 :
24 : //! List element node with pointer to previous and next element in the list.
25 : struct SKListNode
26 : {
27 861 : 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 :
37 : //! List iterator.
38 : class Iterator
39 : {
40 : public:
41 : Iterator() : Current(0) {}
42 :
43 254346 : Iterator& operator ++() { Current = Current->Next; return *this; }
44 23122 : Iterator& operator --() { Current = Current->Prev; return *this; }
45 0 : 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 562473 : 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 282306 : T & operator * () { return Current->Element; }
75 : T * operator ->() { return &Current->Element; }
76 :
77 : private:
78 856848 : explicit Iterator(SKListNode* begin) : Current(begin) {}
79 :
80 : SKListNode* Current;
81 :
82 : friend class list<T>;
83 : friend class ConstIterator;
84 : };
85 :
86 : //! List iterator for const access.
87 : class ConstIterator
88 : {
89 : public:
90 :
91 : ConstIterator() : Current(0) {}
92 : ConstIterator(const Iterator& iter) : Current(iter.Current) {}
93 :
94 238 : ConstIterator& operator ++() { Current = Current->Next; return *this; }
95 : ConstIterator& operator --() { Current = Current->Prev; return *this; }
96 0 : 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 358 : 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 690 : 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 510 : explicit ConstIterator(SKListNode* begin) : Current(begin) {}
128 :
129 : SKListNode* Current;
130 :
131 : friend class Iterator;
132 : friend class list<T>;
133 : };
134 :
135 : //! Default constructor for empty list.
136 523 : list()
137 523 : : First(0), Last(0), Size(0) {}
138 :
139 :
140 : //! Copy constructor.
141 3 : list(const list<T>& other) : First(0), Last(0), Size(0)
142 : {
143 3 : *this = other;
144 3 : }
145 :
146 :
147 : //! Destructor
148 529 : ~list()
149 : {
150 529 : clear();
151 529 : }
152 :
153 :
154 : //! Assignment operator
155 3 : void operator=(const list<T>& other)
156 : {
157 3 : if(&other == this)
158 : {
159 0 : return;
160 : }
161 :
162 3 : clear();
163 :
164 3 : SKListNode* node = other.First;
165 27 : while(node)
166 : {
167 12 : push_back(node->Element);
168 12 : node = node->Next;
169 : }
170 : }
171 :
172 :
173 : //! Returns amount of elements in list.
174 : /** \return Amount of elements in the list. */
175 : u32 size() const
176 : {
177 : return Size;
178 : }
179 : u32 getSize() const
180 : {
181 : return Size;
182 : }
183 :
184 :
185 : //! Clears the list, deletes all elements in the list.
186 : /** All existing iterators of this list will be invalid. */
187 837 : void clear()
188 : {
189 878 : while(First)
190 : {
191 41 : SKListNode * next = First->Next;
192 41 : allocator.destruct(First);
193 41 : allocator.deallocate(First);
194 41 : First = next;
195 : }
196 :
197 : //First = 0; handled by loop
198 796 : Last = 0;
199 796 : Size = 0;
200 796 : }
201 :
202 :
203 : //! Checks for empty list.
204 : /** \return True if the list is empty and false if not. */
205 41 : bool empty() const
206 : {
207 41 : return (First == 0);
208 : }
209 :
210 :
211 : //! Adds an element at the end of the list.
212 : /** \param element Element to add to the list. */
213 861 : void push_back(const T& element)
214 : {
215 861 : SKListNode* node = allocator.allocate(1);
216 861 : allocator.construct(node, element);
217 :
218 861 : ++Size;
219 :
220 861 : if (First == 0)
221 179 : First = node;
222 :
223 861 : node->Prev = Last;
224 :
225 861 : if (Last != 0)
226 682 : Last->Next = node;
227 :
228 861 : Last = node;
229 861 : }
230 :
231 :
232 : //! Adds an element at the begin of the list.
233 : /** \param element: Element to add to the list. */
234 0 : void push_front(const T& element)
235 : {
236 0 : SKListNode* node = allocator.allocate(1);
237 0 : allocator.construct(node, element);
238 :
239 0 : ++Size;
240 :
241 0 : if (First == 0)
242 : {
243 0 : Last = node;
244 0 : First = node;
245 : }
246 : else
247 : {
248 0 : node->Next = First;
249 0 : First->Prev = node;
250 0 : First = node;
251 : }
252 0 : }
253 :
254 :
255 : //! Gets first node.
256 : /** \return A list iterator pointing to the beginning of the list. */
257 264757 : Iterator begin()
258 : {
259 264757 : return Iterator(First);
260 : }
261 :
262 :
263 : //! Gets first node.
264 : /** \return A const list iterator pointing to the beginning of the list. */
265 120 : ConstIterator begin() const
266 : {
267 120 : return ConstIterator(First);
268 : }
269 :
270 :
271 : //! Gets end node.
272 : /** \return List iterator pointing to null. */
273 562473 : Iterator end()
274 : {
275 562473 : return Iterator(0);
276 : }
277 :
278 :
279 : //! Gets end node.
280 : /** \return Const list iterator pointing to null. */
281 358 : ConstIterator end() const
282 : {
283 358 : return ConstIterator(0);
284 : }
285 :
286 :
287 : //! Gets last element.
288 : /** \return List iterator pointing to the last element of the list. */
289 29618 : Iterator getLast()
290 : {
291 29618 : return Iterator(Last);
292 : }
293 :
294 :
295 : //! Gets last element.
296 : /** \return Const list iterator pointing to the last element of the list. */
297 32 : ConstIterator getLast() const
298 : {
299 32 : return ConstIterator(Last);
300 : }
301 :
302 :
303 : //! Inserts an element after an element.
304 : /** \param it Iterator pointing to element after which the new element
305 : should be inserted.
306 : \param element The new element to be inserted into the list.
307 : */
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 :
327 : //! Inserts an element before an element.
328 : /** \param it Iterator pointing to element before which the new element
329 : should be inserted.
330 : \param element The new element to be inserted into the list.
331 : */
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 :
351 : //! Erases an element.
352 : /** \param it Iterator pointing to the element which shall be erased.
353 : \return Iterator pointing to next element. */
354 673 : 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 673 : Iterator returnIterator(it);
360 673 : ++returnIterator;
361 :
362 673 : if(it.Current == First)
363 : {
364 22 : First = it.Current->Next;
365 : }
366 : else
367 : {
368 651 : it.Current->Prev->Next = it.Current->Next;
369 : }
370 :
371 673 : if(it.Current == Last)
372 : {
373 283 : Last = it.Current->Prev;
374 : }
375 : else
376 : {
377 390 : it.Current->Next->Prev = it.Current->Prev;
378 : }
379 :
380 673 : allocator.destruct(it.Current);
381 673 : allocator.deallocate(it.Current);
382 673 : it.Current = 0;
383 673 : --Size;
384 :
385 673 : return returnIterator;
386 : }
387 :
388 : //! Swap the content of this list container with the content of another list
389 : /** Afterwards this object will contain the content of the other object and the other
390 : object will contain the content of this object. Iterators will afterwards be valid for
391 : the swapped object.
392 : \param other Swap content with this object */
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 :
|
