]>
Commit | Line | Data |
---|---|---|
1 | /* Copyright (C) 1995, 1996 Tom Lord | |
2 | * | |
3 | * This program is free software; you can redistribute it and/or modify | |
4 | * it under the terms of the GNU Library General Public License as published by | |
5 | * the Free Software Foundation; either version 2, or (at your option) | |
6 | * any later version. | |
7 | * | |
8 | * This program is distributed in the hope that it will be useful, | |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
11 | * GNU Library General Public License for more details. | |
12 | * | |
13 | * You should have received a copy of the GNU Library General Public License | |
14 | * along with this software; see the file COPYING. If not, write to | |
15 | * the Free Software Foundation, 59 Temple Place - Suite 330, | |
16 | * Boston, MA 02111-1307, USA. | |
17 | */ | |
18 | ||
19 | \f | |
20 | /* | |
21 | * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu) | |
22 | */ | |
23 | \f | |
24 | ||
25 | #include "rxall.h" | |
26 | #include "rxbitset.h" | |
27 | ||
28 | ||
29 | #ifdef __STDC__ | |
30 | int | |
31 | rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b) | |
32 | #else | |
33 | int | |
34 | rx_bitset_is_equal (size, a, b) | |
35 | int size; | |
36 | rx_Bitset a; | |
37 | rx_Bitset b; | |
38 | #endif | |
39 | { | |
40 | int x; | |
41 | RX_subset s; | |
42 | ||
43 | if (size == 0) | |
44 | return 1; | |
45 | ||
46 | s = b[0]; | |
47 | b[0] = ~a[0]; | |
48 | ||
49 | for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x) | |
50 | ; | |
51 | ||
52 | b[0] = s; | |
53 | return !x && (s == a[0]); | |
54 | } | |
55 | ||
56 | ||
57 | #ifdef __STDC__ | |
58 | int | |
59 | rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b) | |
60 | #else | |
61 | int | |
62 | rx_bitset_is_subset (size, a, b) | |
63 | int size; | |
64 | rx_Bitset a; | |
65 | rx_Bitset b; | |
66 | #endif | |
67 | { | |
68 | int x; | |
69 | x = rx_bitset_numb_subsets(size) - 1; | |
70 | while (x-- && ((a[x] & b[x]) == a[x])); | |
71 | return x == -1; | |
72 | } | |
73 | ||
74 | ||
75 | #ifdef __STDC__ | |
76 | int | |
77 | rx_bitset_empty (int size, rx_Bitset set) | |
78 | #else | |
79 | int | |
80 | rx_bitset_empty (size, set) | |
81 | int size; | |
82 | rx_Bitset set; | |
83 | #endif | |
84 | { | |
85 | int x; | |
86 | RX_subset s; | |
87 | s = set[0]; | |
88 | set[0] = 1; | |
89 | for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x) | |
90 | ; | |
91 | set[0] = s; | |
92 | return !s; | |
93 | } | |
94 | ||
95 | #ifdef __STDC__ | |
96 | void | |
97 | rx_bitset_null (int size, rx_Bitset b) | |
98 | #else | |
99 | void | |
100 | rx_bitset_null (size, b) | |
101 | int size; | |
102 | rx_Bitset b; | |
103 | #endif | |
104 | { | |
105 | rx_bzero ((char *)b, rx_sizeof_bitset(size)); | |
106 | } | |
107 | ||
108 | ||
109 | #ifdef __STDC__ | |
110 | void | |
111 | rx_bitset_universe (int size, rx_Bitset b) | |
112 | #else | |
113 | void | |
114 | rx_bitset_universe (size, b) | |
115 | int size; | |
116 | rx_Bitset b; | |
117 | #endif | |
118 | { | |
119 | int x = rx_bitset_numb_subsets (size); | |
120 | while (x--) | |
121 | *b++ = ~(RX_subset)0; | |
122 | } | |
123 | ||
124 | ||
125 | #ifdef __STDC__ | |
126 | void | |
127 | rx_bitset_complement (int size, rx_Bitset b) | |
128 | #else | |
129 | void | |
130 | rx_bitset_complement (size, b) | |
131 | int size; | |
132 | rx_Bitset b; | |
133 | #endif | |
134 | { | |
135 | int x = rx_bitset_numb_subsets (size); | |
136 | while (x--) | |
137 | { | |
138 | *b = ~*b; | |
139 | ++b; | |
140 | } | |
141 | } | |
142 | ||
143 | ||
144 | #ifdef __STDC__ | |
145 | void | |
146 | rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b) | |
147 | #else | |
148 | void | |
149 | rx_bitset_assign (size, a, b) | |
150 | int size; | |
151 | rx_Bitset a; | |
152 | rx_Bitset b; | |
153 | #endif | |
154 | { | |
155 | int x; | |
156 | for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) | |
157 | a[x] = b[x]; | |
158 | } | |
159 | ||
160 | ||
161 | #ifdef __STDC__ | |
162 | void | |
163 | rx_bitset_union (int size, rx_Bitset a, rx_Bitset b) | |
164 | #else | |
165 | void | |
166 | rx_bitset_union (size, a, b) | |
167 | int size; | |
168 | rx_Bitset a; | |
169 | rx_Bitset b; | |
170 | #endif | |
171 | { | |
172 | int x; | |
173 | for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) | |
174 | a[x] |= b[x]; | |
175 | } | |
176 | ||
177 | ||
178 | #ifdef __STDC__ | |
179 | void | |
180 | rx_bitset_intersection (int size, | |
181 | rx_Bitset a, rx_Bitset b) | |
182 | #else | |
183 | void | |
184 | rx_bitset_intersection (size, a, b) | |
185 | int size; | |
186 | rx_Bitset a; | |
187 | rx_Bitset b; | |
188 | #endif | |
189 | { | |
190 | int x; | |
191 | for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) | |
192 | a[x] &= b[x]; | |
193 | } | |
194 | ||
195 | ||
196 | #ifdef __STDC__ | |
197 | void | |
198 | rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b) | |
199 | #else | |
200 | void | |
201 | rx_bitset_difference (size, a, b) | |
202 | int size; | |
203 | rx_Bitset a; | |
204 | rx_Bitset b; | |
205 | #endif | |
206 | { | |
207 | int x; | |
208 | for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) | |
209 | a[x] &= ~ b[x]; | |
210 | } | |
211 | ||
212 | ||
213 | #ifdef __STDC__ | |
214 | void | |
215 | rx_bitset_revdifference (int size, | |
216 | rx_Bitset a, rx_Bitset b) | |
217 | #else | |
218 | void | |
219 | rx_bitset_revdifference (size, a, b) | |
220 | int size; | |
221 | rx_Bitset a; | |
222 | rx_Bitset b; | |
223 | #endif | |
224 | { | |
225 | int x; | |
226 | for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) | |
227 | a[x] = ~a[x] & b[x]; | |
228 | } | |
229 | ||
230 | #ifdef __STDC__ | |
231 | void | |
232 | rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b) | |
233 | #else | |
234 | void | |
235 | rx_bitset_xor (size, a, b) | |
236 | int size; | |
237 | rx_Bitset a; | |
238 | rx_Bitset b; | |
239 | #endif | |
240 | { | |
241 | int x; | |
242 | for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x) | |
243 | a[x] ^= b[x]; | |
244 | } | |
245 | ||
246 | ||
247 | #ifdef __STDC__ | |
248 | unsigned long | |
249 | rx_bitset_hash (int size, rx_Bitset b) | |
250 | #else | |
251 | unsigned long | |
252 | rx_bitset_hash (size, b) | |
253 | int size; | |
254 | rx_Bitset b; | |
255 | #endif | |
256 | { | |
257 | int x; | |
258 | unsigned long answer; | |
259 | ||
260 | answer = 0; | |
261 | ||
262 | for (x = 0; x < size; ++x) | |
263 | { | |
264 | if (RX_bitset_member (b, x)) | |
265 | answer += (answer << 3) + x; | |
266 | } | |
267 | return answer; | |
268 | } | |
269 | ||
270 | ||
271 | RX_subset rx_subset_singletons [RX_subset_bits] = | |
272 | { | |
273 | 0x1, | |
274 | 0x2, | |
275 | 0x4, | |
276 | 0x8, | |
277 | 0x10, | |
278 | 0x20, | |
279 | 0x40, | |
280 | 0x80, | |
281 | 0x100, | |
282 | 0x200, | |
283 | 0x400, | |
284 | 0x800, | |
285 | 0x1000, | |
286 | 0x2000, | |
287 | 0x4000, | |
288 | 0x8000, | |
289 | 0x10000, | |
290 | 0x20000, | |
291 | 0x40000, | |
292 | 0x80000, | |
293 | 0x100000, | |
294 | 0x200000, | |
295 | 0x400000, | |
296 | 0x800000, | |
297 | 0x1000000, | |
298 | 0x2000000, | |
299 | 0x4000000, | |
300 | 0x8000000, | |
301 | 0x10000000, | |
302 | 0x20000000, | |
303 | 0x40000000, | |
304 | 0x80000000 | |
305 | }; | |
306 | ||
307 | ||
308 | /* | |
309 | * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l))))) | |
310 | * (define lb (map (lambda (n) (number->string n 2)) l)) | |
311 | * (define lc (map string->list lb)) | |
312 | * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc)) | |
313 | * (define lt (map (lambda (l) (apply + l)) ln)) | |
314 | */ | |
315 | ||
316 | static int char_pops[256] = | |
317 | { | |
318 | 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, | |
319 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
320 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
321 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
322 | 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
323 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
324 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
325 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
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 | 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
329 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
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 | 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
333 | 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 | |
334 | }; | |
335 | ||
336 | #define RX_char_population(C) (char_pops[C]) | |
337 | ||
338 | #ifdef __STDC__ | |
339 | int | |
340 | rx_bitset_population (int size, rx_Bitset a) | |
341 | #else | |
342 | int | |
343 | rx_bitset_population (size, a) | |
344 | int size; | |
345 | rx_Bitset a; | |
346 | #endif | |
347 | { | |
348 | int x; | |
349 | int total; | |
350 | unsigned char s; | |
351 | ||
352 | if (size == 0) | |
353 | return 0; | |
354 | ||
355 | total = 0; | |
356 | x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1; | |
357 | while (x >= 0) | |
358 | { | |
359 | s = ((unsigned char *)a)[x]; | |
360 | --x; | |
361 | total = total + RX_char_population (s); | |
362 | } | |
363 | return total; | |
364 | } |