home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / rxbitset.c < prev    next >
C/C++ Source or Header  |  1995-12-31  |  7KB  |  371 lines
  1. /***********************************************************
  2.  
  3. Copyright 1995 by Tom Lord
  4.  
  5.                         All Rights Reserved
  6.  
  7. Permission to use, copy, modify, and distribute this software and its 
  8. documentation for any purpose and without fee is hereby granted, 
  9. provided that the above copyright notice appear in all copies and that
  10. both that copyright notice and this permission notice appear in 
  11. supporting documentation, and that the name of the copyright holder not be
  12. used in advertising or publicity pertaining to distribution of the
  13. software without specific, written prior permission.  
  14.  
  15. Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  16. INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  17. EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  18. CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  19. USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  20. OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  21. PERFORMANCE OF THIS SOFTWARE.
  22.  
  23. ******************************************************************/
  24.  
  25.  
  26. /*
  27.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  28.  */
  29.  
  30.  
  31. #include "rxall.h"
  32. #include "rxbitset.h"
  33.  
  34.  
  35. #ifdef __STDC__
  36. int
  37. rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
  38. #else
  39. int
  40. rx_bitset_is_equal (size, a, b)
  41.      int size;
  42.      rx_Bitset a;
  43.      rx_Bitset b;
  44. #endif
  45. {
  46.   int x;
  47.   RX_subset s;
  48.  
  49.   if (size == 0)
  50.     return 1;
  51.  
  52.   s = b[0];
  53.   b[0] = ~a[0];
  54.  
  55.   for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
  56.     ;
  57.  
  58.   b[0] = s;
  59.   return !x && (s == a[0]);
  60. }
  61.  
  62.  
  63. #ifdef __STDC__
  64. int
  65. rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
  66. #else
  67. int
  68. rx_bitset_is_subset (size, a, b)
  69.      int size;
  70.      rx_Bitset a;
  71.      rx_Bitset b;
  72. #endif
  73. {
  74.   int x;
  75.   x = rx_bitset_numb_subsets(size) - 1;
  76.   while (x-- && ((a[x] & b[x]) == a[x]));
  77.   return x == -1;
  78. }
  79.  
  80.  
  81. #ifdef __STDC__
  82. int
  83. rx_bitset_empty (int size, rx_Bitset set)
  84. #else
  85. int
  86. rx_bitset_empty (size, set)
  87.      int size;
  88.      rx_Bitset set;
  89. #endif
  90. {
  91.   int x;
  92.   RX_subset s;
  93.   s = set[0];
  94.   set[0] = 1;
  95.   for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
  96.     ;
  97.   set[0] = s;
  98.   return !s;
  99. }
  100.  
  101. #ifdef __STDC__
  102. void
  103. rx_bitset_null (int size, rx_Bitset b)
  104. #else
  105. void
  106. rx_bitset_null (size, b)
  107.      int size;
  108.      rx_Bitset b;
  109. #endif
  110. {
  111.   bzero (b, rx_sizeof_bitset(size));
  112. }
  113.  
  114.  
  115. #ifdef __STDC__
  116. void
  117. rx_bitset_universe (int size, rx_Bitset b)
  118. #else
  119. void
  120. rx_bitset_universe (size, b)
  121.      int size;
  122.      rx_Bitset b;
  123. #endif
  124. {
  125.   int x = rx_bitset_numb_subsets (size);
  126.   while (x--)
  127.     *b++ = ~(RX_subset)0;
  128. }
  129.  
  130.  
  131. #ifdef __STDC__
  132. void
  133. rx_bitset_complement (int size, rx_Bitset b)
  134. #else
  135. void
  136. rx_bitset_complement (size, b)
  137.      int size;
  138.      rx_Bitset b;
  139. #endif
  140. {
  141.   int x = rx_bitset_numb_subsets (size);
  142.   while (x--)
  143.     {
  144.       *b = ~*b;
  145.       ++b;
  146.     }
  147. }
  148.  
  149.  
  150. #ifdef __STDC__
  151. void
  152. rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
  153. #else
  154. void
  155. rx_bitset_assign (size, a, b)
  156.      int size;
  157.      rx_Bitset a;
  158.      rx_Bitset b;
  159. #endif
  160. {
  161.   int x;
  162.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  163.     a[x] = b[x];
  164. }
  165.  
  166.  
  167. #ifdef __STDC__
  168. void
  169. rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
  170. #else
  171. void
  172. rx_bitset_union (size, a, b)
  173.      int size;
  174.      rx_Bitset a;
  175.      rx_Bitset b;
  176. #endif
  177. {
  178.   int x;
  179.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  180.     a[x] |= b[x];
  181. }
  182.  
  183.  
  184. #ifdef __STDC__
  185. void
  186. rx_bitset_intersection (int size,
  187.             rx_Bitset a, rx_Bitset b)
  188. #else
  189. void
  190. rx_bitset_intersection (size, a, b)
  191.      int size;
  192.      rx_Bitset a;
  193.      rx_Bitset b;
  194. #endif
  195. {
  196.   int x;
  197.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  198.     a[x] &= b[x];
  199. }
  200.  
  201.  
  202. #ifdef __STDC__
  203. void
  204. rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
  205. #else
  206. void
  207. rx_bitset_difference (size, a, b)
  208.      int size;
  209.      rx_Bitset a;
  210.      rx_Bitset b;
  211. #endif
  212. {
  213.   int x;
  214.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  215.     a[x] &=  ~ b[x];
  216. }
  217.  
  218.  
  219. #ifdef __STDC__
  220. void
  221. rx_bitset_revdifference (int size,
  222.              rx_Bitset a, rx_Bitset b)
  223. #else
  224. void
  225. rx_bitset_revdifference (size, a, b)
  226.      int size;
  227.      rx_Bitset a;
  228.      rx_Bitset b;
  229. #endif
  230. {
  231.   int x;
  232.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  233.     a[x] = ~a[x] & b[x];
  234. }
  235.  
  236. #ifdef __STDC__
  237. void
  238. rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
  239. #else
  240. void
  241. rx_bitset_xor (size, a, b)
  242.      int size;
  243.      rx_Bitset a;
  244.      rx_Bitset b;
  245. #endif
  246. {
  247.   int x;
  248.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  249.     a[x] ^= b[x];
  250. }
  251.  
  252.  
  253. #ifdef __STDC__
  254. unsigned long
  255. rx_bitset_hash (int size, rx_Bitset b)
  256. #else
  257. unsigned long
  258. rx_bitset_hash (size, b)
  259.      int size;
  260.      rx_Bitset b;
  261. #endif
  262. {
  263.   int x;
  264.   unsigned long answer;
  265.  
  266.   answer = 0;
  267.  
  268.   for (x = 0; x < size; ++x)
  269.     {
  270.       if (RX_bitset_member (b, x))
  271.     answer += (answer << 3) + x;
  272.     }
  273.   return answer;
  274. }
  275.  
  276.  
  277. RX_subset rx_subset_singletons [RX_subset_bits] = 
  278. {
  279.   0x1,
  280.   0x2,
  281.   0x4,
  282.   0x8,
  283.   0x10,
  284.   0x20,
  285.   0x40,
  286.   0x80,
  287.   0x100,
  288.   0x200,
  289.   0x400,
  290.   0x800,
  291.   0x1000,
  292.   0x2000,
  293.   0x4000,
  294.   0x8000,
  295.   0x10000,
  296.   0x20000,
  297.   0x40000,
  298.   0x80000,
  299.   0x100000,
  300.   0x200000,
  301.   0x400000,
  302.   0x800000,
  303.   0x1000000,
  304.   0x2000000,
  305.   0x4000000,
  306.   0x8000000,
  307.   0x10000000,
  308.   0x20000000,
  309.   0x40000000,
  310.   0x80000000
  311. };
  312.  
  313.  
  314. /* 
  315.  * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
  316.  * (define lb (map (lambda (n) (number->string n 2)) l))
  317.  * (define lc (map string->list lb))
  318.  * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
  319.  * (define lt (map (lambda (l) (apply + l)) ln))
  320.  */
  321.  
  322. static int char_pops[256] = 
  323. {
  324.   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  325.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  326.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  327.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  328.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  329.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  330.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  331.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  332.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  333.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  334.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  335.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  336.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  337.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  338.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  339.   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  340. };
  341.  
  342. #define RX_char_population(C) (char_pops[C])
  343.  
  344. #ifdef __STDC__
  345. int
  346. rx_bitset_population (int size, rx_Bitset a)
  347. #else
  348. int
  349. rx_bitset_population (size, a)
  350.      int size;
  351.      rx_Bitset a;
  352. #endif
  353. {
  354.   int x;
  355.   int total;
  356.   unsigned char s;
  357.  
  358.   if (size == 0)
  359.     return 0;
  360.  
  361.   total = 0;
  362.   x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1;
  363.   while (x >= 0)
  364.     {
  365.       s = ((unsigned char *)a)[x];
  366.       --x;
  367.       total = total + RX_char_population (s);
  368.     }
  369.   return total;
  370. }     
  371.