tList.h

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _TORQUE_LIST_
 25#define _TORQUE_LIST_
 26
 27#ifndef _TORQUE_TYPES_H_
 28#include "platform/types.h"
 29#endif
 30
 31namespace Torque
 32{
 33
 34/// A list template class.
 35/// A classic list class similar to the STL list class. The list
 36/// class supports fast insert and erase operations, but slow dynamic
 37/// access. The list is circular and the iterator supports iterating
 38/// past the end() or rend() in order to loop around.
 39/// @ingroup UtilContainers
 40template<typename Type>
 41class List
 42{
 43   struct Link;
 44   struct PrivatePersist {};  ///< Used instead of a (void *) for type-safety of persistent iterators
 45
 46public:
 47   /// A PersistentIter is used for the special cases where you need to store an iterator for
 48   /// efficiency reasons.  The _Iterator class handles the conversion to/from PersistentIter.
 49   /// @note The data in the node this points to could go away, so only use these in cases where
 50   ///  you control the allocation/deallocation of the nodes in the list.
 51   typedef  PrivatePersist *PersistentIter;
 52
 53   // Iterator support
 54   template<typename U,typename E>
 55   class _Iterator
 56   {
 57   public:
 58      typedef U  ValueType;
 59      typedef U* Pointer;
 60      typedef U& Reference;
 61
 62      _Iterator();
 63      _Iterator(PersistentIter &iter) { _link = (Link *)iter; }
 64 
 65      operator PersistentIter() const { return (PrivatePersist *)_link; }
 66
 67      _Iterator& operator++();
 68      _Iterator  operator++(int);
 69      _Iterator& operator--();
 70      _Iterator  operator--(int);
 71      bool operator==(const _Iterator&) const;
 72      bool operator!=(const _Iterator&) const;
 73      U* operator->() const;
 74      U& operator*() const;
 75
 76   private:
 77      friend class List;
 78
 79      E* _link;
 80      _Iterator(E*);
 81   };
 82
 83   // types
 84   typedef Type        ValueType;
 85   typedef Type&       Reference;
 86   typedef const Type& ConstReference;
 87
 88   typedef _Iterator<Type,Link>              Iterator;
 89   typedef _Iterator<const Type,const Link>  ConstIterator;
 90
 91   typedef S32         DifferenceType;
 92   typedef U32         SizeType;
 93
 94   // initialization
 95   List();
 96   ~List();
 97   List(const List& p);
 98
 99   // management
100   U32  getSize() const;               ///< Return the number of elements
101   void resize(U32);                   ///< Set the list size
102   void clear();                       ///< Empty the List
103   bool isEmpty() const;               ///< Node count == 0?
104
105   // insert elements
106   Iterator insert(U32 index, const Type& = Type());  ///< Insert new element at the given index
107   Iterator insert(Iterator, const Type& = Type());   ///< Insert at the given iter
108   Iterator pushFront(const Type& = Type());    ///< Insert at first element
109   Iterator pushBack(const Type& = Type());     ///< Insert after the last element
110
111   // erase elements
112   void erase(U32);                    ///< Preserves element order
113   void erase(Iterator);               ///< Preserves element order
114   void popFront();                    ///< Remove the first element
115   void popBack();                     ///< Remove the last element
116
117   // forward Iterator access
118   Iterator begin();                   ///< _Iterator to first element
119   ConstIterator begin() const;        ///< _Iterator to first element
120   Iterator end();                     ///< _Iterator to last element + 1
121   ConstIterator end() const;          ///< _Iterator to last element + 1
122
123   // reverse Iterator access
124   Iterator rbegin();                  ///< _Iterator to first element - 1
125   ConstIterator rbegin() const;       ///< _Iterator to first element - 1
126   Iterator rend();                    ///< _Iterator to last element
127   ConstIterator rend() const;         ///< _Iterator to last element
128
129   // type access
130   Type&       first();                ///< First element
131   const Type& first() const;          ///< First element
132   Type&       last();                 ///< Last element
133   const Type& last() const;           ///< Last element
134
135   // operators
136   void operator=(const List& p);
137   Type& operator[](U32);
138   const Type& operator[](U32) const;
139
140private:
141   struct Link
142   {
143      Link* next;
144      Link* prev;
145      Link(): next(NULL), prev(NULL) {}
146      Link(Link* p,Link* n): next(n),prev(p) {}
147   };
148
149   struct Node: Link
150   {
151      Type value;
152      Node() {}
153      Node(Link* p,Link* n,const Type& x): Link(p,n),value(x) {}
154   };
155
156   Link _head;
157   U32 _size;
158
159   Link* _node(U32 index) const;
160   void _destroy();
161};
162
163template<class Type> List<Type>::List()
164{
165   _size = 0;
166   _head.next = &_head;
167   _head.prev = &_head;
168}
169
170template<class Type> List<Type>::List(const List& p)
171{
172   _size = 0;
173   _head.next = &_head;
174   _head.prev = &_head;
175   *this = p;
176}
177
178template<class Type> List<Type>::~List()
179{
180   _destroy();
181}
182
183
184//-----------------------------------------------------------------------------
185
186template<class Type> typename List<Type>::Link* List<Type>::_node(U32 index) const
187{
188   Iterator itr(_head.next);
189   while (index--)
190      itr++;
191   return itr._link;
192}
193
194template<class Type> void List<Type>::_destroy()
195{
196   for (Iterator itr(begin()); itr != end(); )
197   {
198      Node* n = static_cast<Node*>((itr++)._link);
199      delete n;
200   }
201}
202
203
204//-----------------------------------------------------------------------------
205// management
206
207template<class Type> inline U32 List<Type>::getSize() const
208{
209   return _size;
210}
211
212template<class Type> void List<Type>::resize(U32 size)
213{
214   if (size > _size)
215   {
216      while (_size != size)
217         pushBack(Type());
218   }
219   else
220   {
221      while (_size != size)
222         popBack();
223   }
224}
225
226template<class Type> void List<Type>::clear()
227{
228   _destroy();
229   _head.next = &_head;
230   _head.prev = &_head;
231   _size = 0;
232}
233
234template<class Type> inline bool List<Type>::isEmpty() const
235{
236   return _size == 0;
237}
238
239
240//-----------------------------------------------------------------------------
241// add Nodes
242
243template<class Type> typename List<Type>::Iterator List<Type>::insert(Iterator itr, const Type& x)
244{
245   Link* node = itr._link;
246   Node* n = new Node(node->prev,node,x);
247   node->prev->next = n;
248   node->prev = n;
249   _size++;
250   return n;
251}
252
253template<class Type> inline typename List<Type>::Iterator List<Type>::insert(U32 index, const Type& x)
254{
255   return insert(_node(index),x);
256}
257
258template<class Type> inline typename List<Type>::Iterator List<Type>::pushFront(const Type& x)
259{
260   return insert(_head.next,x);
261}
262
263template<class Type> inline typename List<Type>::Iterator List<Type>::pushBack(const Type& x)
264{
265   return insert(&_head,x);
266}
267
268
269//-----------------------------------------------------------------------------
270// remove elements
271
272template<class Type> void List<Type>::erase(Iterator itr)
273{
274   Node* node = static_cast<Node*>(itr._link);
275   node->prev->next = node->next;
276   node->next->prev = node->prev;
277   delete node;
278   _size--;
279}
280
281template<class Type> inline void List<Type>::erase(U32 index)
282{
283   erase(_node(index));
284}
285
286template<class Type> inline void List<Type>::popFront()
287{
288   erase(_head.next);
289}
290
291template<class Type> inline void List<Type>::popBack()
292{
293   erase(_head.prev);
294}
295
296
297//-----------------------------------------------------------------------------
298// Iterator access
299
300template<class Type> inline typename List<Type>::Iterator List<Type>::begin()
301{
302   return _head.next;
303}
304
305template<class Type> inline typename List<Type>::ConstIterator List<Type>::begin() const
306{
307   return _head.next;
308}
309
310template<class Type> inline typename List<Type>::Iterator List<Type>::end()
311{
312   return &_head;
313}
314
315template<class Type> inline typename List<Type>::ConstIterator List<Type>::end() const
316{
317   return &_head;
318}
319
320template<class Type> inline typename List<Type>::Iterator List<Type>::rbegin()
321{
322   return _head.prev;
323}
324
325template<class Type> inline typename List<Type>::ConstIterator List<Type>::rbegin() const
326{
327   return _head.prev;
328}
329
330template<class Type> inline typename List<Type>::Iterator List<Type>::rend()
331{
332   return &_head;
333}
334
335template<class Type> inline typename List<Type>::ConstIterator List<Type>::rend() const
336{
337   return &_head;
338}
339
340
341//-----------------------------------------------------------------------------
342// type access
343
344template<class Type> inline Type& List<Type>::first()
345{
346   return static_cast<Node*>(_head.next)->value;
347}
348
349template<class Type> inline const Type& List<Type>::first() const
350{
351   return static_cast<Node*>(_head.next)->value;
352}
353
354template<class Type> inline Type& List<Type>::last()
355{
356   return static_cast<Node*>(_head.prev)->value;
357}
358
359template<class Type> inline const Type& List<Type>::last() const
360{
361   return static_cast<Node*>(_head.prev)->value;
362}
363
364
365//-----------------------------------------------------------------------------
366// operators
367
368template<class Type> void List<Type>::operator=(const List& p)
369{
370   if (_size >= p._size)
371   {
372      // Destroy the elements we're not going to use and copy the rest
373      while (_size != p._size)
374         popBack();
375   }
376
377   U32 count = _size;
378   ConstIterator src = p.begin();
379   Iterator dst = begin();
380   while (count--)
381      *dst++ = *src++;
382   while (src != p.end())
383      pushBack(*src++);
384}
385
386template<class Type> inline Type& List<Type>::operator[](U32 index)
387{
388   return static_cast<Node*>(_node(index))->value;
389}
390
391template<class Type> inline const Type& List<Type>::operator[](U32 index) const
392{
393   return static_cast<Node*>(_node(index))->value;
394}
395
396//-----------------------------------------------------------------------------
397// _Iterator class
398
399template<class Type> template<class U,typename E>
400inline List<Type>::_Iterator<U,E>::_Iterator()
401{
402   _link = 0;
403}
404
405template<class Type> template<class U,typename E>
406inline List<Type>::_Iterator<U,E>::_Iterator(E* ptr)
407{
408   _link = ptr;
409}
410
411// The checking for _MSC_VER on the ++/-- operators is due to a bug with the VS2008 compiler
412// recheck this and remove if fixed with VS2008 SP1
413
414template<class Type> template<class U,typename E>
415#ifdef _MSC_VER
416inline typename List<Type>:: _Iterator<U,E>& List<Type>::_Iterator<U,E>::operator++()
417#else
418inline typename List<Type>::template _Iterator<U,E>& List<Type>::_Iterator<U,E>::operator++()
419#endif
420{
421   _link = _link->next;
422   return *this;
423}
424
425template<class Type> template<class U,typename E>
426#ifdef _MSC_VER
427inline typename List<Type>::_Iterator<U,E> List<Type>::_Iterator<U,E>::operator++(int)
428#else
429inline typename List<Type>::template _Iterator<U,E> List<Type>::_Iterator<U,E>::operator++(int)
430#endif
431{
432   _Iterator itr(*this);
433   _link = _link->next;
434   return itr;
435}
436
437template<class Type> template<class U,typename E>
438#ifdef _MSC_VER
439inline typename List<Type>::_Iterator<U,E>& List<Type>::_Iterator<U,E>::operator--()
440#else
441inline typename List<Type>::template _Iterator<U,E>& List<Type>::_Iterator<U,E>::operator--()
442#endif
443{
444   _link = _link->prev;
445   return *this;
446}
447
448template<class Type> template<class U,typename E>
449#ifdef _MSC_VER
450inline typename List<Type>::_Iterator<U,E> List<Type>::_Iterator<U,E>::operator--(int)
451#else
452inline typename List<Type>::template _Iterator<U,E> List<Type>::_Iterator<U,E>::operator--(int)
453#endif
454{
455   _Iterator itr(*this);
456   _link = _link->prev;
457   return itr;
458}
459
460template<class Type> template<class U,typename E>
461inline bool List<Type>::_Iterator<U,E>::operator==(const _Iterator& b) const
462{
463   return _link == b._link;
464}
465
466template<class Type> template<class U,typename E>
467inline bool List<Type>::_Iterator<U,E>::operator!=(const _Iterator& b) const
468{
469   return !(_link == b._link);
470}
471
472template<class Type> template<class U,typename E>
473inline U* List<Type>::_Iterator<U,E>::operator->() const
474{
475   // Can't use static_cast because of const / non-const versions of Iterator.
476   // Could use reflection functions, but C-style cast is easier in this case.
477   return &((Node*)_link)->value;
478}
479
480template<class Type> template<class U,typename E>
481inline U& List<Type>::_Iterator<U,E>::operator*() const
482{
483   // Can't use static_cast because of const / non-const versions of Iterator.
484   // Could use reflection functions, but C-style cast is easier in this case.
485   return ((Node*)_link)->value;
486}
487
488}  // Namespace
489
490#endif // _TORQUE_LIST_
491
492