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