OpenNI 1.5.4
XnListT.h
Go to the documentation of this file.
1 #ifndef _XNLISTT_H_
2 #define _XNLISTT_H_
3 
4 //---------------------------------------------------------------------------
5 // Includes
6 //---------------------------------------------------------------------------
7 #include <XnPlatform.h>
8 #include <XnDataTypes.h>
9 #include <XnOS.h>
10 
11 //---------------------------------------------------------------------------
12 // Code
13 //---------------------------------------------------------------------------
14 
20 template<class T>
22 {
23  XnLinkedNodeT() : pPrev(NULL), pNext(NULL) {}
24  XnLinkedNodeT(T const& value) : pPrev(NULL), pNext(NULL), value(value) {}
25 
26  struct XnLinkedNodeT<T>* pPrev;
27  struct XnLinkedNodeT<T>* pNext;
28  T value;
29 };
30 
39 template<class T>
41 {
42 public:
44 
45  static LinkedNode* Allocate(T const& value)
46  {
47  return XN_NEW(LinkedNode, value);
48  }
49 
50  static void Deallocate(LinkedNode* pNode)
51  {
52  XN_DELETE(pNode);
53  }
54 };
55 
63 template<class T, class TAlloc = XnLinkedNodeDefaultAllocatorT<T> >
64 class XnListT
65 {
66 public:
68  typedef T TValue;
69  typedef TAlloc TAllocator;
70 
75  {
76  public:
77  inline ConstIterator() : m_pCurrent(NULL) {}
78 
79  inline ConstIterator(LinkedNode* pNode) : m_pCurrent(pNode) {}
80 
81  inline ConstIterator(const ConstIterator& other) : m_pCurrent(other.m_pCurrent) {}
82 
87  {
88  m_pCurrent = m_pCurrent->pNext;
89  return *this;
90  }
91 
96  {
97  ConstIterator retVal(*this);
98  ++*this;
99  return retVal;
100  }
101 
106  {
107  m_pCurrent = m_pCurrent->pPrev;
108  return *this;
109  }
110 
115  {
116  ConstIterator retVal(*this);
117  --*this;
118  return retVal;
119  }
120 
126  inline XnBool operator==(const ConstIterator& other) const
127  {
128  return m_pCurrent == other.m_pCurrent;
129  }
130 
136  inline XnBool operator!=(const ConstIterator& other) const
137  {
138  return m_pCurrent != other.m_pCurrent;
139  }
140 
144  inline T const& operator*() const
145  {
146  return m_pCurrent->value;
147  }
148 
152  inline T const* operator->() const
153  {
154  return &m_pCurrent->value;
155  }
156 
157  protected:
158  friend class XnListT;
159 
161  LinkedNode* m_pCurrent;
162  };
163 
167  class Iterator : public ConstIterator
168  {
169  public:
170  inline Iterator() : ConstIterator() {}
171 
172  inline Iterator(LinkedNode* pNode) : ConstIterator(pNode) {}
173 
174  inline Iterator(const Iterator& other) : ConstIterator(other) {}
175 
179  inline Iterator& operator++()
180  {
181  ++(*(ConstIterator*)this);
182  return (*this);
183  }
184 
188  inline Iterator operator++(int)
189  {
190  Iterator retVal(*this);
191  ++*this;
192  return (retVal);
193  }
194 
198  inline Iterator& operator--()
199  {
200  --(*(ConstIterator*)this);
201  return (*this);
202  }
206  inline Iterator operator--(int)
207  {
208  Iterator retVal(*this);
209  --*this;
210  return (retVal);
211  }
212 
216  inline T& operator*() const
217  {
218  return this->m_pCurrent->value;
219  }
220 
224  inline T* operator->() const
225  {
226  return &this->m_pCurrent->value;
227  }
228  };
229 
230 public:
232  {
233  Init();
234  }
235 
236  XnListT(const XnListT& other)
237  {
238  Init();
239  *this = other;
240  }
241 
242  XnListT& operator=(const XnListT& other)
243  {
244  Clear();
245 
246  XnStatus nRetVal = XN_STATUS_OK;
247 
248  for (ConstIterator it = other.Begin(); it != other.End(); ++it)
249  {
250  nRetVal = AddLast(*it);
251  XN_ASSERT(nRetVal == XN_STATUS_OK);
252  }
253 
254  return *this;
255  }
256 
258  {
259  Clear();
260  }
261 
265  Iterator Begin()
266  {
267  return Iterator(m_anchor.pNext);
268  }
269 
273  ConstIterator Begin() const
274  {
275  return ConstIterator(const_cast<LinkedNode*>(m_anchor.pNext));
276  }
277 
281  Iterator End()
282  {
283  return Iterator(&m_anchor);
284  }
285 
289  ConstIterator End() const
290  {
291  return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
292  }
293 
297  Iterator ReverseBegin()
298  {
299  return Iterator(m_anchor.pPrev);
300  }
301 
305  ConstIterator ReverseBegin() const
306  {
307  return ConstIterator(const_cast<LinkedNode*>(m_anchor.pPrev));
308  }
309 
313  Iterator ReverseEnd()
314  {
315  return Iterator(&m_anchor);
316  }
317 
321  ConstIterator ReverseEnd() const
322  {
323  return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
324  }
325 
335  XnStatus AddAfter(ConstIterator where, T const& value)
336  {
337  if (where == End())
338  {
339  return XN_STATUS_ILLEGAL_POSITION;
340  }
341 
342  return InsertAfter(where.m_pCurrent, value);
343  }
344 
354  XnStatus AddBefore(ConstIterator where, T const& value)
355  {
356  if (where == End())
357  {
358  return XN_STATUS_ILLEGAL_POSITION;
359  }
360 
361  return InsertAfter(where.m_pCurrent->pPrev, value);
362  }
363 
372  {
373  return InsertAfter(&m_anchor, value);
374  }
375 
384  {
385  return InsertAfter(ReverseBegin().m_pCurrent, value);
386  }
387 
395  ConstIterator Find(T const& value) const
396  {
397  ConstIterator iter = Begin();
398  for (; iter != End(); ++iter)
399  {
400  if (*iter == value)
401  break;
402  }
403  return iter;
404  }
405 
413  Iterator Find(T const& value)
414  {
415  ConstIterator iter = const_cast<const XnListT<T>*>(this)->Find(value);
416  return Iterator(iter.m_pCurrent);
417  }
418 
426  XnStatus Remove(ConstIterator where)
427  {
428  // Verify iterator is valid
429  if (where == End())
430  {
431  return XN_STATUS_ILLEGAL_POSITION;
432  }
433 
434  XnLinkedNodeT<T>* pToRemove = where.m_pCurrent;
435 
436  // Connect other nodes to bypass the one removed
437  pToRemove->pPrev->pNext = pToRemove->pNext;
438  pToRemove->pNext->pPrev = pToRemove->pPrev;
439 
440  --m_nSize;
441 
442  // Free memory
443  TAlloc::Deallocate(pToRemove);
444 
445  return XN_STATUS_OK;
446  }
447 
456  {
457  ConstIterator it = Find(value);
458  if (it != End())
459  {
460  return Remove(it);
461  }
462  else
463  {
464  return XN_STATUS_NO_MATCH;
465  }
466  }
467 
472  {
473  while (!IsEmpty())
474  Remove(Begin());
475 
476  return XN_STATUS_OK;
477  }
478 
482  XnBool IsEmpty() const
483  {
484  return (m_nSize == 0);
485  }
486 
490  XnUInt32 Size() const
491  {
492  return m_nSize;
493  }
494 
501  void CopyTo(T* pArray) const
502  {
503  XN_ASSERT(pArray != NULL);
504 
505  XnUInt32 i = 0;
506  for (ConstIterator iter = Begin(); iter != End(); ++iter, ++i)
507  {
508  pArray[i] = *iter;
509  }
510  }
511 
512 protected:
521  XnStatus InsertAfter(LinkedNode* pAfter, T const& val)
522  {
523  // Get a node from the pool for the entry
524  LinkedNode* pNewNode = TAlloc::Allocate(val);
525  if (pNewNode == NULL)
526  {
527  XN_ASSERT(FALSE);
528  return XN_STATUS_ALLOC_FAILED;
529  }
530  pNewNode->pPrev = pAfter;
531  pNewNode->pNext = pAfter->pNext;
532 
533  // push new node to position
534  pAfter->pNext->pPrev = pNewNode;
535  pAfter->pNext = pNewNode;
536 
537  ++m_nSize;
538 
539  return XN_STATUS_OK;
540  }
541 
542  // A dummy node, pointing to first node, and last node points back to it.
543  LinkedNode m_anchor;
544 
545  XnUInt32 m_nSize;
546 
547 private:
548  void Init()
549  {
550  m_anchor.pNext = &m_anchor;
551  m_anchor.pPrev = &m_anchor;
552  m_nSize = 0;
553  }
554 };
555 
556 #endif // _XNLISTT_H_
XnStatus InsertAfter(LinkedNode *pAfter, T const &val)
Definition: XnListT.h:521
ConstIterator Find(T const &value) const
Definition: XnListT.h:395
Iterator(const Iterator &other)
Definition: XnListT.h:174
void CopyTo(T *pArray) const
Definition: XnListT.h:501
XnBool IsEmpty() const
Definition: XnListT.h:482
struct XnLinkedNodeT< T > * pPrev
Definition: XnListT.h:26
#define FALSE
Definition: XnPlatform.h:94
struct XnLinkedNodeT< T > * pNext
Definition: XnListT.h:27
ConstIterator ReverseBegin() const
Definition: XnListT.h:305
XnUInt32 Size() const
Definition: XnListT.h:490
Iterator & operator++()
Definition: XnListT.h:179
XnListT(const XnListT &other)
Definition: XnListT.h:236
XnStatus AddBefore(ConstIterator where, T const &value)
Definition: XnListT.h:354
#define XN_STATUS_OK
Definition: XnStatus.h:37
ConstIterator operator--(int)
Definition: XnListT.h:114
T const & operator*() const
Definition: XnListT.h:144
LinkedNode m_anchor
Definition: XnListT.h:543
ConstIterator(const ConstIterator &other)
Definition: XnListT.h:81
Iterator ReverseBegin()
Definition: XnListT.h:297
Definition: XnListT.h:74
Iterator Find(T const &value)
Definition: XnListT.h:413
XnStatus Remove(T const &value)
Definition: XnListT.h:455
Definition: XnListT.h:40
Iterator operator--(int)
Definition: XnListT.h:206
T * operator->() const
Definition: XnListT.h:224
XnUInt32 XnStatus
Definition: XnStatus.h:34
XnBool operator!=(const ConstIterator &other) const
Definition: XnListT.h:136
XnLinkedNodeT< T > LinkedNode
Definition: XnListT.h:43
T TValue
Definition: XnListT.h:68
XnUInt32 m_nSize
Definition: XnListT.h:545
XnLinkedNodeT(T const &value)
Definition: XnListT.h:24
XnStatus AddFirst(T const &value)
Definition: XnListT.h:371
XnStatus AddAfter(ConstIterator where, T const &value)
Definition: XnListT.h:335
#define XN_NEW(type,...)
Definition: XnOS.h:326
static LinkedNode * Allocate(T const &value)
Definition: XnListT.h:45
ConstIterator ReverseEnd() const
Definition: XnListT.h:321
XnLinkedNodeT< T > LinkedNode
Definition: XnListT.h:67
Definition: XnListT.h:64
Iterator & operator--()
Definition: XnListT.h:198
T const * operator->() const
Definition: XnListT.h:152
Iterator Begin()
Definition: XnListT.h:265
ConstIterator Begin() const
Definition: XnListT.h:273
ConstIterator()
Definition: XnListT.h:77
XnStatus Clear()
Definition: XnListT.h:471
Iterator operator++(int)
Definition: XnListT.h:188
XnLinkedNodeT()
Definition: XnListT.h:23
T value
Definition: XnListT.h:28
ConstIterator & operator--()
Definition: XnListT.h:105
static void Deallocate(LinkedNode *pNode)
Definition: XnListT.h:50
#define XN_DELETE(p)
Definition: XnOS.h:336
Iterator(LinkedNode *pNode)
Definition: XnListT.h:172
XnStatus Remove(ConstIterator where)
Definition: XnListT.h:426
Definition: XnListT.h:167
ConstIterator(LinkedNode *pNode)
Definition: XnListT.h:79
Iterator End()
Definition: XnListT.h:281
TAlloc TAllocator
Definition: XnListT.h:69
ConstIterator End() const
Definition: XnListT.h:289
ConstIterator & operator++()
Definition: XnListT.h:86
Iterator()
Definition: XnListT.h:170
T & operator*() const
Definition: XnListT.h:216
Definition: XnListT.h:21
~XnListT()
Definition: XnListT.h:257
XnBool operator==(const ConstIterator &other) const
Definition: XnListT.h:126
XnListT()
Definition: XnListT.h:231
XnListT & operator=(const XnListT &other)
Definition: XnListT.h:242
LinkedNode * m_pCurrent
Definition: XnListT.h:161
ConstIterator operator++(int)
Definition: XnListT.h:95
Iterator ReverseEnd()
Definition: XnListT.h:313
XnStatus AddLast(T const &value)
Definition: XnListT.h:383