#if !defined(__DBLINKS__)
#define __DBLINKS__

#ifndef NULL_CLASS_DEFINED
#define NULL_CLASS_DEFINED
class CNullClass {};
#endif

#define TDBLNK(TYPE)                TDoubleLinkRef<TYPE,CNullClass> // TDBLNK(CObject*)
#define TDBLNKCUT(TYPE)             TDoubleLinkCut<TYPE,CNullClass> // TDBLNKDESTROY(TDBLNK(CObject*))
#define TDBLNKFREE(TYPE)            TDoubleLinkFree<TYPE,CNullClass> // TDBLNKFREE(TDBLNK(CObject*))
#define TDBLNKDESTROY(TYPE)         TDoubleLinkDestroy<TYPE,CNullClass> // TDBLNKDESTROY(TDBLNK(CObject*))
#define TDBLNKTREE(TYPE)            TDoubleLinkTreeRef<TYPE,CNullClass> // TDBLNKTREE(CObject*)

#if !defined(DO_VERIFY)
#ifdef _DEBUG
#define DO_VERIFY 0
#else // !_DEBUG
#define DO_VERIFY 0
#endif // _DEBUG
#endif // !defined(DO_VERIFY)

template <class TYPE, class BaseClass>
class TDoubleLinkRef : public BaseClass
{
public:
    TYPE m_pPrev;
    TYPE m_pNext;
public:
#if DO_VERIFY
    void VerifyLinks(const TYPE& pHead) const
    {
        ASSERT(&pHead);
        if (pHead) {
            ASSERT(!pHead->m_pPrev);
            TYPE pLink = (TYPE)this;
            while(pLink != pHead) {
                ASSERT(pLink);
                pLink = pLink->m_pPrev;
            }
            while((pLink = pLink->m_pNext) != NULL)
                ;
        } else {
            ASSERT(!this);
        }
    }
#endif // DO_VERIFY
public:
    TDoubleLinkRef()
    {
        m_pPrev = NULL;
        m_pNext = NULL;
    }
    static TYPE CutHead(TYPE& pHead);
    static void CutListAll(TYPE& pHead);
    static void FreeListAll(TYPE& pHead);
    static void DestroyListAll(TYPE& pHead);
	int GetCount() const;
	TYPE GetHead() const;
	TYPE GetTail() const;
    TYPE GetNeighbor(BOOL bNext);
    TYPE GetTerminal(BOOL bNext);
    BOOL CutCheck(TYPE& pHead);
    TYPE Cut(TYPE& pHead);
    void InsHead(TYPE& pHead);
    void InsBefore(TYPE& pHead, TYPE pPrev = NULL);
    void InsAfter(TYPE& pHead, TYPE pNext = NULL);
    void AddTail(TYPE& pHead);
    TYPE CutGroup(TYPE& pHead);
    void InsHeadGroup(TYPE& pHead);
    void InsGroup(TYPE& pHead, TYPE pPrev = NULL);
    void AddTailGroup(TYPE& pHead);
};

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::CutHead(TYPE& pHead)
{
#if DO_VERIFY
    pHead->VerifyLinks(pHead);
#endif // DO_VERIFY

    TYPE pLink = pHead;

    if (pLink) {
        ASSERT(!pLink->m_pPrev);
        TYPE pLink2 = pLink->m_pNext;
        if (pLink2) {
            ASSERT(pLink2->m_pPrev == pLink);
            pLink2->m_pPrev = NULL;
			pLink->m_pNext = NULL;
        }
        pHead = pLink2;
    }

    return pLink;
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::CutListAll(TYPE& pHead)
{
#if DO_VERIFY
    pHead->VerifyLinks(pHead);
#endif // DO_VERIFY

    TYPE pLink;
    while((pLink = CutHead(pHead)) != NULL)
        ;
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::FreeListAll(TYPE& pHead)
{
#if DO_VERIFY
    pHead->VerifyLinks(pHead);
#endif // DO_VERIFY

    TYPE pLink;
    while((pLink = CutHead(pHead)) != NULL)
        free(pLink);
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::DestroyListAll(TYPE& pHead)
{
#if DO_VERIFY
    pHead->VerifyLinks(pHead);
#endif // DO_VERIFY

    TYPE pLink;
    while((pLink = CutHead(pHead)) != NULL)
        delete pLink;
}

template <class TYPE, class BaseClass>
int TDoubleLinkRef<TYPE, BaseClass>::GetCount() const
{
	int nCount = 0;
    TYPE pLink = (TYPE)this;

    while(pLink) {
        nCount++;
        pLink = pLink->m_pNext;
    }

    return nCount;
}

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::GetHead() const
{
    TYPE p = (TYPE)this;

	if (p) {
	    TYPE pLink;
		while((pLink = p->m_pPrev) != NULL)
			p = pLink;
	}

	return p;
}

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::GetTail() const
{
    TYPE p = (TYPE)this;

	if (p) {
	    TYPE pLink;
		while((pLink = p->m_pNext) != NULL)
			p = pLink;
	}

	return p;
}

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::GetNeighbor(BOOL bNext)
{
    ASSERT(this);
    if (bNext)
        return m_pNext;
    return m_pPrev;
}

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::GetTerminal(BOOL bNext)
{
    if (bNext) {
        return GetTail();
    }
    return GetHead();
}

template <class TYPE, class BaseClass>
BOOL TDoubleLinkRef<TYPE, BaseClass>::CutCheck(TYPE& pHead)
{
    ASSERT(this);

    TYPE pPrev = m_pPrev;
    if (pPrev) {
#if DO_VERIFY
        VerifyLinks(pHead);
#endif // DO_VERIFY
        pPrev->m_pNext = m_pNext;
        TYPE pNext;
        if ((pNext = m_pNext) != NULL) {
            pNext->m_pPrev = pPrev;
			m_pNext = NULL;
        }
		m_pPrev = NULL;

        return TRUE;
    } else {
        if (this == pHead) {
            TYPE pNext = m_pNext;
            pHead = pNext;
            if (pNext) {
                pNext->m_pPrev = NULL;
			    m_pNext = NULL;
            }
            return TRUE;
        } else {
            ASSERT(!m_pNext);
            return FALSE;
        }
    }
}

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::Cut(TYPE& pHead)
{
    ASSERT(this);
#if DO_VERIFY
    VerifyLinks(pHead);
#endif // DO_VERIFY

    TYPE pPrev = m_pPrev;
    TYPE pNext = m_pNext;
    if (pPrev) {
        pPrev->m_pNext = pNext;
        if (pNext != NULL) {
            pNext->m_pPrev = pPrev;
			m_pNext = NULL;
        }
		m_pPrev = NULL;
    } else {
        ASSERT(this == pHead);
        pHead = pNext;
        if (pNext) {
            pNext->m_pPrev = NULL;
			m_pNext = NULL;
        }
    }

    return pPrev;
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::InsHead(TYPE& pHead)
{
    ASSERT(this && !m_pPrev && !m_pNext);

    m_pNext = pHead;
    if (pHead) {
        pHead->m_pPrev = (TYPE)this;
    }
    pHead = (TYPE)this;

#if DO_VERIFY
    VerifyLinks(pHead);
#endif // DO_VERIFY
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::InsBefore(TYPE& pHead, TYPE pPrev/* = NULL*/)
{
    ASSERT(this && !m_pPrev && !m_pNext);

    if (pPrev) {
        TYPE pPrevPrev = pPrev->m_pPrev;
        pPrev->m_pPrev = (TYPE)this;
        m_pNext = pPrev;
        if (pPrevPrev) {
            pPrevPrev->m_pNext = (TYPE)this;
            m_pPrev = pPrevPrev;
        } else {
            pHead = (TYPE)this;
        }
#if DO_VERIFY
        VerifyLinks(pHead);
#endif // DO_VERIFY
    } else {
        AddTail(pHead);
    }
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::InsAfter(TYPE& pHead, TYPE pNext/* = NULL*/)
{
    ASSERT(this && !m_pPrev && !m_pNext);

    if (pNext) {
        TYPE pNextNext = pNext->m_pNext;
        pNext->m_pNext = (TYPE)this;
        m_pPrev = pNext;
        if (pNextNext) {
            pNextNext->m_pPrev = (TYPE)this;
            m_pNext = pNextNext;
        }
#if DO_VERIFY
        VerifyLinks(pHead);
#endif // DO_VERIFY
    } else {
        AddTail(pHead);
    }
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::AddTail(TYPE& pHead)
{
    ASSERT(this && !m_pPrev && !m_pNext);

    if (pHead) {
        TYPE pTail = pHead->GetTail();
        ASSERT(pTail && !pTail->m_pNext);
        pTail->m_pNext = (TYPE)this;
        m_pPrev = pTail;
    } else {
        pHead = (TYPE)this;
    }
#if DO_VERIFY
    VerifyLinks(pHead);
#endif // DO_VERIFY
}

template <class TYPE, class BaseClass>
TYPE TDoubleLinkRef<TYPE, BaseClass>::CutGroup(TYPE& pHead)
{
    if (this) {
#if DO_VERIFY
        VerifyLinks(pHead);
#endif // DO_VERIFY
        TYPE pPrev = m_pPrev;
        if (pPrev) {
            pPrev->m_pNext = NULL;
		    m_pPrev = NULL;
        } else {
            ASSERT(this == pHead);
            pHead = NULL;
        }
    }

    return (TYPE)this;
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::InsHeadGroup(TYPE& pHead)
{
    if (this) {
        ASSERT(!m_pPrev);

        if (pHead) {
            TYPE pTail = GetTail();
            pTail->m_pNext = pHead;
            pHead->m_pPrev = pTail;
        }
        pHead = (TYPE)this;

#if DO_VERIFY
        VerifyLinks(pHead);
#endif // DO_VERIFY
    }
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::InsGroup(TYPE& pHead, TYPE pPrev/* = NULL*/)
{
    if (this) {
        ASSERT(!m_pPrev);

        if (pPrev) {
            TYPE pNext = pPrev->m_pNext;
            pPrev->m_pNext = (TYPE)this;
            m_pPrev = pPrev;
            if (pNext) {
                TYPE pTail = GetTail();
                pTail->m_pNext = pNext;
                pNext->m_pPrev = pTail;
            }
#if DO_VERIFY
            VerifyLinks(pHead);
#endif // DO_VERIFY
        } else {
            InsHeadGroup(pHead);
        }
    }
}

template <class TYPE, class BaseClass>
void TDoubleLinkRef<TYPE, BaseClass>::AddTailGroup(TYPE& pHead)
{
    if (this) {
        ASSERT(!m_pPrev);

        if (pHead) {
            TYPE pTail = pHead->GetTail();
            ASSERT(pTail && !pTail->m_pNext);
            pTail->m_pNext = (TYPE)this;
            m_pPrev = pTail;
        } else {
            pHead = (TYPE)this;
        }
#if DO_VERIFY
        VerifyLinks(pHead);
#endif // DO_VERIFY
    }
}

template <class TYPE, class BaseClass>
class TDoubleLink : public BaseClass
{
public:
    TYPE* m_pLinkStart;
public:
    TDoubleLink()
    {
        m_pLinkStart = NULL;
    }
    ~TDoubleLink()
    {
        ASSERT(!m_pLinkStart);
    }
    operator TYPE* () const { return m_pLinkStart; }
    TYPE* CutHead()
    {
        return TYPE::CutHead(m_pLinkStart);
    }
    void CutListAll()
    {
        TYPE::CutListAll(m_pLinkStart);
    }
    void FreeListAll()
    {
        TYPE::FreeListAll(m_pLinkStart);
    }
    void DestroyListAll()
    {
        TYPE::DestroyListAll(m_pLinkStart);
    }
	int GetCount() const
    {
        return m_pLinkStart->GetCount();
    }
	TYPE* GetHead() const
    {
        return m_pLinkStart;
    }
	TYPE* GetTail() const
    {
        return m_pLinkStart->GetTail();
    }
    BOOL CutCheck(TYPE* pLink)
    {
        return pLink->CutCheck(m_pLinkStart);
    }
    TYPE* Cut(TYPE* pLink)
    {
        return pLink->Cut(m_pLinkStart);
    }
    void InsHead(TYPE* pLink)
    {
        pLink->InsHead(m_pLinkStart);
    }
    void InsBefore(TYPE* pLink, TYPE* pPrev = NULL)
    {
        pLink->InsBefore(m_pLinkStart, pPrev);
    }
    void InsAfter(TYPE* pLink, TYPE* pNext = NULL)
    {
        pLink->InsAfter(m_pLinkStart, pNext);
    }
    void AddTail(TYPE* pLink)
    {
        pLink->AddTail(m_pLinkStart);
    }
    TYPE* CutGroup(TYPE* pLink)
    {
        return pLink->CutGroup(m_pLinkStart);
    }
    void InsHeadGroup(TYPE* pLink)
    {
        pLink->InsHeadGroup(m_pLinkStart);
    }
    void InsGroup(TYPE* pLink, TYPE* pPrev = NULL)
    {
        pLink->InsGroup(m_pLinkStart, pPrev);
    }
    void AddTailGroup(TYPE* pLink)
    {
        pLink->AddTailGroup(m_pLinkStart);
    }
    TYPE* FindIndex(int nIndex) const
    {
        if (nIndex >= 0) {
            TYPE* pLink = m_pLinkStart;

            while(pLink) {
                if (nIndex == 0) {
                    return pLink;
                }
                pLink = pLink->m_pNext;
                nIndex--;
            }
        }

        return NULL;
    }
    int Find(TYPE* pLink) const
    {
        if (pLink) {
            int nIndex = 0;
            TYPE* pLink2 = m_pLinkStart;

            while(pLink2) {
                if (pLink2 == pLink) {
                    return nIndex;
                }
                pLink2 = pLink2->m_pNext;
                nIndex++;
            }
        }

        return -1;
    }
};

template <class TYPE, class BaseClass>
class TDoubleLinkCut : public TDoubleLink<TYPE, BaseClass>
{
public:
    ~TDoubleLinkCut()
    {
        Reset();
    }
    void Reset()
    {
        CutListAll();
    }
    void Del(TYPE* pLink)
    {
        CutCheck(pLink);
    }
};

template <class TYPE, class BaseClass>
class TDoubleLinkFree : public TDoubleLink<TYPE, BaseClass>
{
public:
    ~TDoubleLinkFree()
    {
        Reset();
    }
    void Reset()
    {
        FreeListAll();
    }
    void Del(TYPE* pLink)
    {
        CutCheck(pLink);
        free(pLink);
    }
};

template <class TYPE, class BaseClass>
class TDoubleLinkDestroy : public TDoubleLink<TYPE, BaseClass>
{
public:
    ~TDoubleLinkDestroy()
    {
        Reset();
    }
    void Reset()
    {
        DestroyListAll();
    }
    void Del(TYPE* pLink)
    {
        CutCheck(pLink);
        delete pLink;
    }
};

template <class TYPE, class BaseClass>
class TDoubleLinkTreeRef : public TDoubleLinkRef<TYPE, BaseClass>
{
public:
    TYPE m_pParent;
    TYPE m_pChild;
public:
    TDoubleLinkTreeRef()
    {
        m_pParent = NULL;
        m_pChild = NULL;
    }
#ifdef _DEBUG
    ~TDoubleLinkTreeRef()
    {
        ASSERT(!(m_pPrev || m_pNext || m_pParent));
    }
#endif // _DEBUG
	int CountChildren() const
	{
		return m_pChild->TDoubleLinkRef<TYPE, BaseClass>::GetCount();
	}
	int CountChildrenAll() const
	{
        if (this) {
            TYPE pChild = m_pChild;
            int nCount;

            for(nCount = 0; pChild; nCount++) {
                nCount += pChild->CountChildrenAll();
		        pChild = pChild->m_pNext;
	        }

            return nCount;
        }

        return 0;
	}
    int CountParent() const
    {
	    ASSERT(this);
	    TYPE pParent = m_pParent;
	    int nCount = 0;

	    while(pParent) {
		    nCount++;
		    pParent = pParent->m_pParent;
	    }

	    return nCount;
    }
    TYPE CutChild(TYPE pLink)
    {
        ASSERT(pLink->m_pParent == (TYPE)this);

        TYPE pPrev = pLink->TDoubleLinkRef<TYPE, BaseClass>::Cut(m_pChild);
        pLink->m_pParent = NULL;

        return pPrev;
    }
    void InsChild(TYPE pLink)
    {
        pLink->TDoubleLinkRef<TYPE, BaseClass>::InsHead(m_pChild);
        pLink->m_pParent = (TYPE)this;
    }
    void InsChildBefore(TYPE pLink, TYPE pPrev = NULL)
    {
        pLink->TDoubleLinkRef<TYPE, BaseClass>::InsBefore(m_pChild, pPrev);
        pLink->m_pParent = (TYPE)this;
    }
    void AddChild(TYPE pLink)
    {
        pLink->TDoubleLinkRef<TYPE, BaseClass>::AddTail(m_pChild);
        pLink->m_pParent = (TYPE)this;
    }
	TYPE CutChildren()
	{
		TYPE pChild = m_pChild;
		m_pChild = NULL;

		TYPE p = pChild;
		while(p) {
			p->m_pParent = NULL;
			p = p->m_pNext;
		}

		return pChild;
	}
	void AddChildren(TYPE pChild)
	{
		if (pChild) {
			ASSERT(!pChild->m_pPrev);
			TYPE pTail = m_pChild->TDoubleLinkRef<TYPE, BaseClass>::GetTail();
			if (pTail) {
				pTail->m_pNext = pChild;
				pChild->m_pPrev = pTail;
			} else {
				m_pChild = pChild;
			}
			while(pChild) {
				ASSERT(!pChild->m_pParent);
				pChild->m_pParent = (TYPE)this;
				pChild = pChild->m_pNext;
			}
		}
	}
    static void DestroyAll(TYPE& pStart)
    {
        pStart->DestroyAll();
        pStart = NULL;
    }
    void DestroyAll()
    {
        if (this) {
            DestroyAllChildren();
            if (m_pParent) {
                m_pParent->CutChild((TYPE)this);
            }
            delete this;
        }
    }
    void DestroyAllChildren()
    {
        ASSERT(this);
        while(m_pChild) {
            TYPE pChild = m_pChild;
        
            CutChild(pChild);
            pChild->DestroyAllChildren();

            delete pChild;
        }
    }
    void SetAtArray(TYPE* pArray, int& nIndex) const
    {
        // this is not included...
        ASSERT(&nIndex);
        if (this) {
            TYPE pChild = m_pChild;
            while(pChild) {
                pArray[nIndex++] = pChild;
                pChild->SetAtArray(pArray, nIndex);
                pChild = pChild->m_pNext;
            }
        }
    }
    void MakeArray(TARRAY(TYPE)& aTree) const
    {
        aTree.Reset();
        int nSize = CountChildrenAll();
        int nIndex = 0;
        SetAtArray(&aTree.Add(nSize), nIndex);
    }
};

#endif // !defined(__DBLINKS__)