562 lines
12 KiB
C++
562 lines
12 KiB
C++
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Copyright (C) Microsoft Corporation, 1992 - 1997.
|
||
|
|
//
|
||
|
|
// File: DBLINK.HXX
|
||
|
|
//
|
||
|
|
// Contents: Parametrized doubly linked list and iterators
|
||
|
|
//
|
||
|
|
// History: 15-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
#pragma once
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Class: CDoubleLink
|
||
|
|
//
|
||
|
|
// Purpose: Linked element
|
||
|
|
//
|
||
|
|
// History: 15-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: Use as base for your class. No need to override anything.
|
||
|
|
//
|
||
|
|
// class CFoo: public CDoubleLink
|
||
|
|
// {
|
||
|
|
// // your data and code goes here
|
||
|
|
// };
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
class CDoubleLink
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
|
||
|
|
CDoubleLink* Next() { return _next; }
|
||
|
|
|
||
|
|
CDoubleLink* Prev() { return _prev; }
|
||
|
|
|
||
|
|
void Close() { _next = this; _prev = this; }
|
||
|
|
|
||
|
|
BOOL IsSingle() const { return _next == this; }
|
||
|
|
|
||
|
|
void Unlink()
|
||
|
|
{
|
||
|
|
_next->_prev = _prev;
|
||
|
|
_prev->_next = _next;
|
||
|
|
}
|
||
|
|
|
||
|
|
void InsertBefore ( CDoubleLink* pAfter )
|
||
|
|
{
|
||
|
|
CDoubleLink* pBefore = pAfter->_prev;
|
||
|
|
_next = pAfter;
|
||
|
|
_prev = pBefore;
|
||
|
|
pAfter->_prev = this;
|
||
|
|
pBefore->_next = this;
|
||
|
|
}
|
||
|
|
|
||
|
|
void InsertAfter ( CDoubleLink* pBefore )
|
||
|
|
{
|
||
|
|
CDoubleLink* pAfter = pBefore->_next;
|
||
|
|
_next = pAfter;
|
||
|
|
_prev = pBefore;
|
||
|
|
pAfter->_prev = this;
|
||
|
|
pBefore->_next = this;
|
||
|
|
}
|
||
|
|
|
||
|
|
#ifdef CIEXTMODE
|
||
|
|
void CiExtDump(void *ciExtSelf);
|
||
|
|
#endif
|
||
|
|
|
||
|
|
protected:
|
||
|
|
|
||
|
|
CDoubleLink* _next;
|
||
|
|
CDoubleLink* _prev;
|
||
|
|
};
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Class: CDoubleList
|
||
|
|
//
|
||
|
|
// Purpose: Linked list of indexes
|
||
|
|
//
|
||
|
|
// History: 15-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: Use as base for your own class.
|
||
|
|
// Add methods as needed.
|
||
|
|
// To implement searches use forward and backward
|
||
|
|
// iterators described below. For instance, if you implement
|
||
|
|
// a SORTED list:
|
||
|
|
//
|
||
|
|
// Foo* CFooList::Insert ( CFoo* pFoo )
|
||
|
|
// {
|
||
|
|
// for ( CBackFooIter it(*this); !AtEnd(it); BackUp(it) )
|
||
|
|
// {
|
||
|
|
// if ( it->Size() <= pFoo->Size() ) // overloaded operator ->
|
||
|
|
// {
|
||
|
|
// pFoo->InsertAfter(it.GetFoo());
|
||
|
|
// return;
|
||
|
|
// }
|
||
|
|
// }
|
||
|
|
// // end of list
|
||
|
|
// Push(pFoo);
|
||
|
|
// }
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
class CDoubleList
|
||
|
|
{
|
||
|
|
friend class CForwardIter;
|
||
|
|
friend class CBackwardIter;
|
||
|
|
friend class CDoubleIter;
|
||
|
|
|
||
|
|
public:
|
||
|
|
|
||
|
|
class CDoubleIter
|
||
|
|
{
|
||
|
|
friend class CDoubleList;
|
||
|
|
protected:
|
||
|
|
CDoubleIter ( CDoubleLink* pLink ) : _pLinkCur(pLink) {}
|
||
|
|
CDoubleIter ( CDoubleIter& iter ) : _pLinkCur(iter._pLinkCur) {}
|
||
|
|
CDoubleLink* _pLinkCur;
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
CDoubleList()
|
||
|
|
{
|
||
|
|
_root.Close();
|
||
|
|
}
|
||
|
|
|
||
|
|
BOOL IsEmpty() const { return _root.IsSingle(); }
|
||
|
|
|
||
|
|
void Advance ( CDoubleIter& it );
|
||
|
|
|
||
|
|
void BackUp ( CDoubleIter& it );
|
||
|
|
|
||
|
|
BOOL AtEnd ( CDoubleIter& it);
|
||
|
|
|
||
|
|
void SetToEnd( CDoubleIter& it )
|
||
|
|
{
|
||
|
|
Win4Assert( !IsEmpty() );
|
||
|
|
it._pLinkCur = _root.Prev();
|
||
|
|
}
|
||
|
|
|
||
|
|
void SetToBeginning( CDoubleIter& it )
|
||
|
|
{
|
||
|
|
Win4Assert( !IsEmpty() );
|
||
|
|
it._pLinkCur = _root.Next();
|
||
|
|
}
|
||
|
|
|
||
|
|
BOOL IsFirst( CDoubleLink & link )
|
||
|
|
{
|
||
|
|
return _root.Next() == &link;
|
||
|
|
}
|
||
|
|
|
||
|
|
BOOL IsLast( CDoubleLink & link )
|
||
|
|
{
|
||
|
|
return _root.Prev() == &link;
|
||
|
|
}
|
||
|
|
|
||
|
|
BOOL IsFirst( CDoubleIter & it )
|
||
|
|
{
|
||
|
|
Win4Assert( !AtEnd( it ) );
|
||
|
|
return _root.Next() == it._pLinkCur;
|
||
|
|
}
|
||
|
|
|
||
|
|
BOOL IsLast( CDoubleIter & it )
|
||
|
|
{
|
||
|
|
Win4Assert( !AtEnd(it) );
|
||
|
|
return _root.Prev() == it._pLinkCur;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
// In derived class you can add your own Pop(), Top(), etc.
|
||
|
|
// that will cast the results of _Pop(), _Top(), etc...
|
||
|
|
|
||
|
|
#ifdef CIEXTMODE
|
||
|
|
void CiExtDump(void *ciExtSelf);
|
||
|
|
#endif
|
||
|
|
|
||
|
|
protected:
|
||
|
|
|
||
|
|
CDoubleLink* _Top() { return IsEmpty()? 0: _root.Next(); }
|
||
|
|
|
||
|
|
BOOL _IsRoot ( CDoubleLink* pLink ) const
|
||
|
|
{ return pLink == &_root; }
|
||
|
|
|
||
|
|
void _Push ( CDoubleLink* pLink );
|
||
|
|
|
||
|
|
void _Queue ( CDoubleLink* pLink );
|
||
|
|
|
||
|
|
CDoubleLink* _Pop ( void );
|
||
|
|
|
||
|
|
CDoubleLink * _Replace( CDoubleIter & it, CDoubleLink * pNew )
|
||
|
|
{
|
||
|
|
Win4Assert( !AtEnd(it) );
|
||
|
|
Win4Assert( 0 != pNew );
|
||
|
|
|
||
|
|
CDoubleLink * pCurr = it._pLinkCur;
|
||
|
|
pNew->InsertAfter( pCurr );
|
||
|
|
pCurr->Unlink();
|
||
|
|
|
||
|
|
it._pLinkCur = pNew;
|
||
|
|
return pCurr;
|
||
|
|
}
|
||
|
|
|
||
|
|
CDoubleLink _root;
|
||
|
|
};
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Class: CDoubleIter
|
||
|
|
//
|
||
|
|
// Purpose: Linked list iterator
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: Auxiliary class. See iterators below.
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Class: CForwardIter
|
||
|
|
//
|
||
|
|
// Purpose: Linked list iterator
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: Use as base for your own forward iterator.
|
||
|
|
// Notice the overloading of operator ->
|
||
|
|
// -------------------------------------
|
||
|
|
// It lets you use iterator like a pointer to Foo.
|
||
|
|
//
|
||
|
|
// class CForFooIter : public CForwardIter
|
||
|
|
// {
|
||
|
|
// public:
|
||
|
|
//
|
||
|
|
// CForFooIter ( CFooList& list ) : CForwardIter(list) {}
|
||
|
|
//
|
||
|
|
// CFoo* operator->() { return (CFoo*) _pLinkCur; }
|
||
|
|
// CFoo* GetFoo() { return (CFoo*) _pLinkCur; }
|
||
|
|
// };
|
||
|
|
//
|
||
|
|
// Example of usage:
|
||
|
|
// ----------------
|
||
|
|
//
|
||
|
|
// for ( CForFooIter it(fooList); !fooList.AtEnd(it); fooList.Advance(it))
|
||
|
|
// {
|
||
|
|
// it->FooMethod(); // operator ->
|
||
|
|
// }
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
class CForwardIter: public CDoubleList::CDoubleIter
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
CForwardIter ( CDoubleList& list ): CDoubleIter(list._root.Next()) {}
|
||
|
|
};
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Class: CBackwardIter
|
||
|
|
//
|
||
|
|
// Purpose: Linked list iterator
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: See above.
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
class CBackwardIter: public CDoubleList::CDoubleIter
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
CBackwardIter ( CDoubleList& list ): CDoubleIter(list._root.Prev()) {}
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Member: CDoubleList::AtEnd, public
|
||
|
|
//
|
||
|
|
// Arguments: [it] -- iterator
|
||
|
|
//
|
||
|
|
// Returns: TRUE if iterator at end of list
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: Works for both iterators (forward and backward)
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
inline BOOL CDoubleList::AtEnd ( CDoubleIter& it)
|
||
|
|
{
|
||
|
|
return _IsRoot( it._pLinkCur );
|
||
|
|
}
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Member: CDoubleList::Advance, public
|
||
|
|
//
|
||
|
|
// Synopsis: Advances an iterator
|
||
|
|
//
|
||
|
|
// Arguments: [it] -- iterator
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
inline void CDoubleList::Advance ( CDoubleIter& it )
|
||
|
|
{
|
||
|
|
Win4Assert ( !_IsRoot(it._pLinkCur) );
|
||
|
|
it._pLinkCur = it._pLinkCur->Next();
|
||
|
|
}
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Member: CDoubleList::BackUp, public
|
||
|
|
//
|
||
|
|
// Synopsis: Backs up an iterator
|
||
|
|
//
|
||
|
|
// Arguments: [it] -- iterator
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
inline void CDoubleList::BackUp ( CDoubleIter& it )
|
||
|
|
{
|
||
|
|
Win4Assert ( !_IsRoot(it._pLinkCur) );
|
||
|
|
it._pLinkCur = it._pLinkCur->Prev();
|
||
|
|
}
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Member: CDoubleList::Queue, private
|
||
|
|
//
|
||
|
|
// Arguments: [pLink] -- link to be queued
|
||
|
|
//
|
||
|
|
// History: 17-Mar-93 WadeR Created. (based on Push, below)
|
||
|
|
//
|
||
|
|
// Notest: Override, accept only derived class (type safety!), e.g.
|
||
|
|
//
|
||
|
|
// void CFooList::Queue ( CFoo* pFoo )
|
||
|
|
// {
|
||
|
|
// _Queue ( pFoo );
|
||
|
|
// }
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
inline void CDoubleList::_Queue ( CDoubleLink* pLink )
|
||
|
|
{
|
||
|
|
pLink->InsertBefore ( &_root );
|
||
|
|
}
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Member: CDoubleList::Push, private
|
||
|
|
//
|
||
|
|
// Arguments: [pLink] -- link to be pushed
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notest: Override, accept only derived class (type safety!), e.g.
|
||
|
|
//
|
||
|
|
// void CFooList::Push ( CFoo* pFoo )
|
||
|
|
// {
|
||
|
|
// _Push ( pFoo );
|
||
|
|
// }
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
inline void CDoubleList::_Push ( CDoubleLink* pLink )
|
||
|
|
{
|
||
|
|
pLink->InsertAfter ( &_root );
|
||
|
|
}
|
||
|
|
|
||
|
|
//+---------------------------------------------------------------------------
|
||
|
|
//
|
||
|
|
// Member: CDoubleList::_Pop, private
|
||
|
|
//
|
||
|
|
// History: 17-Jun-92 BartoszM Created.
|
||
|
|
//
|
||
|
|
// Notes: Override: cast the result
|
||
|
|
//
|
||
|
|
// CFoo* CFooList::Pop()
|
||
|
|
// {
|
||
|
|
// return (CFoo*) _Pop();
|
||
|
|
// }
|
||
|
|
//
|
||
|
|
//----------------------------------------------------------------------------
|
||
|
|
|
||
|
|
inline CDoubleLink* CDoubleList::_Pop ( void )
|
||
|
|
{
|
||
|
|
CDoubleLink* pLink = 0;
|
||
|
|
if ( !IsEmpty() )
|
||
|
|
{
|
||
|
|
pLink = _root.Next();
|
||
|
|
pLink->Unlink();
|
||
|
|
}
|
||
|
|
return pLink;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
class TDoubleList : public CDoubleList
|
||
|
|
{
|
||
|
|
|
||
|
|
public:
|
||
|
|
|
||
|
|
TDoubleList() : _cEntries(0) {}
|
||
|
|
|
||
|
|
~TDoubleList()
|
||
|
|
{
|
||
|
|
Clear();
|
||
|
|
}
|
||
|
|
|
||
|
|
T * Top()
|
||
|
|
{
|
||
|
|
return (T *) _Top();
|
||
|
|
}
|
||
|
|
|
||
|
|
BOOL IsRoot(T * pLink)
|
||
|
|
{
|
||
|
|
return _IsRoot( pLink );
|
||
|
|
}
|
||
|
|
|
||
|
|
void Push( T * pLink )
|
||
|
|
{
|
||
|
|
Win4Assert( 0 != pLink );
|
||
|
|
_Push( pLink );
|
||
|
|
_cEntries++;
|
||
|
|
}
|
||
|
|
|
||
|
|
void Queue( T * pLink )
|
||
|
|
{
|
||
|
|
Win4Assert( 0 != pLink );
|
||
|
|
_Queue( pLink );
|
||
|
|
_cEntries++;
|
||
|
|
}
|
||
|
|
|
||
|
|
T * Pop()
|
||
|
|
{
|
||
|
|
if ( _cEntries )
|
||
|
|
{
|
||
|
|
_cEntries--;
|
||
|
|
}
|
||
|
|
return (T *) _Pop();
|
||
|
|
}
|
||
|
|
|
||
|
|
T * GetFirst()
|
||
|
|
{
|
||
|
|
return !IsEmpty() ? (T * ) _root.Next() : 0 ;
|
||
|
|
}
|
||
|
|
|
||
|
|
T * GetLast()
|
||
|
|
{
|
||
|
|
if ( IsEmpty() )
|
||
|
|
return 0;
|
||
|
|
else
|
||
|
|
return (T *) _root.Prev();
|
||
|
|
}
|
||
|
|
|
||
|
|
T * GetIth( ULONG i )
|
||
|
|
{
|
||
|
|
//
|
||
|
|
// Return ith entry
|
||
|
|
//
|
||
|
|
|
||
|
|
Win4Assert( i < _cEntries );
|
||
|
|
|
||
|
|
CDoubleLink *pLink = _root.Next();
|
||
|
|
while ( i != 0 )
|
||
|
|
{
|
||
|
|
pLink = pLink->Next();
|
||
|
|
i--;
|
||
|
|
}
|
||
|
|
|
||
|
|
return (T *) pLink;
|
||
|
|
}
|
||
|
|
|
||
|
|
T * RemoveLast()
|
||
|
|
{
|
||
|
|
T * pEntry = 0;
|
||
|
|
if ( !IsEmpty() )
|
||
|
|
{
|
||
|
|
pEntry = (T *) _root.Prev();
|
||
|
|
pEntry->Unlink();
|
||
|
|
Win4Assert( _cEntries > 0 );
|
||
|
|
_cEntries--;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
{
|
||
|
|
//
|
||
|
|
// NOTE: Some clients of this class may increment, but never decrement
|
||
|
|
// this count. This could happen by directly invoking the Unlink
|
||
|
|
// method on a list element instead of using the RemoveFromList
|
||
|
|
// method which maintains the entry count.
|
||
|
|
//
|
||
|
|
Win4Assert( _cEntries == 0 );
|
||
|
|
}
|
||
|
|
|
||
|
|
return pEntry;
|
||
|
|
}
|
||
|
|
|
||
|
|
void RemoveFromList( T * pEntry )
|
||
|
|
{
|
||
|
|
pEntry->Unlink();
|
||
|
|
Win4Assert( _cEntries > 0 );
|
||
|
|
_cEntries--;
|
||
|
|
}
|
||
|
|
|
||
|
|
void MoveToFront( T * pLink )
|
||
|
|
{
|
||
|
|
pLink->Unlink();
|
||
|
|
_Push( pLink );
|
||
|
|
}
|
||
|
|
|
||
|
|
void Clear()
|
||
|
|
{
|
||
|
|
while ( Count() > 0 )
|
||
|
|
{
|
||
|
|
T *pLink = Pop();
|
||
|
|
delete pLink;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
unsigned Count() const { return _cEntries; }
|
||
|
|
|
||
|
|
private:
|
||
|
|
|
||
|
|
unsigned _cEntries;
|
||
|
|
|
||
|
|
};
|
||
|
|
|
||
|
|
template <class T, class TList>
|
||
|
|
class TFwdListIter : public CForwardIter
|
||
|
|
{
|
||
|
|
|
||
|
|
public:
|
||
|
|
|
||
|
|
TFwdListIter ( TList & list ) : CForwardIter(list) {}
|
||
|
|
|
||
|
|
T* operator->() { return (T*) _pLinkCur; }
|
||
|
|
T* GetEntry() { return (T*) _pLinkCur; }
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
template <class T, class TList>
|
||
|
|
class TBackListIter : public CBackwardIter
|
||
|
|
{
|
||
|
|
|
||
|
|
public:
|
||
|
|
|
||
|
|
TBackListIter ( TList & list ) : CBackwardIter(list) {}
|
||
|
|
|
||
|
|
T* operator->() { return (T*) _pLinkCur; }
|
||
|
|
T* GetEntry() { return (T*) _pLinkCur; }
|
||
|
|
};
|
||
|
|
|