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
20template<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;
29};
30
39template<class T>
41{
42public:
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
63template<class T, class TAlloc = XnLinkedNodeDefaultAllocatorT<T> >
65{
66public:
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 {
89 return *this;
90 }
91
96 {
97 ConstIterator retVal(*this);
98 ++*this;
99 return retVal;
100 }
101
106 {
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
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
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
199 {
200 --(*(ConstIterator*)this);
201 return (*this);
202 }
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
230public:
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
266 {
267 return Iterator(m_anchor.pNext);
268 }
269
274 {
275 return ConstIterator(const_cast<LinkedNode*>(m_anchor.pNext));
276 }
277
282 {
283 return Iterator(&m_anchor);
284 }
285
290 {
291 return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
292 }
293
298 {
299 return Iterator(m_anchor.pPrev);
300 }
301
306 {
307 return ConstIterator(const_cast<LinkedNode*>(m_anchor.pPrev));
308 }
309
314 {
315 return Iterator(&m_anchor);
316 }
317
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
371 XnStatus AddFirst(T const& value)
372 {
373 return InsertAfter(&m_anchor, value);
374 }
375
383 XnStatus AddLast(T const& value)
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
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
455 XnStatus Remove(T const& value)
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
512protected:
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.
544
545 XnUInt32 m_nSize;
546
547private:
548 void Init()
549 {
552 m_nSize = 0;
553 }
554};
555
556#endif // _XNLISTT_H_
#define XN_DELETE(p)
Definition XnOS.h:336
#define XN_NEW(type,...)
Definition XnOS.h:326
#define FALSE
Definition XnPlatform.h:100
XnUInt32 XnStatus
Definition XnStatus.h:34
#define XN_STATUS_OK
Definition XnStatus.h:37
Definition XnListT.h:41
XnLinkedNodeT< T > LinkedNode
Definition XnListT.h:43
static void Deallocate(LinkedNode *pNode)
Definition XnListT.h:50
static LinkedNode * Allocate(T const &value)
Definition XnListT.h:45
Definition XnListT.h:75
ConstIterator & operator++()
Definition XnListT.h:86
LinkedNode * m_pCurrent
Definition XnListT.h:161
T const & operator*() const
Definition XnListT.h:144
XnBool operator==(const ConstIterator &other) const
Definition XnListT.h:126
XnBool operator!=(const ConstIterator &other) const
Definition XnListT.h:136
ConstIterator(LinkedNode *pNode)
Definition XnListT.h:79
ConstIterator & operator--()
Definition XnListT.h:105
ConstIterator(const ConstIterator &other)
Definition XnListT.h:81
ConstIterator operator++(int)
Definition XnListT.h:95
ConstIterator()
Definition XnListT.h:77
ConstIterator operator--(int)
Definition XnListT.h:114
T const * operator->() const
Definition XnListT.h:152
Definition XnListT.h:168
Iterator operator--(int)
Definition XnListT.h:206
T * operator->() const
Definition XnListT.h:224
Iterator & operator++()
Definition XnListT.h:179
Iterator(LinkedNode *pNode)
Definition XnListT.h:172
Iterator()
Definition XnListT.h:170
Iterator operator++(int)
Definition XnListT.h:188
Iterator(const Iterator &other)
Definition XnListT.h:174
T & operator*() const
Definition XnListT.h:216
Iterator & operator--()
Definition XnListT.h:198
Definition XnListT.h:65
XnUInt32 m_nSize
Definition XnListT.h:545
XnStatus Remove(T const &value)
Definition XnListT.h:455
Iterator ReverseEnd()
Definition XnListT.h:313
XnListT()
Definition XnListT.h:231
Iterator Find(T const &value)
Definition XnListT.h:413
ConstIterator Begin() const
Definition XnListT.h:273
XnStatus Clear()
Definition XnListT.h:471
XnUInt32 Size() const
Definition XnListT.h:490
ConstIterator End() const
Definition XnListT.h:289
XnStatus AddAfter(ConstIterator where, T const &value)
Definition XnListT.h:335
XnStatus AddLast(T const &value)
Definition XnListT.h:383
TAlloc TAllocator
Definition XnListT.h:69
XnStatus InsertAfter(LinkedNode *pAfter, T const &val)
Definition XnListT.h:521
XnListT(const XnListT &other)
Definition XnListT.h:236
~XnListT()
Definition XnListT.h:257
T TValue
Definition XnListT.h:68
XnStatus AddBefore(ConstIterator where, T const &value)
Definition XnListT.h:354
XnLinkedNodeT< T > LinkedNode
Definition XnListT.h:67
XnStatus AddFirst(T const &value)
Definition XnListT.h:371
Iterator ReverseBegin()
Definition XnListT.h:297
LinkedNode m_anchor
Definition XnListT.h:543
XnListT & operator=(const XnListT &other)
Definition XnListT.h:242
Iterator End()
Definition XnListT.h:281
ConstIterator ReverseEnd() const
Definition XnListT.h:321
Iterator Begin()
Definition XnListT.h:265
ConstIterator ReverseBegin() const
Definition XnListT.h:305
ConstIterator Find(T const &value) const
Definition XnListT.h:395
XnStatus Remove(ConstIterator where)
Definition XnListT.h:426
void CopyTo(T *pArray) const
Definition XnListT.h:501
XnBool IsEmpty() const
Definition XnListT.h:482
Definition XnListT.h:22
T value
Definition XnListT.h:28
struct XnLinkedNodeT< T > * pNext
Definition XnListT.h:27
XnLinkedNodeT(T const &value)
Definition XnListT.h:24
XnLinkedNodeT()
Definition XnListT.h:23
struct XnLinkedNodeT< T > * pPrev
Definition XnListT.h:26