cset.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257
  1. /* $Id$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. /* S H A R E D F I L E
  7. *
  8. * C S E T . C
  9. */
  10. #include "types.h"
  11. #include "cset.h"
  12. #include "alloc.h"
  13. #include "debug.h"
  14. #include "global.h"
  15. /* A set over a range of integers from 1 to N may be represented
  16. * as a 'compact' set. Such a set is represented as a 'bitvector'
  17. * record, containing the size of the set (i.e. N) and a row
  18. * of words (the bitvector itself). An integer J (1 <= J <= N) is
  19. * an element of the set iff the J-th bit of the vector is a '1'.
  20. * Any redundant bits in the last word are garanteed to be zero bits.
  21. * This package implements the usual operations on sets.
  22. * The name of every operation is preceede by a 'C' to
  23. * distinguish it from the operation on 'long' (list)
  24. * sets whth a similar name.
  25. */
  26. /* The two arithmetic operations 'divide by wordlength' and
  27. * 'modulo wordlength' can be performed very efficiently
  28. * if the word length (of the source machine) is 16.
  29. */
  30. cset Cempty_set(short n)
  31. {
  32. cset s;
  33. s = newbitvect(DIVWL(n-1) + 1);
  34. s->v_size = n;
  35. return s;
  36. }
  37. bool Cis_elem(Celem_t x, cset s)
  38. {
  39. short n;
  40. int mask;
  41. assert(x>0 && x <= s->v_size);
  42. n = DIVWL(x-1);
  43. mask = (1 << MODWL(x-1));
  44. if ((s->v_bits[n] & mask) == 0) {
  45. return FALSE;
  46. } else {
  47. return TRUE;
  48. }
  49. }
  50. void Cadd(Celem_t x, cset *s_p)
  51. {
  52. cset s;
  53. short n;
  54. int mask;
  55. s = *s_p;
  56. assert(x>0 && x <= s->v_size);
  57. n = DIVWL(x-1);
  58. mask = (1 << MODWL(x-1));
  59. s->v_bits[n] |= mask;
  60. }
  61. void Cremove(Celem_t x, cset *s_p)
  62. {
  63. cset s;
  64. short n;
  65. int mask;
  66. s = *s_p;
  67. assert(x>0 && x <= s->v_size);
  68. n = DIVWL(x-1);
  69. mask = (1 << MODWL(x-1));
  70. s->v_bits[n] &= ~mask;
  71. }
  72. /* The operations first, next and elem can be used to iterate
  73. * over a set. For example:
  74. * for (i = Cfirst(s); i != (Cindex) 0; i = Cnext(i,s) {
  75. * x = Celem(i);
  76. * use x
  77. * }
  78. * which is like:
  79. * 'for all elements x of s do'
  80. * use x
  81. *
  82. * The implementation of first and next is not very fast.
  83. * It could be made much more efficient (at the price of a
  84. * higher complexity) by not using 'is_elem'.
  85. * Iteration over a bitvector, however, is not supposed to
  86. * be used very often.
  87. */
  88. Cindex Cfirst(cset s)
  89. {
  90. return Cnext((Cindex) 0,s);
  91. }
  92. Cindex Cnext(Cindex i, cset s)
  93. {
  94. short n;
  95. for (n = i+1; n <= s->v_size; n++) {
  96. if (Cis_elem(n,s)) {
  97. return (Cindex) n;
  98. }
  99. }
  100. return (Cindex) 0;
  101. }
  102. Celem_t Celem(Cindex i)
  103. {
  104. return (Celem_t) i;
  105. }
  106. void Cjoin(cset s1, cset *s2_p)
  107. {
  108. /* Two sets are joined by or-ing their bitvectors,
  109. * word by word.
  110. */
  111. cset s2;
  112. short n;
  113. short i;
  114. s2 = *s2_p;
  115. assert(s1->v_size == s2->v_size);
  116. n = DIVWL(s1->v_size -1); /* #words -1 */
  117. for (i = 0; i <= n; i++) {
  118. s2->v_bits[i] |= s1->v_bits[i];
  119. }
  120. }
  121. void Cintersect(cset s1, cset *s2_p)
  122. {
  123. /* Two sets are intersected by and-ing their bitvectors,
  124. * word by word.
  125. */
  126. cset s2;
  127. short n;
  128. register short i;
  129. s2 = *s2_p;
  130. assert(s1->v_size == s2->v_size);
  131. n = DIVWL(s1->v_size -1); /* #words -1 */
  132. for (i = 0; i <= n; i++) {
  133. s2->v_bits[i] &= s1->v_bits[i];
  134. }
  135. }
  136. void Cdeleteset(cset s)
  137. {
  138. oldbitvect(s,DIVWL(s->v_size - 1) + 1);
  139. }
  140. bool Cis_subset(cset s1, cset s2)
  141. {
  142. /* See if s1 is a subset of s2 */
  143. register short i;
  144. assert(s1->v_size == s2->v_size);
  145. if (s1->v_size == 0) return TRUE;
  146. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  147. if ((s1->v_bits[i] & ~(s2->v_bits[i])) != 0) {
  148. return FALSE;
  149. }
  150. }
  151. return TRUE;
  152. }
  153. void Cclear_set(cset *s_p)
  154. {
  155. cset s;
  156. register short i;
  157. s = *s_p;
  158. assert (s != (cset) 0);
  159. for (i = 0; i <= DIVWL(s->v_size-1); i++) {
  160. s->v_bits[i] = 0;
  161. }
  162. }
  163. void Ccopy_set(cset s1, cset *s2_p)
  164. {
  165. cset s2;
  166. register short i;
  167. s2 = *s2_p;
  168. assert (s1->v_size == s2->v_size);
  169. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  170. s2->v_bits[i] = s1->v_bits[i];
  171. }
  172. }
  173. void Csubtract(cset s1, cset *s2_p)
  174. {
  175. cset s2;
  176. register short i;
  177. s2 = *s2_p;
  178. assert (s1->v_size == s2->v_size);
  179. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  180. s2->v_bits[i] &= ~(s1->v_bits[i]);
  181. }
  182. }
  183. bool Cequal(cset s1, cset s2)
  184. {
  185. register short i;
  186. assert (s1->v_size == s2->v_size);
  187. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  188. if (s1->v_bits[i] != s2->v_bits[i]) return FALSE;
  189. }
  190. return TRUE;
  191. }
  192. short Cnrelems(cset s)
  193. {
  194. register short n, cnt;
  195. cnt = 0;
  196. for (n = 1; n <= s->v_size; n++) {
  197. if (Cis_elem(n,s)) {
  198. cnt++;
  199. }
  200. }
  201. return cnt;
  202. }