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