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
5 #ifndef __IRR_LIST_H_INCLUDED__
\r
6 #define __IRR_LIST_H_INCLUDED__
\r
8 #include "irrTypes.h"
\r
9 #include "irrAllocator.h"
\r
10 #include "irrMath.h"
\r
18 //! Doubly linked list template.
\r
24 //! List element node with pointer to previous and next element in the list.
\r
27 SKListNode(const T& e) : Next(0), Prev(0), Element(e) {}
\r
35 class ConstIterator;
\r
41 Iterator() : Current(0) {}
\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
48 Iterator& operator +=(s32 num)
\r
52 while (num-- && this->Current != 0) ++(*this);
\r
56 while(num++ && this->Current != 0) --(*this);
\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
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
70 T & operator * () { return Current->Element; }
\r
71 T * operator ->() { return &Current->Element; }
\r
74 explicit Iterator(SKListNode* begin) : Current(begin) {}
\r
76 SKListNode* Current;
\r
78 friend class list<T>;
\r
79 friend class ConstIterator;
\r
82 //! List iterator for const access.
\r
87 ConstIterator() : Current(0) {}
\r
88 ConstIterator(const Iterator& iter) : Current(iter.Current) {}
\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
95 ConstIterator& operator +=(s32 num)
\r
99 while(num-- && this->Current != 0) ++(*this);
\r
103 while(num++ && this->Current != 0) --(*this);
\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
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
117 const T & operator * () { return Current->Element; }
\r
118 const T * operator ->() { return &Current->Element; }
\r
120 ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }
\r
123 explicit ConstIterator(SKListNode* begin) : Current(begin) {}
\r
125 SKListNode* Current;
\r
127 friend class Iterator;
\r
128 friend class list<T>;
\r
131 //! Default constructor for empty list.
\r
133 : First(0), Last(0), Size(0) {}
\r
136 //! Copy constructor.
\r
137 list(const list<T>& other) : First(0), Last(0), Size(0)
\r
150 //! Assignment operator
\r
151 void operator=(const list<T>& other)
\r
160 SKListNode* node = other.First;
\r
163 push_back(node->Element);
\r
169 //! Returns amount of elements in list.
\r
170 /** \return Amount of elements in the list. */
\r
175 u32 getSize() const
\r
181 //! Clears the list, deletes all elements in the list.
\r
182 /** All existing iterators of this list will be invalid. */
\r
187 SKListNode * next = First->Next;
\r
188 allocator.destruct(First);
\r
189 allocator.deallocate(First);
\r
193 //First = 0; handled by loop
\r
199 //! Checks for empty list.
\r
200 /** \return True if the list is empty and false if not. */
\r
203 return (First == 0);
\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
211 SKListNode* node = allocator.allocate(1);
\r
212 allocator.construct(node, element);
\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
232 SKListNode* node = allocator.allocate(1);
\r
233 allocator.construct(node, element);
\r
244 node->Next = First;
\r
245 First->Prev = node;
\r
251 //! Gets first node.
\r
252 /** \return A list iterator pointing to the beginning of the list. */
\r
255 return Iterator(First);
\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
263 return ConstIterator(First);
\r
268 /** \return List iterator pointing to null. */
\r
271 return Iterator(0);
\r
276 /** \return Const list iterator pointing to null. */
\r
277 ConstIterator end() const
\r
279 return ConstIterator(0);
\r
283 //! Gets last element.
\r
284 /** \return List iterator pointing to the last element of the list. */
\r
287 return Iterator(Last);
\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
295 return ConstIterator(Last);
\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
304 void insert_after(const Iterator& it, const T& element)
\r
306 SKListNode* node = allocator.allocate(1);
\r
307 allocator.construct(node, element);
\r
309 node->Next = it.Current->Next;
\r
311 if (it.Current->Next)
\r
312 it.Current->Next->Prev = node;
\r
314 node->Prev = it.Current;
\r
315 it.Current->Next = node;
\r
318 if (it.Current == Last)
\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
328 void insert_before(const Iterator& it, const T& element)
\r
330 SKListNode* node = allocator.allocate(1);
\r
331 allocator.construct(node, element);
\r
333 node->Prev = it.Current->Prev;
\r
335 if (it.Current->Prev)
\r
336 it.Current->Prev->Next = node;
\r
338 node->Next = it.Current;
\r
339 it.Current->Prev = node;
\r
342 if (it.Current == First)
\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
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
355 Iterator returnIterator(it);
\r
358 if(it.Current == First)
\r
360 First = it.Current->Next;
\r
364 it.Current->Prev->Next = it.Current->Next;
\r
367 if(it.Current == Last)
\r
369 Last = it.Current->Prev;
\r
373 it.Current->Next->Prev = it.Current->Prev;
\r
376 allocator.destruct(it.Current);
\r
377 allocator.deallocate(it.Current);
\r
381 return returnIterator;
\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
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
397 typedef T value_type;
\r
398 typedef u32 size_type;
\r
405 irrAllocator<SKListNode> allocator;
\r
410 } // end namespace core
\r
411 }// end namespace irr
\r