home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / TEMPLATE / QUEUE.CPP < prev    next >
C/C++ Source or Header  |  1996-01-05  |  13KB  |  429 lines
  1. /****************************************************************************
  2.     $Id: queue.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 TLQueue<T>.
  10.  
  11.     $Log: queue.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:39  ron
  18.     Removed Macintosh-style #include references
  19.  
  20.     Revision 1.4  1994/09/27  20:27:29  ron
  21.     Changed path separator from / to \
  22.  
  23.     Revision 1.3  1994/09/26  15:33:53  ron
  24.     Changed include file references
  25.  
  26.     Revision 1.2  1994/09/07  15:47:32  ron
  27.     Corrected subtle but deadly mistakes in the assumptions about mLeft and
  28.     mRight w.r.t. insertion and extraction
  29.  
  30.     Revision 1.1  1994/08/16  18:15:30  ron
  31.     Initial revision
  32.  
  33. ****************************************************************************/
  34.  
  35. #ifndef _TLX_QUEUE_CPP
  36. #define _TLX_QUEUE_CPP
  37.  
  38. //----- Project headers
  39.  
  40. #ifndef _TLX_ARRAYS_H
  41. #include <tlx\501\arrays.h>
  42. #endif
  43. #ifndef _TLX_DEBUG_H
  44. #include <tlx\501\debug.h>
  45. #endif
  46. #ifndef _TLX_EXCEPT_H
  47. #include <tlx\501\except.h>
  48. #endif
  49.  
  50. #ifndef _TLX_SEQBASE_CPP
  51. #include <tlx\501\template\seqbase.cpp>
  52. #endif
  53.  
  54. /*-------------------------------------------------------------------------*/
  55.     template<class T> TLQueue<T>::TLQueue(size_t size, size_t delta)
  56.  
  57. /*  Constructor, creating a queue with the given initial capacity and
  58.     expansion factor.
  59. ---------------------------------------------------------------------------*/
  60. : TLSeqBase<T>(size, delta)
  61. {
  62.     RemoveAll();
  63. }
  64.  
  65. /*-------------------------------------------------------------------------*/
  66.     template<class T> TLQueue<T>::TLQueue(const T &t)
  67.  
  68. /*  Constructor creating a single element queue. The queue cannot be
  69.     expanded initially.
  70. ---------------------------------------------------------------------------*/
  71. : TLSeqBase<T>(t)
  72. {
  73.     mLeft  = 0;
  74.     mRight = mSize;
  75. }
  76.  
  77. /*-------------------------------------------------------------------------*/
  78.     template<class T> void TLQueue<T>::AddLeft(const T &t)
  79.  
  80. /*  Adds a new element at the left end of the queue.
  81. ---------------------------------------------------------------------------*/
  82. {
  83.     if (IsFull())
  84.         Expand();
  85.  
  86.     TLX_ASSERT(Available() >= 1);
  87.  
  88.     if (--mLeft < 0)
  89.         mLeft = mSize - 1;
  90.     mVect[mLeft] = t;
  91.     mCount++;
  92. }
  93.  
  94. /*-------------------------------------------------------------------------*/
  95.     template<class T> void TLQueue<T>::AddRight(const T &t)
  96.  
  97. /*  Adds a new element at the right end of the queue.
  98. ---------------------------------------------------------------------------*/
  99. {
  100.     if (IsFull())
  101.         Expand();
  102.  
  103.     TLX_ASSERT(Available() >= 1);
  104.  
  105.     mVect[mRight] = t;
  106.     if (++mRight >= mSize)
  107.         mRight = 0;
  108.     mCount++;
  109. }
  110.  
  111. /*-------------------------------------------------------------------------*/
  112.     template<class T> void TLQueue<T>::CompactStorage()
  113.  
  114. /*  Function to adjust the physical storage for the queue to exactly fit
  115.     its logical contents. Not implemented currently.
  116. ---------------------------------------------------------------------------*/
  117. {
  118.     TLX_NOTIMPLEMENTED(TLQueue<T>::CompactStorage());
  119. }
  120.  
  121. /*-------------------------------------------------------------------------*/
  122.     template<class T> void TLQueue<T>::EnqueueUnique(const T &t)
  123.  
  124. /*  Enqueues a new element if it doesn't yet appear in the queue.
  125. ---------------------------------------------------------------------------*/
  126. {
  127.     if (!Contains(t))
  128.         Enqueue(t);
  129. }
  130.  
  131. /*-------------------------------------------------------------------------*/
  132.     template<class T> void TLQueue<T>::Expand()
  133.  
  134. /*  Expands the queue by mDelta elements. If the queue cannot be expanded
  135.     for some reason, a TLXFull exception is thrown.
  136. ---------------------------------------------------------------------------*/
  137. {
  138.     // The ExpandBy() function creates room at the end of the underlying
  139.     // vector. In order to be useful for the circular queue, we must move
  140.     // the newly created gap to the mRight position, which isn't necessarily
  141.     // at the end of the vector. The gap is mDelta elements long.
  142.     //
  143.     // We assume that this function is only called when the queue is full,
  144.     // i.e. mLeft == mRight and mCount == mSize.
  145.  
  146.     TLX_ASSERT(mLeft == mRight);
  147.     TLX_ASSERT(mCount == mSize);
  148.  
  149.     size_t oldsize = mSize;
  150.  
  151.     if (mDelta == 0)
  152.     THROW(TLXFull(LOCUS));
  153.  
  154.     ExpandBy(mDelta);
  155.  
  156.     if (mLeft > 0)        // Gap must be somewhere in the middle
  157.     {
  158.     TLX_ASSERT(oldsize > mLeft);
  159.     TLX_ASSERT(oldsize + mDelta == mSize);
  160.  
  161.         for (size_t i = oldsize - 1; i >= mLeft; --i)
  162.         mVect[i + mDelta] = mVect[i];
  163.  
  164.         mLeft += mDelta;
  165.     }
  166.     else            // Gap must go at the end
  167.     mRight = oldsize;
  168. }
  169.  
  170. /*-------------------------------------------------------------------------*/
  171.     template<class T> T TLQueue<T>::ExtractLeft()
  172.  
  173. /*  Removes and returns the leftmost element from the queue.
  174. ---------------------------------------------------------------------------*/
  175. {
  176.     if (IsEmpty())
  177.     THROW(TLXEmpty(LOCUS));
  178.  
  179.     index_t lft = mLeft;
  180.     if (++mLeft >= mSize)
  181.         mLeft = 0;
  182.  
  183.     TLX_ASSERT(mCount > 0);
  184.     mCount--;
  185.     return mVect[lft];
  186. }
  187.  
  188. /*-------------------------------------------------------------------------*/
  189.     template<class T> T TLQueue<T>::ExtractRight()
  190.  
  191. /*  Removes and returns the rightmost element from the queue.
  192. ---------------------------------------------------------------------------*/
  193. {
  194.     if (IsEmpty())
  195.     THROW(TLXEmpty(LOCUS));
  196.  
  197.     if (--mRight < 0)
  198.         mRight = mSize - 1;
  199.  
  200.     TLX_ASSERT(mCount > 0);
  201.     mCount--;
  202.     return mVect[mRight];
  203. }
  204.  
  205. /*-------------------------------------------------------------------------*/
  206.     template<class T> bool TLQueue<T>::IterFirst(iter_t &i) const
  207.  
  208. /*  Initializes the iterator to address the first item in the queue.
  209.     Returns nonzero if the iterator is valid after the operation, else
  210.     zero.
  211. ---------------------------------------------------------------------------*/
  212. {
  213.     i.ix = mLeft;
  214.     return !IsEmpty();
  215. }
  216.  
  217. /*-------------------------------------------------------------------------*/
  218.     template<class T> bool TLQueue<T>::IterLast(iter_t &i) const
  219.  
  220. /*  Initializes the iterator to address the last item in the queue.
  221.     Returns nonzero if the iterator is valid after the operation, else
  222.     zero.
  223. ---------------------------------------------------------------------------*/
  224. {
  225.     i.ix = mRight - 1;
  226.     if (i.ix < 0)
  227.         i.ix = mSize - 1;
  228.     return !IsEmpty();
  229. }
  230.  
  231. /*-------------------------------------------------------------------------*/
  232.     template<class T> bool TLQueue<T>::IterNext(iter_t &i) const
  233.  
  234. /*  Advances the iterator to address the next (rightward moving) item in
  235.     the queue. Returns nonzero if the iterator is valid after the operation,
  236.     else zero.
  237. ---------------------------------------------------------------------------*/
  238. {
  239.     if (++i.ix >= mSize)
  240.         i.ix = 0;
  241.  
  242.     // Note: we use the '> mLeft' test to ensure termination
  243.     if (mRight >= mLeft)
  244.         return i.ix < mRight;
  245.     else
  246.     return i.ix > mLeft || i.ix < mRight;
  247. }
  248.  
  249. /*-------------------------------------------------------------------------*/
  250.     template<class T> bool TLQueue<T>::IterPrev(iter_t &i) const
  251.  
  252. /*  Advances the iterator to address the previous (leftward moving) item in
  253.     the queue. Returns nonzero if the iterator is valid after the operation,
  254.     else zero.
  255. ---------------------------------------------------------------------------*/
  256. {
  257.     if (--i.ix < 0)
  258.         i.ix = mSize - 1;
  259.  
  260.     if (mRight >= mLeft)
  261.         return i.ix >= mLeft;
  262.     else
  263.     return i.ix >= mLeft || i.ix < mRight;
  264. }
  265.  
  266. /*-------------------------------------------------------------------------*/
  267.     template<class T> index_t TLQueue<T>::MapIndex(index_t i) const
  268.  
  269. /*  Converts logical indices to physical indices for the queue. The
  270.     logical indices range from 1 to Count(), while the physical start
  271.     at mLeft and end at mRight. We must be careful to take the effects
  272.     of wrap-around into account.
  273. ---------------------------------------------------------------------------*/
  274. {
  275.     // Watch out for integer overflow!
  276.     if (--i > mSize - mLeft)
  277.     return i - (mSize - mLeft);
  278.     else
  279.     return i + mLeft;
  280. }
  281.  
  282. /*-------------------------------------------------------------------------*/
  283.     template<class T> bool TLQueue<T>::OK() const
  284.  
  285. /*  Checks the class invariants.
  286. ---------------------------------------------------------------------------*/
  287. {
  288.     return TLSeqBase<T>::OK() && mLeft < mSize && mRight < mSize;
  289. }
  290.  
  291. /*-------------------------------------------------------------------------*/
  292.     template<class T> TLQueue<T> &TLQueue<T>::operator =(const T &t)
  293.  
  294. /*  Overloading of the assignment operator that assigns a single element
  295.     to the queue. The previous queue elements are lost.
  296. ---------------------------------------------------------------------------*/
  297. {
  298.     RemoveAll();
  299.     Enqueue(t);
  300.     return *this;
  301. }
  302.  
  303. /*-------------------------------------------------------------------------*/
  304.     template<class T> TLQueue<T> &TLQueue<T>::operator =(const TLQueue<T> &s)
  305.  
  306. /*  Overloading of the assignment operator.
  307. ---------------------------------------------------------------------------*/
  308. {
  309.     if (this != &s)
  310.     {
  311.     TLSeqBase<T>::operator =(s);
  312.     mLeft  = s.mLeft;
  313.     mRight = s.mRight;
  314.     }
  315.     return *this;
  316. }
  317.  
  318. /*-------------------------------------------------------------------------*/
  319.     template<class T> T &TLQueue<T>::PeekLeft()
  320.  
  321. /*  Returns a reference to the leftmost element in the queue. If the queue
  322.     is empty, a TLXEmpty exception is thrown.
  323. ---------------------------------------------------------------------------*/
  324. {
  325.     if (IsEmpty())
  326.     THROW(TLXEmpty(LOCUS));
  327.  
  328.     return mVect[mLeft];
  329. }
  330.  
  331. /*-------------------------------------------------------------------------*/
  332.     template<class T> const T &TLQueue<T>::PeekLeft() const
  333.  
  334. /*  Returns a reference to the leftmost element in the queue. If the queue
  335.     is empty, a TLXEmpty exception is thrown.
  336. ---------------------------------------------------------------------------*/
  337. {
  338.     if (IsEmpty())
  339.     THROW(TLXEmpty(LOCUS));
  340.  
  341.     return mVect[mLeft];
  342. }
  343.  
  344. /*-------------------------------------------------------------------------*/
  345.     template<class T> T &TLQueue<T>::PeekRight()
  346.  
  347. /*  Returns a reference to the rightmost element in the queue. If the queue
  348.     is empty, a TLXEmpty exception is thrown.
  349. ---------------------------------------------------------------------------*/
  350. {
  351.     if (IsEmpty())
  352.     THROW(TLXEmpty(LOCUS));
  353.  
  354.     return mVect[mRight > 0 ? mRight - 1 : mSize - 1];
  355. }
  356.  
  357. /*-------------------------------------------------------------------------*/
  358. template<class T> const T &TLQueue<T>::PeekRight() const
  359.  
  360. /*  Returns a reference to the rightmost element in the queue. If the queue
  361.     is empty, a TLXEmpty exception is thrown.
  362. ---------------------------------------------------------------------------*/
  363. {
  364.     if (IsEmpty())
  365.     THROW(TLXEmpty(LOCUS));
  366.  
  367.     return mVect[mRight > 0 ? mRight - 1 : mSize - 1];
  368. }
  369.  
  370. /*-------------------------------------------------------------------------*/
  371.     template<class T> void TLQueue<T>::RemoveAll()
  372.  
  373. /*  Removes all elements from the queue.
  374. ---------------------------------------------------------------------------*/
  375. {
  376.     TLSeqBase<T>::RemoveAll();
  377.     mLeft = mRight = 0;
  378. }
  379.  
  380. /*-------------------------------------------------------------------------*/
  381.     template<class T> void TLQueue<T>::RemoveLeft()
  382.  
  383. /*  Removes the leftmost element from the queue.
  384. ---------------------------------------------------------------------------*/
  385. {
  386.     if (IsEmpty())
  387.     THROW(TLXEmpty(LOCUS));
  388.  
  389.     if (++mLeft >= mSize)
  390.         mLeft = 0;
  391.  
  392.     TLX_ASSERT(mCount > 0);
  393.     mCount--;
  394. }
  395.  
  396. /*-------------------------------------------------------------------------*/
  397.     template<class T> void TLQueue<T>::RemoveRight()
  398.  
  399. /*  Removes and returns the rightmost element from the queue.
  400. ---------------------------------------------------------------------------*/
  401. {
  402.     if (IsEmpty())
  403.     THROW(TLXEmpty(LOCUS));
  404.  
  405.     if (--mRight < 0)
  406.         mRight = mSize - 1;
  407.  
  408.     TLX_ASSERT(mCount > 0);
  409.     mCount--;
  410. }
  411.  
  412. /*-------------------------------------------------------------------------*/
  413.     template<class T> index_t TLQueue<T>::UnmapIndex(index_t i) const
  414.  
  415. /*  Converts physical indices to logical indices for the queue. The
  416.     logical indices range from 1 to Count(), while the physical start
  417.     at mLeft and end at mRight. We must be careful to take the effects
  418.     of wrap-around into account.
  419. ---------------------------------------------------------------------------*/
  420. {
  421.     // Watch out for integer overflow!
  422.     if (i >= mLeft)
  423.     return i - mLeft + 1;
  424.     else
  425.     return i + (mSize - mLeft) + 1;
  426. }
  427.  
  428. #endif    // _TLX_QUEUE_CPP
  429.