00001 #ifndef _XNLISTT_H_
00002 #define _XNLISTT_H_
00003
00004
00005
00006
00007 #include <XnPlatform.h>
00008 #include <XnDataTypes.h>
00009 #include <XnOS.h>
00010
00011
00012
00013
00014
00020 template<class T>
00021 struct XnLinkedNodeT
00022 {
00023 XnLinkedNodeT() : pPrev(NULL), pNext(NULL) {}
00024 XnLinkedNodeT(T const& value) : pPrev(NULL), pNext(NULL), value(value) {}
00025
00026 struct XnLinkedNodeT<T>* pPrev;
00027 struct XnLinkedNodeT<T>* pNext;
00028 T value;
00029 };
00030
00039 template<class T>
00040 class XnLinkedNodeDefaultAllocatorT
00041 {
00042 public:
00043 typedef XnLinkedNodeT<T> LinkedNode;
00044
00045 static LinkedNode* Allocate(T const& value)
00046 {
00047 return XN_NEW(LinkedNode, value);
00048 }
00049
00050 static void Deallocate(LinkedNode* pNode)
00051 {
00052 XN_DELETE(pNode);
00053 }
00054 };
00055
00063 template<class T, class TAlloc = XnLinkedNodeDefaultAllocatorT<T> >
00064 class XnListT
00065 {
00066 public:
00067 typedef XnLinkedNodeT<T> LinkedNode;
00068 typedef T TValue;
00069 typedef TAlloc TAllocator;
00070
00074 class ConstIterator
00075 {
00076 public:
00077 inline ConstIterator() : m_pCurrent(NULL) {}
00078
00079 inline ConstIterator(LinkedNode* pNode) : m_pCurrent(pNode) {}
00080
00081 inline ConstIterator(const ConstIterator& other) : m_pCurrent(other.m_pCurrent) {}
00082
00086 inline ConstIterator& operator++()
00087 {
00088 m_pCurrent = m_pCurrent->pNext;
00089 return *this;
00090 }
00091
00095 inline ConstIterator operator++(int)
00096 {
00097 ConstIterator retVal(*this);
00098 ++*this;
00099 return retVal;
00100 }
00101
00105 inline ConstIterator& operator--()
00106 {
00107 m_pCurrent = m_pCurrent->pPrev;
00108 return *this;
00109 }
00110
00114 inline ConstIterator operator--(int)
00115 {
00116 ConstIterator retVal(*this);
00117 --*this;
00118 return retVal;
00119 }
00120
00126 inline XnBool operator==(const ConstIterator& other) const
00127 {
00128 return m_pCurrent == other.m_pCurrent;
00129 }
00130
00136 inline XnBool operator!=(const ConstIterator& other) const
00137 {
00138 return m_pCurrent != other.m_pCurrent;
00139 }
00140
00144 inline T const& operator*() const
00145 {
00146 return m_pCurrent->value;
00147 }
00148
00152 inline T const* operator->() const
00153 {
00154 return &m_pCurrent->value;
00155 }
00156
00157 protected:
00158 friend class XnListT;
00159
00161 LinkedNode* m_pCurrent;
00162 };
00163
00167 class Iterator : public ConstIterator
00168 {
00169 public:
00170 inline Iterator() : ConstIterator() {}
00171
00172 inline Iterator(LinkedNode* pNode) : ConstIterator(pNode) {}
00173
00174 inline Iterator(const Iterator& other) : ConstIterator(other) {}
00175
00179 inline Iterator& operator++()
00180 {
00181 ++(*(ConstIterator*)this);
00182 return (*this);
00183 }
00184
00188 inline Iterator operator++(int)
00189 {
00190 Iterator retVal(*this);
00191 ++*this;
00192 return (retVal);
00193 }
00194
00198 inline Iterator& operator--()
00199 {
00200 --(*(ConstIterator*)this);
00201 return (*this);
00202 }
00206 inline Iterator operator--(int)
00207 {
00208 Iterator retVal(*this);
00209 --*this;
00210 return (retVal);
00211 }
00212
00216 inline T& operator*() const
00217 {
00218 return this->m_pCurrent->value;
00219 }
00220
00224 inline T* operator->() const
00225 {
00226 return &this->m_pCurrent->value;
00227 }
00228 };
00229
00230 public:
00231 XnListT()
00232 {
00233 Init();
00234 }
00235
00236 XnListT(const XnListT& other)
00237 {
00238 Init();
00239 *this = other;
00240 }
00241
00242 XnListT& operator=(const XnListT& other)
00243 {
00244 Clear();
00245
00246 XnStatus nRetVal = XN_STATUS_OK;
00247
00248 for (ConstIterator it = other.Begin(); it != other.End(); ++it)
00249 {
00250 nRetVal = AddLast(*it);
00251 XN_ASSERT(nRetVal == XN_STATUS_OK);
00252 }
00253
00254 return *this;
00255 }
00256
00257 ~XnListT()
00258 {
00259 Clear();
00260 }
00261
00265 Iterator Begin()
00266 {
00267 return Iterator(m_anchor.pNext);
00268 }
00269
00273 ConstIterator Begin() const
00274 {
00275 return ConstIterator(const_cast<LinkedNode*>(m_anchor.pNext));
00276 }
00277
00281 Iterator End()
00282 {
00283 return Iterator(&m_anchor);
00284 }
00285
00289 ConstIterator End() const
00290 {
00291 return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
00292 }
00293
00297 Iterator ReverseBegin()
00298 {
00299 return Iterator(m_anchor.pPrev);
00300 }
00301
00305 ConstIterator ReverseBegin() const
00306 {
00307 return ConstIterator(const_cast<LinkedNode*>(m_anchor.pPrev));
00308 }
00309
00313 Iterator ReverseEnd()
00314 {
00315 return Iterator(&m_anchor);
00316 }
00317
00321 ConstIterator ReverseEnd() const
00322 {
00323 return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
00324 }
00325
00335 XnStatus AddAfter(ConstIterator where, T const& value)
00336 {
00337 if (where == End())
00338 {
00339 return XN_STATUS_ILLEGAL_POSITION;
00340 }
00341
00342 return InsertAfter(where.m_pCurrent, value);
00343 }
00344
00354 XnStatus AddBefore(ConstIterator where, T const& value)
00355 {
00356 if (where == End())
00357 {
00358 return XN_STATUS_ILLEGAL_POSITION;
00359 }
00360
00361 return InsertAfter(where.m_pCurrent->pPrev, value);
00362 }
00363
00371 XnStatus AddFirst(T const& value)
00372 {
00373 return InsertAfter(&m_anchor, value);
00374 }
00375
00383 XnStatus AddLast(T const& value)
00384 {
00385 return InsertAfter(ReverseBegin().m_pCurrent, value);
00386 }
00387
00395 ConstIterator Find(T const& value) const
00396 {
00397 ConstIterator iter = Begin();
00398 for (; iter != End(); ++iter)
00399 {
00400 if (*iter == value)
00401 break;
00402 }
00403 return iter;
00404 }
00405
00413 Iterator Find(T const& value)
00414 {
00415 ConstIterator iter = const_cast<const XnListT<T>*>(this)->Find(value);
00416 return Iterator(iter.m_pCurrent);
00417 }
00418
00426 XnStatus Remove(ConstIterator where)
00427 {
00428
00429 if (where == End())
00430 {
00431 return XN_STATUS_ILLEGAL_POSITION;
00432 }
00433
00434 XnLinkedNodeT<T>* pToRemove = where.m_pCurrent;
00435
00436
00437 pToRemove->pPrev->pNext = pToRemove->pNext;
00438 pToRemove->pNext->pPrev = pToRemove->pPrev;
00439
00440 --m_nSize;
00441
00442
00443 TAlloc::Deallocate(pToRemove);
00444
00445 return XN_STATUS_OK;
00446 }
00447
00455 XnStatus Remove(T const& value)
00456 {
00457 ConstIterator it = Find(value);
00458 if (it != End())
00459 {
00460 return Remove(it);
00461 }
00462 else
00463 {
00464 return XN_STATUS_NO_MATCH;
00465 }
00466 }
00467
00471 XnStatus Clear()
00472 {
00473 while (!IsEmpty())
00474 Remove(Begin());
00475
00476 return XN_STATUS_OK;
00477 }
00478
00482 XnBool IsEmpty() const
00483 {
00484 return (m_nSize == 0);
00485 }
00486
00490 XnUInt32 Size() const
00491 {
00492 return m_nSize;
00493 }
00494
00501 void CopyTo(T* pArray) const
00502 {
00503 XN_ASSERT(pArray != NULL);
00504
00505 XnUInt32 i = 0;
00506 for (ConstIterator iter = Begin(); iter != End(); ++iter, ++i)
00507 {
00508 pArray[i] = *iter;
00509 }
00510 }
00511
00512 protected:
00521 XnStatus InsertAfter(LinkedNode* pAfter, T const& val)
00522 {
00523
00524 LinkedNode* pNewNode = TAlloc::Allocate(val);
00525 if (pNewNode == NULL)
00526 {
00527 XN_ASSERT(FALSE);
00528 return XN_STATUS_ALLOC_FAILED;
00529 }
00530 pNewNode->pPrev = pAfter;
00531 pNewNode->pNext = pAfter->pNext;
00532
00533
00534 pAfter->pNext->pPrev = pNewNode;
00535 pAfter->pNext = pNewNode;
00536
00537 ++m_nSize;
00538
00539 return XN_STATUS_OK;
00540 }
00541
00542
00543 LinkedNode m_anchor;
00544
00545 XnUInt32 m_nSize;
00546
00547 private:
00548 void Init()
00549 {
00550 m_anchor.pNext = &m_anchor;
00551 m_anchor.pPrev = &m_anchor;
00552 m_nSize = 0;
00553 }
00554 };
00555
00556 #endif // _XNLISTT_H_