home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume19 / wacco / part01 / bitset.C < prev    next >
C/C++ Source or Header  |  1991-05-19  |  6KB  |  328 lines
  1. // Copyright (c) 1991 by Parag Patel.  All Rights Reserved.
  2. // $Header: bitset.C,v 1.3 91/02/22 16:05:27 hmgr Exp $
  3.  
  4. // A set of ints (or an array of bits) is implemented by matching
  5. // each element in the set with its corresponding bit position in
  6. // a word of infinite size.  The word is implemented as an array
  7. // of "long" that is grown in size as necessary.  Thus this set of
  8. // ints is not limited in size, like most Pascal implementations.
  9. //
  10. // By  Parag Patel
  11.  
  12. #include <stdio.h>
  13. #include <stdarg.h>
  14. #include "boolean.h"
  15. #include "bitset.h"
  16.  
  17.  
  18. // the following are machine-dependant - change them if necessary
  19. // sizeof long == 32 bits == 2**5 --> 5, therefore ...
  20. const int NUM = 32;
  21. const int SHIFT = 5;
  22. const int MASK = 0x1F;
  23. const long EMPTY = 0;
  24.  
  25.  
  26. // generic minimum function
  27. static inline int MIN(int i1, int i2)
  28. {
  29.     return i1 < i2 ? i1 : i2;
  30. }
  31.  
  32. // this determines which particular "long" in the array has this element
  33. static inline int ELT(int e)
  34. {
  35.     return e >> SHIFT;
  36. }
  37.  
  38. // this gets the bit position in a "long" for this set element
  39. static inline long BIT(int e)
  40. {
  41.     return ((long)(1L << (e & MASK)));
  42. }
  43.  
  44. // this adds an element to an array of longs
  45. static inline void ADD(long *elts, int e)
  46. {
  47.     elts[ELT(e)] |= BIT(e);
  48. }
  49.  
  50.  
  51. // return a new set of elts - clear it
  52. static long *newelts(int largest)
  53. {
  54.     register long *elts = new long[ELT(largest) + 1];
  55.  
  56.     for (register int i = ELT(largest); i >= 0; i--)
  57.         elts[i] = EMPTY;
  58.     return elts;
  59. }
  60.  
  61. // bump the size of a set
  62. void Bitset::bumpsize(int largest)
  63. {
  64.     if (largest <= num)
  65.         return;
  66.  
  67.     // only re-allocate our array if we are out of ELTs
  68.     if (ELT(largest) != ELT(num))
  69.     {
  70.         register long *ne = newelts(largest);
  71.         for (register int i = ELT(num); i >= 0; i--)
  72.             ne[i] = elts[i];
  73.         delete elts;
  74.         elts = ne;
  75.     }
  76.     num = largest;
  77. }
  78.  
  79. // various constructors:
  80.  
  81. // construct a set from a list of elements
  82. Bitset::Bitset(int e1, int e2 ...)
  83. {
  84.     // if the first element is < 0, we ignore the rest
  85.     if (e1 < 0)
  86.     {
  87.     elts = new long;
  88.     num = 0;
  89.     elts[0] = 0L;
  90.     return;
  91.     }
  92.  
  93.     // the largest element in our list for determining the initial
  94.     // Bitset size
  95.     register int largest = e1 > e2 ? e1 : e2;
  96.     va_list ap;
  97.     register int t;
  98.  
  99.     // if we have more than 3 elements, we need to use varargs
  100.     if (e2 >= 0)
  101.     {
  102.     // find the largest element to be put in the set
  103.     va_start(ap, e2);
  104.     while ((t = va_arg(ap, int)) >= 0)
  105.     if (t > largest)
  106.         largest = t;
  107.     va_end(ap);
  108.     }
  109.  
  110.     // allocate the space for this set
  111.     elts = newelts(num = largest);
  112.  
  113.     // add all the elements to the set
  114.     ADD(elts, e1);
  115.     if (e2 >= 0)
  116.     {
  117.     ADD(elts, e2);
  118.     va_start(ap, e2);
  119.     while ((t = va_arg(ap, int)) >= 0)
  120.         ADD(elts, t);
  121.     va_end(ap);
  122.     }
  123. }
  124.  
  125. // make a new set of the specified size
  126. Bitset::Bitset(int size)
  127. {
  128.     if (size <= 1)
  129.         size = 1;
  130.     elts = newelts(num = size - 1);
  131. }
  132.  
  133. // dup a set
  134. Bitset::Bitset(const Bitset &s)
  135. {
  136.     elts = newelts(num = s.num);
  137.     for (register int i = ELT(s.num); i >= 0; i--)
  138.         elts[i] = s.elts[i];
  139. }
  140.  
  141. // assign a set to a set - also a dup
  142. Bitset &Bitset::operator=(const Bitset &s)
  143. {
  144.     register int i, t;
  145.  
  146.     BUMPSIZE(s.num);
  147.     for (i = t = ELT(s.num); i >= 0; i--)
  148.         elts[i] = s.elts[i];
  149.     for (i = ELT(num); i > t; i--)
  150.         elts[i] = EMPTY;
  151.     return *this;
  152. }
  153.  
  154.  
  155. // add an element to a set
  156. Bitset &Bitset::add(int elt)
  157. {
  158.     if (elt < 0)
  159.         return *this;
  160.     BUMPSIZE(elt);
  161.     elts[ELT(elt)] |= BIT(elt);
  162.     return *this;
  163. }
  164.  
  165. // delete an element from a set
  166. Bitset &Bitset::remove(int elt)
  167. {
  168.     if (elt < 0)
  169.         return *this;
  170.     elts[ELT(elt)] &= ~BIT(elt);
  171.     return *this;
  172. }
  173.  
  174. // union with set
  175. Bitset &Bitset::operator|=(const Bitset &s)
  176. {
  177.     BUMPSIZE(s.num);
  178.     for (register int i = ELT(s.num); i >= 0; i--)
  179.         elts[i] |= s.elts[i];
  180.     return *this;
  181. }
  182.  
  183. // intersect with set
  184. Bitset &Bitset::operator&=(const Bitset &s)
  185. {
  186.     register int t = ELT(s.num);
  187.  
  188.     BUMPSIZE(s.num);
  189.     for (register int i = ELT(num); i >= 0; i--)
  190.         elts[i] &= i <= t ? s.elts[i] : EMPTY;
  191.     return *this;
  192. }
  193.  
  194. // difference from set
  195. Bitset &Bitset::operator-=(const Bitset &s)
  196. {
  197.     for (register int i = MIN(ELT(num), ELT(s.num)); i >= 0; i--)
  198.         elts[i] &= ~s.elts[i];
  199.     return *this;
  200. }
  201.  
  202. // symmetric difference (xor) from set
  203. Bitset &Bitset::operator^=(const Bitset &s)
  204. {
  205.     BUMPSIZE(s.num);
  206.     for (register int i = ELT(s.num); i >= 0; i--)
  207.         elts[i] ^= s.elts[i];
  208.     return *this;
  209. }
  210.  
  211. // complement set
  212. Bitset &Bitset::operator~()
  213. {
  214.     register int i = ELT(num);
  215.  
  216.     elts[i] = ((BIT(num) << 1) - 1) & ~elts[i];
  217.     for (i--; i >= 0; i--)
  218.         elts[i] = ~elts[i];
  219.     return *this;
  220. }
  221.  
  222. // is set a subset of s?
  223. boolean Bitset::operator<=(const Bitset &s) const
  224. {
  225.     register int i = MIN(num, s.num);
  226.  
  227.     for (i = ELT(i); i >= 0; i--)
  228.         if ((elts[i] & s.elts[i]) != elts[i])
  229.             return FALSE;
  230.     if (num <= s.num)
  231.         return TRUE;
  232.  
  233.     register int t = ELT(s.num);
  234.     for (i = ELT(num); i > t; i--)
  235.         if (elts[i])
  236.             return FALSE;
  237.     return TRUE;
  238. }
  239.  
  240. // is set same as s?
  241. boolean Bitset::operator==(const Bitset &s) const
  242. {
  243.     register int i = MIN(num, s.num);
  244.  
  245.     for (i = ELT(i); i >= 0; i--)
  246.         if (elts[i] != s.elts[i])
  247.             return FALSE;
  248.     if (num == s.num)
  249.         return TRUE;
  250.  
  251.     register int t;
  252.     if (num < s.num)
  253.     {
  254.         for (t = ELT(num), i = ELT(s.num); i > t; i--)
  255.             if (s.elts[i])
  256.                 return FALSE;
  257.     }
  258.     else
  259.     {
  260.         for (t = ELT(s.num), i = ELT(num); i > t; i--)
  261.             if (elts[i])
  262.                 return FALSE;
  263.     }
  264.     return TRUE;
  265. }
  266.  
  267.  
  268. // return the number of elements in the set (cardinality)
  269. int Bitset::size() const
  270. {
  271.     register int n = 0;
  272.  
  273.     for (register int i = ELT(num); i >= 0; i--)
  274.         for (register long m = 1; m; m <<= 1)
  275.             if (elts[i] & m)
  276.                 n++;
  277.     return n;
  278. }
  279.  
  280. // clear the set of all elements
  281. void Bitset::clear()
  282. {
  283.     for (register int i = ELT(num); i >= 0; i--)
  284.         elts[i] = EMPTY;
  285. }
  286.  
  287. // return a hash number for this set
  288. unsigned long Bitset::hash() const
  289. {
  290.     register int i = ELT(num);
  291.  
  292.     // skip over null elements in array to make
  293.     // hash value independent of size
  294.     while (i >= 0 && elts[i] == 0)
  295.         i--;
  296.  
  297.     // now we can hash safely...
  298.     register unsigned long h = 0;
  299.     for (; i >= 0; i--)
  300.     {
  301.         // "+" moves around the bits a lot better than "^"
  302.         h += elts[i];
  303.         // rotate "h" left by 3 bits, just to mix things up
  304.         h = (h << 3) | (h >> (NUM - 3));
  305.     }
  306.  
  307.     return h;
  308. }
  309.  
  310.  
  311.  
  312. // set iterator class:
  313.  
  314. // creator
  315. Bitsetiter::Bitsetiter(const Bitset &s)
  316. {
  317.     int i, e;
  318.     int num = 0;
  319.  
  320.     arr = new int[len = s.size()];
  321.     int t = ELT(s.num);
  322.     for (e = 0, i = 0; i <= t; i++)
  323.         for (long m = 1; m; e++, m <<= 1)
  324.             if (s.elts[i] & m)
  325.                 arr[num++] = e;
  326.     elt = 0;
  327. }
  328.