home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / bitset.h < prev    next >
C/C++ Source or Header  |  1995-04-09  |  11KB  |  351 lines
  1.  
  2.  
  3. #ifndef _bitset_h_ /* Mon Nov  8 09:02:26 1993 */
  4. #define _bitset_h_
  5.  
  6.  
  7.  
  8.  
  9.  
  10. /*
  11.  *
  12.  *          Copyright (C) 1994, M. A. Sridhar
  13.  *  
  14.  *
  15.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  16.  *     to copy, modify or distribute this software  as you see fit,
  17.  *     and to use  it  for  any  purpose, provided   this copyright
  18.  *     notice and the following   disclaimer are included  with all
  19.  *     copies.
  20.  *
  21.  *                        DISCLAIMER
  22.  *
  23.  *     The author makes no warranties, either expressed or implied,
  24.  *     with respect  to  this  software, its  quality, performance,
  25.  *     merchantability, or fitness for any particular purpose. This
  26.  *     software is distributed  AS IS.  The  user of this  software
  27.  *     assumes all risks  as to its quality  and performance. In no
  28.  *     event shall the author be liable for any direct, indirect or
  29.  *     consequential damages, even if the  author has been  advised
  30.  *     as to the possibility of such damages.
  31.  *
  32.  */
  33.  
  34.  
  35. // This is a class encapsulating the notion of a {\it BitSet,} a set of
  36. // integers represented by a bit vector. It can store a set of integers in
  37. // the range 0..max-1, where max is the maximum cardinality possible. The
  38. // maximum cardinality is the parameter to the constructor.
  39. //
  40. // The bit-vector representation allows very efficient storage and access
  41. // algorithms for small, dense sets of integers. (Dense sets are those in
  42. // which the number of elements is a significant proportion of the maximum
  43. // cardinality.)
  44. //
  45.  
  46.  
  47. #ifdef __GNUC__
  48. #pragma interface
  49. #endif
  50.  
  51.  
  52. #include "base/intset.h"
  53. #include "base/bytstrng.h"
  54. #include "base/iterator.h"
  55.  
  56.  
  57. class CL_EXPORT CL_BitSet: public CL_Object {
  58.  
  59. public:
  60.  
  61.     // --------------------- Construction and destruction -------
  62.  
  63.     CL_BitSet  (long max_size = 128);
  64.     // Construct a bitset that can contain at most the elements between 0
  65.     // and max_size-1.
  66.  
  67.     CL_BitSet (long low, long hi, long max_size = 128);
  68.     // Build a set with containing all the numbers in the range
  69.     // low through hi. If {\tt lo < hi}, the empty set is built.
  70.     
  71.     CL_BitSet  (CL_ByteArray& b);
  72.     // Restore this bitset from the given byte array. The latter should
  73.     // contain the passive representation of a BitSet, produced by the
  74.     // WriteTo method on a ByteStream.
  75.  
  76.     CL_BitSet  (const CL_BitSet& b);
  77.     // Copy constructor.
  78.  
  79.     ~CL_BitSet();
  80.     // Destructor.
  81.     
  82.     
  83.  
  84.     // ----------------------- Element methods ------------------
  85.  
  86.     virtual bool Add     (const long& value);
  87.     // Add a value. Return TRUE on success, FALSE if the element was already
  88.     // in the set.
  89.  
  90.     virtual long Remove    (const long& value);
  91.     // Remove a value. Return the removed value if it was already in the
  92.     // set, and 0 otherwise. (This signature matches the one inherited
  93.     // from {\tt IntegerSet}.) This signature 
  94.  
  95.     virtual bool Includes  (const long& value) const;
  96.     // Check whether the given element is in the set.
  97.  
  98.     virtual long Smallest () const;
  99.     // Return the smallest integer in the set. Return -1 if the set is
  100.     // empty.
  101.     
  102.     virtual long Largest () const;
  103.     // Return the largest integer in the set. Return -1 if the set is
  104.     // empty.
  105.     
  106.     virtual long RankOf (const long& v) const;
  107.     // Return the number of elements in this set that are less than v.
  108.     // The parameter v need not be in the set.
  109.     
  110.     virtual long ItemWithRank (long i) const;
  111.     // Given an index $i$ between 0 and Size()-1, return the element of rank
  112.     // $i$, i.e., the element that has $i$ elements less than it in the set.
  113.     // If $i \le 0$, this returns the 
  114.     // smallest element, and if $i \ge {\tt Size()}$, this returns the
  115.     // largest element. If the set is empty, return -1.
  116.     //
  117.     //   Note that it is possible to iterate through the elements of the set
  118.     // via calls to this method, varying the index from 0 to {\tt Size()-1};
  119.     // however, this is very inefficient iteration. Use of the BitSetIterator
  120.     // is the recommended way to inspect all elements of the BitSet.
  121.  
  122.     virtual long Successor (long i) const;
  123.     // Return the least number in the set that is larger than the parameter.
  124.     // Return -1 if the parameter equals or exceeds the largest value in the
  125.     // set.
  126.     
  127.     virtual long SmallestNonMember () const;
  128.     // Return the smallest element that is {\it not\/} in the set. Return -1 if
  129.     // the set is universal.
  130.     
  131.     bool IsEmpty   () const;
  132.     // Return TRUE if the bitset is empty, FALSE otherwise.
  133.  
  134.     virtual long Size     () const;
  135.     // Return the current cardinality of the set.
  136.  
  137.     virtual CL_BitSet operator+ (long value) const;
  138.     // Return a new set which contains our contents augmented with the given
  139.     // value.
  140.     
  141.     // ----------------------- Set methods ----------------------
  142.  
  143.     virtual void MakeEmpty ();
  144.     // Make this the empty set.
  145.     
  146.     virtual void MakeUniversal ();
  147.     // Make this the universal set (i.e., the set containing all elements
  148.     // between 0 and our maximum size possible).
  149.  
  150.     virtual bool IsUniversal () const;
  151.     // Return TRUE if this is this the universal set, FALSE otherwise.
  152.  
  153.     virtual CL_IntegerSet AsSet () const;
  154.     // Convert this bitset into a set of long values, and return the result.
  155.  
  156.     operator CL_IntegerSet() const {return AsSet(); };
  157.     // Convert this bitset into a set of long values, and return the result.
  158.  
  159.     // ----- Comparisons:
  160.     
  161.     virtual bool operator== (const CL_BitSet& o) const;
  162.     
  163.     virtual bool operator== (const CL_IntegerSet& o) const;
  164.     
  165.     // ----- Assignment operators:
  166.     
  167.     virtual void operator= (const CL_Object& o);
  168.     // Check that the class id of the given object is the same as ours,
  169.     // and assign the result to this class. An invalid class id results in
  170.     // a runtime error message.
  171.                      
  172.     virtual CL_BitSet& operator= (const CL_BitSet& s);
  173.     // Assign the given BitSet to this object.
  174.  
  175.     // ----- Binary set operators:
  176.     
  177.     // The binary set operations union, intersection and difference all
  178.     // yield sets whose maximum size is the larger of the maximum sizes of
  179.     // the two operands.
  180.  
  181.     virtual CL_BitSet operator+ (const CL_BitSet& s) const;
  182.     // Return the union of this set and s.
  183.  
  184.     virtual void operator+= (const CL_BitSet& o);
  185.     // Add the elements of o to this set.
  186.  
  187.     virtual CL_BitSet operator- (const CL_BitSet& o) const;
  188.     // Difference: return the set obtained by removing from this set those
  189.     // elements that are common with o.
  190.  
  191.     virtual void operator-= (const CL_BitSet& o);
  192.     // Remove from this set the elements in common with o.
  193.  
  194.     virtual CL_BitSet operator* (const CL_BitSet& o) const;
  195.     // Intersection: Return the set containing the elements common between
  196.     // this set and o.
  197.  
  198.     virtual void operator*= (const CL_BitSet& o);
  199.     // Replace this set by its intersection with o.
  200.  
  201.     virtual CL_BitSet operator^ (const CL_BitSet& o) const;
  202.     // Exclusive-or: Return the set containing the elements not in common
  203.     // between this set and o.
  204.  
  205.     virtual void operator^= (const CL_BitSet& o);
  206.     // Replace this set by its exclusive-or with o.
  207.  
  208.     virtual CL_BitSet operator~ () const;
  209.     // Complementation: Return the set containing those elements not in
  210.     // this set, but in the universal set.
  211.  
  212.     virtual bool IncludesAll (const CL_BitSet& o) const;
  213.     // Return TRUE if this BitSet contains all the elements that o does, and
  214.     // FALSE otherwise.
  215.     
  216.     virtual bool IncludesAll (const CL_IntegerSet& o) const;
  217.     // Return TRUE if this BitSet contains all the elements that o does, and
  218.     // FALSE otherwise.
  219.     
  220.     // --------------------- Saving and restoring -----------------------
  221.     
  222.     long StorableFormWidth () const;
  223.     
  224.     virtual bool ReadFrom (const CL_Stream&);
  225.  
  226.     virtual bool WriteTo  (CL_Stream&) const;
  227.  
  228.  
  229.     // -------------------- Basic inherited methods ---------------------
  230.  
  231.     const char* ClassName() const { return "CL_BitSet";};
  232.  
  233.     CL_ClassId ClassId () const {return _CL_BitSet_CLASSID;};
  234.  
  235.     bool operator== (const CL_Object& o) const;
  236.  
  237.     CL_String AsString () const {return AsSet().AsString (); };
  238.     
  239.     // --------------------- End public protocol ------------------------
  240.  
  241.     
  242. protected:
  243.  
  244.     friend class CL_BitSetIterator;
  245.     
  246.     ulong*  _rep;
  247.     long    _size;  // Current cardinality
  248.     long    _count; // # ulongs in representation
  249.  
  250.     CL_BitSet (long wordCount, ulong array[]);
  251.  
  252.     CL_BitSet _DoOp (const CL_BitSet&, void (*o)(ulong&, ulong)) const;
  253.  
  254. };
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261. // This is an object that allows iteration over a BitSet, and provides the
  262. // usual iteration methods Reset, More and Next.
  263. //
  264. // {\bf Caution.} Do {\it not\/} instantiate a BitSetIterator on an
  265. // IntegerSet; even though the BitSet is derived from IntegerSet, the
  266. // internal representations of the two are very different.
  267.  
  268.  
  269. class CL_EXPORT CL_BitSetIterator: public CL_Iterator<long> {
  270.  
  271. public:
  272.     CL_BitSetIterator (const CL_BitSet& o);
  273.     // Constructor: tells us which set we're inspecting.
  274.  
  275.     void Reset();
  276.     // Reset the cursor to the beginning of the set.
  277.  
  278.     void BeginFromRank (long l);
  279.     // Begin the iteration from the element of rank l. The first call to
  280.     // Next() returns the element of rank l.
  281.     
  282.     bool More ();
  283.     // Are there more elements in the iteration?
  284.  
  285.     const long& Next();
  286.     // Return the next element in sequence. Return -1 if no more. Elements
  287.     // are returned in ascending order.
  288.  
  289. protected:
  290.     const CL_BitSet& _set;         // Our set
  291.     long             _index;       // Index of word being looked at
  292.     long             _count;       // Number of elements returned so far
  293.     long             _tblIndex;    // Index into table of bits
  294.     long             _data;
  295. };
  296.  
  297.  
  298.  
  299.  
  300.  
  301. inline long CL_BitSet::Size     () const
  302. {
  303.     return _size;
  304. }
  305.  
  306.  
  307. inline bool CL_BitSet::IsEmpty () const
  308. {
  309.     return Size() == 0;
  310. }
  311.  
  312. inline void CL_BitSet::operator = (const CL_Object& o)
  313. {
  314.     if (CheckClassType (o, "CL_BitSet::op= (CL_Object&)"))
  315.         *this = ((const CL_BitSet&) o);
  316. };
  317.  
  318.  
  319.  
  320. inline bool CL_BitSet::operator == (const CL_Object& o) const
  321. {
  322.     return IsA(o) ? *this == ((const CL_BitSet&) o) : FALSE;
  323. };
  324.  
  325.  
  326. inline void CL_BitSet::operator += (const CL_BitSet& o)
  327. {
  328.     *this = *this + o;
  329. }
  330.  
  331. inline void CL_BitSet::operator -= (const CL_BitSet& o)
  332. {
  333.     *this = *this - o;
  334. }
  335.  
  336. inline void CL_BitSet::operator *= (const CL_BitSet& o)
  337. {
  338.     *this = *this * o;
  339. }
  340.  
  341.  
  342. inline void CL_BitSet::operator ^= (const CL_BitSet& o)
  343. {
  344.     *this = *this ^ o;
  345. }
  346.  
  347.  
  348. #endif /* _bitset_h_ */
  349.  
  350.  
  351.