XnListT.h
Go to the documentation of this file.
#ifndef _XNLISTT_H_
#define _XNLISTT_H_
//---------------------------------------------------------------------------
// Includes
//---------------------------------------------------------------------------
#include <XnPlatform.h>
#include <XnDataTypes.h>
#include <XnOS.h>
//---------------------------------------------------------------------------
// Code
//---------------------------------------------------------------------------
template<class T>
struct XnLinkedNodeT
{
XnLinkedNodeT() : pPrev(NULL), pNext(NULL) {}
XnLinkedNodeT(T const& value) : pPrev(NULL), pNext(NULL), value(value) {}
struct XnLinkedNodeT<T>* pPrev;
struct XnLinkedNodeT<T>* pNext;
T value;
};
template<class T>
class XnLinkedNodeDefaultAllocatorT
{
public:
typedef XnLinkedNodeT<T> LinkedNode;
static LinkedNode* Allocate(T const& value)
{
return XN_NEW(LinkedNode, value);
}
static void Deallocate(LinkedNode* pNode)
{
XN_DELETE(pNode);
}
};
template<class T, class TAlloc = XnLinkedNodeDefaultAllocatorT<T> >
class XnListT
{
public:
typedef XnLinkedNodeT<T> LinkedNode;
typedef T TValue;
typedef TAlloc TAllocator;
class ConstIterator
{
public:
inline ConstIterator() : m_pCurrent(NULL) {}
inline ConstIterator(LinkedNode* pNode) : m_pCurrent(pNode) {}
inline ConstIterator(const ConstIterator& other) : m_pCurrent(other.m_pCurrent) {}
inline ConstIterator& operator++()
{
m_pCurrent = m_pCurrent->pNext;
return *this;
}
inline ConstIterator operator++(int)
{
ConstIterator retVal(*this);
++*this;
return retVal;
}
inline ConstIterator& operator--()
{
m_pCurrent = m_pCurrent->pPrev;
return *this;
}
inline ConstIterator operator--(int)
{
ConstIterator retVal(*this);
--*this;
return retVal;
}
inline XnBool operator==(const ConstIterator& other) const
{
return m_pCurrent == other.m_pCurrent;
}
inline XnBool operator!=(const ConstIterator& other) const
{
return m_pCurrent != other.m_pCurrent;
}
inline T const& operator*() const
{
return m_pCurrent->value;
}
inline T const* operator->() const
{
return &m_pCurrent->value;
}
protected:
friend class XnListT;
LinkedNode* m_pCurrent;
};
class Iterator : public ConstIterator
{
public:
inline Iterator() : ConstIterator() {}
inline Iterator(LinkedNode* pNode) : ConstIterator(pNode) {}
inline Iterator(const Iterator& other) : ConstIterator(other) {}
inline Iterator& operator++()
{
++(*(ConstIterator*)this);
return (*this);
}
inline Iterator operator++(int)
{
Iterator retVal(*this);
++*this;
return (retVal);
}
inline Iterator& operator--()
{
--(*(ConstIterator*)this);
return (*this);
}
inline Iterator operator--(int)
{
Iterator retVal(*this);
--*this;
return (retVal);
}
inline T& operator*() const
{
return this->m_pCurrent->value;
}
inline T* operator->() const
{
return &this->m_pCurrent->value;
}
};
public:
XnListT()
{
Init();
}
XnListT(const XnListT& other)
{
Init();
*this = other;
}
XnListT& operator=(const XnListT& other)
{
Clear();
XnStatus nRetVal = XN_STATUS_OK;
for (ConstIterator it = other.Begin(); it != other.End(); ++it)
{
nRetVal = AddLast(*it);
XN_ASSERT(nRetVal == XN_STATUS_OK);
}
return *this;
}
~XnListT()
{
Clear();
}
Iterator Begin()
{
return Iterator(m_anchor.pNext);
}
ConstIterator Begin() const
{
return ConstIterator(const_cast<LinkedNode*>(m_anchor.pNext));
}
Iterator End()
{
return Iterator(&m_anchor);
}
ConstIterator End() const
{
return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
}
Iterator ReverseBegin()
{
return Iterator(m_anchor.pPrev);
}
ConstIterator ReverseBegin() const
{
return ConstIterator(const_cast<LinkedNode*>(m_anchor.pPrev));
}
Iterator ReverseEnd()
{
return Iterator(&m_anchor);
}
ConstIterator ReverseEnd() const
{
return ConstIterator(const_cast<LinkedNode*>(&m_anchor));
}
XnStatus AddAfter(ConstIterator where, T const& value)
{
if (where == End())
{
return XN_STATUS_ILLEGAL_POSITION;
}
return InsertAfter(where.m_pCurrent, value);
}
XnStatus AddBefore(ConstIterator where, T const& value)
{
if (where == End())
{
return XN_STATUS_ILLEGAL_POSITION;
}
return InsertAfter(where.m_pCurrent->pPrev, value);
}
XnStatus AddFirst(T const& value)
{
return InsertAfter(&m_anchor, value);
}
XnStatus AddLast(T const& value)
{
return InsertAfter(ReverseBegin().m_pCurrent, value);
}
ConstIterator Find(T const& value) const
{
ConstIterator iter = Begin();
for (; iter != End(); ++iter)
{
if (*iter == value)
break;
}
return iter;
}
Iterator Find(T const& value)
{
ConstIterator iter = const_cast<const XnListT<T>*>(this)->Find(value);
return Iterator(iter.m_pCurrent);
}
XnStatus Remove(ConstIterator where)
{
// Verify iterator is valid
if (where == End())
{
return XN_STATUS_ILLEGAL_POSITION;
}
XnLinkedNodeT<T>* pToRemove = where.m_pCurrent;
// Connect other nodes to bypass the one removed
pToRemove->pPrev->pNext = pToRemove->pNext;
pToRemove->pNext->pPrev = pToRemove->pPrev;
--m_nSize;
// Free memory
TAlloc::Deallocate(pToRemove);
return XN_STATUS_OK;
}
XnStatus Remove(T const& value)
{
ConstIterator it = Find(value);
if (it != End())
{
return Remove(it);
}
else
{
return XN_STATUS_NO_MATCH;
}
}
XnStatus Clear()
{
while (!IsEmpty())
Remove(Begin());
return XN_STATUS_OK;
}
XnBool IsEmpty() const
{
return (m_nSize == 0);
}
XnUInt32 Size() const
{
return m_nSize;
}
void CopyTo(T* pArray) const
{
XN_ASSERT(pArray != NULL);
XnUInt32 i = 0;
for (ConstIterator iter = Begin(); iter != End(); ++iter, ++i)
{
pArray[i] = *iter;
}
}
protected:
XnStatus InsertAfter(LinkedNode* pAfter, T const& val)
{
// Get a node from the pool for the entry
LinkedNode* pNewNode = TAlloc::Allocate(val);
if (pNewNode == NULL)
{
XN_ASSERT(FALSE);
return XN_STATUS_ALLOC_FAILED;
}
pNewNode->pPrev = pAfter;
pNewNode->pNext = pAfter->pNext;
// push new node to position
pAfter->pNext->pPrev = pNewNode;
pAfter->pNext = pNewNode;
++m_nSize;
return XN_STATUS_OK;
}
// A dummy node, pointing to first node, and last node points back to it.
LinkedNode m_anchor;
XnUInt32 m_nSize;
private:
void Init()
{
m_anchor.pNext = &m_anchor;
m_anchor.pPrev = &m_anchor;
m_nSize = 0;
}
};
#endif // _XNLISTT_H_
XnDataTypes.h
XnOS.h
XN_DELETE
#define XN_DELETE(p)
Definition XnOS.h:336
XN_NEW
#define XN_NEW(type,...)
Definition XnOS.h:326
XnPlatform.h
FALSE
#define FALSE
Definition XnPlatform.h:100
XnStatus
XnUInt32 XnStatus
Definition XnStatus.h:34
XN_STATUS_OK
#define XN_STATUS_OK
Definition XnStatus.h:37
XnLinkedNodeDefaultAllocatorT
Definition XnListT.h:41
XnLinkedNodeDefaultAllocatorT::LinkedNode
XnLinkedNodeT< T > LinkedNode
Definition XnListT.h:43
XnLinkedNodeDefaultAllocatorT::Deallocate
static void Deallocate(LinkedNode *pNode)
Definition XnListT.h:50
XnLinkedNodeDefaultAllocatorT::Allocate
static LinkedNode * Allocate(T const &value)
Definition XnListT.h:45
XnListT::ConstIterator::operator++
ConstIterator & operator++()
Definition XnListT.h:86
XnListT::ConstIterator::m_pCurrent
LinkedNode * m_pCurrent
Definition XnListT.h:161
XnListT::ConstIterator::XnListT
friend class XnListT
Definition XnListT.h:158
XnListT::ConstIterator::operator*
T const & operator*() const
Definition XnListT.h:144
XnListT::ConstIterator::operator==
XnBool operator==(const ConstIterator &other) const
Definition XnListT.h:126
XnListT::ConstIterator::operator!=
XnBool operator!=(const ConstIterator &other) const
Definition XnListT.h:136
XnListT::ConstIterator::ConstIterator
ConstIterator(LinkedNode *pNode)
Definition XnListT.h:79
XnListT::ConstIterator::operator--
ConstIterator & operator--()
Definition XnListT.h:105
XnListT::ConstIterator::ConstIterator
ConstIterator(const ConstIterator &other)
Definition XnListT.h:81
XnListT::ConstIterator::operator++
ConstIterator operator++(int)
Definition XnListT.h:95
XnListT::ConstIterator::ConstIterator
ConstIterator()
Definition XnListT.h:77
XnListT::ConstIterator::operator--
ConstIterator operator--(int)
Definition XnListT.h:114
XnListT::ConstIterator::operator->
T const * operator->() const
Definition XnListT.h:152
XnListT::Iterator::operator--
Iterator operator--(int)
Definition XnListT.h:206
XnListT::Iterator::operator->
T * operator->() const
Definition XnListT.h:224
XnListT::Iterator::operator++
Iterator & operator++()
Definition XnListT.h:179
XnListT::Iterator::Iterator
Iterator(LinkedNode *pNode)
Definition XnListT.h:172
XnListT::Iterator::Iterator
Iterator()
Definition XnListT.h:170
XnListT::Iterator::operator++
Iterator operator++(int)
Definition XnListT.h:188
XnListT::Iterator::Iterator
Iterator(const Iterator &other)
Definition XnListT.h:174
XnListT::Iterator::operator*
T & operator*() const
Definition XnListT.h:216
XnListT::Iterator::operator--
Iterator & operator--()
Definition XnListT.h:198
XnListT< TCallback * >::m_nSize
XnUInt32 m_nSize
Definition XnListT.h:545
XnListT::Remove
XnStatus Remove(T const &value)
Definition XnListT.h:455
XnListT::ReverseEnd
Iterator ReverseEnd()
Definition XnListT.h:313
XnListT::XnListT
XnListT()
Definition XnListT.h:231
XnListT::Find
Iterator Find(T const &value)
Definition XnListT.h:413
XnListT::Begin
ConstIterator Begin() const
Definition XnListT.h:273
XnListT::Clear
XnStatus Clear()
Definition XnListT.h:471
XnListT::Size
XnUInt32 Size() const
Definition XnListT.h:490
XnListT::End
ConstIterator End() const
Definition XnListT.h:289
XnListT::AddAfter
XnStatus AddAfter(ConstIterator where, T const &value)
Definition XnListT.h:335
XnListT::AddLast
XnStatus AddLast(T const &value)
Definition XnListT.h:383
XnListT::InsertAfter
XnStatus InsertAfter(LinkedNode *pAfter, T const &val)
Definition XnListT.h:521
XnListT::XnListT
XnListT(const XnListT &other)
Definition XnListT.h:236
XnListT::~XnListT
~XnListT()
Definition XnListT.h:257
XnListT::AddBefore
XnStatus AddBefore(ConstIterator where, T const &value)
Definition XnListT.h:354
XnListT::AddFirst
XnStatus AddFirst(T const &value)
Definition XnListT.h:371
XnListT::ReverseBegin
Iterator ReverseBegin()
Definition XnListT.h:297
XnListT< TCallback * >::m_anchor
LinkedNode m_anchor
Definition XnListT.h:543
XnListT::operator=
XnListT & operator=(const XnListT &other)
Definition XnListT.h:242
XnListT< TCallback * >::TAllocator
XnLinkedNodeDefaultAllocatorT< TCallback * > TAllocator
Definition XnListT.h:69
XnListT::End
Iterator End()
Definition XnListT.h:281
XnListT::ReverseEnd
ConstIterator ReverseEnd() const
Definition XnListT.h:321
XnListT< TCallback * >::LinkedNode
XnLinkedNodeT< TCallback * > LinkedNode
Definition XnListT.h:67
XnListT::Begin
Iterator Begin()
Definition XnListT.h:265
XnListT::ReverseBegin
ConstIterator ReverseBegin() const
Definition XnListT.h:305
XnListT::Find
ConstIterator Find(T const &value) const
Definition XnListT.h:395
XnListT< TCallback * >::TValue
TCallback * TValue
Definition XnListT.h:68
XnListT::Remove
XnStatus Remove(ConstIterator where)
Definition XnListT.h:426
XnListT::CopyTo
void CopyTo(T *pArray) const
Definition XnListT.h:501
XnListT::IsEmpty
XnBool IsEmpty() const
Definition XnListT.h:482
XnLinkedNodeT
Definition XnListT.h:22
XnLinkedNodeT< TPair >::value
TPair value
Definition XnListT.h:28
XnLinkedNodeT< TPair >::pNext
struct XnLinkedNodeT< TPair > * pNext
Definition XnListT.h:27
XnLinkedNodeT::XnLinkedNodeT
XnLinkedNodeT(T const &value)
Definition XnListT.h:24
XnLinkedNodeT::XnLinkedNodeT
XnLinkedNodeT()
Definition XnListT.h:23
XnLinkedNodeT< TPair >::pPrev
struct XnLinkedNodeT< TPair > * pPrev
Definition XnListT.h:26