1
2
3
4 package net.sf.javabdd;
5
6 import java.util.Iterator;
7
8 /***
9 * <code>BitString</code> implements a vector of bits much like <code>java.util.BitSet</code>,
10 * except that this implementation actually works. Also, <code>BitString</code>
11 * has some groovy features which <code>BitSet</code> doesn't; mostly related to
12 * efficient iteration over <code>true</code> and <code>false</code> components.
13 * <p>
14 * Each component of the <code>BitString</code> has a boolean value.
15 * The bits of a <code>BitString</code> are indexed by non-negative
16 * integers (that means they are zero-based, of course). Individual
17 * indexed bits can be examined, set, or cleared. One
18 * <code>BitString</code> may be used to modify the contents of another
19 * <code>BitString</code> through logical AND, logical inclusive OR,
20 * and logical exclusive OR operations.
21 * <p>
22 * By default, all bits in the set initially have the value
23 * <code>false</code>.
24 * <p>
25 * Every bit set has a current size, which is the number of bits of
26 * space currently in use by the bit set. Note that the size is related
27 * to the implementation of a bit set, so it may change with implementation.
28 * The length of a bit set related to the logical length of a bit set
29 * and is defined independently of implementation.
30 *
31 * @author John Whaley <jwhaley@alum.mit.edu>
32 * @version $Id: BitString.java 2279 2005-05-28 10:24:54Z joewhaley $
33 */
34 public final class BitString implements Cloneable, java.io.Serializable {
35
36 /***
37 * Version ID for serialization.
38 */
39 private static final long serialVersionUID = 3257570590025265971L;
40
41
42 private static final int BITS_PER_UNIT = 5;
43 private static final int MASK = (1 << BITS_PER_UNIT) - 1;
44 private int[] bits;
45
46 /***
47 * Convert bitIndex to a subscript into the bits[] array.
48 */
49 private static int subscript(int bitIndex) {
50 return bitIndex >> BITS_PER_UNIT;
51 }
52
53 /***
54 * Creates an empty string with the specified size.
55 * @param nbits the size of the string
56 */
57 public BitString(int nbits) {
58
59
60 bits = new int[subscript(nbits + MASK)];
61 }
62
63 /***
64 * Returns the first index in the bit string which is set, or
65 * -1 if there is no such index.
66 */
67 public int firstSet() {
68 return firstSet(-1);
69 }
70
71 /***
72 * Returns the first index greater than <code>where</code> in the
73 * bit string which is set, or -1 if there is no such index.
74 * @param where the starting point for the search. May be negative.
75 */
76 public int firstSet(int where) {
77
78 where = (where < -1) ? 0 : (where + 1);
79
80 int mask = (~0) << (where & MASK);
81
82 for (int i = subscript(where); i < bits.length; i++, mask = ~0) {
83 int unit = bits[i] & mask;
84 if (unit != 0) return (i << BITS_PER_UNIT) + (bsf(unit) - 1);
85 }
86 return -1;
87 }
88
89 /***
90 * Utility function to return the number of 1 bits in the given integer
91 * value.
92 *
93 * @param b value to check
94 * @return byte number of one bits
95 */
96 public static final byte popcount(int b) {
97 int t, x;
98 x = b;
99 x = x - ((x >> 1) & 0x55555555);
100 t = ((x >> 2) & 0x33333333);
101 x = (x & 0x33333333) + t;
102 x = (x + (x >> 4)) & 0x0F0F0F0F;
103 x = x + (x >> 8);
104 x = x + (x >> 16);
105 return (byte) x;
106 }
107
108 /***
109 * Utility function to return the number of 1 bits in the given long value.
110 *
111 * @param b value to check
112 * @return byte number of one bits
113 */
114 public static final byte popcount(long b) {
115 long t, x;
116 x = b;
117 x = x - ((x >> 1) & 0x5555555555555555L);
118 t = ((x >> 2) & 0x3333333333333333L);
119 x = (x & 0x3333333333333333L) + t;
120 x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FL;
121 x = x + (x >> 8);
122 x = x + (x >> 16);
123 x = x + (x >> 32);
124 return (byte) x;
125 }
126
127 /***
128 * Utility function to return the index of the first (lowest-order) one bit
129 * in the given integer. Returns zero if the given number is zero.
130 *
131 * @param b value to check
132 * @return byte index of first one bit, or zero if the number is zero
133 */
134 public static final int bsf(int b) {
135 int t = ~(b | -b);
136 return popcount(t);
137 }
138
139 /***
140 * Utility function to return the index of the last one bit in the given
141 * integer. Returns zero if the given number is zero.
142 *
143 * @param v value to check
144 * @return byte index of first one bit, or zero if the number is zero
145 */
146 public static final int bsr(int v) {
147 if ((v & 0xFFFF0000) != 0) {
148 if ((v & 0xFF000000) != 0)
149 return 24 + bytemsb[(v >> 24) & 0xFF];
150 else
151 return 16 + bytemsb[v >> 16];
152 }
153 if ((v & 0x0000FF00) != 0)
154 return 8 + bytemsb[v >> 8];
155 else
156 return bytemsb[v];
157 }
158
159 /*** Highest bit set in a byte. */
160 private static final byte bytemsb[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
161
162 /***
163 * Returns the last index less than <code>where</code> in the
164 * bit string which is set, or -1 if there is no such index.
165 * @param where the starting point for the search.
166 */
167 public int lastSet(int where) {
168
169 if (--where < 0) return -1;
170 int start = (bits.length - 1), mask = ~0;
171 if (subscript(where) < bits.length) {
172
173 start = subscript(where);
174 mask = (~0) >>> (MASK - (where & mask));
175 }
176
177 for (int i = start; i >= 0; i--, mask = ~0) {
178 int unit = bits[i] & mask;
179 if (unit != 0) return (i << BITS_PER_UNIT) + (bsr(unit) - 1);
180 }
181 return -1;
182 }
183
184 /***
185 * Returns the last index in the bit string which is set, or
186 * -1 if there is no such index.
187 */
188 public int lastSet() {
189 return lastSet(size());
190 }
191
192 /***
193 * Sets all bits.
194 */
195 public void setAll() {
196 int i = bits.length;
197 while (i-- > 0) {
198 bits[i] = ~0;
199 }
200 }
201
202 /***
203 * Sets all bits up to and including the given bit.
204 * @param bit the bit to be set up to (zero-based)
205 */
206 public void setUpTo(int bit) {
207 int where = subscript(bit);
208
209 bits[where] |= ((1 << ((bit + 1) & MASK)) - 1);
210 while (where-- > 0) {
211 bits[where] = ~0;
212 }
213 }
214
215 public void setRange(int lo, int hi) {
216 int where1 = subscript(lo);
217 int where2 = subscript(hi);
218 if (where1 == where2) {
219 for ( ; lo <= hi; ++lo)
220 bits[where1] |= (1 << (lo & MASK));
221 } else {
222
223 bits[where2] |= ((1 << ((hi + 1) & MASK)) - 1);
224 while (--where2 > where1) {
225 bits[where2] = ~0;
226 }
227 bits[where1] |= -(1 << (lo & MASK));
228 }
229 }
230
231 /***
232 * Sets a bit.
233 * @param bit the bit to be set (zero-based)
234 */
235 public void set(int bit) {
236 bits[subscript(bit)] |= (1 << (bit & MASK));
237 }
238
239 /***
240 * Clears all bits.
241 */
242 public void clearAll() {
243 int i = bits.length;
244 while (i-- > 0) {
245 bits[i] = 0;
246 }
247 }
248
249 /***
250 * Clears all bits up to and including the given bit.
251 * @param bit the bit to be set up to (zero-based)
252 */
253 public void clearUpTo(int bit) {
254 int where = subscript(bit);
255
256 bits[where] &= ~((1 << ((bit + 1) & MASK)) - 1);
257 while (where-- > 0) {
258 bits[where] = 0;
259 }
260 }
261
262 /***
263 * Clears a bit.
264 * @param bit the bit to be cleared (zero-based)
265 */
266 public void clear(int bit) {
267 bits[subscript(bit)] &= ~(1 << (bit & MASK));
268 }
269
270 /***
271 * Gets a bit.
272 * @param bit the bit to be gotten (zero-based)
273 */
274 public boolean get(int bit) {
275 int n = subscript(bit);
276 return ((bits[n] & (1 << (bit & MASK))) != 0);
277 }
278
279 /***
280 * Logically ANDs this bit set with the specified set of bits.
281 * Returns <code>true</code> if <code>this</code> was modified in
282 * response to the operation.
283 * @param set the bit set to be ANDed with
284 */
285 public boolean and(BitString set) {
286 if (this == set) {
287 return false;
288 }
289 int n = bits.length;
290 boolean changed = false;
291 for (int i = n; i-- > 0;) {
292 int old = bits[i];
293 bits[i] &= set.bits[i];
294 changed |= (old != bits[i]);
295 }
296 return changed;
297 }
298
299 /***
300 * Logically ORs this bit set with the specified set of bits.
301 * Returns <code>true</code> if <code>this</code> was modified in
302 * response to the operation.
303 * @param set the bit set to be ORed with
304 */
305 public boolean or(BitString set) {
306 if (this == set) {
307 return false;
308 }
309 int setLength = set.bits.length;
310 boolean changed = false;
311 for (int i = setLength; i-- > 0;) {
312 int old = bits[i];
313 bits[i] |= set.bits[i];
314 changed |= (old != bits[i]);
315 }
316 return changed;
317 }
318
319 /***
320 * Logically ORs this bit set with the specified set of bits.
321 * Returns <code>true</code> if <code>this</code> was modified in
322 * response to the operation.
323 * @param set the bit set to be ORed with
324 */
325 public boolean or_upTo(BitString set, int bit) {
326 if (this == set) {
327 return false;
328 }
329 boolean result;
330 int where = subscript(bit);
331 int old = bits[where];
332 bits[where] |= (set.bits[where] & ((1 << ((bit + 1) & MASK)) - 1));
333 result = (bits[where] != old);
334 while (where-- > 0) {
335 old = bits[where];
336 bits[where] |= set.bits[where];
337 result |= (bits[where] != old);
338 }
339 return result;
340 }
341
342 /***
343 * Logically XORs this bit set with the specified set of bits.
344 * Returns <code>true</code> if <code>this</code> was modified in
345 * response to the operation.
346 * @param set the bit set to be XORed with
347 */
348 public boolean xor(BitString set) {
349 int setLength = set.bits.length;
350 boolean changed = false;
351 for (int i = setLength; i-- > 0;) {
352 int old = bits[i];
353 bits[i] ^= set.bits[i];
354 changed |= (old != bits[i]);
355 }
356 return changed;
357 }
358
359 /***
360 * Logically subtracts this bit set with the specified set of bits.
361 * Returns <code>true</code> if <code>this</code> was modified in
362 * response to the operation.
363 * @param set the bit set to subtract
364 */
365 public boolean minus(BitString set) {
366 int n = bits.length;
367 boolean changed = false;
368 for (int i = n; i-- > 0;) {
369 int old = bits[i];
370 bits[i] &= ~set.bits[i];
371 changed |= (old != bits[i]);
372 }
373 return changed;
374 }
375
376 /***
377 * Check if the intersection of the two sets is empty
378 * @param other the set to check intersection with
379 */
380 public boolean intersectionEmpty(BitString other) {
381 int n = bits.length;
382 for (int i = n; i-- > 0;) {
383 if ((bits[i] & other.bits[i]) != 0) return false;
384 }
385 return true;
386 }
387
388 /***
389 * Check if this set contains all bits of the given set.
390 * @param other the set to check containment with
391 */
392 public boolean contains(BitString other) {
393 int n = bits.length;
394 for (int i = n; i-- > 0;) {
395 if ((bits[i] & other.bits[i]) != other.bits[i]) return false;
396 }
397 return true;
398 }
399
400 private static void shld(int[] bits, int i1, int i2, int amt) {
401
402 bits[i1] = (bits[i1] << amt) | ((bits[i2] << (BITS_PER_UNIT - amt)) >> (BITS_PER_UNIT - amt));
403 }
404
405 /***
406 * Performs a left-shift operation.
407 * @param amt number of bits to shift, can be negative
408 */
409 public void shl(int amt) {
410 final int div = amt >> BITS_PER_UNIT;
411 final int mod = amt & MASK;
412 final int size = bits.length;
413 if (amt < 0) {
414 shr(-amt); return;
415 }
416
417 if (div > 0) {
418 System.arraycopy(bits, 0, bits, div, size - div);
419 for (int i = 0; i < div; ++i)
420 bits[i] = 0;
421
422
423
424
425
426
427
428
429
430 }
431
432 if (mod > 0) {
433 int i;
434 for (i = size - 1; i > div; --i) {
435 shld(bits, i, i - 1, mod);
436 }
437 bits[i] <<= mod;
438 }
439 }
440
441 private static void shrd(int[] bits, int i1, int i2, int amt) {
442
443 bits[i1] = (bits[i1] >>> amt) | ((bits[i2] >>> (BITS_PER_UNIT - amt)) << (BITS_PER_UNIT - amt));
444 }
445
446 /***
447 * Performs a right-shift operation.
448 * @param amt number of bits to shift
449 */
450 public void shr(int amt) {
451 final int div = amt >> BITS_PER_UNIT;
452 final int mod = amt & MASK;
453 final int size = bits.length;
454
455 if (div > 0) {
456 System.arraycopy(bits, div, bits, 0, size - div);
457 for (int i = size-div; i < size; ++i)
458 bits[i] = 0;
459
460
461
462
463
464
465
466
467
468 }
469
470 if (mod > 0) {
471 int i;
472 for (i = 0; i < size - div - 1; ++i) {
473 shrd(bits, i, i + 1, mod);
474 }
475 bits[i] >>>= mod;
476 }
477 }
478
479 /***
480 * Copies the values of the bits in the specified set into this set.
481 * @param set the bit set to copy the bits from
482 */
483 public void copyBits(BitString set) {
484 System.arraycopy(set.bits, 0, bits, 0, Math.min(bits.length, set.bits.length));
485 }
486
487 /***
488 * Returns a hash code value for this bit string whose value depends
489 * only on which bits have been set within this <code>BitString</code>.
490 */
491 public int hashCode() {
492 int h = 1234;
493 for (int i = bits.length; --i >= 0;) {
494 h ^= bits[i] * (i + 1);
495 }
496 return h;
497 }
498
499 /***
500 * Returns the "logical size" of this <code>BitString</code>: the
501 * index of the highest set bit in the <code>BitString</code> plus
502 * one. Returns zero if the <code>BitString</code> contains no
503 * set bits.
504 */
505 public int length() {
506 return lastSet() + 1;
507 }
508
509 /***
510 * Returns the number of bits of space actually in use by this
511 * <code>BitString</code> to represent bit values.
512 * The maximum element in the set is the size - 1st element.
513 * The minimum element in the set is the zero'th element.
514 */
515 public int size() {
516 return bits.length << BITS_PER_UNIT;
517 }
518
519 /***
520 * Compares this object against the specified object.
521 * @param obj the object to compare with
522 * @return true if the contents of the bitsets are the same; false otherwise.
523 */
524 public boolean equals(Object obj) {
525 BitString set;
526 if (obj == null) return false;
527 if (this == obj) return true;
528 try {
529 set = (BitString) obj;
530 } catch (ClassCastException e) {
531 return false;
532 }
533 if (length() != set.length()) return false;
534 int n = bits.length - 1;
535 while (n >= 0 && bits[n] == 0) n--;
536
537 for (int i = n; i >= 0; i--) {
538 if (bits[i] != set.bits[i]) {
539 return false;
540 }
541 }
542 return true;
543 }
544
545 /***
546 * Returns whether this <code>BitString</code> is all zeroes.
547 * @return true if it is all zeroes.
548 */
549 public boolean isZero() {
550 int setLength = bits.length;
551 for (int i = setLength; i-- > 0;) {
552 if (bits[i] != 0) return false;
553 }
554 return true;
555 }
556
557 /***
558 * Returns the number of ones in this <code>BitString</code>.
559 * @return number of bits set.
560 */
561 public int numberOfOnes() {
562 int setLength = bits.length;
563 int number = 0;
564 for (int i = setLength; i-- > 0;) {
565 number += popcount(bits[i]);
566 }
567 return number;
568 }
569
570 /***
571 * Returns the number of ones in this <code>BitString</code> up to a given index.
572 * @return number of bits set.
573 */
574 public int numberOfOnes(int where) {
575 int setLength = subscript(where);
576 int number = 0;
577 for (int i = setLength; i-- > 0;) {
578 number += popcount(bits[i]);
579 }
580 number += popcount(bits[setLength] & ((1 << ((where + 1) & MASK)) - 1));
581 return number;
582 }
583
584 /***
585 * Clones the BitString.
586 */
587 public Object clone() {
588 BitString result = null;
589 try {
590 result = (BitString) super.clone();
591 } catch (CloneNotSupportedException e) {
592
593 throw new InternalError();
594 }
595 result.bits = new int[bits.length];
596 System.arraycopy(bits, 0, result.bits, 0, result.bits.length);
597 return result;
598 }
599
600 /***
601 * Converts the BitString to a String.
602 */
603 public String toString() {
604 StringBuffer buffer = new StringBuffer();
605 boolean needSeparator = false;
606 buffer.append('{');
607 for (ForwardBitStringIterator i=iterator(); i.hasNext(); ) {
608 int x = i.nextIndex();
609 if (needSeparator) {
610 buffer.append(", ");
611 } else {
612 needSeparator = true;
613 }
614 buffer.append(x);
615 }
616 buffer.append('}');
617 return buffer.toString();
618 }
619
620 /***
621 * Returns an iterator that iterates through the bits in forward order.
622 */
623 public ForwardBitStringIterator iterator() {
624 return new ForwardBitStringIterator();
625 }
626
627 public ForwardBitStringZeroIterator zeroIterator() {
628 return new ForwardBitStringZeroIterator();
629 }
630
631 /***
632 * Returns an iterator that iterates through the bits in backward order.
633 */
634 public BackwardBitStringIterator backwardsIterator() {
635 return new BackwardBitStringIterator();
636 }
637
638 /***
639 * Returns an iterator that iterates through the bits in backward order,
640 * starting at the given index.
641 */
642 public BackwardBitStringIterator backwardsIterator(int i) {
643 return new BackwardBitStringIterator(i);
644 }
645
646 /***
647 * Abstract bit string iterator class.
648 */
649 public abstract static class BitStringIterator implements Iterator {
650
651 /***
652 * Returns the index of the next bit set.
653 */
654 public abstract int nextIndex();
655
656 /***
657 * @see java.util.Iterator#next()
658 */
659 public final Object next() {
660 return new Integer(nextIndex());
661 }
662
663 public void remove() {
664 throw new UnsupportedOperationException("Unmodifiable Iterator");
665 }
666
667 }
668
669 /***
670 * Iterator for iterating through a bit string in forward order.
671 */
672 public class ForwardBitStringIterator extends BitStringIterator {
673 private int j, k, t;
674
675 ForwardBitStringIterator() {
676 j = 0;
677 k = 0;
678 t = bits[0];
679 }
680
681 /***
682 * @see java.util.Iterator#hasNext()
683 */
684 public boolean hasNext() {
685 while (t == 0) {
686 if (j == bits.length - 1) return false;
687 t = bits[++j];
688 k += 1 << BITS_PER_UNIT;
689 }
690 return true;
691 }
692
693 /***
694 * @see jwutil.math.BitString.BitStringIterator#nextIndex()
695 */
696 public int nextIndex() {
697 while (t == 0) {
698 if (j == bits.length - 1) throw new java.util.NoSuchElementException();
699 t = bits[++j];
700 k += 1 << BITS_PER_UNIT;
701 }
702 int t2 = (t ^ (-t));
703 int index = 31 - popcount(t2);
704 t &= t2;
705 return k + index;
706
707
708
709
710
711
712 }
713
714 }
715
716 /***
717 * Iterator for iterating through a bit string in forward order.
718 */
719 public class ForwardBitStringZeroIterator extends BitStringIterator {
720 private int j, k, t;
721
722 ForwardBitStringZeroIterator() {
723 j = 0;
724 k = 0;
725 t = ~bits[0];
726 }
727
728 /***
729 * @see java.util.Iterator#hasNext()
730 */
731 public boolean hasNext() {
732 while (t == 0) {
733 if (j == bits.length - 1) return false;
734 t = ~bits[++j];
735 k += 1 << BITS_PER_UNIT;
736 }
737 return true;
738 }
739
740 /***
741 * @see jwutil.math.BitString.BitStringIterator#nextIndex()
742 */
743 public int nextIndex() {
744 while (t == 0) {
745 if (j == bits.length - 1) throw new java.util.NoSuchElementException();
746 t = ~bits[++j];
747 k += 1 << BITS_PER_UNIT;
748 }
749 int t2 = (t ^ (-t));
750 int index = 31 - popcount(t2);
751 t &= t2;
752 return k + index;
753 }
754
755 }
756
757 /***
758 * Iterator for iterating through a bit string in backward order.
759 */
760 public class BackwardBitStringIterator extends BitStringIterator {
761 private int j, k, t;
762
763 BackwardBitStringIterator(int i) {
764 j = subscript(i);
765 t = bits[j];
766 t &= (1 << ((i + 1) & MASK)) - 1;
767 k = j << BITS_PER_UNIT;
768 }
769
770 BackwardBitStringIterator() {
771 j = bits.length - 1;
772 t = bits[j];
773 k = j << BITS_PER_UNIT;
774 }
775
776 /***
777 * @see java.util.Iterator#hasNext()
778 */
779 public boolean hasNext() {
780 while (t == 0) {
781 if (j == 0) {
782 return false;
783 }
784 t = bits[--j];
785 k -= 1 << BITS_PER_UNIT;
786 }
787 return true;
788 }
789
790 /***
791 * @see jwutil.math.BitString.BitStringIterator#nextIndex()
792 */
793 public int nextIndex() {
794 while (t == 0) {
795 if (j == 0) throw new java.util.NoSuchElementException();
796 t = bits[--j];
797 k -= 1 << BITS_PER_UNIT;
798 }
799 int index = bsr(t) - 1;
800 t &= ~(1 << index);
801 return k + index;
802 }
803
804 }
805 }