home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / DLISTS.H < prev    next >
C/C++ Source or Header  |  1996-01-05  |  12KB  |  388 lines
  1. /****************************************************************************
  2.     $Id: dlists.h 501.0 1995/03/07 12:26:42 RON Exp $
  3.  
  4.     Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
  5.  
  6.     Project:    Tarma Library for C++ V5.0
  7.     Author:    Ron van der Wal
  8.  
  9.     All lists in this file are doubly linked lists, based on TLDLink
  10.     elements. The file also contains templates for lists based on classes
  11.     derived from class TLDLink.
  12.  
  13.     TLDLink        - element in doubly linked lists
  14.     TLDLBase        - linear list of Links
  15.     TLDLCBase        - circular list of Links
  16.     TLDLQueueBase     - queue based on a linked list
  17.     TLDLStackBase     - stack based on a linked list
  18.  
  19.     TLDList<T>        - template for TLDLBase
  20.     TLDLCList<T>      - template for TLDLCBase
  21.     TLDLQueue<T>      - template for TLDLQueueBase
  22.     TLDLStack<T>      - template for TLDLStackBase
  23.  
  24.     $Log: dlists.h $
  25.     Revision 501.0  1995/03/07 12:26:42  RON
  26.     Updated for TLX 5.01
  27.     Revision 1.6  1995/01/31 16:29:20  RON
  28.     Update for release 012
  29.     Added partial support for SunPro C++ compiler
  30.     Revision 1.5  1994/09/28  14:26:43  ron
  31.     Removed Macintosh-style #include references
  32.  
  33.     Revision 1.4  1994/09/27  20:25:03  ron
  34.     Changed path separator from / to \
  35.  
  36.     Revision 1.3  1994/09/26  15:17:39  ron
  37.     Changed include file references
  38.  
  39.     Revision 1.2  1994/09/06  13:58:09  ron
  40.     Adapted to changes in tlx.h
  41.  
  42.     Revision 1.1  1994/08/16  18:06:46  ron
  43.     Initial revision
  44.  
  45. ****************************************************************************/
  46.  
  47. #ifndef _TLX_DLISTS_H
  48. #define _TLX_DLISTS_H
  49.  
  50. #ifndef _TLX_TLX_H
  51. #include <tlx\501\tlx.h>
  52. #endif
  53.  
  54. /*---------------------------------------------------------------------------
  55.     TLDLink -
  56.  
  57.     Base class for all classes that may be stored in a doubly linked list.
  58.     It contains forward and backwards pointers.
  59. ---------------------------------------------------------------------------*/
  60.  
  61. class _TLXCLASS TLDLink
  62. {
  63.     friend class _TLXCLASS TLDLBase;
  64.     friend class _TLXCLASS TLDLCBase;
  65.  
  66.     TLDLink *        mNext;        // Forward pointer
  67.     TLDLink *        mPrev;        // Backward pointer
  68.  
  69. public:
  70.     virtual ~TLDLink();
  71.  
  72.     // Functions to traverse through lists of DLinks.
  73.  
  74.     TLDLink *        Next() const { return mNext; }
  75.     TLDLink *        Prev() const { return mPrev; }
  76.     bool         IsLast() const { return mNext == 0; }
  77.  
  78. protected:
  79.     // Constructors and destructor are only for use by derived classes;
  80.     // copy constructor does *not* copy the link fields.
  81.  
  82.     TLDLink();
  83.     TLDLink(const TLDLink &);
  84.  
  85.     // Assignment operator does *not* copy the link fields.
  86.  
  87.     TLDLink &        operator =(const TLDLink &);
  88.  
  89. private:
  90.     // Helper functions for use by list classes.
  91.  
  92.     void        Append(TLDLink *);
  93.     void        Prepend(TLDLink *);
  94.     void        Unlink();
  95. };
  96.  
  97. /*---------------------------------------------------------------------------
  98.     TLDLBase -
  99.  
  100.     Manages linear doubly linked lists based on TLDLinks. It serves as a base
  101.     class for other list classes.
  102. ---------------------------------------------------------------------------*/
  103.  
  104. class _TLXCLASS TLDLBase
  105. {
  106.     TLDLink *        mHead;        // First element in the list
  107.     TLDLink *        mTail;        // Last element in the list
  108.     size_t        mCount;        // Number of elements
  109.  
  110.     // If the list manager is owner of the elements stored in the list,
  111.     // the elements will be deleted when the list manager itself is
  112.     // destroyed. The owner status may be changed by everyone.
  113.  
  114.     bool         mOwner;        // If nonzero, elements are discarded
  115.  
  116. public:
  117.     // Constructor creates an empty list and sets owner status. Destructor
  118.     // optionally deletes elements.
  119.  
  120.     TLDLBase(bool = false);
  121.     virtual ~TLDLBase();
  122.  
  123.     bool         IsOwner() const { return mOwner; }
  124.     bool         BecomeOwner(bool = true);
  125.  
  126.     // Operations that insert or remove elements or sublists.
  127.  
  128.     void        Append(TLDLink *);
  129.     void        Append(TLDLink *, TLDLink *);
  130.     void        RemoveAll();
  131.     void        Concat(TLDLink *);
  132.     void        Concat(TLDLBase &);
  133.     void        Prepend(TLDLink *);
  134.     void        Prepend(TLDLink *, TLDLink *);
  135.     TLDLink *        Extract(TLDLink *);
  136.     TLDLink *        ExtractHead();
  137.     TLDLink *        ExtractTail();
  138.     TLDLink *        Replace(TLDLink *, TLDLink *);
  139.     TLDLink *        Split(TLDLink *);
  140.  
  141.     TLDLink *        PeekHead() const { return mHead; }
  142.     TLDLink *        PeekTail() const { return mTail; }
  143.     size_t        Count() const { return mCount; }
  144.     bool         IsEmpty() const;
  145.     bool         Contains(TLDLink *) const;
  146.  
  147. private:
  148.     // Copying and assignment are prohibited.
  149.  
  150.     TLDLBase(const TLDLBase &);
  151.     TLDLBase &        operator =(const TLDLBase &);
  152.  
  153.     // Implementation helper function.
  154.  
  155.     void        CleanUp();
  156. };
  157.  
  158. /*---------------------------------------------------------------------------
  159.     TLDLCBase -
  160.  
  161.     Manages a circular linked list consisting of TLDLink elements.
  162. ---------------------------------------------------------------------------*/
  163.  
  164. class _TLXCLASS TLDLCBase
  165. {
  166.     // In the circular list, we only store a pointer to the first element.
  167.  
  168.     TLDLink *        mHead;
  169.     size_t        mCount;
  170.  
  171.     // If the list manager is owner of the elements stored in the list,
  172.     // the elements will be deleted when the list manager itself is
  173.     // destroyed. The owner status may be changed by everyone.
  174.  
  175.     bool         mOwner;
  176.  
  177. public:
  178.     // Constructor creates an empty list and sets owner status. Destructor
  179.     // optionally deletes elements.
  180.  
  181.     TLDLCBase(bool = false);
  182.     virtual ~TLDLCBase();
  183.  
  184.     bool         IsOwner() const { return mOwner; }
  185.     bool         BecomeOwner(bool = true);
  186.  
  187.     // Operations that insert or remove elements or sublists.
  188.  
  189.     void        Append(TLDLink *);
  190.     void        Append(TLDLink *, TLDLink *);
  191.     void        Prepend(TLDLink *);
  192.     void        Prepend(TLDLink *, TLDLink *);
  193.     TLDLink *        Extract(TLDLink *);
  194.     TLDLink *        ExtractHead();
  195.     TLDLink *        ExtractTail();
  196.     void        RemoveAll();
  197.  
  198.     TLDLink *        PeekHead() const { return mHead; }
  199.     TLDLink *        PeekTail() const { return mHead ? mHead->mPrev : 0; }
  200.     size_t        Count() const { return mCount; }
  201.     bool         IsEmpty() const;
  202.     bool         Contains(TLDLink *) const;
  203.  
  204. private:
  205.     // Copying and assignment are prohibited.
  206.  
  207.     TLDLCBase(const TLDLCBase &);
  208.     TLDLCBase &        operator =(const TLDLCBase &);
  209.  
  210.     // Implementation helper function.
  211.  
  212.     void        CleanUp();
  213. };
  214.  
  215. /*---------------------------------------------------------------------------
  216.     TLDLQueueBase -
  217.  
  218.     Represents a queue based on a doubly-linked list. TLDLQueueBase is
  219.     an intrusive queue.
  220. ---------------------------------------------------------------------------*/
  221.  
  222. class _TLXCLASS TLDLQueueBase: private TLDLBase
  223. {
  224. public:
  225.     TLDLQueueBase(bool = false);
  226.  
  227.     void        Enqueue(TLDLink *aLink) { Append(aLink); }
  228.     TLDLink *        Dequeue() { return ExtractHead(); }
  229.  
  230.     TLDLBase::IsOwner;
  231.     TLDLBase::RemoveAll;
  232.     TLDLBase::Count;
  233.     TLDLBase::IsEmpty;
  234.     TLDLBase::PeekHead;
  235.     TLDLBase::PeekTail;
  236. };
  237.  
  238. /*---------------------------------------------------------------------------
  239.     TLDLStackBase -
  240.  
  241.     Represents a stack based on a doubly-linked list. TLDLStackBase is
  242.     an intrusive stack.
  243. ---------------------------------------------------------------------------*/
  244.  
  245. class _TLXCLASS TLDLStackBase: private TLDLBase
  246. {
  247. public:
  248.     TLDLStackBase(bool = false);
  249.  
  250.     void        Push(TLDLink *aLink) { Prepend(aLink); }
  251.     TLDLink *        Pop() { return ExtractHead(); }
  252.     TLDLink *        PeekTop() const { return PeekHead(); }
  253.  
  254.     TLDLBase::IsOwner;
  255.     TLDLBase::RemoveAll;
  256.     TLDLBase::Count;
  257.     TLDLBase::IsEmpty;
  258. };
  259.  
  260. /*---------------------------------------------------------------------------
  261.     TLDList<T> -
  262.  
  263.     This class is a template for a type-safe derivation of TLDLBase for
  264.     classes T that are derived from TLDLink. TLDList<T> is an intrusive
  265.     list for items of type T.
  266. ---------------------------------------------------------------------------*/
  267.  
  268. template<class T> class TLDList: private TLDLBase
  269. {
  270. public:
  271.     TLDList(bool = false);
  272.  
  273.     TLDList<T> &    operator =(const TLDList<T> &) { return  *this; }
  274.  
  275.     void        Append(T *aLink) { TLDLBase::Append(aLink); }
  276.     void        Append(T *aLink, T *aPos)
  277.                 { TLDLBase::Append(aLink, aPos); }
  278.     void        Concat(T *aLink) { TLDLBase::Concat(aLink); }
  279.     void        Concat(TLDList<T> &aList) { TLDLBase::Concat(aList); }
  280.     void        Prepend(T *aLink) { TLDLBase::Prepend(aLink); }
  281.     void        Prepend(T *aLink, T *aPos)
  282.                 { TLDLBase::Prepend(aLink, aPos); }
  283.     T *            ExtractHead() { return (T *) TLDLBase::ExtractHead(); }
  284.     T *            ExtractTail() { return (T *) TLDLBase::ExtractTail(); }
  285.     T *            Extract(T *aLink)
  286.                 { return (T *) TLDLBase::Extract(aLink); }
  287.     T *            Replace(T *aPos, T *aLink)
  288.                 { return (T *) TLDLBase::Replace(aPos, aLink); }
  289.     T *            Split(T *aLink) { return (T *) TLDLBase::Split(aLink); }
  290.  
  291.     T *            PeekHead() const { return (T *) TLDLBase::PeekHead(); }
  292.     T *            PeekTail() const { return (T *) TLDLBase::PeekTail(); }
  293.     bool         Contains(T *t) const { return TLDLBase::Contains(t); }
  294.  
  295.     TLDLBase::IsOwner;
  296.     TLDLBase::RemoveAll;
  297.     TLDLBase::Count;
  298.     TLDLBase::IsEmpty;
  299. };
  300.  
  301. /*---------------------------------------------------------------------------
  302.     TLDLCList<T> -
  303.  
  304.     A template for a type-safe derivation of TLDLCBase for classes T that
  305.     are derived from TLDLink. TLDLCList<T> is an intrusive list for items of
  306.     type T.
  307. ---------------------------------------------------------------------------*/
  308.  
  309. template<class T> class TLDLCList: private TLDLCBase
  310. {
  311. public:
  312.     TLDLCList(bool = false);
  313.  
  314.     TLDLCList<T> &    operator =(const TLDLCList<T> &) { return *this; }
  315.  
  316.     void        Append(T *aLink) { TLDLCBase::Append(aLink); }
  317.     void        Append(T *aLink, T *aPos)
  318.                 { TLDLCBase::Append(aLink, aPos); }
  319.     void        Prepend(T *aLink) { TLDLCBase::Prepend(aLink); }
  320.     void        Prepend(T *aLink, T *aPos)
  321.                 { TLDLCBase::Prepend(aLink, aPos); }
  322.     T *            ExtractHead() { return (T *) TLDLCBase::ExtractHead(); }
  323.     T *            ExtractTail() { return (T *) TLDLCBase::ExtractTail(); }
  324.     T *            Extract(T *aLink)
  325.                 { return (T *) TLDLCBase::Extract(aLink); }
  326.  
  327.     T *            PeekHead() const { return (T *) TLDLCBase::PeekHead(); }
  328.     T *            PeekTail() const { return (T *) TLDLCBase::PeekTail(); }
  329.  
  330.     TLDLCBase::IsOwner;
  331.     TLDLCBase::RemoveAll;
  332.     TLDLCBase::Count;
  333.     TLDLCBase::IsEmpty;
  334. };
  335.  
  336. /*---------------------------------------------------------------------------
  337.     TLDLQueue<T> -
  338.  
  339.     A template for a type-safe derivation of TLDLQueueBase for classes T that
  340.     are derived from TLDLink. TLDLQueue<T> is an intrusive queue for items of
  341.     type T.
  342. ---------------------------------------------------------------------------*/
  343.  
  344. template<class T> class TLDLQueue: private TLDLQueueBase
  345. {
  346. public:
  347.     TLDLQueue(bool = false);
  348.  
  349.     void        Enqueue(T *aLink) { TLDLQueueBase::Enqueue(aLink); }
  350.     T *            Dequeue() { return (T *) TLDLQueueBase::Dequeue(); }
  351.  
  352.     T *            PeekHead() const
  353.                     { return (T *) TLDLQueueBase::PeekHead(); }
  354.     T *            PeekTail() const
  355.                     { return (T *) TLDLQueueBase::PeekTail(); }
  356.  
  357.     TLDLQueueBase::IsOwner;
  358.     TLDLQueueBase::RemoveAll;
  359.     TLDLQueueBase::Count;
  360.     TLDLQueueBase::IsEmpty;
  361. };
  362.  
  363. /*---------------------------------------------------------------------------
  364.     TLDLStack<T> -
  365.  
  366.     A template for a type-safe derivation of TLDLStackBase for classes T that
  367.     are derived from TLDLink. TLDLStack<T> is an intrusive stack for items of
  368.     type T.
  369. ---------------------------------------------------------------------------*/
  370.  
  371. template<class T> class TLDLStack: private TLDLStackBase
  372. {
  373. public:
  374.     TLDLStack(bool = false);
  375.  
  376.     void        Push(T *aLink) { TLDLStackBase::Push(aLink); }
  377.     T *            Pop() { return (T *) TLDLStackBase::Pop(); }
  378.     T *            PeekTop() const
  379.                     { return (T *) TLDLStackBase::PeekTop(); }
  380.  
  381.     TLDLStackBase::IsOwner;
  382.     TLDLStackBase::RemoveAll;
  383.     TLDLStackBase::Count;
  384.     TLDLStackBase::IsEmpty;
  385. };
  386.  
  387. #endif    // _TLX_DLISTS_H
  388.