diff options
Diffstat (limited to 'public/sdk/inc/dlink.hxx')
| -rw-r--r-- | public/sdk/inc/dlink.hxx | 349 |
1 files changed, 349 insertions, 0 deletions
diff --git a/public/sdk/inc/dlink.hxx b/public/sdk/inc/dlink.hxx new file mode 100644 index 000000000..f239d990c --- /dev/null +++ b/public/sdk/inc/dlink.hxx @@ -0,0 +1,349 @@ +#if !defined __DLINK_HXX__ +#define __DLINK_HXX__ +//+--------------------------------------------------------------------------- +// +// File: DLINK.HXX +// +// Contents: Parametrized doubly linked list and iterators +// +// History: 15-Jun-92 BartoszM Created. +// +//---------------------------------------------------------------------------- + +//+--------------------------------------------------------------------------- +// +// 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; + } + +protected: + + CDoubleLink* _next; + CDoubleLink* _prev; +}; + +//+--------------------------------------------------------------------------- +// +// Class: CDoubleList +// +// Purpose: Linked list of indexes +// +// History: 15-Jun-92 BartoszM Created. +// 15-Dec-94 SuChang Added _End() routine +// +// 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) {} + CDoubleLink* _pLinkCur; + }; + + + CDoubleList() + { + _root.Close(); + } + + BOOL IsEmpty() const { return _root.IsSingle(); } + + void Advance ( CDoubleIter& it ); + + void BackUp ( CDoubleIter& it ); + + BOOL AtEnd ( CDoubleIter& it); + + // In derived class you can add your own Pop(), Top(), etc. + // that will cast the results of _Pop(), _Top(), etc... + +protected: + + CDoubleLink* _Top() { return IsEmpty()? 0: _root.Next(); } + CDoubleLink* _End() { return IsEmpty()? 0: _root.Prev(); } + + BOOL _IsRoot ( CDoubleLink* pLink ) const + { return pLink == &_root; } + + void _Push ( CDoubleLink* pLink ); + + void _Queue ( CDoubleLink* pLink ); + + CDoubleLink* _Pop ( void ); + + 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; +} + +#endif |