home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / TEMPLATE / SEQ.CPP < prev    next >
C/C++ Source or Header  |  1996-07-02  |  19KB  |  613 lines
  1. /****************************************************************************
  2.     $Id: seq.cpp 501.0 1995/03/07 12:27:00 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 TLSeq<T>.
  10.  
  11.     $Log: seq.cpp $
  12.     Revision 501.0  1995/03/07 12:27:00  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.6  1995/01/31 16:30:48  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.5  1994/09/28  14:41:59  ron
  18.     Removed Macintosh-style #include references
  19.  
  20.     Revision 1.4  1994/09/27  20:27:33  ron
  21.     Changed path separator from / to \
  22.  
  23.     Revision 1.3  1994/09/26  15:34:21  ron
  24.     Changed include file references
  25.  
  26.     Revision 1.2  1994/09/06  14:15:36  ron
  27.     Adapted to changes in tlx.h
  28.  
  29.     Revision 1.1  1994/08/16  18:15:31  ron
  30.     Initial revision
  31.  
  32. ****************************************************************************/
  33.  
  34. #ifndef _TLX_SEQ_CPP
  35. #define _TLX_SEQ_CPP
  36.  
  37. //----- Project headers
  38.  
  39. #ifndef _TLX_ARRAYS_H
  40. #include <tlx\501\arrays.h>
  41. #endif
  42. #ifndef _TLX_DEBUG_H
  43. #include <tlx\501\debug.h>
  44. #endif
  45. #ifndef _TLX_EXCEPT_H
  46. #include <tlx\501\except.h>
  47. #endif
  48.  
  49. #ifndef _TLX_SEQBASE_CPP
  50. #include <tlx\501\template\seqbase.cpp>
  51. #endif
  52.  
  53. /*---------------------------------------------------------------------------
  54.     Implementation note
  55.     -------------------
  56.     TLSeq<T> can be indexed using index base 1, i.e. valid indices range
  57.     from 1..mCount. The underlying TLVector<T> has index base 0, i.e. its
  58.     valid indices range from 0.._size-1. Several TLSeq<T> member functions
  59.     have these index bounds coded in for reasons of speed.
  60. ---------------------------------------------------------------------------*/
  61.  
  62. /*-------------------------------------------------------------------------*/
  63.     template<class T> TLSeq<T>::TLSeq(size_t size, size_t delta)
  64.  
  65. /*  Normal constructor for TLSeq<T>. It calls the TLVector<T>(size_t)
  66.     constructor to create a vector of the desired size, then it sets
  67.     mCount to 0 to indicate an empty sequence, and mDelta to the
  68.     delta parameter.
  69. ---------------------------------------------------------------------------*/
  70. : TLSeqBase<T>(size, delta)
  71. {
  72. }
  73.  
  74. /*-------------------------------------------------------------------------*/
  75.     template<class T> TLSeq<T>::TLSeq(const T &t)
  76.  
  77. /*  Constructor creating a single element sequence that is initially not
  78.     expandable.
  79. ---------------------------------------------------------------------------*/
  80. : TLSeqBase<T>(t)
  81. {
  82. }
  83.  
  84. /*-------------------------------------------------------------------------*/
  85.     template<class T> TLSeq<T>::TLSeq(const T *tp, size_t sz)
  86.  
  87. /*  Constructor creating a sequence from a C-style vector of a given size.
  88. ---------------------------------------------------------------------------*/
  89. : TLSeqBase<T>(tp, sz)
  90. {
  91. }
  92.  
  93. /*-------------------------------------------------------------------------*/
  94.     template<class T> void TLSeq<T>::Append(const T &t, const T &pos)
  95.  
  96. /*  Adds a new element after a given other one, or at the end of the
  97.     sequence if the positioning element does not appear in the sequence.
  98. ---------------------------------------------------------------------------*/
  99. {
  100. #ifndef NDEBUG
  101.     size_t csz = Count();
  102. #endif
  103.  
  104.     index_t ipos = IndexOf(pos);
  105.     InsertAt(IsValidIndex(ipos) ? ipos : mCount + 1, t);
  106.  
  107.     TLX_ASSERT(Count() == csz + 1);
  108. }
  109.  
  110. /*-------------------------------------------------------------------------*/
  111.     template<class T> void TLSeq<T>::Append(const TLSeq<T> &s)
  112.  
  113. /*  Adds another sequence at the end of the current sequence.
  114. ---------------------------------------------------------------------------*/
  115. {
  116.     if (this == &s) return;
  117.  
  118. #ifndef NDEBUG
  119.     size_t csz = Count();
  120. #endif
  121.  
  122.     if (Available() < s.Count())
  123.     ExpandBy(s.Count() - Available());
  124.  
  125.     TLX_ASSERT(Available() < s.Count());
  126.  
  127.     const T *src = &s.PeekAt(1);
  128.     T *dst      = &PeekAt(mCount + 1);
  129.  
  130.     for (size_t cnt = s.mCount; cnt; --cnt)
  131.     *dst++ = *src++;
  132.     mCount += s.mCount;
  133.  
  134.     TLX_ASSERT(Count() == csz + s.Count());
  135. }
  136.  
  137. /*-------------------------------------------------------------------------*/
  138.     template<class T> T TLSeq<T>::Extract(const T &t)
  139.  
  140. /*  Removes and returns a given value from the sequence.
  141. ---------------------------------------------------------------------------*/
  142. {
  143.     index_t index = IndexOf(t);
  144.  
  145.     if (!IsValidIndex(index))
  146.     THROW(TLXNotFound(LOCUS));
  147.  
  148.     return ExtractAt(index);
  149. }
  150.  
  151. /*-------------------------------------------------------------------------*/
  152.     template<class T> T TLSeq<T>::ExtractAt(index_t index)
  153.  
  154. /*  Removes and returns a value at the given index from the sequence.
  155. ---------------------------------------------------------------------------*/
  156. {
  157.     if (!IsValidIndex(index))
  158.     THROW(TLXIndex(LOCUS, index));
  159.  
  160.     // Take 0/1 index base difference into account
  161.  
  162.     index--;
  163.     T tmp = mVect[index];
  164.     for (index_t i = index; (tSize)i < (mCount-1); i++)
  165.     mVect[i] = mVect[i + 1];
  166.  
  167.     TLX_ASSERT(Count() > 0);
  168.     mCount--;
  169.     return tmp;
  170. }
  171.  
  172. /*-------------------------------------------------------------------------*/
  173.     template<class T> T TLSeq<T>::ExtractFirst()
  174.  
  175. /*  Removes and returns the first value from the sequence.
  176. ---------------------------------------------------------------------------*/
  177. {
  178.     if (IsEmpty())
  179.     THROW(TLXEmpty(LOCUS));
  180.  
  181.     return ExtractAt(Mini());
  182. }
  183.  
  184. /*-------------------------------------------------------------------------*/
  185.     template<class T> T TLSeq<T>::ExtractLast()
  186.  
  187. /*  Removes and returns the last value from the sequence.
  188. ---------------------------------------------------------------------------*/
  189. {
  190.     if (IsEmpty())
  191.     THROW(TLXEmpty(LOCUS));
  192.  
  193.     return ExtractAt(Maxi());
  194. }
  195.  
  196. /*-------------------------------------------------------------------------*/
  197.     template<class T> bool TLSeq<T>::FindInsertPos
  198.     (
  199.         const T &    t,     // Value to find
  200.     index_t &    pos    // Will receive index position
  201.     ) const
  202.  
  203. /*  Performs a binary search in the sequence. Sets index of the item if
  204.     found, or best position if not. Returns true or false.
  205.  
  206.     NOTE: we use 1-based indices to avoid problems with expressions like
  207.     'pos - 1' which might otherwise wrap around to +kMaxSize for the size_t
  208.     (i.e. unsigned) variables we use.
  209. ---------------------------------------------------------------------------*/
  210. {
  211.     // Initialize invariant:
  212.     //
  213.     // low <= pos(t) <= up...
  214.  
  215.     index_t low = 1, up = mCount;
  216.     pos = (low + up) / 2;
  217.     while (low <= up)
  218.     {
  219.     int result = mCompare(t, PeekAt(pos));
  220.     if (result == 0)    // Found a match
  221.         return true;
  222.     else if (result < 0)    // 't' less than mVect[i]
  223.         up = pos - 1;
  224.     else            // 't' greater than mVect[i]
  225.         low = pos + 1;
  226.     pos = (low + up) / 2;    // Adjust position
  227.     }
  228.     pos++;            // TLSeq<T>::Insert() inserts BEFORE position 'i'
  229.  
  230.     return false;
  231. }
  232.  
  233. /*-------------------------------------------------------------------------*/
  234.     template<class T> void TLSeq<T>::Insert(const T &t)
  235.  
  236. /*  Inserts a new element in its properly sorted position.
  237. ---------------------------------------------------------------------------*/
  238. {
  239. #ifndef NDEBUG
  240.     size_t csz = Count();
  241. #endif
  242.     index_t pos;
  243.     FindInsertPos(t, pos);
  244.     InsertAt(pos, t);
  245.  
  246.     TLX_ASSERT(Count() == csz + 1);
  247. }
  248.  
  249. /*-------------------------------------------------------------------------*/
  250.     template<class T> void TLSeq<T>::InsertAt(index_t index, const T &t)
  251.  
  252. /*  Inserts a new element at the given position in the sequence.
  253. ---------------------------------------------------------------------------*/
  254. {
  255.     if (IsFull())
  256.     Expand();
  257.  
  258.     TLX_ASSERT(Available() >= 1);
  259.  
  260. #ifndef NDEBUG
  261.     size_t csz = Count();
  262. #endif
  263.  
  264.     if (index < 1) index = 1;
  265.     if ((tSize)index > (mCount + 1)) index = mCount + 1;
  266.  
  267.     --index;        // Adjust to 0-based indexing
  268.     for (size_t i = mCount; i > (tSize)index; i--)
  269.     mVect[i] = mVect[i - 1];
  270.     mVect[index] = t;
  271.     ++mCount;
  272.  
  273.     TLX_ASSERT(Count() == csz + 1);
  274. }
  275.  
  276. /*-------------------------------------------------------------------------*/
  277.     template<class T> bool TLSeq<T>::IterFirst(iter_t &i) const
  278.  
  279. /*  Initializes the iterator to address the first element in the sequence.
  280.     Returns nonzero if the iterator is valid after the operation, else zero.
  281. ---------------------------------------------------------------------------*/
  282. {
  283.     return ((tSize)(i.ix = 0)) < mCount;
  284. }
  285.  
  286. /*-------------------------------------------------------------------------*/
  287.     template<class T> bool TLSeq<T>::IterLast(iter_t &i) const
  288.  
  289. /*  Initializes the iterator to address the last element in the sequence.
  290.     Returns nonzero if the iterator is valid after the operation, else zero.
  291. ---------------------------------------------------------------------------*/
  292. {
  293.     return (i.ix = mCount - 1) >= 0;
  294. }
  295.  
  296. /*-------------------------------------------------------------------------*/
  297.     template<class T> bool TLSeq<T>::IterNext(iter_t &i) const
  298.  
  299. /*  Initializes the iterator to address the next element in the sequence.
  300.     Returns nonzero if the iterator is valid after the operation, else zero.
  301. ---------------------------------------------------------------------------*/
  302. {
  303.     return ((tSize)(++i.ix)) < mCount;
  304. }
  305.  
  306. /*-------------------------------------------------------------------------*/
  307.     template<class T> bool TLSeq<T>::IterPrev(iter_t &i) const
  308.  
  309. /*  Initializes the iterator to address the previous element in the sequence.
  310.     Returns nonzero if the iterator is valid after the operation, else zero.
  311. ---------------------------------------------------------------------------*/
  312. {
  313.     return --i.ix >= 0;
  314. }
  315.  
  316. /*-------------------------------------------------------------------------*/
  317.     template<class T> TLSeq<T> &TLSeq<T>::operator =(const T &t)
  318.  
  319. /*  Overloading of assignment operator that allows assignment of a single
  320.     element to a sequence. The previous contents of the sequence are lost.
  321. ---------------------------------------------------------------------------*/
  322. {
  323.     RemoveAll();
  324.     Append(t);
  325.     return *this;
  326. }
  327.  
  328. /*-------------------------------------------------------------------------*/
  329.     template<class T> TLSeq<T> &TLSeq<T>::operator =(const TLSeq<T> &s)
  330.  
  331. /*  Overloading of the assignment operator.
  332. ---------------------------------------------------------------------------*/
  333. {
  334.     if (this != &s)
  335.     {
  336.     TLSeqBase<T>::operator =(s);
  337.     mLower = s.mLower;
  338.     }
  339.     return *this;
  340. }
  341.  
  342. /*-------------------------------------------------------------------------*/
  343.     template<class T> T &TLSeq<T>::PeekAt(index_t aIndex)
  344.  
  345. /*  Returns a reference to the element at the given index.
  346. ---------------------------------------------------------------------------*/
  347. {
  348.     TLX_ASSERT(aIndex >= Mini());
  349.     TLX_ASSERT(aIndex <= Maxi());
  350.  
  351.     return mVect[aIndex - 1];
  352. }
  353.  
  354. /*-------------------------------------------------------------------------*/
  355.     template<class T> const T &TLSeq<T>::PeekAt(index_t aIndex) const
  356.  
  357. /*  Returns a reference to the element at the given index.
  358. ---------------------------------------------------------------------------*/
  359. {
  360.     TLX_ASSERT(aIndex >= Mini());
  361.     TLX_ASSERT(aIndex <= Maxi());
  362.  
  363.     return mVect[aIndex - 1];
  364. }
  365.  
  366. /*-------------------------------------------------------------------------*/
  367.     template<class T> T &TLSeq<T>::PeekFirst()
  368.  
  369. /*  Returns a reference to the first element in the sequence. If the
  370.     sequence is empty, a TLXEmpty exception is thrown.
  371. ---------------------------------------------------------------------------*/
  372. {
  373.     if (IsEmpty())
  374.     THROW(TLXEmpty(LOCUS));
  375.  
  376.     return PeekAt(Mini());
  377. }
  378.  
  379. /*-------------------------------------------------------------------------*/
  380.     template<class T> const T &TLSeq<T>::PeekFirst() const
  381.  
  382. /*  Returns a reference to the first element in the sequence. If the
  383.     sequence is empty, a TLXEmpty exception is thrown.
  384. ---------------------------------------------------------------------------*/
  385. {
  386.     if (IsEmpty())
  387.     THROW(TLXEmpty(LOCUS));
  388.  
  389.     return PeekAt(Mini());
  390. }
  391.  
  392. /*-------------------------------------------------------------------------*/
  393.     template<class T> T &TLSeq<T>::PeekLast()
  394.  
  395. /*  Returns a reference to the last element in the sequence. If the
  396.     sequence is empty, a TLXEmpty exception is thrown.
  397. ---------------------------------------------------------------------------*/
  398. {
  399.     if (IsEmpty())
  400.     THROW(TLXEmpty(LOCUS));
  401.  
  402.     return PeekAt(Maxi());
  403. }
  404.  
  405. /*-------------------------------------------------------------------------*/
  406.     template<class T> const T &TLSeq<T>::PeekLast() const
  407.  
  408. /*  Returns a reference to the last element in the sequence. If the
  409.     sequence is empty, a TLXEmpty exception is thrown.
  410. ---------------------------------------------------------------------------*/
  411. {
  412.     if (IsEmpty())
  413.     THROW(TLXEmpty(LOCUS));
  414.  
  415.     return PeekAt(Maxi());
  416. }
  417.  
  418. /*-------------------------------------------------------------------------*/
  419.     template<class T> T &TLSeq<T>::PeekValue(const T &t)
  420.  
  421. /*  Returns a reference to the first element with a given value. If the
  422.     value does not appear in the sequence, a TLXNotFound exception is
  423.     thrown.
  424. ---------------------------------------------------------------------------*/
  425. {
  426.     index_t i = IndexOf(t);
  427.  
  428.     if (!IsValidIndex(i))
  429.     THROW(TLXNotFound(LOCUS));
  430.  
  431.     return PeekAt(i);
  432. }
  433.  
  434. /*-------------------------------------------------------------------------*/
  435.     template<class T> const T &TLSeq<T>::PeekValue(const T &t) const
  436.  
  437. /*  Returns a reference to the first element with a given value. If the
  438.     value does not appear in the sequence, a TLXNotFound exception is
  439.     thrown.
  440. ---------------------------------------------------------------------------*/
  441. {
  442.     index_t i = IndexOf(t);
  443.  
  444.     if (!IsValidIndex(i))
  445.     THROW(TLXNotFound(LOCUS));
  446.  
  447.     return PeekAt(i);
  448. }
  449.  
  450. /*-------------------------------------------------------------------------*/
  451.     template<class T> void TLSeq<T>::Prepend(const T &t, const T &pos)
  452.  
  453. /*  Inserts a new element before a given value. If the value does not
  454.     appear in the sequence, the new element is inserted at the start
  455.     of the sequence.
  456. ---------------------------------------------------------------------------*/
  457. {
  458.     index_t ipos = IndexOf(pos);
  459.     InsertAt(IsValidIndex(ipos) ? ipos : 1, t);
  460. }
  461.  
  462. /*-------------------------------------------------------------------------*/
  463.     template<class T> void TLSeq<T>::Prepend(const TLSeq<T> &s)
  464.  
  465. /*  Inserts another sequence at the start of the current sequence.
  466. ---------------------------------------------------------------------------*/
  467. {
  468.     if (this == &s) return;
  469.  
  470.     if (Available() < s.Count())
  471.     ExpandBy(s.Count() - Available());
  472.  
  473.     TLX_ASSERT(Available() < s.Count());
  474.  
  475.     const T *src = &PeekAt(mCount);
  476.     T *dst      = &PeekAt(mCount + s.mCount);
  477.  
  478.     for (size_t cnt = mCount; cnt; --cnt)
  479.     *dst-- = *src--;
  480.  
  481.     src = &s.PeekAt(1);
  482.     dst = &PeekAt(1);
  483.     for (size_t cnt2 = s.mCount; cnt2; --cnt2)
  484.     *dst++ = *src++;
  485.  
  486.     mCount += s.mCount;
  487. }
  488.  
  489. /*-------------------------------------------------------------------------*/
  490.     template<class T> index_t TLSeq<T>::QPart(index_t low, index_t up)
  491.  
  492. /*  Partitions a subarray of the sequence for quick-sort sorting.
  493. ---------------------------------------------------------------------------*/
  494. {
  495.     T &pivot = PeekAt(low);
  496.  
  497.     index_t i = low - 1;        // Rover in lower part
  498.     index_t j = up + 1;        // Rover in upper part
  499.  
  500.     for (;;)
  501.     {
  502.     // Find subsequence in upper part
  503.     do j--; while (mCompare(PeekAt(j), pivot) > 0);
  504.  
  505.     // Find subsequence in lower part
  506.     do i++; while (mCompare(PeekAt(i), pivot) < 0);
  507.  
  508.     // Swap elements, or return partition position
  509.     if (i < j)
  510.     {
  511.         T tmp = PeekAt(i);
  512.         PeekAt(i) = PeekAt(j);
  513.         PeekAt(j) = tmp;
  514.     }
  515.     else
  516.         return j;        // Done
  517.     }
  518. }
  519.  
  520. /*-------------------------------------------------------------------------*/
  521.     template<class T> void TLSeq<T>::QSort(index_t low, index_t up)
  522.  
  523. /*  Performs quick sort on a partition of the sequence.
  524. ---------------------------------------------------------------------------*/
  525. {
  526.     if (low >= up) return;        // Empty or single-item partition
  527.  
  528.     index_t mid = QPart(low, up);    // Make partitions
  529.  
  530.     QSort(low, mid);            // Sort lower part
  531.     QSort(mid + 1, up);            // Sort upper part
  532. }
  533.  
  534. /*-------------------------------------------------------------------------*/
  535.     template<class T> void TLSeq<T>::Remove(const T &t)
  536.  
  537. /*  Removes a given value from the sequence.
  538. ---------------------------------------------------------------------------*/
  539. {
  540.     index_t index = IndexOf(t);
  541.  
  542.     if (!IsValidIndex(index))
  543.     THROW(TLXNotFound(LOCUS));
  544.  
  545.     RemoveAt(index);
  546. }
  547.  
  548. /*-------------------------------------------------------------------------*/
  549.     template<class T> void TLSeq<T>::RemoveAt(index_t index)
  550.  
  551. /*  Removes a value at the given index from the sequence.
  552. ---------------------------------------------------------------------------*/
  553. {
  554.     if (!IsValidIndex(index))
  555.     THROW(TLXIndex(LOCUS, index));
  556.  
  557.     // Take 0/1 index base difference into account
  558.  
  559.     index--;
  560.     for (index_t i = index; (tSize)i < (mCount-1); i++)
  561.     mVect[i] = mVect[i + 1];
  562.  
  563.     TLX_ASSERT(Count() > 0);
  564.     mCount--;
  565. }
  566.  
  567. /*-------------------------------------------------------------------------*/
  568.     template<class T> void TLSeq<T>::RemoveFirst()
  569.  
  570. /*  Removes the first value from the sequence.
  571. ---------------------------------------------------------------------------*/
  572. {
  573.     if (IsEmpty())
  574.     THROW(TLXEmpty(LOCUS));
  575.  
  576.     RemoveAt(Mini());
  577. }
  578.  
  579. /*-------------------------------------------------------------------------*/
  580.     template<class T> void TLSeq<T>::RemoveLast()
  581.  
  582. /*  Removes the last value from the sequence.
  583. ---------------------------------------------------------------------------*/
  584. {
  585.     if (IsEmpty())
  586.     THROW(TLXEmpty(LOCUS));
  587.  
  588.     RemoveAt(Maxi());
  589. }
  590.  
  591. /*-------------------------------------------------------------------------*/
  592.     template<class T> index_t TLSeq<T>::Search(const T &t) const
  593.  
  594. /*  Performs a binary search in the sequence. Returns index, or 0
  595.     if not found.
  596. ---------------------------------------------------------------------------*/
  597. {
  598.     index_t pos;
  599.     return FindInsertPos(t, pos) ? pos : 0;
  600. }
  601.  
  602. /*-------------------------------------------------------------------------*/
  603.     template<class T> void TLSeq<T>::Sort()
  604.  
  605. /*  Performs quick sort on the sequence.
  606. ---------------------------------------------------------------------------*/
  607. {
  608.     QSort(1, Count());
  609. }
  610.  
  611. #endif    // _TLX_SEQ_CPP
  612.  
  613.