cset.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282
  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(n)
  31. short n;
  32. {
  33. cset s;
  34. s = newbitvect(DIVWL(n-1) + 1);
  35. s->v_size = n;
  36. return s;
  37. }
  38. bool Cis_elem(x,s)
  39. Celem_t x;
  40. cset s;
  41. {
  42. short n;
  43. int mask;
  44. assert(x>0 && x <= s->v_size);
  45. n = DIVWL(x-1);
  46. mask = (1 << MODWL(x-1));
  47. if ((s->v_bits[n] & mask) == 0) {
  48. return FALSE;
  49. } else {
  50. return TRUE;
  51. }
  52. }
  53. Cadd(x,s_p)
  54. Celem_t x;
  55. cset *s_p;
  56. {
  57. cset s;
  58. short n;
  59. int mask;
  60. s = *s_p;
  61. assert(x>0 && x <= s->v_size);
  62. n = DIVWL(x-1);
  63. mask = (1 << MODWL(x-1));
  64. s->v_bits[n] |= mask;
  65. }
  66. Cremove(x,s_p)
  67. Celem_t x;
  68. cset *s_p;
  69. {
  70. cset s;
  71. short n;
  72. int mask;
  73. s = *s_p;
  74. assert(x>0 && x <= s->v_size);
  75. n = DIVWL(x-1);
  76. mask = (1 << MODWL(x-1));
  77. s->v_bits[n] &= ~mask;
  78. }
  79. /* The operations first, next and elem can be used to iterate
  80. * over a set. For example:
  81. * for (i = Cfirst(s); i != (Cindex) 0; i = Cnext(i,s) {
  82. * x = Celem(i);
  83. * use x
  84. * }
  85. * which is like:
  86. * 'for all elements x of s do'
  87. * use x
  88. *
  89. * The implementation of first and next is not very fast.
  90. * It could be made much more efficient (at the price of a
  91. * higher complexity) by not using 'is_elem'.
  92. * Iteration over a bitvector, however, is not supposed to
  93. * be used very often.
  94. */
  95. Cindex Cfirst(s)
  96. cset s;
  97. {
  98. return Cnext((Cindex) 0,s);
  99. }
  100. Cindex Cnext(i,s)
  101. Cindex i;
  102. cset s;
  103. {
  104. register short n;
  105. for (n = i+1; n <= s->v_size; n++) {
  106. if (Cis_elem(n,s)) {
  107. return (Cindex) n;
  108. }
  109. }
  110. return (Cindex) 0;
  111. }
  112. Celem_t Celem(i)
  113. Cindex i;
  114. {
  115. return (Celem_t) i;
  116. }
  117. Cjoin(s1,s2_p)
  118. cset s1, *s2_p;
  119. {
  120. /* Two sets are joined by or-ing their bitvectors,
  121. * word by word.
  122. */
  123. cset s2;
  124. short n;
  125. register short i;
  126. s2 = *s2_p;
  127. assert(s1->v_size == s2->v_size);
  128. n = DIVWL(s1->v_size -1); /* #words -1 */
  129. for (i = 0; i <= n; i++) {
  130. s2->v_bits[i] |= s1->v_bits[i];
  131. }
  132. }
  133. Cintersect(s1,s2_p)
  134. cset s1, *s2_p;
  135. {
  136. /* Two sets are intersected by and-ing their bitvectors,
  137. * word by word.
  138. */
  139. cset s2;
  140. short n;
  141. register short i;
  142. s2 = *s2_p;
  143. assert(s1->v_size == s2->v_size);
  144. n = DIVWL(s1->v_size -1); /* #words -1 */
  145. for (i = 0; i <= n; i++) {
  146. s2->v_bits[i] &= s1->v_bits[i];
  147. }
  148. }
  149. Cdeleteset(s)
  150. cset s;
  151. {
  152. oldbitvect(s,DIVWL(s->v_size - 1) + 1);
  153. }
  154. bool Cis_subset(s1,s2)
  155. cset s1,s2;
  156. {
  157. /* See if s1 is a subset of s2 */
  158. register short i;
  159. assert(s1->v_size == s2->v_size);
  160. if (s1->v_size == 0) return TRUE;
  161. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  162. if ((s1->v_bits[i] & ~(s2->v_bits[i])) != 0) {
  163. return FALSE;
  164. }
  165. }
  166. return TRUE;
  167. }
  168. Cclear_set(s_p)
  169. cset *s_p;
  170. {
  171. cset s;
  172. register short i;
  173. s = *s_p;
  174. assert (s != (cset) 0);
  175. for (i = 0; i <= DIVWL(s->v_size-1); i++) {
  176. s->v_bits[i] = 0;
  177. }
  178. }
  179. Ccopy_set(s1,s2_p)
  180. cset s1, *s2_p;
  181. {
  182. cset s2;
  183. register short i;
  184. s2 = *s2_p;
  185. assert (s1->v_size == s2->v_size);
  186. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  187. s2->v_bits[i] = s1->v_bits[i];
  188. }
  189. }
  190. Csubtract(s1,s2_p)
  191. cset s1, *s2_p;
  192. {
  193. cset s2;
  194. register short i;
  195. s2 = *s2_p;
  196. assert (s1->v_size == s2->v_size);
  197. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  198. s2->v_bits[i] &= ~(s1->v_bits[i]);
  199. }
  200. }
  201. bool Cequal(s1,s2)
  202. cset s1, s2;
  203. {
  204. register short i;
  205. assert (s1->v_size == s2->v_size);
  206. for (i = 0; i <= DIVWL(s1->v_size-1); i++) {
  207. if (s1->v_bits[i] != s2->v_bits[i]) return FALSE;
  208. }
  209. return TRUE;
  210. }
  211. short Cnrelems(s)
  212. cset s;
  213. {
  214. register short n, cnt;
  215. cnt = 0;
  216. for (n = 1; n <= s->v_size; n++) {
  217. if (Cis_elem(n,s)) {
  218. cnt++;
  219. }
  220. }
  221. return cnt;
  222. }