home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / VPQUEUE.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  19KB  |  638 lines
  1. /****************************************************************************
  2.     $Id: vpqueue.cpp 501.0 1995/03/07 12:26:28 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 TLVPQueue.
  10.  
  11.     $Log: vpqueue.cpp $
  12.     Revision 501.0  1995/03/07 12:26:28  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.10  1995/01/31 16:30:34  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.9  1995/01/06  15:58:51  ron
  18.     Corrected Revision keyword
  19.  
  20.     Revision 1.8  1994/11/16  15:45:55  ron
  21.     Added module info; rearranged #include directives
  22.  
  23.     Revision 1.7  1994/10/05  18:46:06  ron
  24.     Renamed TLx...() functions to tl...()
  25.  
  26.     Revision 1.6  1994/09/28  14:47:35  ron
  27.     Removed Macintosh-style #include references
  28.  
  29.     Revision 1.5  1994/09/27  20:23:27  ron
  30.     Changed path separator from / to \
  31.  
  32.     Revision 1.4  1994/09/26  15:51:16  ron
  33.     Renamed SetSize() to Resize()
  34.  
  35.     Revision 1.3  1994/09/07  15:45:25  ron
  36.     Corrected 3 subtle, but horrible mistakes in the assumptions about
  37.     mLeft and mRight w.r.t. insertion and extraction
  38.  
  39.     Revision 1.2  1994/09/06  20:28:18  ron
  40.     Corrected assertions in Count()
  41.     Removed references to Count() in other asserts where the class invariant
  42.     was temporarily violated
  43.  
  44.     Revision 1.1  1994/08/16  18:13:22  ron
  45.     Initial revision
  46.  
  47. ****************************************************************************/
  48.  
  49. #include <tlx\501\_build.h>
  50.  
  51. TLX_MODULE_INFO("$Revision: 501.0 $");
  52.  
  53. #include <string.h>        // For mem... routines
  54. #include <tlx\501\except.h>        // Exception handling
  55. #include <tlx\501\vparrays.h>    // Class declaration
  56.  
  57. /*-------------------------------------------------------------------------*/
  58.     TLVPQueue::TLVPQueue(size_t aSize, size_t aDelta)
  59.  
  60. /*  Constructor, also doubles as default constructor. Creates an empty
  61.     queue with a given initial capacity and expansion factor.
  62. ---------------------------------------------------------------------------*/
  63. : mVector(aSize), mDelta(aDelta), mLeft(0), mRight(0), mCount(0)
  64. {
  65.     TLX_ASSERT(Size() == aSize);
  66. }
  67.  
  68. /*-------------------------------------------------------------------------*/
  69.     TLVPQueue::TLVPQueue(void *vp)
  70.  
  71. /*  Constructor creating a queue with a single element in it. The queue
  72.     is not expandable initially.
  73. ---------------------------------------------------------------------------*/
  74. : mVector(vp), mDelta(0), mLeft(0), mRight(0), mCount(1)
  75. {
  76.     TLX_ASSERT(Size() == 1);
  77. }
  78.  
  79. /*-------------------------------------------------------------------------*/
  80.     TLVPQueue::TLVPQueue(void **vpp, size_t sz)
  81.  
  82. /*  Constructor creating a queue from a C-style vector of pointers. The
  83.     queue is not expandable initially.
  84. ---------------------------------------------------------------------------*/
  85. : mVector(vpp, sz), mDelta(0), mLeft(0), mRight(0), mCount(sz)
  86. {
  87.     TLX_ASSERT(Size() == sz);
  88. }
  89.  
  90. /*-------------------------------------------------------------------------*/
  91.     TLVPQueue::TLVPQueue(const TLVPQueue &q)
  92.  
  93. /*  Copy constructor.
  94. ---------------------------------------------------------------------------*/
  95. : mVector(q.mVector), mDelta(q.mDelta), mLeft(q.mLeft), mRight(q.mRight),
  96.    mCount(q.mCount)
  97. {
  98.     TLX_ASSERT(Size() == q.Size());
  99. }
  100.  
  101. /*-------------------------------------------------------------------------*/
  102.     void TLVPQueue::AddLeft(void *vp)
  103.  
  104. /*  Adds a single element to the left end of the queue, expanding the queue
  105.     if necessary and allowed.
  106. ---------------------------------------------------------------------------*/
  107. {
  108.     TLX_ASSERT_PTR(vp);
  109.     EnsureAvailable(1);
  110.  
  111.     if (--mLeft < 0)
  112.         mLeft = Size() - 1;
  113.     mVector[mLeft] = vp;
  114.     mCount++;
  115. }
  116.  
  117. #if defined(_MSC_VER) && _MSC_VER < 1011
  118. // MSVC++ 4.1 internal compiler error
  119. #pragma optimize( "g", off)
  120. #endif
  121.  
  122. /*-------------------------------------------------------------------------*/
  123.     void TLVPQueue::AddRight(void *vp)
  124.  
  125. /*  Adds a single element to the right end of the queue, expanding the
  126.     queue if necessary and allowed.
  127. ---------------------------------------------------------------------------*/
  128. {
  129.     TLX_ASSERT_PTR(vp);
  130.     EnsureAvailable(1);
  131.  
  132.     mVector[mRight] = vp;
  133.     if ((tSize)++mRight >= Size())
  134.         mRight = 0;
  135.     mCount++;
  136. }
  137.  
  138. #if defined(_MSC_VER) && _MSC_VER < 1011
  139. #pragma optimize( "", on)
  140. #endif
  141.  
  142. /*-------------------------------------------------------------------------*/
  143.     size_t TLVPQueue::Available() const
  144.  
  145. /*  Returns the number of free slots in the storage for the queue.
  146. ---------------------------------------------------------------------------*/
  147. {
  148.     TLX_ASSERT(Size() >= Count());
  149.     return Size() - Count();
  150. }
  151.  
  152. /*-------------------------------------------------------------------------*/
  153.     bool TLVPQueue::Contains(void *vp) const
  154.  
  155. /*  Checks if the given pointer appears in the queue.
  156. ---------------------------------------------------------------------------*/
  157. {
  158.     if (Count() < 1)
  159.         return false;
  160.  
  161.     for (index_t i = mLeft;;)
  162.     {
  163.     if (mVector[i] == vp)
  164.         return true;
  165.     if ((tSize)++i >= Size())
  166.         i = 0;
  167.     if (i == mRight)
  168.         break;
  169.     }
  170.     return false;
  171. }
  172.  
  173. /*-------------------------------------------------------------------------*/
  174.     size_t TLVPQueue::Count() const
  175.  
  176. /*  Returns the number of elements in the queue.
  177. ---------------------------------------------------------------------------*/
  178. {
  179. #ifdef _TLXDBG
  180.     // Perform some sanity checks
  181.  
  182.     TLX_ASSERT(mCount <= Size());
  183.  
  184.     if (mCount == Size())               // Queue full
  185.     TLX_ASSERT(mLeft == mRight);
  186.     else if (mLeft <= mRight)        // No wrap around
  187.     TLX_ASSERT(mRight - mLeft == mCount);
  188.     else                // Wrap around
  189.     TLX_ASSERT(Size() - mLeft + mRight == mCount);
  190. #endif
  191.     return mCount;
  192. }
  193.  
  194. /*-------------------------------------------------------------------------*/
  195.     void TLVPQueue::EnqueueUnique(void *vp)
  196.  
  197. /*  Adds the pointer to the queue, but only if it does not yet appear
  198.     in the queue.
  199. ---------------------------------------------------------------------------*/
  200. {
  201.     if (!Contains(vp))
  202.         Enqueue(vp);
  203. }
  204.  
  205. /*-------------------------------------------------------------------------*/
  206.     void TLVPQueue::EnsureAvailable(size_t aSize)
  207.  
  208. /*  Ensures that there are at least 'aSize' positions available in the
  209.     physical storage for the queue. If necessary and allowed, the queue
  210.     storage is resized to make room.
  211. ---------------------------------------------------------------------------*/
  212. {
  213.     size_t avail = Available();
  214.  
  215.     if (avail >= aSize)
  216.         return;
  217.  
  218.     if (IsFrozen())
  219.     THROW(TLXFull(LOCUS));
  220.  
  221.     size_t expansion = ((aSize - avail) % mDelta + 1) * mDelta;
  222.     Resize(Size() + expansion);
  223.     TLX_ASSERT(Available() >= aSize);
  224. }
  225.  
  226. /*-------------------------------------------------------------------------*/
  227.     void *TLVPQueue::Extract(void *vp)
  228.  
  229. /*  Removes the given pointer from the queue and returns it.
  230. ---------------------------------------------------------------------------*/
  231. {
  232.     if (IsEmpty())
  233.     THROW(TLXEmpty(LOCUS));
  234.  
  235.     // Find index of item to be removed
  236.     index_t i;
  237.     for (i = mLeft; mVector[i] != vp; )
  238.     {
  239.     if ((tSize)++i >= Size()) i = 0;
  240.     if (i >= mRight)
  241.         THROW(TLXNotFound(LOCUS));
  242.     }
  243.  
  244.     // Fill the gap by either moving left part to the right, or right
  245.     // part to the left, depending on the easier operation.
  246.  
  247.     if (i >= mLeft)        // Move left part to the right
  248.     {
  249.     TLX_ASSERT(mLeft < Size() - 1 || mLeft == i);
  250.  
  251.     memmove(&mVector[mLeft + 1], &mVector[mLeft],
  252.         (i - mLeft) * sizeof(void *));
  253.     mVector[mLeft] = 0;
  254.     if ((tSize)++mLeft >= Size()) mLeft = 0;
  255.     }
  256.     else            // Move right wrap-around to the left
  257.     {
  258.     TLX_ASSERT(i < mRight);
  259.     TLX_ASSERT(mRight <= mLeft);
  260.     TLX_ASSERT(mRight > 0);
  261.  
  262.     mRight--;
  263.     memmove(&mVector[mRight - 1], &mVector[mRight],
  264.             (mRight - i) * sizeof(void *));
  265.     mVector[mRight] = 0;
  266.     }
  267.  
  268.     TLX_ASSERT(mCount > 0);
  269.     mCount--;
  270.     return vp;
  271. }
  272.  
  273. /*-------------------------------------------------------------------------*/
  274.     void *TLVPQueue::ExtractLeft()
  275.  
  276. /*  Removes the leftmost element from the queue and returns it.
  277. ---------------------------------------------------------------------------*/
  278. {
  279.     if (IsEmpty())
  280.     THROW(TLXEmpty(LOCUS));
  281.  
  282.     void *tmp        = mVector[mLeft];
  283.     mVector[mLeft] = 0;
  284.     if ((tSize)++mLeft >= Size())
  285.         mLeft = 0;
  286.  
  287.     TLX_ASSERT(mCount > 0);
  288.     mCount--;
  289.  
  290.     return tmp;
  291. }
  292.  
  293. /*-------------------------------------------------------------------------*/
  294.     void *TLVPQueue::ExtractRight()
  295.  
  296. /*  Removes the rightmost element from the queue and returns it.
  297. ---------------------------------------------------------------------------*/
  298. {
  299.     if (IsEmpty())
  300.     THROW(TLXEmpty(LOCUS));
  301.  
  302.     if (--mRight < 0)
  303.         mRight = Size() - 1;
  304.     void *tmp         = mVector[mRight];
  305.     mVector[mRight] = 0;
  306.  
  307.     TLX_ASSERT(mCount > 0);
  308.     mCount--;
  309.  
  310.     return tmp;
  311. }
  312.  
  313. #if 0
  314. /*-------------------------------------------------------------------------*/
  315.     bool TLVPQueue::IterFirst(index_t &i) const
  316.  
  317. /*  Initializes the iterator to point at the first (leftmost) element of
  318.     the queue. Returns nonzero if the iterator is valid, else zero.
  319. ---------------------------------------------------------------------------*/
  320. {
  321.     i = mLeft;
  322.     return !IsEmpty();
  323. }
  324.  
  325. /*-------------------------------------------------------------------------*/
  326.     bool TLVPQueue::IterLast(index_t &i) const
  327.  
  328. /*  Initializes the iterator to point at the last (rightmost) element of
  329.     the queue. Returns nonzero if the iterator is valid, else zero.
  330. ---------------------------------------------------------------------------*/
  331. {
  332.     i = mRight - 1;
  333.     if (i < 0)
  334.         i = Size() - 1;
  335.     return !IsEmpty();
  336. }
  337.  
  338. /*-------------------------------------------------------------------------*/
  339.     bool TLVPQueue::IterNext(index_t &i) const
  340.  
  341. /*  Advances the iterator one position from left to right, returning nonzero
  342.     if the iterator is still valid after the operation.
  343. ---------------------------------------------------------------------------*/
  344. {
  345.     if (++i >= Size())
  346.         i = 0;
  347.  
  348.     // Note: we use the '> mLeft' test to ensure termination
  349.     if (mRight >= mLeft)
  350.         return i < mRight;
  351.     else
  352.     return i > mLeft || i < mRight;
  353. }
  354.  
  355. /*-------------------------------------------------------------------------*/
  356.     bool TLVPQueue::IterPrev(index_t &i) const
  357.  
  358. /*  Advances the iterator one position from right to left, returning nonzero
  359.     if the iterator is still valid after the operation.
  360. ---------------------------------------------------------------------------*/
  361. {
  362.     if (--i < 0)
  363.         i = Size() - 1;
  364.  
  365.     if (mRight >= mLeft)
  366.         return i >= mLeft;
  367.     else
  368.     return i >= mLeft || i < mRight;
  369. }
  370. #endif
  371. /*-------------------------------------------------------------------------*/
  372.     TLVPQueue &TLVPQueue::operator =(void *vp)
  373.  
  374. /*  Overloading of assignment operator which allows assignment of a single
  375.     pointer to the queue. The previous contents of the queue are deleted.
  376. ---------------------------------------------------------------------------*/
  377. {
  378.     mVector.operator =(vp);
  379.     mLeft = 0;
  380.     mRight = 0;
  381.     mCount = 1;
  382.     return *this;
  383. }
  384.  
  385. /*-------------------------------------------------------------------------*/
  386.     TLVPQueue &TLVPQueue::operator =(const TLVPQueue &q)
  387.  
  388. /*  Overloading of assignment operator.
  389. ---------------------------------------------------------------------------*/
  390. {
  391.     if (this != &q)
  392.     {
  393.         mVector.operator =(q.mVector);
  394.     mDelta = q.mDelta;
  395.         mLeft = q.mLeft;
  396.     mRight = q.mRight;
  397.     mCount = q.mCount;
  398.     }
  399.     return *this;
  400. }
  401. #if 0
  402. /*-------------------------------------------------------------------------*/
  403.     void *&TLVPQueue::PeekIter(index_t i)
  404.  
  405. /*  Returns a reference to the element that is being addressed by the
  406.     iterator.
  407. ---------------------------------------------------------------------------*/
  408. {
  409.     TLX_ASSERT(Count() > 0);
  410.  
  411.     if (mLeft < mRight)
  412.         TLX_ASSERT(i >= mLeft && i < mRight);
  413.     else
  414.         TLX_ASSERT((i >= mLeft && i < Size()) || (i > 0 && i < mRight));
  415.  
  416.     return mVector[i];
  417. }
  418.  
  419. /*-------------------------------------------------------------------------*/
  420.     void *TLVPQueue::PeekIter(index_t i) const
  421.  
  422. /*  Returns the value of the element that is being addressed by the
  423.     iterator.
  424. ---------------------------------------------------------------------------*/
  425. {
  426.     TLX_ASSERT(Count() > 0);
  427.  
  428.     if (mLeft < mRight)
  429.         TLX_ASSERT(i >= mLeft && i < mRight);
  430.     else
  431.         TLX_ASSERT((i >= mLeft && i < Size()) || (i > 0 && i < mRight));
  432.  
  433.     return mVector[i];
  434. }
  435. #endif
  436. /*-------------------------------------------------------------------------*/
  437.     void *&TLVPQueue::PeekLeft()
  438.  
  439. /*  Returns a reference to the leftmost element in the queue.
  440. ---------------------------------------------------------------------------*/
  441. {
  442.     if (IsEmpty())
  443.     THROW(TLXEmpty(LOCUS));
  444.  
  445.     return mVector[mLeft];
  446. }
  447.  
  448. /*-------------------------------------------------------------------------*/
  449.     void *TLVPQueue::PeekLeft() const
  450.  
  451. /*  Returns the value of the leftmost element in the queue.
  452. ---------------------------------------------------------------------------*/
  453. {
  454.     if (IsEmpty())
  455.     THROW(TLXEmpty(LOCUS));
  456.  
  457.     return mVector[mLeft];
  458. }
  459.  
  460. /*-------------------------------------------------------------------------*/
  461.     void *&TLVPQueue::PeekRight()
  462.  
  463. /*  Returns a reference to the rightmost element in the queue.
  464. ---------------------------------------------------------------------------*/
  465. {
  466.     if (IsEmpty())
  467.     THROW(TLXEmpty(LOCUS));
  468.  
  469.     return mVector[mRight > 0 ? mRight - 1 : Size() - 1];
  470. }
  471.  
  472. /*-------------------------------------------------------------------------*/
  473.     void *TLVPQueue::PeekRight() const
  474.  
  475. /*  Returns the value of the rightmost element in the queue.
  476. ---------------------------------------------------------------------------*/
  477. {
  478.     if (IsEmpty())
  479.     THROW(TLXEmpty(LOCUS));
  480.  
  481.     return mVector[mRight > 0 ? mRight - 1 : Size() - 1];
  482. }
  483.  
  484. #if defined(_MSC_VER) && _MSC_VER < 1011
  485. // MSVC++ 4.1 internal compiler error
  486. #pragma optimize( "g", off)
  487. #endif
  488.  
  489. /*-------------------------------------------------------------------------*/
  490.     void TLVPQueue::Remove(void *vp)
  491.  
  492. /*  Removes a single element from the queue, deleting the pointed to object
  493.     if we own it.
  494. ---------------------------------------------------------------------------*/
  495. {
  496.     void *ptr = Extract(vp);
  497.     TLX_ASSERT(ptr == vp);
  498.     if (IsOwner())
  499.     DeletePtr(ptr);
  500. }
  501.  
  502. #if defined(_MSC_VER) && _MSC_VER < 1011
  503. #pragma optimize( "", on)
  504. #endif
  505.  
  506. /*-------------------------------------------------------------------------*/
  507.     void TLVPQueue::RemoveAll()
  508.  
  509. /*  Removes all pointers in the queue, deleting the pointed to objects
  510.     if we are the owner of them.
  511. ---------------------------------------------------------------------------*/
  512. {
  513.     mVector.RemoveAll();
  514.     mLeft = mRight = mCount = 0;
  515. }
  516.  
  517. /*-------------------------------------------------------------------------*/
  518.     void TLVPQueue::RemoveLeft()
  519.  
  520. /*  Removes the leftmost element from the queue, deleting the pointed to
  521.     object if we are the owner.
  522. ---------------------------------------------------------------------------*/
  523. {
  524.     void *ptr = ExtractLeft();
  525.     if (IsOwner())
  526.     DeletePtr(ptr);
  527. }
  528.  
  529. /*-------------------------------------------------------------------------*/
  530.     void TLVPQueue::RemoveRight()
  531.  
  532. /*  Removes the rightmost element from the queue, deleting the pointed to
  533.     object if we are the owner.
  534. ---------------------------------------------------------------------------*/
  535. {
  536.     void *ptr = ExtractRight();
  537.     if (IsOwner())
  538.     DeletePtr(ptr);
  539. }
  540.  
  541. /*-------------------------------------------------------------------------*/
  542.     size_t TLVPQueue::SetDelta(size_t aDelta)
  543.  
  544. /*  Sets a new delta, returning the old one.
  545. ---------------------------------------------------------------------------*/
  546. {
  547.     size_t olddelta = mDelta;
  548.     mDelta = aDelta;
  549.     return olddelta;
  550. }
  551.  
  552. /*-------------------------------------------------------------------------*/
  553.     void TLVPQueue::Resize(size_t aSize)
  554.  
  555. /*  Changes the physical size of the queue, without disturbing the items in
  556.     the queue. It is an error to reduce the size of the queue below the
  557.     current logical length.
  558. ---------------------------------------------------------------------------*/
  559. {
  560.     if (aSize < Count())
  561.     THROW(TLXResize(LOCUS, aSize, Count()));
  562.  
  563.     if (aSize == Size())    // Trivial
  564.     return;
  565.  
  566.     // Resizing the queue is complicated by the fact that the elements in
  567.     // the queue may be wrapped around. If we simply use the mVector.Size()
  568.     // operation, this may result in a malformed queue, as follows:
  569.     //
  570.     //    - If the size of the queue is reduced, elements at the right end
  571.     //      of the queue will be lost;
  572.     //    - If the size of the queue is increased, a gap at the right end
  573.     //      will open.
  574.     //
  575.     // To prevent this from happening, we take some precautions:
  576.     //
  577.     //    - If the size of the queue is reduced, we first move down the elements
  578.     //      at the right;
  579.     //    - If the size of the queue is enlarged, we move the elements at the
  580.     //      right up after the enlargement.
  581.  
  582.     size_t oldsize  = Size();
  583.  
  584.     if (aSize < oldsize)
  585.     {
  586.     // Move endangered items to a safe place
  587.     if (mLeft < mRight)    // No wrap around; just move down
  588.     {
  589.         if (mLeft > 0)
  590.         {
  591.             memmove(&mVector[0], &mVector[mLeft], mCount * sizeof(void *));
  592.         memset(&mVector[mRight], 0, (Size()-mRight+1) * sizeof(void *));
  593.         mLeft = 0;
  594.         mRight = mCount;
  595.         }
  596.     }
  597.     else            // Wrap around; reduce the gap
  598.     {
  599.         // Elements are moved to the left
  600.         size_t reduction = oldsize - aSize;
  601.         memmove(&mVector[mLeft-reduction], &mVector[mLeft],
  602.         (Size() - mLeft) * sizeof(void *));
  603.         mLeft -= reduction;
  604.  
  605.         // We now have a gap at the far right that will vanish as the
  606.         // vector is reduced in size.
  607.     }
  608.     }
  609.  
  610.     // Perform the resize operation
  611.  
  612.     mVector.Resize(aSize);
  613.  
  614.     TLX_ASSERT(Size() == aSize);
  615.     TLX_ASSERT(Size() >= mCount);
  616.  
  617.     // See if we must adjust the queue items any further
  618.     if (aSize > oldsize)
  619.     {
  620.     // If there was a wrap around to start with, we now have a gap in
  621.     // the middle of the queue (located at the end of the underlying
  622.     // vector). Move up the right part of the vector to close it.
  623.  
  624.     if (mLeft >= mRight && mCount > 0)    // Wrap around
  625.     {
  626.         size_t expansion   = Size() - oldsize;
  627.         size_t bytesToMove = oldsize - mLeft;
  628.  
  629.         memmove(&mVector[mLeft + expansion], &mVector[mLeft],
  630.                 bytesToMove * sizeof(void *));
  631.         memset(&mVector[mLeft], 0, bytesToMove * sizeof(void *));
  632.         mLeft += expansion;
  633.     }
  634.     }
  635.     TLX_ASSERT(Count() == mCount);
  636. }
  637.  
  638.