BitSet


1   package antlr.collections.impl;
2   
3   /* ANTLR Translator Generator
4    * Project led by Terence Parr at http://www.jGuru.com
5    * Software rights: http://www.antlr.org/RIGHTS.html
6    *
7    * $Id: //depot/code/org.antlr/main/main/antlr/collections/impl/BitSet.java#6 $
8    */
9   
10  import antlr.CharFormatter;
11  
12  /**A BitSet to replace java.util.BitSet.
13   * Primary differences are that most set operators return new sets
14   * as opposed to oring and anding "in place".  Further, a number of
15   * operations were added.  I cannot contain a BitSet because there
16   * is no way to access the internal bits (which I need for speed)
17   * and, because it is final, I cannot subclass to add functionality.
18   * Consider defining set degree.  Without access to the bits, I must
19   * call a method n times to test the ith bit...ack!
20   *
21   * Also seems like or() from util is wrong when size of incoming set is bigger
22   * than this.bits.length.
23   *
24   * @author Terence Parr
25   * @author <br><a HREF="mailto:pete@yamuna.demon.co.uk">Pete Wells</a>
26   */
27  public class BitSet implements Cloneable   {
28      protected final static int BITS = 64;    // number of bits / long
29      protected final static int NIBBLE = 4;
30      protected final static int LOG_BITS = 6; // 2^6 == 64
31  
32      /* We will often need to do a mod operator (i mod nbits).  Its
33       * turns out that, for powers of two, this mod operation is
34       * same as (i & (nbits-1)).  Since mod is slow, we use a
35       * precomputed mod mask to do the mod instead.
36       */
37      protected final static int MOD_MASK = BITS - 1;
38  
39      /** The actual data bits */
40      protected long bits[];
41  
42      /** Construct a bitset of size one word (64 bits) */
43      public BitSet() {
44          this(BITS);
45      }
46  
47      /** Construction from a static array of longs */
48      public BitSet(long[] bits_) {
49          bits = bits_;
50      }
51  
52      /** Construct a bitset given the size
53       * @param nbits The size of the bitset in bits
54       */
55      public BitSet(int nbits) {
56          bits = new long[((nbits - 1) >> LOG_BITS) + 1];
57      }
58  
59      /** or this element into this set (grow as necessary to accommodate) */
60      public void add(int el) {
61          //System.out.println("add("+el+")");
62          int n = wordNumber(el);
63          //System.out.println("word number is "+n);
64          //System.out.println("bits.length "+bits.length);
65          if (n >= bits.length) {
66              growToInclude(el);
67          }
68          bits[n] |= bitMask(el);
69      }
70  
71      public BitSet and(BitSet a) {
72          BitSet s = (BitSet)this.clone();
73          s.andInPlace(a);
74          return s;
75      }
76  
77      public void andInPlace(BitSet a) {
78          int min = Math.min(bits.length, a.bits.length);
79          for (int i = min - 1; i >= 0; i--) {
80              bits[i] &= a.bits[i];
81          }
82          // clear all bits in this not present in a (if this bigger than a).
83          for (int i = min; i < bits.length; i++) {
84              bits[i] = 0;
85          }
86      }
87  
88      private final static long bitMask(int bitNumber) {
89          int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
90          return 1L << bitPosition;
91      }
92  
93      public void clear() {
94          for (int i = bits.length - 1; i >= 0; i--) {
95              bits[i] = 0;
96          }
97      }
98  
99      public void clear(int el) {
100         int n = wordNumber(el);
101         if (n >= bits.length) { // grow as necessary to accommodate
102             growToInclude(el);
103         }
104         bits[n] &= ~bitMask(el);
105     }
106 
107     public Object   clone() {
108         BitSet s;
109         try {
110             s = (BitSet)super.clone();
111             s.bits = new long[bits.length];
112             System.arraycopy(bits, 0, s.bits, 0, bits.length);
113         }
114         catch (CloneNotSupportedException   e) {
115             throw new InternalError  ();
116         }
117         return s;
118     }
119 
120     public int degree() {
121         int deg = 0;
122         for (int i = bits.length - 1; i >= 0; i--) {
123             long word = bits[i];
124             if (word != 0L) {
125                 for (int bit = BITS - 1; bit >= 0; bit--) {
126                     if ((word & (1L << bit)) != 0) {
127                         deg++;
128                     }
129                 }
130             }
131         }
132         return deg;
133     }
134 
135     /** code "inherited" from java.util.BitSet */
136     public boolean equals(Object   obj) {
137         if ((obj != null) && (obj instanceof BitSet)) {
138             BitSet set = (BitSet)obj;
139 
140             int n = Math.min(bits.length, set.bits.length);
141             for (int i = n; i-- > 0;) {
142                 if (bits[i] != set.bits[i]) {
143                     return false;
144                 }
145             }
146             if (bits.length > n) {
147                 for (int i = bits.length; i-- > n;) {
148                     if (bits[i] != 0) {
149                         return false;
150                     }
151                 }
152             }
153             else if (set.bits.length > n) {
154                 for (int i = set.bits.length; i-- > n;) {
155                     if (set.bits[i] != 0) {
156                         return false;
157                     }
158                 }
159             }
160             return true;
161         }
162         return false;
163     }
164 
165     /** Find ranges in a set element array.  @param elems The array of
166      * elements representing the set, usually from Bit Set.toArray().
167      * @return Vector of ranges.
168      */
169     public static Vector getRanges(int[] elems) {
170         if (elems.length == 0) {
171             return null;
172         }
173         int begin = elems[0];
174         int end = elems[elems.length - 1];
175         if (elems.length <= 2) {
176             // Not enough elements for a range expression
177             return null;
178         }
179 
180         Vector ranges = new Vector(5);
181         // look for ranges
182         for (int i = 0; i < elems.length - 2; i++) {
183             int lastInRange;
184             lastInRange = elems.length - 1;
185             for (int j = i + 1; j < elems.length; j++) {
186                 if (elems[j] != elems[j - 1] + 1) {
187                     lastInRange = j - 1;
188                     break;
189                 }
190             }
191             // found a range
192             if (lastInRange - i > 2) {
193                 ranges.appendElement(new IntRange(elems[i], elems[lastInRange]));
194             }
195         }
196         return ranges;
197     }
198 
199     /**
200      * Grows the set to a larger number of bits.
201      * @param bit element that must fit in set
202      */
203     public void growToInclude(int bit) {
204         int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
205         long newbits[] = new long[newSize];
206         System.arraycopy(bits, 0, newbits, 0, bits.length);
207         bits = newbits;
208     }
209 
210     public boolean member(int el) {
211         int n = wordNumber(el);
212         if (n >= bits.length) return false;
213         return (bits[n] & bitMask(el)) != 0;
214     }
215 
216     public boolean nil() {
217         for (int i = bits.length - 1; i >= 0; i--) {
218             if (bits[i] != 0) 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)) 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) return;
320         // for all words of 'a', turn off corresponding bits of 'this'
321         for (int i = 0; i < bits.length && i < a.bits.length; i++) {
322             bits[i] &= ~a.bits[i];
323         }
324     }
325 
326     public int[] toArray() {
327         int[] elems = new int[degree()];
328         int en = 0;
329         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
330             if (member(i)) {
331                 elems[en++] = i;
332             }
333         }
334         return elems;
335     }
336 
337     public long[] toPackedArray() {
338         return bits;
339     }
340 
341     public String   toString() {
342         return toString(",");
343     }
344 
345     /** Transform a bit set into a string by formatting each element as an integer
346      * @separator The string to put in between elements
347      * @return A commma-separated list of values
348      */
349     public String   toString(String   separator) {
350         String   str = "";
351         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
352             if (member(i)) {
353                 if (str.length() > 0) {
354                     str += separator;
355                 }
356                 str = str + i;
357             }
358         }
359         return str;
360     }
361 
362     /** Transform a bit set into a string of characters.
363      * @separator The string to put in between elements
364      * @param formatter An object implementing the CharFormatter interface.
365      * @return A commma-separated list of character constants.
366      */
367     public String   toString(String   separator, CharFormatter formatter) {
368         String   str = "";
369 
370         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
371             if (member(i)) {
372                 if (str.length() > 0) {
373                     str += separator;
374                 }
375                 str = str + formatter.literalChar(i);
376             }
377         }
378         return str;
379     }
380 
381     /**Create a string representation where instead of integer elements, the
382      * ith element of vocabulary is displayed instead.  Vocabulary is a Vector
383      * of Strings.
384      * @separator The string to put in between elements
385      * @return A commma-separated list of character constants.
386      */
387     public String   toString(String   separator, Vector vocabulary) {
388         if (vocabulary == null) {
389             return toString(separator);
390         }
391         String   str = "";
392         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
393             if (member(i)) {
394                 if (str.length() > 0) {
395                     str += separator;
396                 }
397                 if (i >= vocabulary.size()) {
398                     str += "<bad element " + i + ">";
399                 }
400                 else if (vocabulary.elementAt(i) == null) {
401                     str += "<" + i + ">";
402                 }
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) 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) s += ", ";
439             s += (bits[i] + "L");
440         }
441         return s;
442     }
443 
444     /** Print out the bit set but collapse char ranges. */
445     public String   toStringWithRanges(String   separator, CharFormatter formatter) {
446         String   str = "";
447         int[] elems = this.toArray();
448         if (elems.length == 0) {
449             return "";
450         }
451         // look for ranges
452         int i = 0;
453         while (i < elems.length) {
454             int lastInRange;
455             lastInRange = 0;
456             for (int j = i + 1; j < elems.length; j++) {
457                 if (elems[j] != elems[j - 1] + 1) {
458                     break;
459                 }
460                 lastInRange = j;
461             }
462             // found a range
463             if (str.length() > 0) {
464                 str += separator;
465             }
466             if (lastInRange - i >= 2) {
467                 str += formatter.literalChar(elems[i]);
468                 str += "..";
469                 str += formatter.literalChar(elems[lastInRange]);
470                 i = lastInRange;    // skip past end of range for next range
471             }
472             else {  // no range, just print current char and move on
473                 str += formatter.literalChar(elems[i]);
474             }
475             i++;
476         }
477         return str;
478     }
479 
480     private final static int wordNumber(int bit) {
481         return bit >> LOG_BITS; // bit / BITS
482     }
483 }
484
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags