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>
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 
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 
107  {
109  return *this;
110  }
111 
116  {
117  ConstIterator retVal(*this);
118  ++*this;
119  return retVal;
120  }
121 
126  {
128  return *this;
129  }
130 
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:
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 
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 
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_
XnStatus InsertAfter(LinkedNode *pAfter, T const &val)
Definition: XnListT.h:541
Iterator(const Iterator &other)
Definition: XnListT.h:194
struct XnLinkedNodeT< T > * pPrev
Definition: XnListT.h:46
#define FALSE
Definition: XnPlatform.h:89
struct XnLinkedNodeT< T > * pNext
Definition: XnListT.h:47
ConstIterator ReverseBegin() const
Definition: XnListT.h:325
XnBool IsEmpty() const
Definition: XnListT.h:502
Iterator & operator++()
Definition: XnListT.h:199
XnListT(const XnListT &other)
Definition: XnListT.h:256
XnStatus AddBefore(ConstIterator where, T const &value)
Definition: XnListT.h:374
#define XN_STATUS_OK
Definition: XnStatus.h:36
ConstIterator operator--(int)
Definition: XnListT.h:134
ConstIterator End() const
Definition: XnListT.h:309
LinkedNode m_anchor
Definition: XnListT.h:563
ConstIterator(const ConstIterator &other)
Definition: XnListT.h:101
XnBool operator!=(const ConstIterator &other) const
Definition: XnListT.h:156
Iterator ReverseBegin()
Definition: XnListT.h:317
Definition: XnListT.h:94
Iterator Find(T const &value)
Definition: XnListT.h:433
XnStatus Remove(T const &value)
Definition: XnListT.h:475
T & operator*() const
Definition: XnListT.h:236
Definition: XnListT.h:60
Iterator operator--(int)
Definition: XnListT.h:226
T const & operator*() const
Definition: XnListT.h:164
XnUInt32 XnStatus
Definition: XnStatus.h:33
T const * operator->() const
Definition: XnListT.h:172
void CopyTo(T *pArray) const
Definition: XnListT.h:521
XnLinkedNodeT< T > LinkedNode
Definition: XnListT.h:63
T TValue
Definition: XnListT.h:88
XnUInt32 Size() const
Definition: XnListT.h:510
XnUInt32 m_nSize
Definition: XnListT.h:565
XnLinkedNodeT(T const &value)
Definition: XnListT.h:44
XnStatus AddFirst(T const &value)
Definition: XnListT.h:391
XnBool operator==(const ConstIterator &other) const
Definition: XnListT.h:146
XnStatus AddAfter(ConstIterator where, T const &value)
Definition: XnListT.h:355
ConstIterator ReverseEnd() const
Definition: XnListT.h:341
#define XN_NEW(type,...)
Definition: XnOS.h:329
static LinkedNode * Allocate(T const &value)
Definition: XnListT.h:65
XnLinkedNodeT< T > LinkedNode
Definition: XnListT.h:87
Definition: XnListT.h:84
Iterator & operator--()
Definition: XnListT.h:218
Iterator Begin()
Definition: XnListT.h:285
ConstIterator()
Definition: XnListT.h:97
XnStatus Clear()
Definition: XnListT.h:491
Iterator operator++(int)
Definition: XnListT.h:208
XnLinkedNodeT()
Definition: XnListT.h:43
T value
Definition: XnListT.h:48
ConstIterator & operator--()
Definition: XnListT.h:125
static void Deallocate(LinkedNode *pNode)
Definition: XnListT.h:70
#define XN_DELETE(p)
Definition: XnOS.h:339
Iterator(LinkedNode *pNode)
Definition: XnListT.h:192
XnStatus Remove(ConstIterator where)
Definition: XnListT.h:446
Definition: XnListT.h:187
ConstIterator(LinkedNode *pNode)
Definition: XnListT.h:99
T * operator->() const
Definition: XnListT.h:244
Iterator End()
Definition: XnListT.h:301
TAlloc TAllocator
Definition: XnListT.h:89
ConstIterator Begin() const
Definition: XnListT.h:293
ConstIterator Find(T const &value) const
Definition: XnListT.h:415
ConstIterator & operator++()
Definition: XnListT.h:106
Iterator()
Definition: XnListT.h:190
Definition: XnListT.h:41
~XnListT()
Definition: XnListT.h:277
XnListT()
Definition: XnListT.h:251
XnListT & operator=(const XnListT &other)
Definition: XnListT.h:262
LinkedNode * m_pCurrent
Definition: XnListT.h:181
ConstIterator operator++(int)
Definition: XnListT.h:115
Iterator ReverseEnd()
Definition: XnListT.h:333
XnStatus AddLast(T const &value)
Definition: XnListT.h:403