001: package antlr.collections.impl;
002:
003: /* ANTLR Translator Generator
004: * Project led by Terence Parr at http://www.cs.usfca.edu
005: * Software rights: http://www.antlr.org/license.html
006: */
007:
008: import antlr.CharFormatter;
009:
010: /**A BitSet to replace java.util.BitSet.
011: * Primary differences are that most set operators return new sets
012: * as opposed to oring and anding "in place". Further, a number of
013: * operations were added. I cannot contain a BitSet because there
014: * is no way to access the internal bits (which I need for speed)
015: * and, because it is final, I cannot subclass to add functionality.
016: * Consider defining set degree. Without access to the bits, I must
017: * call a method n times to test the ith bit...ack!
018: *
019: * Also seems like or() from util is wrong when size of incoming set is bigger
020: * than this.bits.length.
021: *
022: * @author Terence Parr
023: * @author <br><a href="mailto:pete@yamuna.demon.co.uk">Pete Wells</a>
024: */
025: public class BitSet implements Cloneable {
026: protected final static int BITS = 64; // number of bits / long
027: protected final static int NIBBLE = 4;
028: protected final static int LOG_BITS = 6; // 2^6 == 64
029:
030: /* We will often need to do a mod operator (i mod nbits). Its
031: * turns out that, for powers of two, this mod operation is
032: * same as (i & (nbits-1)). Since mod is slow, we use a
033: * precomputed mod mask to do the mod instead.
034: */
035: protected final static int MOD_MASK = BITS - 1;
036:
037: /** The actual data bits */
038: protected long bits[];
039:
040: /** Construct a bitset of size one word (64 bits) */
041: public BitSet() {
042: this (BITS);
043: }
044:
045: /** Construction from a static array of longs */
046: public BitSet(long[] bits_) {
047: bits = bits_;
048: }
049:
050: /** Construct a bitset given the size
051: * @param nbits The size of the bitset in bits
052: */
053: public BitSet(int nbits) {
054: bits = new long[((nbits - 1) >> LOG_BITS) + 1];
055: }
056:
057: /** or this element into this set (grow as necessary to accommodate) */
058: public void add(int el) {
059: //System.out.println("add("+el+")");
060: int n = wordNumber(el);
061: //System.out.println("word number is "+n);
062: //System.out.println("bits.length "+bits.length);
063: if (n >= bits.length) {
064: growToInclude(el);
065: }
066: bits[n] |= bitMask(el);
067: }
068:
069: public BitSet and(BitSet a) {
070: BitSet s = (BitSet) this .clone();
071: s.andInPlace(a);
072: return s;
073: }
074:
075: public void andInPlace(BitSet a) {
076: int min = Math.min(bits.length, a.bits.length);
077: for (int i = min - 1; i >= 0; i--) {
078: bits[i] &= a.bits[i];
079: }
080: // clear all bits in this not present in a (if this bigger than a).
081: for (int i = min; i < bits.length; i++) {
082: bits[i] = 0;
083: }
084: }
085:
086: private final static long bitMask(int bitNumber) {
087: int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
088: return 1L << bitPosition;
089: }
090:
091: public void clear() {
092: for (int i = bits.length - 1; i >= 0; i--) {
093: bits[i] = 0;
094: }
095: }
096:
097: public void clear(int el) {
098: int n = wordNumber(el);
099: if (n >= bits.length) { // grow as necessary to accommodate
100: growToInclude(el);
101: }
102: bits[n] &= ~bitMask(el);
103: }
104:
105: public Object clone() {
106: BitSet s;
107: try {
108: s = (BitSet) super .clone();
109: s.bits = new long[bits.length];
110: System.arraycopy(bits, 0, s.bits, 0, bits.length);
111: } catch (CloneNotSupportedException e) {
112: throw new InternalError();
113: }
114: return s;
115: }
116:
117: public int degree() {
118: int deg = 0;
119: for (int i = bits.length - 1; i >= 0; i--) {
120: long word = bits[i];
121: if (word != 0L) {
122: for (int bit = BITS - 1; bit >= 0; bit--) {
123: if ((word & (1L << bit)) != 0) {
124: deg++;
125: }
126: }
127: }
128: }
129: return deg;
130: }
131:
132: /** code "inherited" from java.util.BitSet */
133: public boolean equals(Object obj) {
134: if ((obj != null) && (obj instanceof BitSet)) {
135: BitSet set = (BitSet) obj;
136:
137: int n = Math.min(bits.length, set.bits.length);
138: for (int i = n; i-- > 0;) {
139: if (bits[i] != set.bits[i]) {
140: return false;
141: }
142: }
143: if (bits.length > n) {
144: for (int i = bits.length; i-- > n;) {
145: if (bits[i] != 0) {
146: return false;
147: }
148: }
149: } else if (set.bits.length > n) {
150: for (int i = set.bits.length; i-- > n;) {
151: if (set.bits[i] != 0) {
152: return false;
153: }
154: }
155: }
156: return true;
157: }
158: return false;
159: }
160:
161: /** Find ranges in a set element array. @param elems The array of
162: * elements representing the set, usually from Bit Set.toArray().
163: * @return Vector of ranges.
164: */
165: public static Vector getRanges(int[] elems) {
166: if (elems.length == 0) {
167: return null;
168: }
169: int begin = elems[0];
170: int end = elems[elems.length - 1];
171: if (elems.length <= 2) {
172: // Not enough elements for a range expression
173: return null;
174: }
175:
176: Vector ranges = new Vector(5);
177: // look for ranges
178: for (int i = 0; i < elems.length - 2; i++) {
179: int lastInRange;
180: lastInRange = elems.length - 1;
181: for (int j = i + 1; j < elems.length; j++) {
182: if (elems[j] != elems[j - 1] + 1) {
183: lastInRange = j - 1;
184: break;
185: }
186: }
187: // found a range
188: if (lastInRange - i > 2) {
189: ranges.appendElement(new IntRange(elems[i],
190: elems[lastInRange]));
191: }
192: }
193: return ranges;
194: }
195:
196: /**
197: * Grows the set to a larger number of bits.
198: * @param bit element that must fit in set
199: */
200: public void growToInclude(int bit) {
201: int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
202: long newbits[] = new long[newSize];
203: System.arraycopy(bits, 0, newbits, 0, bits.length);
204: bits = newbits;
205: }
206:
207: public boolean member(int el) {
208: int n = wordNumber(el);
209: if (n >= bits.length)
210: return false;
211: return (bits[n] & bitMask(el)) != 0;
212: }
213:
214: public boolean nil() {
215: for (int i = bits.length - 1; i >= 0; i--) {
216: if (bits[i] != 0)
217: return false;
218: }
219: return true;
220: }
221:
222: public BitSet not() {
223: BitSet s = (BitSet) this .clone();
224: s.notInPlace();
225: return s;
226: }
227:
228: public void notInPlace() {
229: for (int i = bits.length - 1; i >= 0; i--) {
230: bits[i] = ~bits[i];
231: }
232: }
233:
234: /** complement bits in the range 0..maxBit. */
235: public void notInPlace(int maxBit) {
236: notInPlace(0, maxBit);
237: }
238:
239: /** complement bits in the range minBit..maxBit.*/
240: public void notInPlace(int minBit, int maxBit) {
241: // make sure that we have room for maxBit
242: growToInclude(maxBit);
243: for (int i = minBit; i <= maxBit; i++) {
244: int n = wordNumber(i);
245: bits[n] ^= bitMask(i);
246: }
247: }
248:
249: private final int numWordsToHold(int el) {
250: return (el >> LOG_BITS) + 1;
251: }
252:
253: public static BitSet of(int el) {
254: BitSet s = new BitSet(el + 1);
255: s.add(el);
256: return s;
257: }
258:
259: /** return this | a in a new set */
260: public BitSet or(BitSet a) {
261: BitSet s = (BitSet) this .clone();
262: s.orInPlace(a);
263: return s;
264: }
265:
266: public void orInPlace(BitSet a) {
267: // If this is smaller than a, grow this first
268: if (a.bits.length > bits.length) {
269: setSize(a.bits.length);
270: }
271: int min = Math.min(bits.length, a.bits.length);
272: for (int i = min - 1; i >= 0; i--) {
273: bits[i] |= a.bits[i];
274: }
275: }
276:
277: // remove this element from this set
278: public void remove(int el) {
279: int n = wordNumber(el);
280: if (n >= bits.length) {
281: growToInclude(el);
282: }
283: bits[n] &= ~bitMask(el);
284: }
285:
286: /**
287: * Sets the size of a set.
288: * @param nwords how many words the new set should be
289: */
290: private void setSize(int nwords) {
291: long newbits[] = new long[nwords];
292: int n = Math.min(nwords, bits.length);
293: System.arraycopy(bits, 0, newbits, 0, n);
294: bits = newbits;
295: }
296:
297: public int size() {
298: return bits.length << LOG_BITS; // num words * bits per word
299: }
300:
301: /** return how much space is being used by the bits array not
302: * how many actually have member bits on.
303: */
304: public int lengthInLongWords() {
305: return bits.length;
306: }
307:
308: /**Is this contained within a? */
309: public boolean subset(BitSet a) {
310: if (a == null || !(a instanceof BitSet))
311: return false;
312: return this .and(a).equals(this );
313: }
314:
315: /**Subtract the elements of 'a' from 'this' in-place.
316: * Basically, just turn off all bits of 'this' that are in 'a'.
317: */
318: public void subtractInPlace(BitSet a) {
319: if (a == null)
320: return;
321: // for all words of 'a', turn off corresponding bits of 'this'
322: for (int i = 0; i < bits.length && i < a.bits.length; i++) {
323: bits[i] &= ~a.bits[i];
324: }
325: }
326:
327: public int[] toArray() {
328: int[] elems = new int[degree()];
329: int en = 0;
330: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
331: if (member(i)) {
332: elems[en++] = i;
333: }
334: }
335: return elems;
336: }
337:
338: public long[] toPackedArray() {
339: return bits;
340: }
341:
342: public String toString() {
343: return toString(",");
344: }
345:
346: /** Transform a bit set into a string by formatting each element as an integer
347: * @separator The string to put in between elements
348: * @return A commma-separated list of values
349: */
350: public String toString(String separator) {
351: String str = "";
352: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
353: if (member(i)) {
354: if (str.length() > 0) {
355: str += separator;
356: }
357: str = str + i;
358: }
359: }
360: return str;
361: }
362:
363: /** Transform a bit set into a string of characters.
364: * @separator The string to put in between elements
365: * @param formatter An object implementing the CharFormatter interface.
366: * @return A commma-separated list of character constants.
367: */
368: public String toString(String separator, CharFormatter formatter) {
369: String str = "";
370:
371: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
372: if (member(i)) {
373: if (str.length() > 0) {
374: str += separator;
375: }
376: str = str + formatter.literalChar(i);
377: }
378: }
379: return str;
380: }
381:
382: /**Create a string representation where instead of integer elements, the
383: * ith element of vocabulary is displayed instead. Vocabulary is a Vector
384: * of Strings.
385: * @separator The string to put in between elements
386: * @return A commma-separated list of character constants.
387: */
388: public String toString(String separator, Vector vocabulary) {
389: if (vocabulary == null) {
390: return toString(separator);
391: }
392: String str = "";
393: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
394: if (member(i)) {
395: if (str.length() > 0) {
396: str += separator;
397: }
398: if (i >= vocabulary.size()) {
399: str += "<bad element " + i + ">";
400: } else if (vocabulary.elementAt(i) == null) {
401: str += "<" + i + ">";
402: } else {
403: str += (String) vocabulary.elementAt(i);
404: }
405: }
406: }
407: return str;
408: }
409:
410: /**
411: * Dump a comma-separated list of the words making up the bit set.
412: * Split each 64 bit number into two more manageable 32 bit numbers.
413: * This generates a comma-separated list of C++-like unsigned long constants.
414: */
415: public String toStringOfHalfWords() {
416: String s = new String();
417: for (int i = 0; i < bits.length; i++) {
418: if (i != 0)
419: s += ", ";
420: long tmp = bits[i];
421: tmp &= 0xFFFFFFFFL;
422: s += (tmp + "UL");
423: s += ", ";
424: tmp = bits[i] >>> 32;
425: tmp &= 0xFFFFFFFFL;
426: s += (tmp + "UL");
427: }
428: return s;
429: }
430:
431: /**
432: * Dump a comma-separated list of the words making up the bit set.
433: * This generates a comma-separated list of Java-like long int constants.
434: */
435: public String toStringOfWords() {
436: String s = new String();
437: for (int i = 0; i < bits.length; i++) {
438: if (i != 0)
439: s += ", ";
440: s += (bits[i] + "L");
441: }
442: return s;
443: }
444:
445: /** Print out the bit set but collapse char ranges. */
446: public String toStringWithRanges(String separator,
447: CharFormatter formatter) {
448: String str = "";
449: int[] elems = this .toArray();
450: if (elems.length == 0) {
451: return "";
452: }
453: // look for ranges
454: int i = 0;
455: while (i < elems.length) {
456: int lastInRange;
457: lastInRange = 0;
458: for (int j = i + 1; j < elems.length; j++) {
459: if (elems[j] != elems[j - 1] + 1) {
460: break;
461: }
462: lastInRange = j;
463: }
464: // found a range
465: if (str.length() > 0) {
466: str += separator;
467: }
468: if (lastInRange - i >= 2) {
469: str += formatter.literalChar(elems[i]);
470: str += "..";
471: str += formatter.literalChar(elems[lastInRange]);
472: i = lastInRange; // skip past end of range for next range
473: } else { // no range, just print current char and move on
474: str += formatter.literalChar(elems[i]);
475: }
476: i++;
477: }
478: return str;
479: }
480:
481: private final static int wordNumber(int bit) {
482: return bit >> LOG_BITS; // bit / BITS
483: }
484: }
|