/*********************************************************************
Copyright 2001 Alexander Berthold, alexander-berthold@web.de.
-- This file is part of ctkCommon --
"ctkCommon" is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2 of the License, or any later version.
"ctkCommon" is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with "ctkCommon"; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330,
Boston, MA 02111-1307 USA
---------------------------------------------------------------
If you find any bugs or if you make other corrections/
enhancements, i'd appreciate if you'd let me know about
that. My email is
alexander-berthold@web.de
If you share this code, do not remove this text.
---------------------------------------------------------------
Class: ctkHLinkedList
Author: Alexander Berthold
Copyright: Alexander Berthold
Date: 2001/05/20
Version: 0.1.05
Purpose: Implements a hierarchical doubly-linked list.
ctkHLinkedListElement<class T> is the base class for the
elements of the linked list. ctkHLinkedListNode<class Y,
class T> is the mixin class to implement the methods of
a node of the linked list. ctkHLinkedListBranch<class Y,
class T> is the mixin class to implement the methods of
a branch of the linked list.
Version history:
- 2001/05/19
Released the current version 0.1.05
ToDo:
- The iterator/const_iterator implementation lacks functionality
and conformity.
- begin() is not const correct.
- Options to control the doubly-linkedness are missing (is
not necessary for the project cxAnalyzer).
- The methods exposed by ctkHLinkedListBranch are not nearly
orthogonal yet and will change in a later release.
*********************************************************************/
// ctkHLinkedList.h: interface for the ctkHLinkedList class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_CTKHLINKEDLIST_H__227FC0EE_697C_4EF5_AD09_5A2AD1C7CC16__INCLUDED_)
#define AFX_CTKHLINKEDLIST_H__227FC0EE_697C_4EF5_AD09_5A2AD1C7CC16__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
template<class Y, class T>
class ctkHLinkedListNode;
template<class Y, class T, bool fDontCareIfNodeExistsAlready = true>
class ctkHLinkedListBranch;
template<class T>
class ctkHLinkedListElement
{
public:
ctkHLinkedListElement(bool _fIsNode)
{
pthlleParent =NULL;
pthllePrev =NULL;
pthlleNext =NULL;
fIsNode_ =_fIsNode;
}
virtual ~ctkHLinkedListElement()
{};
public:
bool fIsNode_;
T* pthlleParent;
T* pthllePrev;
T* pthlleNext;
public:
bool fCheckValidHLL() const
{
return true;
};
virtual bool fIsBranch() const { return !fIsNode_; };
virtual bool fIsNode() const { return fIsNode_; };
T* tGetParent() const { return pthlleParent; };
T* tGetNext() const { return pthlleNext; };
T* tGetPrev() const { return pthllePrev; };
ctkHLinkedListElement<T>* phlleGetParent() const
{ return (ctkHLinkedListElement<T>*)pthlleParent; };
ctkHLinkedListElement<T>* phlleGetNext() const
{ return (ctkHLinkedListElement<T>*)pthlleNext; };
ctkHLinkedListElement<T>* phlleGetPrev() const
{ return (ctkHLinkedListElement<T>*)pthllePrev; };
bool operator<(T& thlleOther) const
{
ctkHLinkedListElement<T>* phlleOther = (ctkHLinkedListElement<T>*)&pthlleOther;
ASSERT(pthlleParent!=NULL);
ASSERT(phlleOther->pthlleParent==pthlleParent);
if(phlleOther==this)
return false;
T* pthlleCurEl = pthlleNext;
while(pthlleCurEl!=NULL)
{
ASSERT(pthlleCurEl->pthlleParent==pthlleParent);
ASSERT(pthlleCurEl->pthllePrev!=NULL);
if(pthlleCurEl == pthlleOther)
return true;
pthlleCurEl =((ctkHLinkedListElement<T>*)pthlleCurEl)->pthlleNext();
}
return false;
}
bool operator<(ctkHLinkedListElement<T>& hlleOther)
{
return operator<( *((T*)&hlleOther) );
}
bool operator>(T& thlleOther) const
{
ctkHLinkedListElement<T>* phlleOther = (ctkHLinkedListElement<T>*)&thlleOther;
ASSERT(pthlleParent!=NULL);
ASSERT(phlleOther->pthlleParent==pthlleParent);
if(phlleOther==this)
return false;
T* pthlleCurEl = pthllePrev;
while(pthlleCurEl!=NULL)
{
ASSERT(pthlleCurEl->pthlleParent==pthlleParent);
ASSERT(pthlleCurEl->pthlleNext!=NULL);
if(pthlleCurEl == &thlleOther)
return true;
pthlleCurEl =((ctkHLinkedListElement<T>*)pthlleCurEl)->pthllePrev;
}
return false;
}
bool operator>(ctkHLinkedListElement<T>& hlleOther)
{
return operator>( *((T*)&hlleOther) );
}
bool operator==(T& thlleOther) const
{
ctkHLinkedListElement<T>* phlleOther = (ctkHLinkedListElement<T>*)&thlleOther;
ASSERT(pthlleParent!=NULL);
ASSERT(phlleOther->pthlleParent==pthlleParent);
if(phlleOther==this)
return true;
return false;
}
bool operator==(ctkHLinkedListElement<T>& hlleOther)
{
return operator==( *((T*)&hlleOther) );
}
bool operator>=(T& thlleOther) const
{
return !operator<(thlleOther);
}
bool operator>=(ctkHLinkedListElement<T>& hlleOther)
{
return operator>=( *((T*)&hlleOther) );
}
bool operator<=(T& thlleOther) const
{
return !operator>(thlleOther);
};
bool operator<=(ctkHLinkedListElement<T>& hlleOther)
{
return operator<=( *((T*)&hlleOther) );
}
friend class ctkHLinkedListNode;
friend class ctkHLinkedListBranch;
};
template<class Y, class T>
class ctkHLinkedListNode
{
public:
ctkHLinkedListNode<Y,T>()
{
};
virtual ~ctkHLinkedListNode<Y,T>()
{
};
bool fCheckValid() const
{
if(!((ctkHLinkedListElement<T>*)((T*)this))->fCheckValidHLL())
return false;
return true;
};
};
template<class Y, class T, bool fDontCareIfNodeExistsAlready = true>
class ctkHLinkedListBranchBase
{
public:
ctkHLinkedListBranchBase<Y,T,fDontCareIfNodeExistsAlready>()
{
pthlleFront =NULL;
pthlleBack =NULL;
};
virtual ~ctkHLinkedListBranchBase<Y,T,fDontCareIfNodeExistsAlready>()
{
};
public:
T* pthlleFront;
T* pthlleBack;
bool fIsEmpty() const { return pthlleFront==NULL; };
T* tGetFront() const { return pthlleFront; };
T* tGetBack() const { return pthlleBack; };
ctkHLinkedListElement<T>* phlleGetFront() const
{ return (ctkHLinkedListElement<T>*)pthlleFront; };
ctkHLinkedListElement<T>* phlleGetBack() const
{ return (ctkHLinkedListElement<T>*)pthlleBack; };
ctkHLinkedListElement<T>* phlleGetThis() const
{
return ((ctkHLinkedListElement<T>*)((Y*)this));
};
void vPushFront(T* pthlleItem)
{
ctkHLinkedListElement<T>* phlleItem =
(ctkHLinkedListElement<T>*)pthlleItem;
ASSERT(phlleItem->fCheckValidHLL());
ASSERT(phlleItem!=phlleGetThis() );
if(!fDontCareIfNodeExistsAlready)
{
ASSERT(phlleItem->tGetParent()==NULL);
ASSERT(phlleItem->tGetPrev()==NULL);
ASSERT(phlleItem->tGetNext()==NULL);
}
else
{
phlleItem->pthlleNext=NULL;
phlleItem->pthllePrev=NULL;
phlleItem->pthlleParent=NULL;
}
if(pthlleFront==NULL)
{
ASSERT(pthlleBack==NULL);
pthlleFront =pthlleItem;
pthlleBack =pthlleItem;
}
else
{
ASSERT(pthlleBack!=NULL);
ctkHLinkedListElement<T>* phlleFront = phlleGetFront();
ASSERT(phlleFront->tGetPrev()==NULL);
phlleFront->pthllePrev =pthlleItem;
phlleItem->pthlleNext =pthlleFront;
pthlleFront =pthlleItem;
}
phlleItem->pthlleParent=(T*)((Y*)this);
};
T* tPopFront()
{
T *pthlleRet = NULL;
ASSERT(pthlleFront!=NULL);
ASSERT(phlleGetFront()->tGetPrev()==NULL);
pthlleRet =pthlleFront;
if(pthlleFront==pthlleBack)
{
pthlleFront =NULL;
pthlleBack =NULL;
}
else
{
pthlleFront =pthlleFront->tGetNext();
pthlleFront->pthllePrev=NULL;
}
pthlleRet->pthlleNext=NULL;
return pthlleRet;
}
T* tPopBack()
{
T *pthlleRet = NULL;
ASSERT(pthlleBack!=NULL);
ASSERT(phlleGetBack()->tGetNext()==NULL);
pthlleRet =pthlleBack;
if(pthlleFront==pthlleBack)
{
pthlleFront =NULL;
pthlleBack =NULL;
}
else
{
pthlleBack =pthlleBack->tGetPrev();
pthlleBack->pthlleNext=NULL;
}
pthlleRet->pthllePrev=NULL;
return pthlleRet;
}
void vPushBack(T* pthlleItem)
{
if(pthlleFront==NULL)
vPushFront(pthlleItem);
else
vInsertAfter(pthlleBack,pthlleItem);
}
bool fIsChild(T* pthlleItem)
{
T* pthlleCur = pthlleFront;
while(pthlleCur!=NULL)
{
if(pthlleCur==pthlleItem)
return true;
pthlleCur =((ctkHLinkedListElement<T>*)pthlleCur)->tGetNext();
}
return false;
}
void vInsertBefore(T* pthlleItem, T* pthlleInsert)
{
ctkHLinkedListElement<T>* phlleItem =
(ctkHLinkedListElement<T>*)pthlleItem;
ctkHLinkedListElement<T>* phlleInsert =
(ctkHLinkedListElement<T>*)pthlleInsert;
if(pthlleItem==NULL)
vPushFront(pthlleInsert);
else
{
ASSERT(fIsChild(pthlleItem));
if(!fDontCareIfNodeExistsAlready)
{
ASSERT(phlleInsert->tGetParent()==NULL);
ASSERT(phlleInsert->tGetPrev()==NULL);
ASSERT(phlleInsert->tGetNext()==NULL);
}
else
{
phlleInsert->pthlleNext=NULL;
phlleInsert->pthllePrev=NULL;
phlleInsert->pthlleParent=NULL;
}
phlleInsert->pthllePrev=phlleItem->tGetPrev();
phlleInsert->pthlleNext=pthlleItem;
if(phlleItem->tGetPrev()!=NULL)
{
ASSERT(phlleItem->phlleGetPrev()->pthlleNext==pthlleItem);
phlleItem->phlleGetPrev()->pthlleNext=pthlleInsert;
}
phlleItem->pthllePrev=pthlleInsert;
if(pthlleItem == pthlleFront)
pthlleFront = pthlleInsert;
phlleInsert->pthlleParent=(T*)((Y*)this);
}
}
void vInsertAfter(T* pthlleItem, T* pthlleInsert)
{
ctkHLinkedListElement<T>* phlleItem =
(ctkHLinkedListElement<T>*)pthlleItem;
ctkHLinkedListElement<T>* phlleInsert =
(ctkHLinkedListElement<T>*)pthlleInsert;
if(pthlleItem==NULL)
vPushFront(pthlleInsert);
else
{
ASSERT(fIsChild(pthlleItem));
if(!fDontCareIfNodeExistsAlready)
{
ASSERT(phlleInsert->tGetParent()==NULL);
ASSERT(phlleInsert->tGetPrev()==NULL);
ASSERT(phlleInsert->tGetNext()==NULL);
}
else
{
phlleInsert->pthlleNext=NULL;
phlleInsert->pthllePrev=NULL;
phlleInsert->pthlleParent=NULL;
}
phlleInsert->pthlleNext=phlleItem->tGetNext();
phlleInsert->pthllePrev=pthlleItem;
if(phlleItem->tGetNext()!=NULL)
{
ASSERT(phlleItem->phlleGetNext()->pthllePrev==pthlleItem);
phlleItem->phlleGetNext()->pthllePrev=pthlleInsert;
}
phlleItem->pthlleNext=pthlleInsert;
if(pthlleItem == pthlleBack)
pthlleBack = pthlleInsert;
phlleInsert->pthlleParent=(T*)((Y*)this);
}
}
void vUnlink(T* pthlleFirst, T* pthlleLast,
T** ppthlleOneBefore = NULL,
T** ppthlleOneAfter = NULL,
bool fNullizeParents = false)
{
ASSERT(pthlleFirst!=NULL);
ASSERT(pthlleLast!=NULL);
ctkHLinkedListElement<T>* phlleFirst =
(ctkHLinkedListElement<T>*)pthlleFirst;
ctkHLinkedListElement<T>* phlleLast =
(ctkHLinkedListElement<T>*)pthlleLast;
ASSERT(fIsChild(pthlleFirst));
ASSERT(fIsChild(pthlleLast));
ASSERT(phlleFirst->phlleGetParent()==phlleGetThis());
ASSERT(phlleLast->phlleGetParent()==phlleGetThis());
ASSERT( (*phlleFirst)<=(*phlleLast) );
if(pthlleFirst!=pthlleFront)
phlleFirst->phlleGetPrev()->pthlleNext=phlleLast->pthlleNext;
else
pthlleFront=phlleLast->pthlleNext;
if(pthlleLast!=pthlleBack)
phlleLast->phlleGetNext()->pthllePrev=phlleFirst->pthllePrev;
else
pthlleBack=phlleFirst->pthllePrev;
if(ppthlleOneBefore)
(*ppthlleOneBefore) = phlleFirst->pthllePrev;
if(ppthlleOneAfter)
(*ppthlleOneAfter) = phlleLast->pthlleNext;
phlleFirst->pthllePrev =NULL;
phlleLast->pthlleNext =NULL;
if(fNullizeParents)
{
ctkHLinkedListElement<T>* phlleCur = phlleFirst;
while(phlleCur!=NULL)
{
phlleCur->pthlleParent=NULL;
if(phlleCur==phlleLast)
break;
phlleCur =phlleCur->phlleGetNext();
}
}
}
void vMoveToSubBranch(T* pthlleBranch,
T* pthlleFirst, T* pthlleLast)
{
ctkHLinkedListElement<T>* phlleBranch =
(ctkHLinkedListElement<T>*)pthlleBranch;
ctkHLinkedListBranch<Y,T>* phllbBranch =
(ctkHLinkedListBranch<Y,T>*)((Y*)pthlleBranch);
ctkHLinkedListElement<T>* phlleFirst =
(ctkHLinkedListElement<T>*)pthlleFirst;
ctkHLinkedListElement<T>* phlleLast =
(ctkHLinkedListElement<T>*)pthlleLast;
ASSERT(phlleBranch->phlleGetParent()==NULL);
ASSERT(phllbBranch->pthlleBack==NULL);
ASSERT(phllbBranch->pthlleFront==NULL);
ASSERT(fIsChild(pthlleFirst));
ASSERT(fIsChild(pthlleLast));
ASSERT(phlleFirst->phlleGetParent()==phlleGetThis());
ASSERT(phlleLast->phlleGetParent()==phlleGetThis());
(*phlleFirst).operator <=(*pthlleLast);
ASSERT( (*phlleFirst)<=(*phlleLast) );
// Unlink the part [pthlleFirst ... pthlleLast]
T *pthlleOneAfter = NULL, *pthlleOneBefore = NULL;
vUnlink(pthlleFirst,pthlleLast,&pthlleOneBefore, &pthlleOneAfter);
if(pthlleFront==NULL)
{
ASSERT(pthlleBack==NULL);
pthlleFront =pthlleBranch;
pthlleBack =pthlleBranch;
phlleBranch->pthlleParent=(T*)this;
}
else
{
if(pthlleOneBefore!=NULL)
vInsertAfter(pthlleOneBefore,pthlleBranch);
else
vInsertBefore(pthlleOneAfter,pthlleBranch);
}
// Adjust the parent of the unlinked part
T* pthlleCurEl = pthlleFirst;
while(pthlleCurEl!=NULL)
{
((ctkHLinkedListElement<T>*)pthlleCurEl)->pthlleParent=pthlleBranch;
pthlleCurEl =((ctkHLinkedListElement<T>*)pthlleCurEl)->pthlleNext;
}
phllbBranch->pthlleFront=pthlleFirst;
phllbBranch->pthlleBack =pthlleLast;
// Done.
}
public:
bool fCheckValid() const
{
T* pthlleThis = (T*)((Y*)this);
if(!phlleGetThis()->fCheckValidHLL())
return false;
// Test integrity of front/back pointers
if(pthlleFront!=NULL)
{
if(pthlleBack==NULL)
{
ASSERT(FALSE);
return false;
}
}
if(pthlleBack!=NULL)
{
if(pthlleFront==NULL)
{
ASSERT(FALSE);
return false;
}
}
// Test integrity of the order of the front/back pointers
if(pthlleFront!=NULL)
{
if( phlleGetFront()->pthllePrev!=NULL )
{
ASSERT(FALSE);
return false;
}
if( phlleGetBack()->pthlleNext!=NULL )
{
ASSERT(FALSE);
return false;
}
if( (*phlleGetFront())>(*phlleGetBack()) )
{
ASSERT(FALSE);
return false;
}
}
// Test integrity of the child elements
T* pthlleCurEl = pthlleFront;
while(pthlleCurEl!=NULL)
{
bool fOk = true;
ctkHLinkedListElement<T>* phlleCurEl = (ctkHLinkedListElement<T>*)pthlleCurEl;
// Check if parent of the child node equals to this branch
if(phlleCurEl->pthlleParent!=pthlleThis)
fOk=false;
// If the child node is a branch, test its integrity
if(phlleCurEl->fIsBranch())
{
ctkHLinkedListBranch<Y,T>* phllbCurEl =
((ctkHLinkedListBranch<Y,T>*)((Y*)pthlleCurEl));
if(!phllbCurEl->fCheckValid())
{
ASSERT(FALSE);
return false;
}
}
else
{
// It is a node. Test the nodes' integrity
ctkHLinkedListNode<Y,T>* phllnCurEl =
(ctkHLinkedListNode<Y,T>*)((Y*)pthlleCurEl);
if(!phllnCurEl->fCheckValid())
{
ASSERT(FALSE);
return false;
}
}
pthlleCurEl =phlleCurEl->pthlleNext;
}
return true;
};
};
template<class Y, class T, bool fDontCareIfNodeExistsAlready = true>
class ctkHLinkedListBranch : public ctkHLinkedListBranchBase<Y,T,fDontCareIfNodeExistsAlready>
{
public:
class iterator
{
public:
const ctkHLinkedListBranch<Y,T,fDontCareIfNodeExistsAlready>* phllbBranch;
T* pthlleCur;
public:
ctkHLinkedListElement<T>* phlleGetCur() const
{ return (ctkHLinkedListElement<T>*)pthlleCur; };
bool fIsFirst() const
{
ASSERT(pthlleCur!=NULL);
return (pthlleCur->pthllePrev==NULL);
}
bool fIsLast() const
{
ASSERT(pthlleCur!=NULL);
return (pthlleCur->pthlleNext==NULL);
}
bool fIsEnd() const
{
return (pthlleCur==NULL);
}
bool operator==(const iterator& other) const
{
if(pthlleCur==NULL || other.pthlleCur==NULL)
{
if(pthlleCur==NULL && other.pthlleCur==NULL)
return true;
return false;
}
return (*phlleGetCur())==(*other.phlleGetCur());
};
bool operator!=(const iterator& other) const
{
return !operator==(other);
}
bool operator<(const iterator& other) const
{
if(pthlleCur==NULL) return false;
if(other.pthlleCur==NULL) return true;
return (*phlleGetCur())<(*other.phlleGetCur());
}
bool operator>(const iterator& other) const
{
if(pthlleCur==NULL) return false;
if(other.pthlleCur==NULL) return true;
return (*phlleGetCur())>(*other.phlleGetCur());
}
bool operator<=(const iterator& other) const
{
return !operator>(other);
}
bool operator>=(const iterator& other) const
{
return !operator<(other);
}
iterator& operator++()
{
ASSERT(pthlleCur!=NULL);
if(pthlleCur==NULL)
return (*this);
pthlleCur =phlleGetCur()->pthlleNext;
return (*this);
}
iterator operator++(int)
{
iterator res = (*this);
++*this;
return res;
}
iterator& operator--()
{
if(pthlleCur==NULL)
{
pthlleCur=phllbBranch->pthlleBack;
ASSERT(pthlleCur==NULL);
return (*this);
}
ASSERT(phlleGetCur()->pthllePrev!=NULL);
pthlleCur =phlleGetCur()->pthllePrev;
return (*this);
}
iterator operator--(int)
{
iterator res = (*this);
--*this;
return res;
}
iterator& operator+(int n)
{
if(pthlleCur==NULL)
{
ASSERT(FALSE);
return (*this);
}
int i;
for(i=0;i<n;i++)
++(*this);
return (*this);
}
iterator& operator-(int n)
{
int i;
for(i=0;i<n;i++)
--(*this);
return (*this);
}
T* operator*() const
{
ASSERT(pthlleCur!=NULL);
return (pthlleCur);
}
};
class const_iterator : public iterator
{
public:
const T* operator*() const
{
return iterator::operator*();
}
};
public:
iterator from_const_iterator(const_iterator& it)
{
return iterator(it);
}
iterator begin()
{
iterator it;
it.phllbBranch =this;
it.pthlleCur =tGetFront();
return it;
}
iterator end()
{
iterator it;
it.phllbBranch =this;
it.pthlleCur =NULL;
return it;
}
const_iterator begin() const
{
const_iterator it;
it.phllbBranch =this;
it.pthlleCur =tGetFront();
return it;
}
const_iterator end() const
{
const_iterator it;
it.phllbBranch =this;
it.pthlleCur =NULL;
return it;
}
iterator get_iterator(T* pthlleItem)
{
ctkHLinkedListElement<T>* phlleItem =
(ctkHLinkedListElement<T>*)pthlleItem;
ASSERT(phlleItem->phlleGetParent()==phlleGetThis());
ASSERT(fIsChild(pthlleItem));
iterator it;
it.phllbBranch =this;
it.pthlleCir =pthlleItem;
return it;
}
const_iterator get_iterator(const T* pthlleItem) const
{
ctkHLinkedListElement<T>* phlleItem =
(ctkHLinkedListElement<T>*)pthlleItem;
ASSERT(phlleItem->phlleGetParent()==phlleGetThis());
ASSERT(fIsChild(pthlleItem));
const_iterator it;
it.phllbBranch =this;
it.pthlleCir =pthlleItem;
return it;
}
void push_front(T* pthlleItem)
{
vPushFront(pthlleItem);
}
void push_back(T* pthlleItem)
{
vPushBack(pthlleItem);
}
void pop_front()
{
tPopFront();
}
void pop_back()
{
tPopBack();
}
};
#endif // !defined(AFX_CTKHLINKEDLIST_H__227FC0EE_697C_4EF5_AD09_5A2AD1C7CC16__INCLUDED_)