home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / SLBASE.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  11KB  |  401 lines

  1. /****************************************************************************
  2.     $Id: slbase.cpp 501.0 1995/03/07 12:26:20 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.     Implementation of class TLSLBase.
  10.  
  11.     $Log: slbase.cpp $
  12.     Revision 501.0  1995/03/07 12:26:20  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.7  1995/01/31 16:30:24  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.6  1995/01/06  15:58:17  ron
  18.     Corrected Revision keyword
  19.  
  20.     Revision 1.5  1994/11/16  15:42:53  ron
  21.     Added module info; rearranged #include directives
  22.  
  23.     Revision 1.4  1994/09/28  14:21:31  ron
  24.     Removed Macintosh-style #include references
  25.  
  26.     Revision 1.3  1994/09/27  20:22:56  ron
  27.     Changed path separator from / to \
  28.  
  29.     Revision 1.2  1994/09/26  15:47:15  ron
  30.     Changed include file references
  31.  
  32.     Revision 1.1  1994/08/16  18:13:12  ron
  33.     Initial revision
  34.  
  35. ****************************************************************************/
  36.  
  37. #include <tlx\501\_build.h>
  38.  
  39. TLX_MODULE_INFO("$Revision: 501.0 $");
  40.  
  41. #include <tlx\501\except.h>        // Exception handling
  42. #include <tlx\501\slists.h>        // Class declaration
  43.  
  44. /*-------------------------------------------------------------------------*/
  45.     TLSLBase::TLSLBase(bool aOwner)
  46.  
  47. /*  Constructor, also doubles as default constructor. Creates an empty list.
  48. ---------------------------------------------------------------------------*/
  49. : mHead(0), mTail(0), mCount(0), mOwner(aOwner)
  50. {
  51. }
  52.  
  53. /*-------------------------------------------------------------------------*/
  54.     TLSLBase::TLSLBase(const TLSLBase &)
  55.  
  56. /*  Copy constructor, does not copy the other list.
  57. ---------------------------------------------------------------------------*/
  58. : mHead(0), mTail(0), mCount(0), mOwner(false)
  59. {
  60. }
  61.  
  62. /*-------------------------------------------------------------------------*/
  63.     TLSLBase::~TLSLBase()
  64.  
  65. /*  Destructor. If the list is woner of its elements at the time of
  66.     destruction, it deletes all its elements.
  67. ---------------------------------------------------------------------------*/
  68. {
  69.     if (mOwner) CleanUp();
  70. }
  71.  
  72. /*-------------------------------------------------------------------------*/
  73.     void TLSLBase::Append(TLSLink *aLink)
  74.  
  75. /*  Adds an element at the end of the list. The element pointer must be
  76.     nonzero, and the element must not currently be part of a list.
  77. ---------------------------------------------------------------------------*/
  78. {
  79.     TLX_ASSERT_PTR(aLink);
  80.     TLX_ASSERT_NULL(aLink->mNext);
  81.  
  82.     if (mTail)
  83.     mTail->Append(aLink);
  84.     else
  85.     mHead = aLink;
  86.  
  87.     mTail = aLink;
  88.     mCount++;
  89. }
  90.  
  91. /*-------------------------------------------------------------------------*/
  92.     void TLSLBase::Append(TLSLink *aLink, TLSLink *aPos)
  93.  
  94. /*  Inserts a link after another link in the list. The link to insert
  95.     must not currently be part of a list.
  96. ---------------------------------------------------------------------------*/
  97. {
  98.     TLX_ASSERT_PTR(aLink);
  99.     TLX_ASSERT_PTR(aPos);
  100.     TLX_ASSERT_NULL(aLink->mNext);
  101.     TLX_ASSERT(Contains(aPos));
  102.  
  103.     aPos->Append(aLink);
  104.     if (aPos == mTail)
  105.         mTail = aLink;
  106.     mCount++;
  107. }
  108.  
  109. /*-------------------------------------------------------------------------*/
  110.     bool TLSLBase::BecomeOwner(bool aOwner)
  111.  
  112. /*  Changes the owner status, returning the previous status.
  113. ---------------------------------------------------------------------------*/
  114. {
  115.     bool oldstat = mOwner;
  116.     mOwner = aOwner;
  117.     return oldstat;
  118. }
  119.  
  120. /*-------------------------------------------------------------------------*/
  121.     void TLSLBase::CleanUp()
  122.  
  123. /*  Deletes all elements in the list. The list should be owner for this
  124.     function to be called.
  125. ---------------------------------------------------------------------------*/
  126. {
  127.     TLX_ASSERT(mOwner);
  128.  
  129.     TLSLink *rover = mHead;
  130.     while (rover)
  131.     {
  132.     TLSLink *tmp = rover;
  133.     rover = rover->Next();
  134.     tmp->Unlink();
  135.     delete tmp;
  136.     }
  137. }
  138.  
  139. /*-------------------------------------------------------------------------*/
  140.     void TLSLBase::Concat(TLSLink *aList)
  141.  
  142. /*  Appends another list to the current one. This function differs from
  143.     Append() in that Append() assumes the addition of a single element.
  144. ---------------------------------------------------------------------------*/
  145. {
  146.     TLX_ASSERT_PTR(aList);
  147.  
  148.     if (mTail)
  149.     mTail->Append(aList);
  150.     else
  151.     mHead = aList;
  152.  
  153.     // Find end of new list, counting additional elements as we go
  154.     mTail = aList;
  155.     while (mTail)
  156.     {
  157.     ++mCount;
  158.     mTail = mTail->mNext;
  159.     }
  160. }
  161.  
  162. /*-------------------------------------------------------------------------*/
  163.     void TLSLBase::Concat(TLSLBase &aList)
  164.  
  165. /*  Takes over another list in its entirety. The new list is added at the
  166.     end of the current list; the original list is then made empty.
  167. ---------------------------------------------------------------------------*/
  168. {
  169.     TLX_ASSERT(this != &aList);
  170.     TLX_ASSERT(aList.mCount > 0 || (aList.mHead == 0 && aList.mTail == 0));
  171.  
  172.     if (aList.mHead)
  173.     {
  174.     Concat(aList.mHead);
  175.     aList.mHead  =
  176.     aList.mTail  = 0;
  177.     aList.mCount = 0;
  178.     }
  179. }
  180.  
  181. /*-------------------------------------------------------------------------*/
  182.     bool TLSLBase::Contains(TLSLink *aLink) const
  183.  
  184. /*  Tests whether a given element appears in the list. The function performs
  185.     a linear search.
  186. ---------------------------------------------------------------------------*/
  187. {
  188.     if (!aLink) return false;
  189.  
  190.     for (TLSLink *rover = mHead; rover; rover = rover->Next())
  191.     if (rover == aLink)
  192.         return true;
  193.  
  194.     return false;
  195. }
  196.  
  197. /*-------------------------------------------------------------------------*/
  198.     TLSLink *TLSLBase::Extract(TLSLink *aLink)
  199.  
  200. /*  Removes and returns a specific link from the list.
  201. ---------------------------------------------------------------------------*/
  202. {
  203.     TLX_ASSERT_PTR(aLink);
  204.     TLX_ASSERT(Contains(aLink));
  205.  
  206.     if (aLink == mTail)
  207.     {
  208.     TLX_ASSERT_NULL(aLink->Next());
  209.  
  210.     if (aLink == mHead)        // Single element list
  211.         mTail = 0;
  212.     else
  213.     {
  214.         // Find the link preceding the one now being removed
  215.         TLSLink *rover;
  216.         for (rover = mHead; rover && rover->Next() != aLink;
  217.          rover = rover->Next())
  218.         ;
  219.         if (rover)
  220.         {
  221.         TLX_ASSERT(rover->Next() == aLink);
  222.         mTail = rover;
  223.         }
  224.     }
  225.     }
  226.  
  227.     if (aLink == mHead)
  228.         mHead = aLink->Next();
  229.  
  230.     aLink->Unlink();
  231.     TLX_ASSERT(mCount > 0);
  232.     mCount--;
  233.  
  234.     return aLink;
  235. }
  236.  
  237. /*-------------------------------------------------------------------------*/
  238.     TLSLink *TLSLBase::ExtractHead()
  239.  
  240. /*  Removes and returns the first element of the list.
  241. ---------------------------------------------------------------------------*/
  242. {
  243.     if (IsEmpty())
  244.     THROW(TLXEmpty(LOCUS));
  245.  
  246.     TLX_ASSERT_PTR(mHead);
  247.     return Extract(mHead);
  248. }
  249.  
  250. /*-------------------------------------------------------------------------*/
  251.     TLSLink *TLSLBase::ExtractTail()
  252.  
  253. /*  Removes and returns the last element of the list.
  254. ---------------------------------------------------------------------------*/
  255. {
  256.     if (IsEmpty())
  257.     THROW(TLXEmpty(LOCUS));
  258.  
  259.     TLX_ASSERT_PTR(mTail);
  260.     return Extract(mTail);
  261. }
  262.  
  263. /*-------------------------------------------------------------------------*/
  264.     bool TLSLBase::IsEmpty() const
  265.  
  266. /*  Checks if the list is currently empty, returning nonzero if it is.
  267. ---------------------------------------------------------------------------*/
  268. {
  269.     TLX_ASSERT(mCount > 0 || (mHead == 0 && mTail == 0));
  270.     return mCount == 0;
  271. }
  272.  
  273. /*-------------------------------------------------------------------------*/
  274.     TLSLBase &TLSLBase::operator =(const TLSLBase &)
  275.  
  276. /*  Assignment operator, does not copy anything.
  277. ---------------------------------------------------------------------------*/
  278. {
  279.     return *this;
  280. }
  281.  
  282. /*-------------------------------------------------------------------------*/
  283.     void TLSLBase::Prepend(TLSLink *aLink)
  284.  
  285. /*  Adds a new link at the start of the current list. The new link should
  286.     not be 0 and not be part of a list yet.
  287. ---------------------------------------------------------------------------*/
  288. {
  289.     TLX_ASSERT_PTR(aLink);
  290.     TLX_ASSERT_NULL(aLink->mNext);
  291.  
  292.     if (mHead)
  293.     aLink->Append(mHead);
  294.     else
  295.     mTail = aLink;
  296.  
  297.     mHead = aLink;
  298.     mCount++;
  299. }
  300.  
  301. /*-------------------------------------------------------------------------*/
  302.     void TLSLBase::Prepend(TLSLink *aLink, TLSLink *aPos)
  303.  
  304. /*  Inserts a link before another one. The link to insert should not
  305.     be 0 and not be part of a list yet.
  306. ---------------------------------------------------------------------------*/
  307. {
  308.     TLX_ASSERT_PTR(aLink);
  309.     TLX_ASSERT_PTR(aPos);
  310.     TLX_ASSERT_NULL(aLink->mNext);
  311.     TLX_ASSERT(Contains(aPos));
  312.  
  313.     if (aPos == mHead)
  314.     {
  315.     aLink->Append(mHead);
  316.     mHead = aLink;
  317.     }
  318.     else
  319.     {
  320.         // Find the element preceding 'aPos'
  321.     TLSLink *rover;
  322.     for (rover = mHead; rover && rover->Next() != aPos;
  323.          rover = rover->Next())
  324.         ;
  325.     if (rover)
  326.     {
  327.         TLX_ASSERT(rover->Next() == aPos);
  328.         rover->Append(aLink);
  329.         aLink->Append(aPos);
  330.     }
  331.     }
  332.     mCount++;
  333. }
  334.  
  335. /*-------------------------------------------------------------------------*/
  336.     void TLSLBase::RemoveAll()
  337.  
  338. /*  Removes all elements from the list. If the list owns its items, they
  339.     are deleted; else they are simply forgotten.
  340. ---------------------------------------------------------------------------*/
  341. {
  342.     if (mOwner) CleanUp();
  343.     mHead = mTail = 0;
  344.     mCount = 0;
  345. }
  346.  
  347. /*-------------------------------------------------------------------------*/
  348.     TLSLink *TLSLBase::Replace(TLSLink *aPos, TLSLink *aLink)
  349.  
  350. /*  Replaces one link by another, returning the original link.
  351. ---------------------------------------------------------------------------*/
  352. {
  353.     TLX_ASSERT_PTR(aPos);
  354.     TLX_ASSERT_PTR(aLink);
  355.     TLX_ASSERT(Contains(aPos));
  356.  
  357.     // Insert the new link (before or after the original one), then remove
  358.     // and return the original link.
  359.  
  360.     Append(aLink, aPos);
  361.     return Extract(aPos);
  362. }
  363.  
  364. /*-------------------------------------------------------------------------*/
  365.     TLSLink *TLSLBase::Split(TLSLink *aLink)
  366.  
  367. /*  Splits the list in two at the indicated position. The indicated link
  368.     will become the head of the new list.
  369. ---------------------------------------------------------------------------*/
  370. {
  371.     TLX_ASSERT_PTR(aLink);
  372.     TLX_ASSERT(Contains(aLink));
  373.  
  374.     if (mHead == aLink)
  375.     mHead = 0;
  376.     else
  377.     {
  378.         // Find the element preceding 'aLink'
  379.     TLSLink *rover;
  380.     for (rover = mHead; rover && rover->Next() != aLink;
  381.          rover = rover->Next())
  382.         ;
  383.     if (rover)
  384.     {
  385.         TLX_ASSERT(rover->Next() == aLink);
  386.         rover->Unlink();
  387.     }
  388.     }
  389.  
  390.     // Recount remaining elements
  391.     mCount = 0;
  392.     mTail  = mHead;
  393.     while (mTail)
  394.     {
  395.     ++mCount;
  396.     mTail = mTail->mNext;
  397.     }
  398.     return aLink;
  399. }
  400.  
  401.