001: package mlsub.typing.lowlevel;
002:
003: /**
004: Same as java.util.BitSet, without the synchronization stuff
005: plus additional features.
006:
007: @see java.util.BitSet
008:
009: @version $Revision: 1.13 $, $Date: 2005/03/30 23:08:11 $
010: @author Alexandre Frey
011: @author Daniel Bonniot
012: (replaced the underlying java.util.Vector by an array
013: for efficiency reasons;
014: most bitvectors are less than 64 elements, so using a long often avoids
015: allocating the array)
016: **/
017: public class BitVector implements java.io.Serializable {
018: private final static int BITS_PER_UNIT = 6;
019: private final static int MASK = (1 << BITS_PER_UNIT) - 1;
020:
021: private long bits0; // first 64 bits
022: private long bits1[]; // used if more than 64 bits are stored
023:
024: /**
025: @return number of WORDS allocated
026: */
027: private int length() {
028: if (bits1 == null)
029: return 1;
030: else
031: return bits1.length;
032: }
033:
034: /**
035: * Convert bitIndex to a subscript into the bits[] array.
036: */
037: private static int subscript(int bitIndex) {
038: return bitIndex >> BITS_PER_UNIT;
039: }
040:
041: /**
042: * Convert a subscript into the bits[] array to a (maximum) bitIndex.
043: */
044: private static int bitIndex(int subscript) {
045: return (subscript << BITS_PER_UNIT) + MASK;
046: }
047:
048: /**
049: * Creates an empty set.
050: */
051: public BitVector() {
052: bits0 = 0L;
053: bits1 = null;
054: }
055:
056: /**
057: * Creates an empty set with the specified size.
058: * @param nbits the size of the set
059: */
060: public BitVector(int nbits) {
061: /* nbits can't be negative; size 0 is OK */
062: if (nbits < 0) {
063: throw new NegativeArraySizeException(Integer
064: .toString(nbits));
065: }
066: if (nbits <= (1 << BITS_PER_UNIT))
067: // can fit on a word
068: {
069: bits0 = 0L;
070: bits1 = null;
071: } else {
072: /* On wraparound, truncate size; almost certain to o-flo memory. */
073: if (nbits + MASK < 0) {
074: System.out.println("Wraparoud");
075: nbits = Integer.MAX_VALUE - MASK;
076: }
077: /* subscript(nbits + MASK) is the length of the array needed to hold nbits */
078: int length = subscript(nbits + MASK);
079: bits1 = new long[length];
080: }
081: }
082:
083: /**
084: * Creates a copy of a BitVector.
085: */
086: public BitVector(BitVector old) {
087: if (old.bits1 == null) {
088: this .bits0 = old.bits0;
089: this .bits1 = null;
090: } else {
091: this .bits0 = 0L;
092: // optim: shrink to nonZeroLength()?
093: int n = old.bits1.length;
094: this .bits1 = new long[n];
095: System.arraycopy(old.bits1, 0, this .bits1, 0, n);
096: }
097: }
098:
099: /**
100: * Ensures that the BitVector can hold at least an nth bit.
101: * This cannot leave the bits array at length 0.
102: * @param nth the 0-origin number of the bit to ensure is there.
103: */
104: private void ensureCapacity(int nth) {
105: int required = subscript(nth) + 1; /* +1 to get length, not index */
106: if (required == 1)
107: return;
108: if (required > length()) {
109: /* Ask for larger of doubled size or required size */
110: int request = Math.max(2 * length(), required);
111: if (bits1 == null) {
112: bits1 = new long[request];
113: bits1[0] = bits0;
114: } else {
115: long[] newBits = new long[request];
116: System.arraycopy(bits1, 0, newBits, 0, bits1.length);
117: bits1 = newBits;
118: }
119: }
120: }
121:
122: /**
123: * Sets a bit.
124: * @param bit the bit to be set
125: */
126: public void set(int bit) {
127: if (bit < 0) {
128: throw new IndexOutOfBoundsException(Integer.toString(bit));
129: }
130: ensureCapacity(bit);
131: if (bits1 == null)
132: bits0 |= (1L << bit); // we know that bit <= 64
133: else
134: bits1[subscript(bit)] |= (1L << (bit & MASK));
135: }
136:
137: /**
138: * Clears a bit.
139: * @param bit the bit to be cleared
140: */
141: final public void clear(int bit) {
142: if (bit < 0) {
143: throw new IndexOutOfBoundsException(Integer.toString(bit));
144: }
145: ensureCapacity(bit);
146: if (bits1 == null)
147: bits0 &= ~(1L << bit); // we know that bit <= 64
148: else
149: bits1[subscript(bit)] &= ~(1L << (bit & MASK));
150: }
151:
152: /**
153: * Gets a bit.
154: * @param bit the bit to be gotten
155: */
156: final public boolean get(int bit) {
157: if (bit < 0) {
158: throw new IndexOutOfBoundsException(Integer.toString(bit));
159: }
160: if (bits1 == null)
161: if (bit <= MASK)
162: return (bits0 & (1L << bit)) != 0L;
163: else
164: return false;
165:
166: // long representation
167:
168: int n = subscript(bit); /* always positive */
169:
170: if (n < bits1.length)
171: return (bits1[n] & (1L << (bit & MASK))) != 0L;
172: return false;
173: }
174:
175: /**
176: * Logically ANDs this bit set with the specified set of bits.
177: * @param set the bit set to be ANDed with
178: */
179: final public void and(BitVector set) {
180: if (bits1 == null) {
181: if (set.bits1 == null)
182: bits0 &= set.bits0;
183: else
184: bits0 &= set.bits1[0];
185: return;
186: }
187:
188: if (this == set) {
189: return;
190: }
191:
192: if (set.bits1 == null) {
193: // go back to a short representation
194: bits0 = bits1[0] & set.bits0;
195: bits1 = null;
196: return;
197: }
198:
199: int bitsLength = length();
200: int setLength = set.length();
201: int n = Math.min(bitsLength, setLength);
202: for (int i = n; i-- > 0;) {
203: bits1[i] &= set.bits1[i];
204: }
205: for (; n < bitsLength; n++) {
206: bits1[n] = 0L;
207: }
208: }
209:
210: /**
211: * do this = this & ~(set)
212: */
213: final public void andNot(BitVector set) {
214: if (this == set) {
215: clearAll();
216: return;
217: }
218:
219: if (bits1 == null) {
220: if (set.bits1 == null)
221: bits0 &= ~set.bits0;
222: else
223: bits0 &= ~set.bits1[0];
224: return;
225: }
226:
227: if (set.bits1 == null) {
228: bits1[0] &= ~set.bits0;
229: return;
230: }
231:
232: int bitsLength = length();
233: int setLength = set.length();
234: int n = Math.min(bitsLength, setLength);
235: for (int i = n; i-- > 0;) {
236: bits1[i] &= ~set.bits1[i];
237: }
238: }
239:
240: /**
241: Assumes i is a valid word index.
242:
243: @return bits[i]
244: */
245: private long getW(int i) {
246: if (bits1 == null)
247: return bits0; // since i is valid, it must be 0
248: else
249: return bits1[i];
250: }
251:
252: /**
253: Sets bits[i] = w
254:
255: Assumes i is a valid word index.
256: */
257: private void setW(int i, long w) {
258: if (bits1 == null)
259: bits0 = w;
260: else
261: bits1[i] = w;
262: }
263:
264: /**
265: Do bits[i] &= w
266:
267: Assumes i is a valid word index.
268: */
269: private void andW(int i, long w) {
270: if (bits1 == null)
271: bits0 &= w;
272: else
273: bits1[i] &= w;
274: }
275:
276: /**
277: Do bits[i] |= w
278:
279: Assumes i is a valid word index.
280: */
281: private void orW(int i, long w) {
282: if (bits1 == null)
283: bits0 |= w;
284: else
285: bits1[i] |= w;
286: }
287:
288: /**
289: Do bits[i] ^= w
290:
291: Assumes i is a valid word index.
292: */
293: private void xorW(int i, long w) {
294: if (bits1 == null)
295: bits0 ^= w;
296: else
297: bits1[i] ^= w;
298: }
299:
300: /**
301: * do this = this & (~set) on bits >= from
302: */
303: final public void andNot(int from, BitVector set) {
304: int n = Math.min(length(), set.length());
305: int i = subscript(from);
306: if (i < n) {
307: andW(i, ~set.getW(i) & (-1L) << (from & MASK));
308: i++;
309: for (; i < n; i++) {
310: bits1[i] &= ~set.getW(i);
311: }
312: }
313: }
314:
315: /**
316: * Do this = this & (~set1 | set2) on all bits >= from
317: **/
318: final public void andNotOr(int from, BitVector set1, BitVector set2) {
319: int bitsLength = length();
320: int set1Length = set1.length();
321: int set2Length = set2.length();
322: int n = Math.min(bitsLength, set1Length);
323: int i = subscript(from);
324: if (i < n) {
325: andW(i, ~(set1.getW(i) & ((-1L) << (from & MASK)))
326: | (i < set2Length ? set2.getW(i) : 0L)); // BUG? pas de from pour set2? daniel
327: i++;
328: for (; i < n; i++) {
329: bits1[i] &= ~set1.getW(i)
330: | (i < set2Length ? set2.getW(i) : 0L);
331: }
332: }
333: }
334:
335: /**
336: * Do this = this & (~set1 | set2)
337: **/
338: final public void andNotOr(BitVector set1, BitVector set2) {
339: andNotOr(0, set1, set2);
340: }
341:
342: /**
343: * Do this = this & ~(S1 & S2)
344: **/
345: final public void andNotAnd(BitVector set1, BitVector set2) {
346: int n = Math.min(this .length(), Math.min(set1.length(), set2
347: .length()));
348: for (int i = 0; i < n; i++) {
349: andW(i, ~(set1.getW(i) & set2.getW(i)));
350: }
351: }
352:
353: /**
354: * Do this = this & (~(S1 & S2) | S3)
355: * i.e. this = this & ~(S1 & S2 & ~S3)
356: **/
357: final public void andNotAndOr(BitVector S1, BitVector S2,
358: BitVector S3) {
359: int n = length();
360: int bits1length = S1.length();
361: if (bits1length < n) {
362: n = bits1length;
363: }
364: int bits2length = S2.length();
365: if (bits2length < n) {
366: n = bits2length;
367: }
368:
369: if (n <= 1) {
370: andW(0, ~(S1.getW(0) & S2.getW(0)) | S3.getW(0));
371: } else {
372: int bits3length = S3.length();
373: if (bits3length > n) {
374: bits3length = n;
375: }
376:
377: for (int i = 0; i < bits3length; i++)
378: bits1[i] &= ~(S1.bits1[i] & S2.bits1[i]) | S3.getW(i);
379:
380: for (int i = bits3length; i < n; i++)
381: bits1[i] &= ~(S1.bits1[i] & S2.bits1[i]);
382: }
383: }
384:
385: /**
386: * Do this = this | set
387: **/
388: final public void or(BitVector set) {
389: if (this == set) {
390: return;
391: }
392: int setLength = set.nonZeroLength();
393: if (setLength > 1) {
394: ensureCapacity(bitIndex(setLength - 1));
395: for (int i = setLength; i-- > 0;) {
396: bits1[i] |= set.bits1[i];
397: }
398: } else {
399: orW(0, set.getW(0));
400: }
401: }
402:
403: /**
404: * Do this = this | (set1 & ~set2)
405: **/
406: final public void orNotIn(BitVector set1, BitVector set2) {
407: if (this == set1) {
408: return;
409: }
410: int set1Length = set1.nonZeroLength();
411: int set2Length = set2.length();
412: if (set1Length > 0) {
413: ensureCapacity(bitIndex(set1Length - 1)); // XXX: problem ?
414: }
415: for (int i = set1Length; i-- > 0;) {
416: if (i < set2Length) {
417: orW(i, set1.getW(i) & ~set2.getW(i));
418: } else {
419: orW(i, set1.getW(i));
420: }
421: }
422: }
423:
424: /**
425: * Do this = this | (set1 & set2)
426: **/
427: final public void orAnd(BitVector set1, BitVector set2) {
428: if (this == set1 || this == set2) {
429: return;
430: }
431: int setLength = Math.min(set1.nonZeroLength(), set2
432: .nonZeroLength());
433: if (setLength > 0) {
434: ensureCapacity(bitIndex(setLength - 1));// this might cause some problem...
435: }
436: for (int i = setLength; i-- > 0;) {
437: orW(i, set1.getW(i) & set2.getW(i));
438: }
439: }
440:
441: /*
442: * If there are some trailing zeros, don't count them
443: */
444: private int nonZeroLength() {
445: if (bits1 == null)
446: return 1;
447:
448: int n = bits1.length;
449: while (n > 0 && bits1[n - 1] == 0L) {
450: n--;
451: }
452: return n;
453: }
454:
455: /**
456: * Do this = this ^ set
457: **/
458: final public void xor(BitVector set) {
459: int setLength = set.length();
460: if (setLength > 0) {
461: ensureCapacity(bitIndex(setLength - 1));
462: }
463: for (int i = setLength; i-- > 0;) {
464: xorW(i, set.getW(i));
465: }
466: }
467:
468: /**
469: * Gets the hashcode.
470: */
471: final public int hashCode() {
472: long h = 1234;
473: for (int i = length(); --i >= 0;) {
474: h ^= getW(i) * (i + 1);
475: }
476: return (int) ((h >> 32) ^ h);
477: }
478:
479: /**
480: * Calculates and returns the set's size in bits.
481: * The maximum element in the set is the size - 1st element.
482: */
483: final public int size() {
484: return length() << BITS_PER_UNIT;
485: }
486:
487: /**
488: * Compares this object against the specified object.
489: * @param obj the object to compare with
490: * @return true if the objects are the same; false otherwise.
491: */
492: final public boolean equals(Object obj) {
493: if ((obj == null) || !(obj instanceof BitVector))
494: return false;
495:
496: if (this == obj)
497: return true;
498:
499: BitVector set = (BitVector) obj;
500: int bitsLength = length();
501: int setLength = set.length();
502: int n = Math.min(bitsLength, setLength);
503: for (int i = n; i-- > 0;) {
504: if (getW(i) != set.getW(i)) {
505: return false;
506: }
507: }
508: if (bitsLength > n) {
509: for (int i = bitsLength; i-- > n;) {
510: if (bits1[i] != 0L) {
511: return false;
512: }
513: }
514: } else if (setLength > n) {
515: for (int i = setLength; i-- > n;) {
516: if (set.bits1[i] != 0L) {
517: return false;
518: }
519: }
520: }
521: return true;
522: }
523:
524: /**
525: * Converts the BitVector to a String.
526: */
527: public String toString() {
528: StringBuffer buffer = new StringBuffer();
529: Separator sep = new Separator(", ");
530: buffer.append('{');
531: int limit = size();
532: for (int i = 0; i < limit; i++) {
533: if (get(i)) {
534: buffer.append(sep).append(i);
535: }
536: }
537: buffer.append('}');
538: return buffer.toString();
539: }
540:
541: /**
542: * Computes the number of bits set in this BitVector.
543: * This function is specially efficient on sparse bit sets.
544: * NOTE: in previous implementations of MLsub type-checkers, there were
545: * an average number of 2 bits set per vector...
546: **/
547: final public int bitCount() {
548: int cnt = 0;
549: int bitsLength = length();
550: for (int i = 0; i < bitsLength; i++) {
551: long chunk = getW(i);
552: while (chunk != 0L) {
553: chunk &= chunk - 1L;
554: cnt++;
555: }
556: }
557: return cnt;
558: }
559:
560: /**
561: * Computes the number of bits set among the first n bits
562: **/
563: final public int bitCount(int n) {
564: int cnt = 0;
565: int maxChunk = subscript(n);
566: if (maxChunk >= length())
567: return bitCount();
568:
569: for (int i = 0; i < maxChunk; i++) {
570: long chunk = getW(i);
571: while (chunk != 0L) {
572: chunk &= chunk - 1L;
573: cnt++;
574: }
575: }
576: long lastChunk = getW(maxChunk) & ((1L << (n & MASK)) - 1);
577: while (lastChunk != 0L) {
578: lastChunk &= lastChunk - 1L;
579: cnt++;
580: }
581: return cnt;
582: }
583:
584: private static/* XXX: work around Symantec JIT bug: comment static */
585: int chunkLowestSetBit(long chunk) {
586: int bit = 0;
587: chunk &= -chunk; //fix sign bit
588: if ((chunk & 0xffffffff00000000L) != 0)
589: bit += 32;
590: if ((chunk & 0xffff0000ffff0000L) != 0)
591: bit += 16;
592: if ((chunk & 0xff00ff00ff00ff00L) != 0)
593: bit += 8;
594: if ((chunk & 0xf0f0f0f0f0f0f0f0L) != 0)
595: bit += 4;
596: if ((chunk & 0xccccccccccccccccL) != 0)
597: bit += 2;
598: if ((chunk & 0xaaaaaaaaaaaaaaaaL) != 0)
599: bit += 1;
600: return bit;
601: }
602:
603: final public static int UNDEFINED_INDEX = Integer.MIN_VALUE;
604:
605: /**
606: * Compute the first bit set in this BitVector or UNDEFINED_INDEX if this
607: * set is empty.
608: **/
609: final public int getLowestSetBit() {
610: if (bits1 == null) {
611: if (bits0 != 0L)
612: return chunkLowestSetBit(bits0);
613: } else {
614: int n = bits1.length;
615: for (int i = 0; i < n; i++) {
616: long chunk = bits1[i];
617: if (chunk != 0L)
618: return (i << BITS_PER_UNIT)
619: + chunkLowestSetBit(chunk);
620: }
621: }
622: return UNDEFINED_INDEX;
623: }
624:
625: /**
626: * Compute the first cleared bit in this BitVector (a BitVector always
627: * contains a finite number of set bits, so this method always returns a
628: * value)
629: **/
630: final public int getLowestClearedBit() {
631: int n = length();
632: int i;
633: for (i = 0; i < n; i++) {
634: long chunk = getW(i);
635: if (chunk != ~0L) {
636: return (i << BITS_PER_UNIT) + chunkLowestSetBit(~chunk);
637: }
638: }
639: return i << BITS_PER_UNIT;
640: }
641:
642: /**
643: * Compute the first bit set that is greater or equal than pos, or
644: * UNDEFINED_INDEX if there is no such bit
645: **/
646: final public int getLowestSetBit(int pos) {
647: int n = length();
648: int i = subscript(pos);
649: if (i >= n) {
650: return UNDEFINED_INDEX; // was -1, Alex's bug?
651: } else {
652: long chunk = getW(i) & ((~0L) << (pos & MASK));
653: while (true) {
654: if (chunk != 0L) {
655: return (i << BITS_PER_UNIT)
656: + chunkLowestSetBit(chunk);
657: }
658: i++;
659: if (i >= n) {
660: return UNDEFINED_INDEX;
661: }
662: chunk = bits1[i];
663: }
664: }
665: }
666:
667: /**
668: * Gets the first bit set that is strictly greater than i or
669: * UNDEFINED_INDEX if there is none
670: **/
671: public int getNextBit(int i) {
672: return getLowestSetBit(i + 1);
673: }
674:
675: /**
676: * Compute the first bit set in this & ~set.
677: * @return UNDEFINED_INDEX if there is no such bit
678: **/
679: final public int getLowestSetBitNotIn(BitVector set) {
680: int n = length();
681: int setLength = set.length();
682: for (int i = 0; i < n; i++) {
683: long chunk = getW(i);
684: if (i < setLength) {
685: chunk &= ~set.getW(i);
686: }
687: if (chunk != 0L) {
688: return (i << BITS_PER_UNIT) + chunkLowestSetBit(chunk);
689: }
690: }
691: return UNDEFINED_INDEX;
692: }
693:
694: /**
695: * Compute the first bit in this & set
696: * @return UNDEFINED_INDEX if there is no such bit
697: **/
698: final public int getLowestSetBitAnd(BitVector set) {
699: int n = length();
700: int setLength = set.length();
701: int result = 0;
702: for (int i = 0; i < n; i++) {
703: long chunk = getW(i);
704: if (i < setLength) {
705: chunk &= set.getW(i);
706: } else {
707: return UNDEFINED_INDEX;
708: }
709: if (chunk != 0L) {
710: return result + chunkLowestSetBit(chunk);
711: } else {
712: result += 64;
713: }
714: }
715: return UNDEFINED_INDEX;
716: }
717:
718: final public int getLowestSetBitAndNotIn(BitVector set,
719: BitVector exclude) {
720: int n = length();
721: int setLength = set.length();
722: int excludeLength = exclude.length();
723: int result = 0;
724: for (int i = 0; i < n; i++) {
725: long chunk = getW(i);
726: if (i < setLength) {
727: chunk &= set.getW(i);
728: } else {
729: return UNDEFINED_INDEX;
730: }
731: if (i < excludeLength) {
732: chunk &= ~exclude.getW(i);
733: }
734: if (chunk != 0L) {
735: return result + chunkLowestSetBit(chunk);
736: } else {
737: result += 64;
738: }
739: }
740: return UNDEFINED_INDEX;
741: }
742:
743: /**
744: * Return true if this BitVector is included in set
745: **/
746: final public boolean includedIn(BitVector set) {
747: if (this == set) {
748: return true;
749: } else {
750: int bitsLength = nonZeroLength();
751: int setLength = set.nonZeroLength();
752: if (bitsLength > setLength) {
753: return false;
754: } else {
755: for (int i = 0; i < bitsLength; i++) {
756: if ((getW(i) & ~set.getW(i)) != 0L) {
757: return false;
758: }
759: }
760: return true;
761: }
762: }
763: }
764:
765: /**
766: * Clear all the bits in this BitVector
767: **/
768: final public void clearAll() {
769: bits0 = 0L;
770: bits1 = null;
771: }
772:
773: /**
774: * Returns true if no bit is set in this BitVector
775: **/
776: public boolean isEmpty() {
777: if (bits1 == null)
778: return bits0 == 0L;
779:
780: int n = bits1.length;
781: for (int i = 0; i < n; i++) {
782: if (bits1[i] != 0L) {
783: return false;
784: }
785: }
786: return true;
787: }
788:
789: /**
790: * Copy bit src into bit dest and clear src bit
791: **/
792: final public void bitCopy(int src, int dest) {
793: if (get(src)) {
794: set(dest);
795: clear(src);
796: } else {
797: clear(dest);
798: }
799: }
800:
801: /**
802: * Merge bit src and bit dest, put the result in bit dest.
803: **/
804: final public void bitMerge(int src, int dest) {
805: if (get(src)) {
806: set(dest);
807: }
808: }
809:
810: /**
811: * Clear all the bits beyond newSize (newSize included), so that this
812: * BitVector has less than newSize bits.
813: **/
814: final public void truncate(int newSize) {
815: int i = subscript(newSize);
816: int bitsLength = length();
817: if (i < bitsLength) {
818: andW(i, (1L << (newSize & MASK)) - 1);
819: for (i++; i < bitsLength; i++) {
820: bits1[i] = 0L;
821: }
822: }
823: // XXX: should shrink the vector to lower memory usage ?
824: }
825:
826: /**
827: * Fills the n first bit of this BitVector
828: **/
829: final public void fill(int n) {
830: ensureCapacity(n - 1);
831: int maxChunk = subscript(n);
832: for (int i = 0; i < maxChunk; i++) {
833: setW(i, ~0L);
834: }
835: if (maxChunk < length()) {
836: orW(maxChunk, (1L << (n & MASK)) - 1);
837: }
838: }
839:
840: /**
841: * Clears the first n bits of this BitVector
842: **/
843: final public void fillNot(int n) {
844: int maxChunk = subscript(n);
845: if (maxChunk >= length()) {
846: clearAll();
847: } else {
848: for (int i = 0; i < maxChunk; i++) {
849: setW(i, 0L);
850: }
851: andW(maxChunk, (~0L) << (n & MASK));
852: }
853: }
854:
855: /**
856: * add to this the product of M by v, that is the BitVector v' such that v' =
857: * union of all M.getRow(i) such that v.get(i) is true.
858: **/
859: final public void addProduct(BitMatrix M, BitVector v) {
860: int n = M.size();
861:
862: for (int i = v.getLowestSetBit(); i >= 0; i = v
863: .getLowestSetBit(i + 1))
864: or(M.getRow(i));
865: }
866:
867: final public void slowaddProduct(BitMatrix M, BitVector v) {
868: int n = M.size();
869: for (int i = 0; i < n; i++) {
870: if (v.get(i)) {
871: or(M.getRow(i));
872: }
873: }
874: }
875: }
|