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
40template<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;
49};
50
59template<class T>
61{
62public:
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
83template<class T, class TAlloc = XnLinkedNodeDefaultAllocatorT<T> >
85{
86public:
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
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
219 {
220 --(*(ConstIterator*)this);
221 return (*this);
222 }
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
250public:
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
286 {
287 return Iterator(m_anchor.pNext);
288 }
289
294 {
295 return ConstIterator(const_cast<LinkedNode*>(m_anchor.pNext));
296 }
297
302 {
303 return Iterator(&m_anchor);
304 }
305
310 {
311 return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
312 }
313
318 {
319 return Iterator(m_anchor.pPrev);
320 }
321
326 {
327 return ConstIterator(const_cast<LinkedNode*>(m_anchor.pPrev));
328 }
329
334 {
335 return Iterator(&m_anchor);
336 }
337
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
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
532protected:
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
567private:
568 void Init()
569 {
572 m_nSize = 0;
573 }
574};
575
576#endif // _XNLISTT_H_
#define XN_DELETE(p)
Definition XnOS.h:339
#define XN_NEW(type,...)
Definition XnOS.h:329
#define FALSE
Definition XnPlatform.h:89
XnUInt32 XnStatus
Definition XnStatus.h:33
#define XN_STATUS_OK
Definition XnStatus.h:36
Definition XnListT.h:61
XnLinkedNodeT< T > LinkedNode
Definition XnListT.h:63
static void Deallocate(LinkedNode *pNode)
Definition XnListT.h:70
static LinkedNode * Allocate(T const &value)
Definition XnListT.h:65
Definition XnListT.h:95
ConstIterator & operator++()
Definition XnListT.h:106
LinkedNode * m_pCurrent
Definition XnListT.h:181
T const & operator*() const
Definition XnListT.h:164
XnBool operator==(const ConstIterator &other) const
Definition XnListT.h:146
XnBool operator!=(const ConstIterator &other) const
Definition XnListT.h:156
ConstIterator(LinkedNode *pNode)
Definition XnListT.h:99
ConstIterator & operator--()
Definition XnListT.h:125
ConstIterator(const ConstIterator &other)
Definition XnListT.h:101
ConstIterator operator++(int)
Definition XnListT.h:115
ConstIterator()
Definition XnListT.h:97
ConstIterator operator--(int)
Definition XnListT.h:134
T const * operator->() const
Definition XnListT.h:172
Definition XnListT.h:188
Iterator operator--(int)
Definition XnListT.h:226
T * operator->() const
Definition XnListT.h:244
Iterator & operator++()
Definition XnListT.h:199
Iterator(LinkedNode *pNode)
Definition XnListT.h:192
Iterator()
Definition XnListT.h:190
Iterator operator++(int)
Definition XnListT.h:208
Iterator(const Iterator &other)
Definition XnListT.h:194
T & operator*() const
Definition XnListT.h:236
Iterator & operator--()
Definition XnListT.h:218
Definition XnListT.h:85
XnUInt32 m_nSize
Definition XnListT.h:565
XnStatus Remove(T const &value)
Definition XnListT.h:475
Iterator ReverseEnd()
Definition XnListT.h:333
XnListT()
Definition XnListT.h:251
Iterator Find(T const &value)
Definition XnListT.h:433
ConstIterator Begin() const
Definition XnListT.h:293
XnStatus Clear()
Definition XnListT.h:491
XnUInt32 Size() const
Definition XnListT.h:510
ConstIterator End() const
Definition XnListT.h:309
XnStatus AddAfter(ConstIterator where, T const &value)
Definition XnListT.h:355
XnStatus AddLast(T const &value)
Definition XnListT.h:403
XnStatus InsertAfter(LinkedNode *pAfter, T const &val)
Definition XnListT.h:541
XnListT(const XnListT &other)
Definition XnListT.h:256
~XnListT()
Definition XnListT.h:277
XnStatus AddBefore(ConstIterator where, T const &value)
Definition XnListT.h:374
XnStatus AddFirst(T const &value)
Definition XnListT.h:391
Iterator ReverseBegin()
Definition XnListT.h:317
LinkedNode m_anchor
Definition XnListT.h:563
XnListT & operator=(const XnListT &other)
Definition XnListT.h:262
TAlloc TAllocator
Definition XnListT.h:89
Iterator End()
Definition XnListT.h:301
ConstIterator ReverseEnd() const
Definition XnListT.h:341
XnLinkedNodeT< T > LinkedNode
Definition XnListT.h:87
Iterator Begin()
Definition XnListT.h:285
ConstIterator ReverseBegin() const
Definition XnListT.h:325
ConstIterator Find(T const &value) const
Definition XnListT.h:415
T TValue
Definition XnListT.h:88
XnStatus Remove(ConstIterator where)
Definition XnListT.h:446
void CopyTo(T *pArray) const
Definition XnListT.h:521
XnBool IsEmpty() const
Definition XnListT.h:502
Definition XnListT.h:42
T value
Definition XnListT.h:48
struct XnLinkedNodeT< T > * pNext
Definition XnListT.h:47
XnLinkedNodeT(T const &value)
Definition XnListT.h:44
XnLinkedNodeT()
Definition XnListT.h:43
struct XnLinkedNodeT< T > * pPrev
Definition XnListT.h:46