OpenNI 1.5.7
XnListT.h
Go to the documentation of this file.
1 /*****************************************************************************
2 * *
3 * OpenNI 1.x Alpha *
4 * Copyright (C) 2012 PrimeSense Ltd. *
5 * *
6 * This file is part of OpenNI. *
7 * *
8 * Licensed under the Apache License, Version 2.0 (the "License"); *
9 * you may not use this file except in compliance with the License. *
10 * You may obtain a copy of the License at *
11 * *
12 * http://www.apache.org/licenses/LICENSE-2.0 *
13 * *
14 * Unless required by applicable law or agreed to in writing, software *
15 * distributed under the License is distributed on an "AS IS" BASIS, *
16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
17 * See the License for the specific language governing permissions and *
18 * limitations under the License. *
19 * *
20 *****************************************************************************/
21 #ifndef _XNLISTT_H_
22 #define _XNLISTT_H_
23 
24 //---------------------------------------------------------------------------
25 // Includes
26 //---------------------------------------------------------------------------
27 #include <XnPlatform.h>
28 #include <XnDataTypes.h>
29 #include <XnOS.h>
30 
31 //---------------------------------------------------------------------------
32 // Code
33 //---------------------------------------------------------------------------
34 
40 template<class T>
41 struct XnLinkedNodeT
42 {
43  XnLinkedNodeT() : pPrev(NULL), pNext(NULL) {}
44  XnLinkedNodeT(T const& value) : pPrev(NULL), pNext(NULL), value(value) {}
45 
46  struct XnLinkedNodeT<T>* pPrev;
47  struct XnLinkedNodeT<T>* pNext;
48  T value;
49 };
50 
59 template<class T>
61 {
62 public:
64 
65  static LinkedNode* Allocate(T const& value)
66  {
67  return XN_NEW(LinkedNode, value);
68  }
69 
70  static void Deallocate(LinkedNode* pNode)
71  {
72  XN_DELETE(pNode);
73  }
74 };
75 
83 template<class T, class TAlloc = XnLinkedNodeDefaultAllocatorT<T> >
84 class XnListT
85 {
86 public:
88  typedef T TValue;
89  typedef TAlloc TAllocator;
90 
94  class ConstIterator
95  {
96  public:
97  inline ConstIterator() : m_pCurrent(NULL) {}
98 
99  inline ConstIterator(LinkedNode* pNode) : m_pCurrent(pNode) {}
100 
101  inline ConstIterator(const ConstIterator& other) : m_pCurrent(other.m_pCurrent) {}
102 
106  inline ConstIterator& operator++()
107  {
109  return *this;
110  }
111 
115  inline ConstIterator operator++(int)
116  {
117  ConstIterator retVal(*this);
118  ++*this;
119  return retVal;
120  }
121 
125  inline ConstIterator& operator--()
126  {
128  return *this;
129  }
130 
134  inline ConstIterator operator--(int)
135  {
136  ConstIterator retVal(*this);
137  --*this;
138  return retVal;
139  }
140 
146  inline XnBool operator==(const ConstIterator& other) const
147  {
148  return m_pCurrent == other.m_pCurrent;
149  }
150 
156  inline XnBool operator!=(const ConstIterator& other) const
157  {
158  return m_pCurrent != other.m_pCurrent;
159  }
160 
164  inline T const& operator*() const
165  {
166  return m_pCurrent->value;
167  }
168 
172  inline T const* operator->() const
173  {
174  return &m_pCurrent->value;
175  }
176 
177  protected:
178  friend class XnListT;
179 
182  };
183 
187  class Iterator : public ConstIterator
188  {
189  public:
190  inline Iterator() : ConstIterator() {}
191 
192  inline Iterator(LinkedNode* pNode) : ConstIterator(pNode) {}
193 
194  inline Iterator(const Iterator& other) : ConstIterator(other) {}
195 
199  inline Iterator& operator++()
200  {
201  ++(*(ConstIterator*)this);
202  return (*this);
203  }
204 
208  inline Iterator operator++(int)
209  {
210  Iterator retVal(*this);
211  ++*this;
212  return (retVal);
213  }
214 
218  inline Iterator& operator--()
219  {
220  --(*(ConstIterator*)this);
221  return (*this);
222  }
226  inline Iterator operator--(int)
227  {
228  Iterator retVal(*this);
229  --*this;
230  return (retVal);
231  }
232 
236  inline T& operator*() const
237  {
238  return this->m_pCurrent->value;
239  }
240 
244  inline T* operator->() const
245  {
246  return &this->m_pCurrent->value;
247  }
248  };
249 
250 public:
251  XnListT()
252  {
253  Init();
254  }
255 
256  XnListT(const XnListT& other)
257  {
258  Init();
259  *this = other;
260  }
261 
262  XnListT& operator=(const XnListT& other)
263  {
264  Clear();
265 
266  XnStatus nRetVal = XN_STATUS_OK;
267 
268  for (ConstIterator it = other.Begin(); it != other.End(); ++it)
269  {
270  nRetVal = AddLast(*it);
271  XN_ASSERT(nRetVal == XN_STATUS_OK);
272  }
273 
274  return *this;
275  }
276 
277  ~XnListT()
278  {
279  Clear();
280  }
281 
285  Iterator Begin()
286  {
287  return Iterator(m_anchor.pNext);
288  }
289 
293  ConstIterator Begin() const
294  {
295  return ConstIterator(const_cast<LinkedNode*>(m_anchor.pNext));
296  }
297 
301  Iterator End()
302  {
303  return Iterator(&m_anchor);
304  }
305 
309  ConstIterator End() const
310  {
311  return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
312  }
313 
317  Iterator ReverseBegin()
318  {
319  return Iterator(m_anchor.pPrev);
320  }
321 
325  ConstIterator ReverseBegin() const
326  {
327  return ConstIterator(const_cast<LinkedNode*>(m_anchor.pPrev));
328  }
329 
333  Iterator ReverseEnd()
334  {
335  return Iterator(&m_anchor);
336  }
337 
341  ConstIterator ReverseEnd() const
342  {
343  return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
344  }
345 
355  XnStatus AddAfter(ConstIterator where, T const& value)
356  {
357  if (where == End())
358  {
359  return XN_STATUS_ILLEGAL_POSITION;
360  }
361 
362  return InsertAfter(where.m_pCurrent, value);
363  }
364 
374  XnStatus AddBefore(ConstIterator where, T const& value)
375  {
376  if (where == End())
377  {
378  return XN_STATUS_ILLEGAL_POSITION;
379  }
380 
381  return InsertAfter(where.m_pCurrent->pPrev, value);
382  }
383 
391  XnStatus AddFirst(T const& value)
392  {
393  return InsertAfter(&m_anchor, value);
394  }
395 
403  XnStatus AddLast(T const& value)
404  {
405  return InsertAfter(ReverseBegin().m_pCurrent, value);
406  }
407 
415  ConstIterator Find(T const& value) const
416  {
417  ConstIterator iter = Begin();
418  for (; iter != End(); ++iter)
419  {
420  if (*iter == value)
421  break;
422  }
423  return iter;
424  }
425 
433  Iterator Find(T const& value)
434  {
435  ConstIterator iter = const_cast<const XnListT<T>*>(this)->Find(value);
436  return Iterator(iter.m_pCurrent);
437  }
438 
446  XnStatus Remove(ConstIterator where)
447  {
448  // Verify iterator is valid
449  if (where == End())
450  {
451  return XN_STATUS_ILLEGAL_POSITION;
452  }
453 
454  XnLinkedNodeT<T>* pToRemove = where.m_pCurrent;
455 
456  // Connect other nodes to bypass the one removed
457  pToRemove->pPrev->pNext = pToRemove->pNext;
458  pToRemove->pNext->pPrev = pToRemove->pPrev;
459 
460  --m_nSize;
461 
462  // Free memory
463  TAlloc::Deallocate(pToRemove);
464 
465  return XN_STATUS_OK;
466  }
467 
475  XnStatus Remove(T const& value)
476  {
477  ConstIterator it = Find(value);
478  if (it != End())
479  {
480  return Remove(it);
481  }
482  else
483  {
484  return XN_STATUS_NO_MATCH;
485  }
486  }
487 
491  XnStatus Clear()
492  {
493  while (!IsEmpty())
494  Remove(Begin());
495 
496  return XN_STATUS_OK;
497  }
498 
502  XnBool IsEmpty() const
503  {
504  return (m_nSize == 0);
505  }
506 
510  XnUInt32 Size() const
511  {
512  return m_nSize;
513  }
514 
521  void CopyTo(T* pArray) const
522  {
523  XN_ASSERT(pArray != NULL);
524 
525  XnUInt32 i = 0;
526  for (ConstIterator iter = Begin(); iter != End(); ++iter, ++i)
527  {
528  pArray[i] = *iter;
529  }
530  }
531 
532 protected:
541  XnStatus InsertAfter(LinkedNode* pAfter, T const& val)
542  {
543  // Get a node from the pool for the entry
544  LinkedNode* pNewNode = TAlloc::Allocate(val);
545  if (pNewNode == NULL)
546  {
547  XN_ASSERT(FALSE);
548  return XN_STATUS_ALLOC_FAILED;
549  }
550  pNewNode->pPrev = pAfter;
551  pNewNode->pNext = pAfter->pNext;
552 
553  // push new node to position
554  pAfter->pNext->pPrev = pNewNode;
555  pAfter->pNext = pNewNode;
556 
557  ++m_nSize;
558 
559  return XN_STATUS_OK;
560  }
561 
562  // A dummy node, pointing to first node, and last node points back to it.
564 
565  XnUInt32 m_nSize;
566 
567 private:
568  void Init()
569  {
572  m_nSize = 0;
573  }
574 };
575 
576 #endif // _XNLISTT_H_
XnListT::TValue
T TValue
Definition: XnListT.h:87
XnListT::Clear
XnStatus Clear()
Definition: XnListT.h:490
XnListT::ConstIterator::ConstIterator
ConstIterator()
Definition: XnListT.h:96
XnOS.h
XnDataTypes.h
XnListT::End
Iterator End()
Definition: XnListT.h:300
XnListT::ConstIterator::operator++
ConstIterator & operator++()
Definition: XnListT.h:105
XnListT
Definition: XnListT.h:83
XnLinkedNodeT::pNext
struct XnLinkedNodeT< T > * pNext
Definition: XnListT.h:64
XnListT::LinkedNode
XnLinkedNodeT< T > LinkedNode
Definition: XnListT.h:86
XN_STATUS_OK
#define XN_STATUS_OK
Definition: XnStatus.h:35
XnListT::Remove
XnStatus Remove(ConstIterator where)
Definition: XnListT.h:445
XnListT::ConstIterator::operator*
T const & operator*() const
Definition: XnListT.h:163
XnListT::ConstIterator::operator--
ConstIterator & operator--()
Definition: XnListT.h:124
FALSE
#define FALSE
Definition: XnPlatform.h:88
XnListT::Iterator::operator++
Iterator & operator++()
Definition: XnListT.h:198
XnStatus
XnUInt32 XnStatus
Definition: XnStatus.h:32
XnListT::Find
ConstIterator Find(T const &value) const
Definition: XnListT.h:414
XnListT::Iterator::operator--
Iterator & operator--()
Definition: XnListT.h:217
XnLinkedNodeT
Definition: XnListT.h:40
XnLinkedNodeDefaultAllocatorT::LinkedNode
XnLinkedNodeT< T > LinkedNode
Definition: XnListT.h:62
XnLinkedNodeDefaultAllocatorT
Definition: XnListT.h:59
XN_NEW
#define XN_NEW(type,...)
Definition: XnOS.h:328
XnLinkedNodeDefaultAllocatorT::Allocate
static LinkedNode * Allocate(T const &value)
Definition: XnListT.h:64
XnListT::InsertAfter
XnStatus InsertAfter(LinkedNode *pAfter, T const &val)
Definition: XnListT.h:540
XnListT::TAllocator
TAlloc TAllocator
Definition: XnListT.h:88
XnLinkedNodeT::value
T value
Definition: XnListT.h:65
XnListT::~XnListT
~XnListT()
Definition: XnListT.h:276
XnLinkedNodeT::pPrev
struct XnLinkedNodeT< T > * pPrev
Definition: XnListT.h:63
XnListT::operator=
XnListT & operator=(const XnListT &other)
Definition: XnListT.h:261
XnListT::ConstIterator::operator->
T const * operator->() const
Definition: XnListT.h:171
XnListT::XnListT
XnListT()
Definition: XnListT.h:250
XnListT::ConstIterator::operator!=
XnBool operator!=(const ConstIterator &other) const
Definition: XnListT.h:155
XnLinkedNodeDefaultAllocatorT::Deallocate
static void Deallocate(LinkedNode *pNode)
Definition: XnListT.h:69
XnListT::ReverseEnd
Iterator ReverseEnd()
Definition: XnListT.h:332
XnListT::AddBefore
XnStatus AddBefore(ConstIterator where, T const &value)
Definition: XnListT.h:373
XnListT::ConstIterator::operator==
XnBool operator==(const ConstIterator &other) const
Definition: XnListT.h:145
XnListT::ConstIterator
Definition: XnListT.h:93
XnListT::AddLast
XnStatus AddLast(T const &value)
Definition: XnListT.h:402
XnListT::Iterator::operator*
T & operator*() const
Definition: XnListT.h:235
XnListT::IsEmpty
XnBool IsEmpty() const
Definition: XnListT.h:501
XnListT::ConstIterator::m_pCurrent
LinkedNode * m_pCurrent
Definition: XnListT.h:180
XnListT::m_anchor
LinkedNode m_anchor
Definition: XnListT.h:562
XnListT::CopyTo
void CopyTo(T *pArray) const
Definition: XnListT.h:520
XnListT::Size
XnUInt32 Size() const
Definition: XnListT.h:509
XN_DELETE
#define XN_DELETE(p)
Definition: XnOS.h:338
XnPlatform.h
XnListT::m_nSize
XnUInt32 m_nSize
Definition: XnListT.h:564
XnLinkedNodeT::XnLinkedNodeT
XnLinkedNodeT()
Definition: XnListT.h:60
XnListT::ReverseBegin
Iterator ReverseBegin()
Definition: XnListT.h:316
XnListT::Iterator::operator->
T * operator->() const
Definition: XnListT.h:243
XnListT::Iterator::Iterator
Iterator()
Definition: XnListT.h:189
XnListT::Iterator
Definition: XnListT.h:186
XnListT::Begin
Iterator Begin()
Definition: XnListT.h:284
XnListT::AddAfter
XnStatus AddAfter(ConstIterator where, T const &value)
Definition: XnListT.h:354
XnListT::AddFirst
XnStatus AddFirst(T const &value)
Definition: XnListT.h:390