home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / bitset.cxx < prev    next >
C/C++ Source or Header  |  1995-04-09  |  17KB  |  775 lines
  1.  
  2.  
  3.  
  4.  
  5. /*
  6.  *
  7.  *          Copyright (C) 1994, M. A. Sridhar
  8.  *  
  9.  *
  10.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  11.  *     to copy, modify or distribute this software  as you see fit,
  12.  *     and to use  it  for  any  purpose, provided   this copyright
  13.  *     notice and the following   disclaimer are included  with all
  14.  *     copies.
  15.  *
  16.  *                        DISCLAIMER
  17.  *
  18.  *     The author makes no warranties, either expressed or implied,
  19.  *     with respect  to  this  software, its  quality, performance,
  20.  *     merchantability, or fitness for any particular purpose. This
  21.  *     software is distributed  AS IS.  The  user of this  software
  22.  *     assumes all risks  as to its quality  and performance. In no
  23.  *     event shall the author be liable for any direct, indirect or
  24.  *     consequential damages, even if the  author has been  advised
  25.  *     as to the possibility of such damages.
  26.  *
  27.  */
  28.  
  29.  
  30.  
  31.  
  32. #if defined(__GNUC__)
  33. #pragma implementation
  34. #endif
  35.  
  36.  
  37.  
  38. #include "base/bitset.h"
  39. #include "base/bytestrm.h"
  40. #include "base/intset.h"
  41.  
  42. static const short BitsInLong = sizeof (ulong)*8;
  43.  
  44. // The following inline functions are used for indexing into the array of
  45. // ulong's, and assume that a ulong has 32 bits.
  46. inline long __Div32 (long x)
  47. {
  48.     return (x >> 5) & ((1L << 27) - 1);
  49. }
  50.  
  51. inline short __Mod32 (long x)
  52. {
  53.     return x & ((1L << 5) - 1);
  54. }
  55.  
  56. inline ulong __Mul32 (long x)
  57. {
  58.     return x << 5;
  59. }
  60.  
  61.  
  62. static ulong __FAR BitTable [32] = {
  63.     0x00000001L, 0x00000002L, 0x00000004L, 0x00000008L,
  64.     0x00000010L, 0x00000020L, 0x00000040L, 0x00000080L,
  65.     0x00000100L, 0x00000200L, 0x00000400L, 0x00000800L,
  66.     0x00001000L, 0x00002000L, 0x00004000L, 0x00008000L,
  67.     0x00010000L, 0x00020000L, 0x00040000L, 0x00080000L,
  68.     0x00100000L, 0x00200000L, 0x00400000L, 0x00800000L,
  69.     0x01000000L, 0x02000000L, 0x04000000L, 0x08000000L,
  70.     0x10000000L, 0x20000000L, 0x40000000L, 0x80000000L
  71. };
  72.  
  73. static short BitCount (ulong n)
  74. {
  75.     short count = 0;
  76.     while (n != 0) {
  77.         n &= n-1;
  78.         count++;
  79.     }
  80.     return count;
  81. }
  82.  
  83.  
  84.  
  85. inline bool DoAdd (ulong _rep[], long value)
  86. {
  87.     ulong mask = (1L << (__Mod32 (value)));
  88. #if defined(__DOS__) || defined(__MS_WINDOWS__)
  89.     short index = __Div32 (value);
  90. #else
  91.     long index = __Div32 (value);
  92. #endif
  93.     register long b =  (_rep [index] & mask);
  94.     if (!b)
  95.         _rep[index] |= mask;
  96.     return !b;
  97. }
  98.  
  99.  
  100. CL_DEFINE_CLASS(CL_BitSet, _CL_Sequence_CLASSID);
  101.  
  102. CL_BitSet::CL_BitSet  (long max_size)
  103. {
  104.     long div = __Div32 (max_size);
  105.     long mod = __Mod32 (max_size);
  106.     _count = (mod == 0) ? div : div+1;
  107. #if defined(__DOS__) || defined(__MS_WINDOWS__)
  108.     _rep = new ulong [(short) _count];
  109. #else
  110.     _rep = new ulong [_count];
  111. #endif
  112.     if (!_rep) {
  113.         _count = 0;
  114.         return;
  115.     }
  116.     register ulong* p = _rep;
  117.     for (register long i = 0; i < _count; i++)
  118.         *p++ = 0L;
  119.     _size = 0;
  120. }
  121.  
  122. CL_BitSet::CL_BitSet  (const CL_BitSet& o)
  123. {
  124.     _count = o._count;
  125.     _rep = new ulong [_count];
  126.     if (!_rep) {
  127.         _count = 0;
  128.         return;
  129.     }
  130.     register ulong *p, *q;
  131.     p = _rep; q = o._rep;
  132.     for (long i = 0; i < _count; i++)
  133.         *p++ = *q++;
  134.     _size = o._size;
  135. }
  136.  
  137.  
  138. CL_BitSet::CL_BitSet (long lo, long hi, long max_size)
  139. {
  140.     long div = __Div32 (max_size);
  141.     long mod = __Mod32 (max_size);
  142.     _count = (mod == 0) ? div : div+1;
  143.     _rep = new ulong [_count];
  144.     if (!_rep) {
  145.         _count = 0;
  146.         return;
  147.     }
  148.     register ulong* p = _rep;
  149.     long i;
  150.     for (i = 0; i < _count; i++)
  151.         *p++ = 0L;
  152.     _size = 0;
  153.     for (i = lo; i <= hi; i++)
  154.         Add (i);
  155. }
  156.  
  157. CL_BitSet::CL_BitSet  (CL_ByteArray& o)
  158. {
  159.     CL_ByteStream s (o);
  160.     ReadFrom (s);
  161. }
  162.  
  163.  
  164. // Protected constructor
  165. CL_BitSet::CL_BitSet (long wordCount, ulong* array)
  166. {
  167.     _rep = array;
  168.     _size = 0;
  169.     _count = wordCount;
  170.     for (long i = 0; i < _count; i++) {
  171.         _size += BitCount (_rep[i]);
  172.     }
  173. }
  174.  
  175.  
  176. CL_BitSet::~CL_BitSet ()
  177. {
  178.     if (_rep)
  179.         delete [] _rep;
  180. }
  181.  
  182.  
  183.  
  184. // ----------------------- Element methods ------------------
  185.  
  186. bool CL_BitSet::Includes     (const long& value) const
  187. {
  188.     if (value < 0 || value >= __Mul32 (_count))
  189.         return FALSE;
  190.     return (_rep [__Div32 (value)] &
  191.             (1L << (__Mod32 (value)))) ? TRUE : FALSE;
  192. }
  193.  
  194. long CL_BitSet::Remove    (const long& value)
  195. {
  196.     if (!PrepareToChange())
  197.         return FALSE;
  198.     if (value < 0 || value >= __Mul32 (_count))
  199.         return 0;
  200.     long index = __Div32(value);
  201.     ulong mask = 1L << __Mod32 (value);
  202.     if (!(_rep [index] & mask))
  203.         return 0;
  204.     _rep[index] &= ~mask;
  205.     _size --;
  206.     Notify();
  207.     return value;
  208. }
  209.  
  210.  
  211.  
  212. bool CL_BitSet::Add  (const long& value)
  213. {
  214.     if (!PrepareToChange())
  215.         return FALSE;
  216.     if (value < 0 || value >= __Mul32 (_count))
  217.         return FALSE;
  218.     if (DoAdd (_rep, value)) {
  219.         _size++;
  220.         Notify();
  221.         return TRUE;
  222.     }
  223.     return FALSE;
  224. }
  225.  
  226.  
  227. long CL_BitSet::Largest () const
  228. {
  229.     // This implementation is likely to be more efficient than simply using
  230.     // ItemWithRank.
  231.     if (_size <= 0)
  232.         return -1;
  233.     register long i = _count-1;
  234.     register ulong* p = _rep + i;
  235.     while (i >= 0 && *p == 0)
  236.         i--, p--;
  237.     if (i < 0) {
  238.         // Can't be: we checked for size > 0 already
  239.         CL_Error::Warning ("CL_BitSet::Largest: internal error");
  240.         return -1;
  241.     }
  242.     register ulong data = *p;
  243.     for (short j = 31; j >= 0; j--) {
  244.         if (data & BitTable[j])
  245.             break;
  246.     }
  247.     return __Mul32(i) + j;
  248. }
  249.  
  250.  
  251. long CL_BitSet::Smallest () const
  252. {
  253.     // This implementation is likely to be more efficient than simply using
  254.     // ItemWithRank.
  255.     if (_size <= 0)
  256.         return -1;
  257.     register short i = 0;
  258.     register ulong* p = _rep;
  259.     while (i < _count && *p == 0)
  260.         i++, p++;
  261.     if (i >= _count) {
  262.         // Can't be: we checked for size > 0 already
  263.         CL_Error::Warning ("CL_BitSet::Smallest: internal error");
  264.         return 0;
  265.     }
  266.     register ulong data = *p;
  267.     for (short j = 0; j < 32; j++) {
  268.         if (data & BitTable[j])
  269.             break;
  270.     }
  271.     return __Mul32 (i) + j;
  272. }
  273.  
  274.  
  275.  
  276.  
  277. long  CL_BitSet::Successor (long n) const
  278. {
  279.     if (_size <= 0)
  280.         return -1;
  281.     long index = __Div32 (n);
  282.     short offs = __Mod32 (n);
  283.     if (index >= _count)
  284.         return -1;
  285.     else if (index < 0)
  286.         index = 0;
  287.     register ulong word = _rep[index];
  288.     register short j;
  289.     // See if next larger element is in the same long cell as n
  290.     for (j = offs+1; j < BitsInLong; j++)
  291.         if (BitTable [j] & word)
  292.             return __Mul32 (index) + j;
  293.  
  294.     // No, it isn't. Scan the rest of the cells, from index+1 up
  295.     register long i;
  296.     for (i = index+1; i < _count; i++) {
  297.         word = _rep[i];
  298.         if (word)
  299.             break;
  300.     }
  301.     if (i >= _count)
  302.         return -1;
  303.     for (j = 0; j < BitsInLong; j++)
  304.         if (word & BitTable[j])
  305.             return __Mul32 (i) + j;
  306.     // Huh? We found a non-zero cell, but no 1-bit in it??
  307.     CL_Error::Warning ("BitSet::Successor: internal error");
  308.     return -1;
  309. }
  310.  
  311.  
  312. long  CL_BitSet::SmallestNonMember () const
  313. {
  314.     if (_size <= 0)
  315.         return 0;
  316.     if (_size == __Mul32 (_count))
  317.         return -1;
  318.     register long i = 0;
  319.     register ulong* p = _rep;
  320.     while (i < _count && *p == (ulong) -1)
  321.         i++, p++;
  322.     if (i >= _count)
  323.         return __Mul32 (_count);
  324.     register ulong data = ~ (*p);
  325.     for (short j = 0; j < 32; j++) {
  326.         if (data & BitTable[j])
  327.             break;
  328.     }
  329.     return __Mul32(i) + j;
  330. }
  331.  
  332.  
  333. long CL_BitSet::RankOf (const long& value) const
  334. {
  335.     if (_size <= 0 || value <= 0)
  336.         return 0;
  337.     long index = minl (__Div32(value), _count-1);
  338.     register long mod32 = __Mod32 (value);
  339.     ulong mask = (-1L) << mod32; // Shift in zeros at right
  340.     long rank = 0;
  341.     for (register long i = 0; i < index; i++)
  342.         rank += BitCount (_rep[i]);
  343.     register ulong tmp = _rep[index];
  344.     rank += BitCount (tmp & ~mask);
  345.     return rank;
  346. }
  347.  
  348.  
  349.  
  350. long CL_BitSet::ItemWithRank (long rank) const
  351. {
  352.     if (_size <= 0)
  353.         return -1;
  354.     rank = maxl (0, minl (rank, _size - 1));
  355.     long r = 0, l = 0;
  356.     for (long i = 0; i < _count; i++) {
  357.         l = BitCount (_rep[i]);
  358.         if (r + l > rank)
  359.             break;
  360.         r += l;
  361.     }
  362.     if (i >= _count) // We've looked at all the words in _rep
  363.         i = _count-1;
  364.     long m = _rep[i];
  365.     for (short j = 0; j < 32; j++) {
  366.         if (m & 1) {
  367.             if (r == rank)
  368.                 break;
  369.             r++;
  370.         }
  371.         m >>= 1;
  372.     }
  373.     return __Mul32(i) + j;
  374. }
  375.  
  376.  
  377.  
  378. CL_BitSet CL_BitSet::operator + (long value) const
  379. {
  380.     CL_BitSet s (*this);
  381.     s.Add (value);
  382.     return s;
  383. }
  384.  
  385.  
  386. // void CL_BitSet::operator= (const CL_Set<long>& s)
  387. // {
  388. //     if (!PrepareToChange ())
  389. //         return;
  390. //     if (this == &s)
  391. //         return;
  392. //     MakeEmpty();
  393. //     long n = s.Size();
  394. //     for (long i = 0; i < n; i++)
  395. //         Add (s.ItemWithRank(i));
  396. //     Notify ();
  397. // }
  398.  
  399. // void CL_BitSet::operator= (const CL_Sequence<long>& s)
  400. // {
  401. //     if (!PrepareToChange ())
  402. //         return;
  403. //     MakeEmpty();
  404. //     register long n = s.Size();
  405. //     for (long i = 0; i < n; i++)
  406. //         Add (s[i]);
  407. //     Notify ();
  408. // }
  409.  
  410. // ----------------------- Set methods ----------------------
  411.  
  412. void CL_BitSet::MakeEmpty ()
  413. {
  414.     if (!PrepareToChange())
  415.         return;
  416.     ulong* p = _rep;
  417.     for (long i = 0; i < _count; i++)
  418.         *p++ = (ulong) 0;
  419.     _size = 0;
  420.     Notify();
  421. }
  422.  
  423.  
  424.  
  425. // Make this the universal set:
  426. void CL_BitSet::MakeUniversal ()
  427. {
  428.     if (!PrepareToChange())
  429.         return;
  430.     register ulong* p = _rep;
  431.     for (register long i = 0; i < _count; i++)
  432.         *p++ = (ulong) (-1);
  433.     _size = __Mul32 (_count);
  434.     Notify();
  435. }
  436.  
  437.  
  438. bool CL_BitSet::IsUniversal () const
  439. {
  440.     return Size() == __Mul32 (_count);
  441. }
  442.  
  443. CL_IntegerSet CL_BitSet::AsSet () const
  444. {
  445.     CL_IntegerSet aSet;
  446.     
  447.     long offset = 0;
  448.     for (long i = 0; i < _count; i++, offset += BitsInLong) {
  449.         register ulong mask = 1;
  450.         register ulong data = _rep[i];
  451.         for (short j = 0; j < BitsInLong; j++) {
  452.             if (data & mask)
  453.                 aSet.Add (offset + j);
  454.             mask <<= 1;
  455.         }
  456.     }
  457.     return aSet;
  458. }
  459.  
  460.  
  461.             
  462. CL_BitSet& CL_BitSet::operator = (const CL_BitSet& o)
  463. {
  464.     if (!PrepareToChange())
  465.         return *this;
  466.     if (_count != o._count) {
  467.         delete [] _rep;
  468.         _rep = new ulong[_count = o._count];
  469.         if (!_rep) {
  470.             _count = 0;
  471.             return *this;
  472.         }
  473.     }
  474.     for (long i = 0; i < _count; i++)
  475.         _rep[i] = o._rep[i];
  476.     _size = o._size;
  477.     Notify();
  478.     return *this;
  479. }
  480.  
  481.  
  482.  
  483.  
  484.  
  485. static void DoOr (ulong& w1, ulong w2)
  486. {
  487.     w1 |= w2;
  488. }
  489.  
  490.  
  491. static void DoAnd (ulong& w1, ulong w2)
  492. {
  493.     w1 &= w2;
  494. }
  495.  
  496.  
  497. static void DoDiff (ulong& w1, ulong w2)
  498. {
  499.     w1 &= ~w2;
  500. }
  501.  
  502. static void DoXor  (ulong& w1, ulong w2)
  503. {
  504.     w1 ^= w2;
  505. }
  506.  
  507.  
  508.  
  509. CL_BitSet CL_BitSet::_DoOp (const CL_BitSet& s, void (*opr)(ulong&, ulong))
  510.     const
  511. {
  512.     long cnt = maxl (s._count, _count);
  513.     ulong* new_rep = new ulong[cnt];
  514.     if (! new_rep)
  515.         return *this; // No memory
  516.     for (long i = 0; i < cnt; i++)
  517.         new_rep[i] = (i < _count) ? _rep[i] : 0;
  518.     for (i = 0; i < s._count; i++) {
  519.         (*opr) (new_rep[i], s._rep[i]);
  520.     }
  521.     CL_BitSet o (cnt, new_rep);
  522.     return o;
  523. }
  524.  
  525.  
  526. // Union:
  527. CL_BitSet CL_BitSet::operator + (const CL_BitSet& s) const
  528. {
  529.     return _DoOp (s, DoOr);
  530. }
  531.  
  532.  
  533.  
  534. // Difference:
  535. CL_BitSet CL_BitSet::operator - (const CL_BitSet& s) const
  536. {
  537.     return _DoOp (s, DoDiff);
  538. }
  539.  
  540.  
  541.  
  542. // Intersection:
  543. CL_BitSet CL_BitSet::operator * (const CL_BitSet& s) const
  544. {
  545.     return _DoOp (s, DoAnd);
  546. }
  547.  
  548.  
  549. // Ex-or:
  550. CL_BitSet CL_BitSet::operator ^ (const CL_BitSet& s) const
  551. {
  552.     return _DoOp (s, DoXor);
  553. }
  554.  
  555.  
  556.  
  557.  
  558. // Complement:
  559. CL_BitSet CL_BitSet::operator ~ () const
  560. {
  561.     CL_BitSet s (*this);
  562.     for (long i = 0; i < _count; i++)
  563.         s._rep[i] = ~s._rep[i];
  564.     s._size = s._count * BitsInLong - _size;
  565.     return s;
  566. }
  567.  
  568.  
  569. bool CL_BitSet::operator == (const CL_IntegerSet& o) const
  570. {
  571.     if (Size() != o.Size())
  572.         return FALSE;
  573.     for (long i = 0; i < _count; i++) {
  574.         ulong b = _rep[i];
  575.         for (short j = 0; j < BitsInLong; j++) {
  576.             if (b & 1)
  577.                 if (!o.Includes (i*BitsInLong + j))
  578.                     return FALSE;
  579.             b >>= 1;
  580.         }
  581.     }
  582.     return TRUE;
  583. }
  584.  
  585.  
  586. bool CL_BitSet::operator == (const CL_BitSet& o) const
  587. {
  588.     if (_size != o._size)
  589.         return FALSE;
  590.     for (long i = 0; i < minl (o._count, _count); i++) {
  591.         if (_rep[i] != o._rep[i])
  592.             return FALSE;
  593.     }
  594.     return TRUE;
  595. }
  596.  
  597.  
  598.  
  599. bool CL_BitSet::IncludesAll (const CL_IntegerSet& o) const
  600. {
  601.     long n = o.Size();
  602.     for (long i = 0; i < n; i++)
  603.         if (!Includes (o.ItemWithRank(i)))
  604.             return FALSE;
  605.     return TRUE;
  606. }
  607.  
  608.  
  609. bool CL_BitSet::IncludesAll (const CL_BitSet& o) const
  610. {
  611.     if (_size < o._size)
  612.         return FALSE;
  613.     register long n;
  614.     if (o._count > _count) {
  615.         for (register long i = _count; i < o._count; i++)
  616.             if (o._rep[i] != 0)
  617.                 return FALSE;
  618.         n = _count;
  619.     }
  620.     else
  621.         n = o._count;  // n is the smaller of the two counts
  622.     for (register long i = 0; i < n; i++) {
  623.         register ulong p = _rep[i];
  624.         register ulong q = o._rep[i];
  625.         if ((p | q) != p)
  626.             return FALSE;
  627.     }
  628.     return TRUE;
  629. }
  630.  
  631.  
  632.  
  633. // ------------------------ Save/restore -------------------------
  634.  
  635. long CL_BitSet::StorableFormWidth() const
  636. {
  637.     return sizeof (CL_ClassId) + sizeof (long) + sizeof (ulong) +
  638.         _count*sizeof (ulong);
  639. }
  640.  
  641.  
  642.  
  643. bool CL_BitSet::ReadFrom (const CL_Stream& s)
  644. {
  645.     if (!PrepareToChange())
  646.         return 0;
  647.     if (!ReadClassId (s))
  648.         return FALSE;
  649.     long  new_count;
  650.     if (!s.Read (new_count))
  651.         return FALSE;
  652.     if (!s.Read (_size))
  653.         return FALSE;
  654.     if (new_count != _count) {
  655.         ulong* new_rep   = new ulong [new_count];
  656.         if (!new_rep) 
  657.             return FALSE; // No memory
  658.         if (_rep)
  659.             delete [] _rep;
  660.         _rep = new_rep;
  661.         _count = new_count;
  662.     }
  663.     if (!s.Read ((uchar*) _rep, _count*sizeof(ulong)))
  664.         return FALSE;
  665. //     _size = 0;
  666. //     for (long i = 0; i < _count; i++) {
  667. //         _size += BitCount (_rep[i]);
  668. //     }
  669.     Notify();
  670.     return TRUE;
  671. }
  672.  
  673. bool CL_BitSet::WriteTo  (CL_Stream& s) const
  674. {
  675.     return s.Write (ClassId())  &&
  676.         s.Write (_count) && s.Write (_size) &&
  677.         s.Write ((uchar*) _rep, _count*sizeof(ulong));
  678. }
  679.  
  680.  
  681.  
  682.  
  683. // ---------------------- BitSetIterator methods ----------------------
  684.  
  685.  
  686.  
  687. CL_BitSetIterator::CL_BitSetIterator (const CL_BitSet& o)
  688. : _set (o)
  689. {
  690.     _count = _index = 0;
  691.     _tblIndex = 0;
  692. }
  693.  
  694.  
  695.  
  696.  
  697.  
  698. void CL_BitSetIterator::Reset ()
  699. {
  700.     _index = _count = 0;
  701.     _tblIndex = 0;
  702. }
  703.  
  704.  
  705.  
  706. void CL_BitSetIterator::BeginFromRank (long l)
  707. {
  708.     register ulong* p = _set._rep;
  709.     _count = maxl (0, l);
  710.     if (!p)
  711.         return;
  712.     for (register long i = 0; i < _set._count; i++, p++) {
  713.         short q = BitCount (*p);
  714.         if (l < q) break;
  715.         l -= q;
  716.     }
  717.     _index = i;
  718.     if (i < _set._count) {
  719.         register ulong r = _set._rep[i];
  720.         register short j;
  721.         for (j = 0; j < BitsInLong; j++)
  722.             if (BitTable[j] & r) {
  723.                 l--;
  724.                 if (l < 0)
  725.                     break;
  726.             }
  727.         _tblIndex = j;
  728.             
  729.     }
  730. }
  731.  
  732.  
  733.  
  734. bool CL_BitSetIterator::More ()
  735. {
  736.     return _count < _set.Size();
  737. }
  738.  
  739.  
  740. const long& CL_BitSetIterator::Next ()
  741. {
  742.     if (_count >= _set.Size()) {
  743.         _data = -1;
  744.         return _data;
  745.     }
  746.     ulong* p = _set._rep;
  747.     while (_index < _set._count) {
  748.         ulong mask =  BitTable[_tblIndex];
  749.     if (mask & p[_index]) break;
  750.         _tblIndex++;
  751.         if (_tblIndex >= BitsInLong) {
  752.             _tblIndex = 0;
  753.             _index++;
  754.         }
  755.     }
  756.     if (_index < _set._count) {
  757.         _data = __Mul32 (_index) + _tblIndex;
  758.         _count++;
  759.         _tblIndex++;
  760.         if (_tblIndex >= BitsInLong) {
  761.             _tblIndex = 0;
  762.             _index++;
  763.         }
  764.     }
  765.     else
  766.         _data = -1;
  767.     return _data;
  768. }
  769.  
  770.  
  771.  
  772.  
  773.  
  774.  
  775.