home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / INTSET.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  10KB  |  328 lines
  1. /****************************************************************************
  2.     $Id: intset.cpp 501.0 1995/03/07 12:26:16 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 TLIntSet.
  10.  
  11.     $Log: intset.cpp $
  12.     Revision 501.0  1995/03/07 12:26:16  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.6  1995/01/31 16:30:14  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17.     Revision 1.5  1995/01/06  15:57:53  ron
  18.     Corrected Revision keyword
  19.  
  20.     Revision 1.4  1994/11/16  15:39:58  ron
  21.     Added module info; rearranged #include directives
  22.  
  23.     Revision 1.3  1994/10/05  18:39:10  ron
  24.     Renamed TLx...() functions to tl...()
  25.  
  26.     Revision 1.2  1994/09/27  20:22:32  ron
  27.     Changed path separator from / to \
  28.  
  29.     Revision 1.1  1994/09/26  15:43:28  ron
  30.     Initial revision
  31.  
  32. ****************************************************************************/
  33.  
  34. #include <tlx\501\_build.h>
  35.  
  36. TLX_MODULE_INFO("$Revision: 501.0 $");
  37.  
  38. #include <tlx\501\except.h>
  39. #include <tlx\501\intset.h>
  40.  
  41. #include <tlx\501\template\valiter.cpp>
  42.  
  43. /*-------------------------------------------------------------------------*/
  44.     TLIntSet::Iter::Iter(const TLIntSet &aSet)
  45.  
  46. /*  Constructor. Links to the given set of integers and resets the iterator.
  47. ---------------------------------------------------------------------------*/
  48. : mSet(aSet)
  49. {
  50. }
  51.  
  52. /*-------------------------------------------------------------------------*/
  53.     bool TLIntSet::Iter::FirstPos()
  54.  
  55. /*  Sets the iterator to the first element (if any) in the associated
  56.     set, returning true if that operation succeeds, else false.
  57. ---------------------------------------------------------------------------*/
  58. {
  59.     return SearchFrom(mSet.First());
  60. }
  61.  
  62. /*-------------------------------------------------------------------------*/
  63.     bool TLIntSet::Iter::NextPos()
  64.  
  65. /*  Advances the iterator to the next element (if any) in the associated
  66.     set, returning true if that operation succeeds, else false.
  67. ---------------------------------------------------------------------------*/
  68. {
  69.     if (mPos < mSet.Last())
  70.     return SearchFrom(mPos + 1);
  71.     else
  72.     return false;
  73. }
  74.  
  75. /*-------------------------------------------------------------------------*/
  76.     const int &TLIntSet::Iter::Peek() const
  77.  
  78. /*  Returns a reference to the current element. It is an error to call this
  79.     function if the last call to Next() wasn't successful, or if there has
  80.     been no call to Next() since construction or the last Reset().
  81. ---------------------------------------------------------------------------*/
  82. {
  83.     TLX_ASSERT(IsValid());
  84.     return mPos;
  85. }
  86.  
  87. /*-------------------------------------------------------------------------*/
  88.     bool TLIntSet::Iter::SearchFrom(int aPos)
  89.  
  90. /*  Searches for the next element in the set, starting at the given
  91.     position. It updates mPos, and returns true if successful, else false.
  92. ---------------------------------------------------------------------------*/
  93. {
  94.     index_t lastpos = mSet.Last();
  95.  
  96.     while (!mSet.Contains(aPos))
  97.     {
  98.     if (aPos < lastpos)
  99.         aPos++;
  100.     else
  101.         return false;
  102.     }
  103.  
  104.     mPos = aPos;
  105.     return true;
  106. }
  107.  
  108. /*-------------------------------------------------------------------------*/
  109.     TLIntSet::TLIntSet(size_t aSize)
  110.  
  111. /*  Constructor. Creates an empty set with the capacity to hold [0, aSize>.
  112. ---------------------------------------------------------------------------*/
  113. : mSet(aSize)
  114. {
  115.     mBase = 0;
  116. }
  117.  
  118. /*-------------------------------------------------------------------------*/
  119.     TLIntSet::TLIntSet(int aLower, int aUpper)
  120.  
  121. /*  Constructor. Creates an empty set with the given lower and upper bounds
  122.     (inclusive) and the capacity to hold [aLower, aUpper].
  123. ---------------------------------------------------------------------------*/
  124. : mSet(aUpper - aLower + 1)
  125. {
  126.     TLX_ASSERT(aUpper >= aLower);
  127.     mBase = aLower;
  128. }
  129.  
  130. /*-------------------------------------------------------------------------*/
  131.     TLIntSet::TLIntSet(int *aVector, size_t aSize)
  132.  
  133. /*  Constructor. Creates a set with the values in the given vector as its
  134.     initial contents. The resulting set has a capacity that matches the
  135.     lowest and highest elements from the set.
  136. ---------------------------------------------------------------------------*/
  137. : mSet(0U)
  138. {
  139.     TLX_ASSERT_PTR(aVector);
  140.  
  141.     // We start with an empty bit vector, and first determine the required
  142.     // capacity.
  143.  
  144.     int min = INT_MAX;
  145.     int max = INT_MIN;
  146.  
  147.     for (size_t i = 0; i <= aSize; i++)
  148.     {
  149.     min = tlMin(min, aVector[i]);
  150.     max = tlMax(max, aVector[i]);
  151.     }
  152.  
  153.     // Resize the bit vector and fill its contents
  154.  
  155.     if (min > max) tlSwap(min, max);
  156.  
  157.     // The following relies on the 2-complement property that max - min
  158.     // will result in a valid unsigned number even if their difference
  159.     // is larger than INT_MAX.
  160.  
  161.     size_t sz = (size_t)(max - min + 1);
  162.     mSet.Resize(sz);
  163.     mBase = min;
  164.     Insert(aVector, aSize);
  165. }
  166.  
  167. /*-------------------------------------------------------------------------*/
  168.     size_t TLIntSet::Count() const
  169.  
  170. /*  Returns the number of elements in the set.
  171. ---------------------------------------------------------------------------*/
  172. {
  173.     return mSet.Test();
  174. }
  175.  
  176. /*-------------------------------------------------------------------------*/
  177.     bool TLIntSet::Contains(int aValue) const
  178.  
  179. /*  Tests for the presence of the given element, returning true if it
  180.     appears in the set, else false.
  181. ---------------------------------------------------------------------------*/
  182. {
  183.     if (aValue < LowerBound() || aValue > UpperBound())
  184.     THROW(TLXIndex(LOCUS, aValue));
  185.  
  186.     return mSet.Test(aValue - mBase) != 0;
  187. }
  188.  
  189. /*-------------------------------------------------------------------------*/
  190.     int TLIntSet::First() const
  191.  
  192. /*  Returns the value of the smallest element in the set. It is an error
  193.     to call this function if the set is empty.
  194. ---------------------------------------------------------------------------*/
  195. {
  196.     if (IsEmpty())
  197.     THROW(TLXEmpty(LOCUS));
  198.  
  199.     return mSet.First() + mBase;
  200. }
  201.  
  202. /*-------------------------------------------------------------------------*/
  203.     void TLIntSet::Insert(int aValue)
  204.  
  205. /*  Adds a value to the set.
  206. ---------------------------------------------------------------------------*/
  207. {
  208.     if (aValue < LowerBound() || aValue > UpperBound())
  209.     THROW(TLXIndex(LOCUS, aValue));
  210.  
  211.     mSet.Set(aValue - mBase);
  212. }
  213.  
  214. /*-------------------------------------------------------------------------*/
  215.     void TLIntSet::Insert(int aLower, int aUpper)
  216.  
  217. /*  Adds a range of values to the set: [aLower,aUpper].
  218. ---------------------------------------------------------------------------*/
  219. {
  220.     if (aLower > aUpper)
  221.     return;                // Empty range
  222.  
  223.     if (aLower < LowerBound())
  224.     THROW(TLXIndex(LOCUS, aLower));
  225.     if (aUpper > UpperBound())
  226.     THROW(TLXIndex(LOCUS, aUpper));
  227.  
  228.     mSet.Set(aLower - mBase, aUpper - mBase);
  229. }
  230.  
  231. /*-------------------------------------------------------------------------*/
  232.     void TLIntSet::Insert(int *aVector, size_t aSize)
  233.  
  234. /*  Adds a number of individual elements to the set.
  235. ---------------------------------------------------------------------------*/
  236. {
  237.     for (size_t i = 0; i < aSize; i++)
  238.     Insert(aVector[i]);
  239. }
  240.  
  241. /*-------------------------------------------------------------------------*/
  242.     void TLIntSet::InsertAll()
  243.  
  244. /*  Adds all elements to the set.
  245. ---------------------------------------------------------------------------*/
  246. {
  247.     mSet.Set();
  248. }
  249.  
  250. /*-------------------------------------------------------------------------*/
  251.     int TLIntSet::Last() const
  252.  
  253. /*  Returns the value of the largest element in the set. It is an error
  254.     to call this function if the set is empty.
  255. ---------------------------------------------------------------------------*/
  256. {
  257.     if (IsEmpty())
  258.     THROW(TLXEmpty(LOCUS));
  259.  
  260.     return mSet.Last() + mBase;
  261. }
  262.  
  263. /*-------------------------------------------------------------------------*/
  264.     int TLIntSet::LowerBound() const
  265.  
  266. /*  Returns the lower bound (i.e. lowest valid member value) of the set.
  267. ---------------------------------------------------------------------------*/
  268. {
  269.     return mBase;
  270. }
  271.  
  272. /*-------------------------------------------------------------------------*/
  273.     void TLIntSet::Remove(int aValue)
  274.  
  275. /*  Removes the given element from the set.
  276. ---------------------------------------------------------------------------*/
  277. {
  278.     if (aValue < LowerBound() || aValue > UpperBound())
  279.     THROW(TLXIndex(LOCUS, aValue));
  280.  
  281.     mSet.Reset(aValue - mBase);
  282. }
  283.  
  284. /*-------------------------------------------------------------------------*/
  285.     void TLIntSet::Remove(int aLower, int aUpper)
  286.  
  287. /*  Removes a range of values from the set: [aLower,aUpper].
  288. ---------------------------------------------------------------------------*/
  289. {
  290.     if (aLower > aUpper)
  291.     return;                // Empty range
  292.  
  293.     if (aLower < LowerBound())
  294.     THROW(TLXIndex(LOCUS, aLower));
  295.     if (aUpper > UpperBound())
  296.     THROW(TLXIndex(LOCUS, aUpper));
  297.  
  298.     mSet.Reset(aLower - mBase, aUpper - mBase);
  299. }
  300.  
  301. /*-------------------------------------------------------------------------*/
  302.     void TLIntSet::Remove(int *aVector, size_t aSize)
  303.  
  304. /*  Removes a number of individual elements to the set.
  305. ---------------------------------------------------------------------------*/
  306. {
  307.     for (size_t i = 0; i < aSize; i++)
  308.     Remove(aVector[i]);
  309. }
  310.  
  311. /*-------------------------------------------------------------------------*/
  312.     void TLIntSet::RemoveAll()
  313.  
  314. /*  Removes all elements from the set.
  315. ---------------------------------------------------------------------------*/
  316. {
  317.     mSet.Reset();
  318. }
  319.  
  320. /*-------------------------------------------------------------------------*/
  321.     int TLIntSet::UpperBound() const
  322.  
  323. /*  Returns the upper bound (i.e. highest valid member value) of the set.
  324. ---------------------------------------------------------------------------*/
  325. {
  326.     return mBase + mSet.Size() - 1;
  327. }
  328.