BitSet


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