home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / VPSEQ.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  30KB  |  832 lines
  1. /****************************************************************************
  2.     $Id: vpseq.cpp 501.0 1995/03/07 12:26:28 RON Exp $
  3.  
  4.     Copyright (c) 1993-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 TLVPSeq.
  10.  
  11.     $Log: vpseq.cpp $
  12.     Revision 501.0  1995/03/07 12:26:28  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.8  1995/01/31 16:31:50  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.7  1995/01/06  15:58:53  ron
  18.     Corrected Revision keyword
  19.  
  20.     Revision 1.6  1994/11/16  15:46:02  ron
  21.     Added module info; rearranged #include directives
  22.  
  23.     Revision 1.5  1994/10/05  18:46:42  ron
  24.     Formatting changes
  25.  
  26.     Revision 1.4  1994/09/28  14:47:45  ron
  27.     Removed Macintosh-style #include references
  28.  
  29.     Revision 1.3  1994/09/27  20:23:30  ron
  30.     Changed path separator from / to \
  31.  
  32.     Revision 1.2  1994/09/26  15:51:33  ron
  33.     Renamed SetSize() to Resize()
  34.  
  35.     Revision 1.1  1994/08/16  18:13:23  ron
  36.     Initial revision
  37.  
  38. ****************************************************************************/
  39.  
  40. #include <tlx\501\_build.h>
  41.  
  42. TLX_MODULE_INFO("$Revision: 501.0 $");
  43.  
  44. #include <string.h>        // For memcpy(), memmove()
  45. #include <tlx\501\except.h>        // Exception handling
  46. #include <tlx\501\vparrays.h>    // Class declaration
  47.  
  48. /*-------------------------------------------------------------------------*/
  49.     TLVPSeq::TLVPSeq(
  50.         size_t         aSize,     // Initial capacity
  51.         size_t         aDelta    // Initial expansion factor
  52.     )
  53.  
  54. /*  Constructor, creates a sequence of specific initial capacity and
  55.     expansion factor. Also doubles as default constructor, creating
  56.     and empty and nonexpandable sequence.
  57. ---------------------------------------------------------------------------*/
  58. : mVector(aSize), mCount(0), mDelta(aDelta),
  59.   mCompare(TLVPVector::DefaultCompare)
  60. {
  61.     TLX_ASSERT(Size() == aSize);
  62. }
  63.  
  64. /*-------------------------------------------------------------------------*/
  65.     TLVPSeq::TLVPSeq(void *aPtr)
  66.  
  67. /*  Constructor, creating a single element sequence that is not expandable.
  68. ---------------------------------------------------------------------------*/
  69. : mVector(aPtr), mCount(1), mDelta(0), mCompare(TLVPVector::DefaultCompare)
  70. {
  71.     TLX_ASSERT(Size() == 1);
  72.     TLX_ASSERT(Size() == Count());
  73.     TLX_ASSERT(mVector.PeekAt(0) == aPtr);
  74.     mCount = Size();        // Security for our nondebugging version
  75. }
  76.  
  77. /*-------------------------------------------------------------------------*/
  78.     TLVPSeq::TLVPSeq(void **aVector, size_t aSize)
  79.  
  80. /*  Constructor creating a sequence that contains a copy of a C-style vector.
  81.     The sequence is not expandable.
  82. ---------------------------------------------------------------------------*/
  83. : mVector(aVector, aSize), mCount(aSize), mDelta(0),
  84.   mCompare(TLVPVector::DefaultCompare)
  85. {
  86.     TLX_ASSERT(Size() == aSize);
  87.     TLX_ASSERT(Size() == Count());
  88.     mCount = Size();        // Security for our nondebugging version
  89. }
  90.  
  91. /*-------------------------------------------------------------------------*/
  92.     TLVPSeq::TLVPSeq(const TLVPSeq &aSeq)
  93.  
  94. /*  Copy constructor. Creates a copy of another sequence.
  95. ---------------------------------------------------------------------------*/
  96. : mVector(aSeq.mVector), mCount(aSeq.mCount), mDelta(aSeq.mDelta),
  97.   mCompare(aSeq.mCompare)
  98. {
  99.     TLX_ASSERT(Size() == aSeq.Size());
  100.     TLX_ASSERT(Count() == aSeq.Count());
  101.     TLX_ASSERT(Delta() == aSeq.Delta());
  102. }
  103.  
  104. /*-------------------------------------------------------------------------*/
  105.     TLVPSeq::~TLVPSeq()
  106.  
  107. /*  Destructor. Not really necessary (the compiler generated version
  108.     would work as well because of the mVector destructor), but useful
  109.     to do a few extra checks and to set breakpoints at.
  110. ---------------------------------------------------------------------------*/
  111. {
  112.     TLX_ASSERT(Count() <= Size());
  113. }
  114.  
  115. /*-------------------------------------------------------------------------*/
  116.     void TLVPSeq::Append(void *aPtr)
  117.  
  118. /*  Adds a single element at the end of the sequence. If necessary and
  119.     allowed, the sequence is expanded.
  120. ---------------------------------------------------------------------------*/
  121. {
  122.     InsertAt(Maxi() + 1, aPtr);
  123.     TLX_ASSERT(PeekLast() == aPtr);
  124. }
  125.  
  126. /*-------------------------------------------------------------------------*/
  127.     void TLVPSeq::Append(void **aVector, size_t aSize)
  128.  
  129. /*  Adds a C-style vector at the end of the sequence. If necessary and
  130.     allowed, the sequence is expanded. It is an error to add the current
  131.     sequence to itself.
  132. ---------------------------------------------------------------------------*/
  133. {
  134.     TLX_ASSERT(aVector != mVector.StorageVector());
  135.     InsertAt(Maxi() + 1, aVector, aSize);
  136.     TLX_ASSERT(aSize == 0 || PeekLast() == aVector[aSize - 1]);
  137. }
  138.  
  139. /*-------------------------------------------------------------------------*/
  140.     void TLVPSeq::Append(const TLVPSeq &aSeq)
  141.  
  142. /*  Adds another sequence at the end of the sequence. If necessary and
  143.     allowed, the sequence is expanded. It is an error to add the current
  144.     sequence to itself.
  145. ---------------------------------------------------------------------------*/
  146. {
  147.     TLX_ASSERT(this != &aSeq);
  148.     InsertAt(Maxi() + 1, aSeq);
  149.     TLX_ASSERT(PeekLast() == aSeq.PeekLast());
  150. }
  151.  
  152. /*-------------------------------------------------------------------------*/
  153.     size_t TLVPSeq::Available() const
  154.  
  155. /*  Returns the amount of free space in the sequence, i.e. the difference
  156.     between the physical and the logical length.
  157. ---------------------------------------------------------------------------*/
  158. {
  159.     TLX_ASSERT(Count() <= Size());
  160.     return Size() - Count();
  161. }
  162.  
  163. /*-------------------------------------------------------------------------*/
  164.     bool TLVPSeq::Contains(const void *aPtr) const
  165.  
  166. /*  Checks for the presence of an element, returning nonzero if it appears
  167.     in the sequence.
  168. ---------------------------------------------------------------------------*/
  169. {
  170.     return IsValidIndex(IndexOf(aPtr));
  171. }
  172.  
  173. /*-------------------------------------------------------------------------*/
  174.     void TLVPSeq::Remove(void *aPtr)
  175.  
  176. /*  Removes the indicated pointer from the sequence, and deletes the
  177.     asociated object if we are the owner.
  178. ---------------------------------------------------------------------------*/
  179. {
  180.     void *vptr = Extract(aPtr);
  181.     if (IsOwner()) DeletePtr(vptr);
  182. }
  183.  
  184. /*-------------------------------------------------------------------------*/
  185.     void TLVPSeq::RemoveAll()
  186.  
  187. /*  Removes all elements from the sequence and set the contents of the
  188.     sequence to 0. If we are owner of the pointed to objects, they are
  189.     delete during the operation.
  190. ---------------------------------------------------------------------------*/
  191. {
  192.     // Removal comes down to setting the count to 0 and clearing the vector.
  193.     mVector.RemoveAll();
  194.     mCount = 0;
  195. }
  196.  
  197. /*-------------------------------------------------------------------------*/
  198.     void TLVPSeq::RemoveAt(index_t aIndex, size_t aCount)
  199.  
  200. /*  Removes a number of elements from the vector without returning them.
  201.     It is not an error to remove more elements than there are left in the
  202.     sequence; only the remainder is removed in that case.
  203.  
  204.     If we are the owner of the pointed to objects, they are deleted.
  205. ---------------------------------------------------------------------------*/
  206. {
  207.     if (!IsValidIndex(aIndex))
  208.     THROW(TLXIndex(LOCUS, aIndex));
  209.     while (aCount-- > 0 && IsValidIndex(aIndex)) {
  210.     void *vptr = Extract(aIndex);
  211.     if (IsOwner()) DeletePtr(vptr);
  212.     }
  213. }
  214.  
  215. /*-------------------------------------------------------------------------*/
  216.     void TLVPSeq::RemoveFirst(size_t aLength)
  217.  
  218. /*  Removes the first 'aLength' elements from the vector without returning
  219.     them. It is not an error to remove more elements than there are left in
  220.     the sequence; only the remainder is removed in that case.
  221.  
  222.     If we are the owner of the pointed to objects, they are deleted.
  223. ---------------------------------------------------------------------------*/
  224. {
  225.     if (IsEmpty())
  226.     THROW(TLXEmpty(LOCUS));
  227.     RemoveAt(Mini(), aLength);
  228. }
  229.  
  230. /*-------------------------------------------------------------------------*/
  231.     void TLVPSeq::RemoveLast(size_t aLength)
  232.  
  233. /*  Removes the last 'aLength' elements from the vector without returning
  234.     them. It is not an error to remove more elements than there are left in
  235.     the sequence; only the remainder is removed in that case.
  236.  
  237.     If we are the owner of the pointed to objects, they are deleted.
  238. ---------------------------------------------------------------------------*/
  239. {
  240.     if (IsEmpty())
  241.     THROW(TLXEmpty(LOCUS));
  242.     if (aLength > Count())
  243.     aLength = Count();
  244.     RemoveAt(Maxi() - aLength + 1, aLength);
  245. }
  246.  
  247. /*-------------------------------------------------------------------------*/
  248.     void *TLVPSeq::Extract(void *aPtr)
  249.  
  250. /*  Removes a single value from the sequence and returns that value.
  251. ---------------------------------------------------------------------------*/
  252. {
  253.     index_t i = IndexOf(aPtr);
  254.     if (!IsValidIndex(i))
  255.     THROW(TLXNotFound(LOCUS));
  256.     return Extract(i);
  257. }
  258.  
  259. /*-------------------------------------------------------------------------*/
  260.     void *TLVPSeq::Extract(index_t aIndex)
  261.  
  262. /*  Removes a single value from the sequence and returns that value.
  263. ---------------------------------------------------------------------------*/
  264. {
  265.     if (!IsValidIndex(aIndex))
  266.     THROW(TLXIndex(LOCUS, aIndex));
  267.     void *vPtr = PeekAt(aIndex);
  268.  
  269.     // Close the gap that is left by the element just removed
  270.     if (aIndex < Maxi())
  271.     memmove(&PeekAt(aIndex), &PeekAt(aIndex + 1),
  272.         (Maxi() - aIndex) * sizeof(void *));
  273.  
  274.     // Zero out the position that has been vacated
  275.     PeekAt(Maxi()) = 0;
  276.     TLX_ASSERT(Count() > 0);
  277.     mCount--;
  278.     return vPtr;
  279. }
  280.  
  281. /*-------------------------------------------------------------------------*/
  282.     TLVPSeq TLVPSeq::Extract(index_t aIndex, size_t aCount)
  283.  
  284. /*  Removes a number of pointers from the sequence and returns them
  285.     in another sequence. If the remaining length of the current sequence
  286.     is less than the requested number, only the remaining elements are
  287.     removed. This is not considered an error.
  288. ---------------------------------------------------------------------------*/
  289. {
  290.     if (!IsValidIndex(aIndex))
  291.     THROW(TLXIndex(LOCUS, aIndex));
  292.  
  293.     // Adjust number of items to remove, if necessary
  294.     if (aCount > (tSize)(Maxi() - aIndex + 1))
  295.         aCount = Maxi() - aIndex + 1;
  296.  
  297.     // Create a copy of the subsequence, then remove the elements
  298.     TLVPSeq vCopy(&PeekAt(aIndex), aCount);
  299.     TLX_ASSERT(aCount > 0);
  300.     TLX_ASSERT(aCount <= Count());
  301.  
  302.     // Close the gap that is left by the elements to be removed
  303.     if (aIndex < Maxi())
  304.     memmove(&PeekAt(aIndex), &PeekAt(aIndex + aCount),
  305.         (Maxi() - aIndex - aCount + 1) * sizeof(void *));
  306.  
  307.     // Zero out the positions that have been vacated
  308.     memset(&PeekAt(Maxi() - aCount + 1), 0, aCount * sizeof(void *));
  309.     mCount -= aCount;
  310.     return vCopy;
  311. }
  312.  
  313. /*-------------------------------------------------------------------------*/
  314.     void *TLVPSeq::ExtractFirst()
  315.  
  316. /*  Extracts and returns the first element of the sequence.
  317. ---------------------------------------------------------------------------*/
  318. {
  319.     if (IsEmpty())
  320.     THROW(TLXEmpty(LOCUS));
  321.     return Extract(Mini());
  322. }
  323.  
  324. /*-------------------------------------------------------------------------*/
  325.     TLVPSeq TLVPSeq::ExtractFirst(size_t aLength)
  326.  
  327. /*  Removes a number of pointers from the sequence and return them in
  328.     another sequence. If the remaining length of the current sequence
  329.     is less than the requested number, only the remaining elements are
  330.     removed. This is not considered an error.
  331. ---------------------------------------------------------------------------*/
  332. {
  333.     return Extract(Mini(), aLength);
  334. }
  335.  
  336. /*-------------------------------------------------------------------------*/
  337.     TLVPSeq TLVPSeq::ExtractLast(size_t aLength)
  338.  
  339. /*  Removes a number of pointers from the sequence and returns them
  340.     in another sequence. If the remaining length of the current sequence
  341.     is less than the requested number, only the remaining elements are
  342.     removed. This is not considered an error.
  343. ---------------------------------------------------------------------------*/
  344. {
  345.     if (aLength > Count())
  346.     aLength = Count();
  347.     return Extract(Maxi() - aLength + 1, aLength);
  348. }
  349.  
  350. /*-------------------------------------------------------------------------*/
  351.     void *TLVPSeq::ExtractLast()
  352.  
  353. /*  Extracts and returns the last element of the sequence.
  354. ---------------------------------------------------------------------------*/
  355. {
  356.     if (IsEmpty())
  357.     THROW(TLXEmpty(LOCUS));
  358.     return Extract(Maxi());
  359. }
  360.  
  361. /*-------------------------------------------------------------------------*/
  362.     index_t TLVPSeq::IndexOf(const void *aPtr) const
  363.  
  364. /*  Finds the position of a pointer in the sequence. The function performs
  365.     a linear search, and only finds the first occurrence of the pointer
  366.     value (if any). It returns the index of the pointer, or Maxi() + 1
  367.     if the pointer does not appear in the sequence.
  368. ---------------------------------------------------------------------------*/
  369. {
  370.     return mVector.IndexOf(aPtr) + 1;
  371. }
  372.  
  373. /*-------------------------------------------------------------------------*/
  374.     void TLVPSeq::Insert(void *aPtr)
  375.  
  376. /*  Inserts a new pointer value into the (sorted) sequence at the correct
  377.     position according to the comparison function.
  378. ---------------------------------------------------------------------------*/
  379. {
  380.     TLX_ASSERT_PTR(aPtr);
  381.     index_t aIndex;
  382.     Search(aPtr, aIndex);
  383.     InsertAt(aIndex, aPtr);
  384. }
  385.  
  386. /*-------------------------------------------------------------------------*/
  387.     void TLVPSeq::InsertAt(index_t aIndex, void *aPtr)
  388.  
  389. /*  Inserts a single pointer at the indicated position. The previous
  390.     element at that position and all subsequent ones are moved up
  391.     one position. If necessary, the physical vector is resized.
  392.  
  393.     Legal indices for the insertion point range from Mini() to Maxi() + 1;
  394.     in the latter case, the new element is added to the end of the sequence.
  395. ---------------------------------------------------------------------------*/
  396. {
  397.     InsertAt(aIndex, &aPtr, 1);
  398. }
  399.  
  400. /*-------------------------------------------------------------------------*/
  401.     void TLVPSeq::InsertAt(index_t aIndex, void **aVector, size_t aSize)
  402.  
  403. /*  Inserts a C-style vector at the indicated position. The previous
  404.     element at that position and all subsequent ones are moved up.
  405.     If necessary, the physical vector is resized.
  406.  
  407.     Legal indices for the insertion point range from Mini() to Maxi() + 1;
  408.     in the latter case, the new elements are added to the end of the
  409.     sequence.
  410. ---------------------------------------------------------------------------*/
  411. {
  412.     if (aIndex < Mini() || aIndex > Maxi() + 1)
  413.     THROW(TLXIndex(LOCUS, aIndex));
  414.  
  415.     // Check if we have enough room; if not, expand
  416.     if (Available() < aSize) {
  417.     if (IsFrozen())
  418.         THROW(TLXFull(LOCUS));
  419.  
  420.     // Increment the size in multiples of mDelta
  421.     mVector.ExpandBy(((aSize - Available()) % mDelta + 1) * mDelta);
  422.     }
  423.     TLX_ASSERT(Available() >= aSize);
  424.  
  425.     // Open up the gap for the new elements
  426.     if (aIndex <= Maxi())
  427.     memmove(&mVector.PeekAt(aIndex + aSize - 1),
  428.         &mVector.PeekAt(aIndex - 1),
  429.             (Maxi() - aIndex + 1) * sizeof(void *));
  430.  
  431.     // Copy the new elements to their positions
  432.     memcpy(&mVector.PeekAt(aIndex - 1), aVector, aSize * sizeof(void *));
  433.     mCount += aSize;
  434.     TLX_ASSERT(Count() <= Size());
  435. }
  436.  
  437. /*-------------------------------------------------------------------------*/
  438.     void TLVPSeq::InsertAt(index_t aIndex, const TLVPSeq &aSeq)
  439.  
  440. /*  Inserts another sequence at the indicated position. The previous
  441.     element at that position and all subsequent ones are moved up.
  442.     If necessary, the physical vector is resized.
  443.  
  444.     It is an error to insert the current sequence in itself.
  445.  
  446.     Legal indices for the insertion point range from Mini() to Maxi() + 1;
  447.     in the latter case, the sequence is added to the end of the current
  448.     sequence.
  449. ---------------------------------------------------------------------------*/
  450. {
  451.     if (this != &aSeq)
  452.         InsertAt(aIndex, aSeq.mVector.StorageVector(), aSeq.Count());
  453. }
  454.  
  455. /*-------------------------------------------------------------------------*/
  456.     bool TLVPSeq::IsValidIndex(index_t aIndex) const
  457.  
  458. /*  Tests whether a particular index is valid for the sequence in its
  459.     current configuration, returning nonzero if it is.
  460. ---------------------------------------------------------------------------*/
  461. {
  462.     return (aIndex >= Mini() && aIndex <= Maxi());
  463. }
  464.  
  465. /*-------------------------------------------------------------------------*/
  466.     void *&TLVPSeq::operator [](index_t aIndex)
  467.  
  468. /*  Returns a reference to the aIndex-th element in the sequence. The
  469.     index is range checked, and an TLXIndex exception is thrown if it is
  470.     out of range.
  471. ---------------------------------------------------------------------------*/
  472. {
  473.     if (!IsValidIndex(aIndex))
  474.     THROW(TLXIndex(LOCUS, aIndex));
  475.     return PeekAt(aIndex);
  476. }
  477.  
  478. /*-------------------------------------------------------------------------*/
  479.     void *TLVPSeq::operator [](index_t aIndex) const
  480.  
  481. /*  Returns the value of the aIndex-th element in the sequence. The
  482.     index is range checked, and an TLXIndex exception is thrown if it is
  483.     out of range.
  484. ---------------------------------------------------------------------------*/
  485. {
  486.     if (!IsValidIndex(aIndex))
  487.     THROW(TLXIndex(LOCUS, aIndex));
  488.     return PeekAt(aIndex);
  489. }
  490.  
  491. /*-------------------------------------------------------------------------*/
  492.     TLVPSeq &TLVPSeq::operator =(const TLVPSeq &aSeq)
  493.  
  494. /*  Overloading of assignment operator for class TLVPSeq. The overloading
  495.     is not really necessary (the compiler generated version would work as
  496.     well), but is useful for extra tests and breakpoints.
  497. ---------------------------------------------------------------------------*/
  498. {
  499.     if (this != &aSeq) {
  500.     mVector = aSeq.mVector;
  501.     mCount  = aSeq.mCount;
  502.     mDelta  = aSeq.mDelta;
  503.     }
  504.     return *this;
  505. }
  506.  
  507. /*-------------------------------------------------------------------------*/
  508.     TLVPSeq &TLVPSeq::operator =(void *aPtr)
  509.  
  510. /*  Overloading of assignment operator that allows a single pointer to be
  511.     assigned to the sequence. The sequence consists of a single element
  512.     afterwards.
  513.  
  514.     NOTE: If the current sequence has currently a physical size of zero
  515.     and is not allowed to expand, this function fails.
  516. ---------------------------------------------------------------------------*/
  517. {
  518.     RemoveAll();
  519.     Append(aPtr);
  520.     TLX_ASSERT(Size() == 1);
  521.     TLX_ASSERT(PeekAt(1) == aPtr);
  522.     return *this;
  523. }
  524.  
  525. /*-------------------------------------------------------------------------*/
  526.     void *&TLVPSeq::PeekAt(index_t aIndex)
  527.  
  528. /*  Returns a reference to the aIndex-th pointer in the sequence. There is
  529.     no range checking.
  530. ---------------------------------------------------------------------------*/
  531. {
  532.     TLX_ASSERT(aIndex >= Mini());
  533.     TLX_ASSERT(aIndex <= Maxi());
  534.     return mVector.PeekAt(aIndex - 1);
  535. }
  536.  
  537. /*-------------------------------------------------------------------------*/
  538.     void *TLVPSeq::PeekAt(index_t aIndex) const
  539.  
  540. /*  Returns the aIndex-th pointer value in the sequence. There is no range
  541.     checking.
  542. ---------------------------------------------------------------------------*/
  543. {
  544.     TLX_ASSERT(aIndex >= Mini());
  545.     TLX_ASSERT(aIndex <= Maxi());
  546.     return mVector.PeekAt(aIndex - 1);
  547. }
  548.  
  549. /*-------------------------------------------------------------------------*/
  550.     void *&TLVPSeq::PeekFirst()
  551.  
  552. /*  Returns a reference to the first element in the sequence. The sequence
  553.     must be non empty.
  554. ---------------------------------------------------------------------------*/
  555. {
  556.     if (IsEmpty())
  557.     THROW(TLXEmpty(LOCUS));
  558.     return PeekAt(1);
  559. }
  560.  
  561. /*-------------------------------------------------------------------------*/
  562.     void *TLVPSeq::PeekFirst() const
  563.  
  564. /*  Returns the value of the first element in the sequence. The sequence
  565.     must be non empty.
  566. ---------------------------------------------------------------------------*/
  567. {
  568.     if (IsEmpty())
  569.     THROW(TLXEmpty(LOCUS));
  570.     return PeekAt(1);
  571. }
  572.  
  573. /*-------------------------------------------------------------------------*/
  574.     void *&TLVPSeq::PeekLast()
  575.  
  576. /*  Returns a reference to the last element in the sequence. The sequence
  577.     must be non empty.
  578. ---------------------------------------------------------------------------*/
  579. {
  580.     if (IsEmpty())
  581.     THROW(TLXEmpty(LOCUS));
  582.     return PeekAt(Maxi());
  583. }
  584.  
  585. /*-------------------------------------------------------------------------*/
  586.     void *TLVPSeq::PeekLast() const
  587.  
  588. /*  Returns the value of the last element in the sequence. The sequence
  589.     must be non empty.
  590. ---------------------------------------------------------------------------*/
  591. {
  592.     if (IsEmpty())
  593.     THROW(TLXEmpty(LOCUS));
  594.     return PeekAt(Maxi());
  595. }
  596.  
  597. /*-------------------------------------------------------------------------*/
  598.     void *&TLVPSeq::PeekReverse(index_t aIndex)
  599.  
  600. /*  Returns a reference to the pointer at the aIndex-th item from the *end*
  601.     of the sequence.
  602. ---------------------------------------------------------------------------*/
  603. {
  604.     TLX_ASSERT(aIndex >= Mini());
  605.     TLX_ASSERT(aIndex <= Maxi());
  606.  
  607.     // Convert to normal index value
  608.     aIndex = Maxi() - aIndex + 1;
  609.     return PeekAt(aIndex);
  610. }
  611.  
  612. /*-------------------------------------------------------------------------*/
  613.     void *TLVPSeq::PeekReverse(index_t aIndex) const
  614.  
  615. /*  Returns the value of the element at the aIndex-th item from the *end*
  616.     of the sequence.
  617. ---------------------------------------------------------------------------*/
  618. {
  619.     TLX_ASSERT(aIndex >= Mini());
  620.     TLX_ASSERT(aIndex <= Maxi());
  621.  
  622.     // Convert to normal index value
  623.     aIndex = Maxi() - aIndex + 1;
  624.     return PeekAt(aIndex);
  625. }
  626.  
  627. /*-------------------------------------------------------------------------*/
  628.     void TLVPSeq::Prepend(void *aPtr)
  629.  
  630. /*  Adds a single element at the start of the sequence. If necessary and
  631.     allowed, the sequence is expanded.
  632. ---------------------------------------------------------------------------*/
  633. {
  634.     InsertAt(Mini(), aPtr);
  635.     TLX_ASSERT(PeekFirst() == aPtr);
  636. }
  637.  
  638. /*-------------------------------------------------------------------------*/
  639.     void TLVPSeq::Prepend(void **aVector, size_t aSize)
  640.  
  641. /*  Adds a C-style vector at the start of the sequence. If necessary and
  642.     allowed, the sequence is expanded. It is an error to add the current
  643.     sequence to itself.
  644. ---------------------------------------------------------------------------*/
  645. {
  646.     TLX_ASSERT(aVector != mVector.StorageVector());
  647.     InsertAt(Mini(), aVector, aSize);
  648.     TLX_ASSERT(aSize == 0 || PeekFirst() == aVector[0]);
  649. }
  650.  
  651. /*-------------------------------------------------------------------------*/
  652.     void TLVPSeq::Prepend(const TLVPSeq &aSeq)
  653.  
  654. /*  Adds another sequence at the start of the sequence. If necessary and
  655.     allowed, the sequence is expanded. It is an error to add the current
  656.     sequence to itself.
  657. ---------------------------------------------------------------------------*/
  658. {
  659.     TLX_ASSERT(this != &aSeq);
  660.     InsertAt(Mini(), aSeq);
  661.     TLX_ASSERT(PeekFirst() == aSeq.PeekFirst());
  662. }
  663.  
  664. /*-------------------------------------------------------------------------*/
  665.     index_t TLVPSeq::QPart(index_t low, index_t up)
  666.  
  667. /*  Partitions a subarray of the sequence for quick-sort sorting.
  668. ---------------------------------------------------------------------------*/
  669. {
  670.     void *pivot = PeekAt(low);
  671.     index_t i     = low - 1;        // Rover in lower part
  672.     index_t j     = up + 1;        // Rover in upper part
  673.  
  674.     TLX_ASSERT_PTR(mCompare);
  675.     for (;;) {
  676.     // Find subsequence in upper part
  677.     do j--; while ((*mCompare)(PeekAt(j), pivot) > 0);
  678.  
  679.     // Find subsequence in lower part
  680.     do i++; while ((*mCompare)(PeekAt(i), pivot) < 0);
  681.  
  682.     // Swap elements, or return partition position
  683.     if (i < j) {
  684.         void *vp = PeekAt(i);
  685.         PeekAt(i) = PeekAt(j);
  686.         PeekAt(j) = vp;
  687.     } else
  688.         return j;        // Done
  689.     }
  690. }
  691.  
  692. /*-------------------------------------------------------------------------*/
  693.     void TLVPSeq::QSort(index_t low, index_t up)
  694.  
  695. /*  Performs Quicksort on a partition of the sequence.
  696. ---------------------------------------------------------------------------*/
  697. {
  698.     if (low >= up) return;        // Empty or single-item partition
  699.     index_t mid = QPart(low, up);    // Make partitions
  700.     QSort(low, mid);            // Sort lower part
  701.     QSort(mid + 1, up);            // Sort upper part
  702. }
  703.  
  704. /*-------------------------------------------------------------------------*/
  705.     void TLVPSeq::Replace(index_t aIndex, void *aPtr)
  706.  
  707. /*  Replaces a single element by another. The length of the sequence does
  708.     not change.
  709. ---------------------------------------------------------------------------*/
  710. {
  711.     if (!IsValidIndex(aIndex))
  712.     THROW(TLXIndex(LOCUS, aIndex));
  713.     PeekAt(aIndex) = aPtr;
  714. }
  715.  
  716. /*-------------------------------------------------------------------------*/
  717.     void TLVPSeq::Replace(index_t aIndex, void **aVector, size_t aSize)
  718.  
  719. /*  Replaces a part of the sequence by a C-style vector. The length of the
  720.     sequence does not change. If the C-style vector is longer than the
  721.     remaining positions in the sequence from aIndex onwards, only the
  722.     remainder is replaced.
  723. ---------------------------------------------------------------------------*/
  724. {
  725.     if (!IsValidIndex(aIndex))
  726.     THROW(TLXIndex(LOCUS, aIndex));
  727.     if (aSize > (tSize)(Maxi() - aIndex))
  728.     aSize = Maxi() - aIndex;
  729.     memmove(&PeekAt(aIndex), aVector, aSize * sizeof(void *));
  730. }
  731.  
  732. /*-------------------------------------------------------------------------*/
  733.     void TLVPSeq::Replace(index_t aIndex, const TLVPSeq &aSeq)
  734.  
  735. /*  Replaces a part or whole of the current sequence by the contents
  736.     of another sequence. The length of the current sequence does not
  737.     change. The length of the other sequence must be less than or equal
  738.     to the (logical) length of the part that is replaced.
  739.  
  740.     It is an error to replace a sequence by (a part of) itself.
  741. ---------------------------------------------------------------------------*/
  742. {
  743.     if (this != &aSeq)
  744.         Replace(aIndex, aSeq.mVector.StorageVector(), aSeq.Count());
  745. }
  746.  
  747. /*-------------------------------------------------------------------------*/
  748.     bool TLVPSeq::Search(const void *aPtr, index_t &aIndex) const
  749.  
  750. /*  Searches the sequence for a given pointer value. The search is
  751.     performed with the aid of the comparison function.
  752.  
  753.     The function performs a binary search which assumes that the
  754.     sequence is proprly sorted according to the comparison function.
  755.  
  756.     If the element is not found, the index argument is set to the index
  757.     value where the element should be inserted if the sequence were
  758.     to remain sorted.
  759. ---------------------------------------------------------------------------*/
  760. {
  761.     TLX_ASSERT_PTR(mCompare);
  762.     TLX_ASSERT_PTR(aPtr);
  763.  
  764.     // Initialize invariant:
  765.     //
  766.     //  low <= pos(t) <= up...
  767.     index_t low = 1;
  768.     index_t up  = mCount;
  769.     aIndex     = (low + up) / 2;
  770.  
  771.     while (low <= up) {
  772.     int result = (*mCompare)(aPtr, PeekAt(aIndex));
  773.  
  774.     if (result < 0)            // 't' less than _vect[i]
  775.         up = aIndex - 1;
  776.     else if (result == 0)        // Found a match
  777.         return true;
  778.     else                // 't' greater than _vect[i]
  779.         low = aIndex + 1;
  780.  
  781.     aIndex = (low + up) / 2;    // Adjust position
  782.     }
  783.  
  784.     aIndex++;        // VPSeq::InsertAt() inserts BEFORE position 'i'
  785.     return false;
  786. }
  787.  
  788. /*-------------------------------------------------------------------------*/
  789.     tCompareFunc TLVPSeq::SetCompare(tCompareFunc aFunc)
  790.  
  791. /*  Sets a new comparison function and return a pointer to the previous one.
  792.     If 0 is passed for the comparison function, the default function is
  793.     restored.
  794. ---------------------------------------------------------------------------*/
  795. {
  796.     tCompareFunc oldF = mCompare;
  797.     mCompare = aFunc ? aFunc : TLVPVector::DefaultCompare;
  798.     return oldF;
  799. }
  800.  
  801. /*-------------------------------------------------------------------------*/
  802.     size_t TLVPSeq::SetDelta(size_t aDelta)
  803.  
  804. /*  Change the expansion factor of the sequence. Returns the original factor.
  805. ---------------------------------------------------------------------------*/
  806. {
  807.     size_t oldDelta = mDelta;
  808.     mDelta = aDelta;
  809.     return oldDelta;
  810. }
  811.  
  812. /*-------------------------------------------------------------------------*/
  813.     void TLVPSeq::Resize(size_t aSize)
  814.  
  815. /*  Changes the physical size of the sequence. The new size must be able
  816.     to accomodate all current elements; if necessary, the requested size
  817.     is adjusted.
  818. ---------------------------------------------------------------------------*/
  819. {
  820.     mVector.Resize(tlMax(aSize, Count()));
  821. }
  822.  
  823. /*-------------------------------------------------------------------------*/
  824.     void TLVPSeq::Sort()
  825.  
  826. /*  Performs Quicksort on the sequence.
  827. ---------------------------------------------------------------------------*/
  828. {
  829.     QSort(Mini(), Maxi());
  830. }
  831.  
  832.