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_