FileDocCategorySizeDatePackage
BitSet.javaAPI DocGlassfish v2 API14568Wed Aug 30 15:34:14 BST 2006persistence.antlr.collections.impl

BitSet

public class BitSet extends Object implements Cloneable
A BitSet to replace java.util.BitSet. Primary differences are that most set operators return new sets as opposed to oring and anding "in place". Further, a number of operations were added. I cannot contain a BitSet because there is no way to access the internal bits (which I need for speed) and, because it is final, I cannot subclass to add functionality. Consider defining set degree. Without access to the bits, I must call a method n times to test the ith bit...ack! Also seems like or() from util is wrong when size of incoming set is bigger than this.bits.length.
author
Terence Parr
author

Pete Wells

Fields Summary
protected static final int
BITS
protected static final int
NIBBLE
protected static final int
LOG_BITS
protected static final int
MOD_MASK
protected long[]
bits
The actual data bits
Constructors Summary
public BitSet()
Construct a bitset of size one word (64 bits)


              
      
        this(BITS);
    
public BitSet(long[] bits_)
Construction from a static array of longs

        bits = bits_;
    
public BitSet(int nbits)
Construct a bitset given the size

param
nbits The size of the bitset in bits

        bits = new long[((nbits - 1) >> LOG_BITS) + 1];
    
Methods Summary
public voidadd(int el)
or this element into this set (grow as necessary to accommodate)

        //System.out.println("add("+el+")");
        int n = wordNumber(el);
        //System.out.println("word number is "+n);
        //System.out.println("bits.length "+bits.length);
        if (n >= bits.length) {
            growToInclude(el);
        }
        bits[n] |= bitMask(el);
    
public persistence.antlr.collections.impl.BitSetand(persistence.antlr.collections.impl.BitSet a)

        BitSet s = (BitSet)this.clone();
        s.andInPlace(a);
        return s;
    
public voidandInPlace(persistence.antlr.collections.impl.BitSet a)

        int min = Math.min(bits.length, a.bits.length);
        for (int i = min - 1; i >= 0; i--) {
            bits[i] &= a.bits[i];
        }
        // clear all bits in this not present in a (if this bigger than a).
        for (int i = min; i < bits.length; i++) {
            bits[i] = 0;
        }
    
private static final longbitMask(int bitNumber)

        int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
        return 1L << bitPosition;
    
public voidclear()

        for (int i = bits.length - 1; i >= 0; i--) {
            bits[i] = 0;
        }
    
public voidclear(int el)

        int n = wordNumber(el);
        if (n >= bits.length) {	// grow as necessary to accommodate
            growToInclude(el);
        }
        bits[n] &= ~bitMask(el);
    
public java.lang.Objectclone()

        BitSet s;
        try {
            s = (BitSet)super.clone();
            s.bits = new long[bits.length];
            System.arraycopy(bits, 0, s.bits, 0, bits.length);
        }
        catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
        return s;
    
public intdegree()

        int deg = 0;
        for (int i = bits.length - 1; i >= 0; i--) {
            long word = bits[i];
            if (word != 0L) {
                for (int bit = BITS - 1; bit >= 0; bit--) {
                    if ((word & (1L << bit)) != 0) {
                        deg++;
                    }
                }
            }
        }
        return deg;
    
public booleanequals(java.lang.Object obj)
code "inherited" from java.util.BitSet

        if ((obj != null) && (obj instanceof BitSet)) {
            BitSet set = (BitSet)obj;

            int n = Math.min(bits.length, set.bits.length);
            for (int i = n; i-- > 0;) {
                if (bits[i] != set.bits[i]) {
                    return false;
                }
            }
            if (bits.length > n) {
                for (int i = bits.length; i-- > n;) {
                    if (bits[i] != 0) {
                        return false;
                    }
                }
            }
            else if (set.bits.length > n) {
                for (int i = set.bits.length; i-- > n;) {
                    if (set.bits[i] != 0) {
                        return false;
                    }
                }
            }
            return true;
        }
        return false;
    
public static persistence.antlr.collections.impl.VectorgetRanges(int[] elems)
Find ranges in a set element array. @param elems The array of elements representing the set, usually from Bit Set.toArray().

return
Vector of ranges.

        if (elems.length == 0) {
            return null;
        }
        int begin = elems[0];
        int end = elems[elems.length - 1];
        if (elems.length <= 2) {
            // Not enough elements for a range expression
            return null;
        }

        Vector ranges = new Vector(5);
        // look for ranges
        for (int i = 0; i < elems.length - 2; i++) {
            int lastInRange;
            lastInRange = elems.length - 1;
            for (int j = i + 1; j < elems.length; j++) {
                if (elems[j] != elems[j - 1] + 1) {
                    lastInRange = j - 1;
                    break;
                }
            }
            // found a range
            if (lastInRange - i > 2) {
                ranges.appendElement(new IntRange(elems[i], elems[lastInRange]));
            }
        }
        return ranges;
    
public voidgrowToInclude(int bit)
Grows the set to a larger number of bits.

param
bit element that must fit in set

        int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
        long newbits[] = new long[newSize];
        System.arraycopy(bits, 0, newbits, 0, bits.length);
        bits = newbits;
    
public intlengthInLongWords()
return how much space is being used by the bits array not how many actually have member bits on.

        return bits.length;
    
public booleanmember(int el)

        int n = wordNumber(el);
        if (n >= bits.length) return false;
        return (bits[n] & bitMask(el)) != 0;
    
public booleannil()

        for (int i = bits.length - 1; i >= 0; i--) {
            if (bits[i] != 0) return false;
        }
        return true;
    
public persistence.antlr.collections.impl.BitSetnot()

        BitSet s = (BitSet)this.clone();
        s.notInPlace();
        return s;
    
public voidnotInPlace()

        for (int i = bits.length - 1; i >= 0; i--) {
            bits[i] = ~bits[i];
        }
    
public voidnotInPlace(int maxBit)
complement bits in the range 0..maxBit.

        notInPlace(0, maxBit);
    
public voidnotInPlace(int minBit, int maxBit)
complement bits in the range minBit..maxBit.

        // make sure that we have room for maxBit
        growToInclude(maxBit);
        for (int i = minBit; i <= maxBit; i++) {
            int n = wordNumber(i);
            bits[n] ^= bitMask(i);
        }
    
private final intnumWordsToHold(int el)

        return (el >> LOG_BITS) + 1;
    
public static persistence.antlr.collections.impl.BitSetof(int el)

        BitSet s = new BitSet(el + 1);
        s.add(el);
        return s;
    
public persistence.antlr.collections.impl.BitSetor(persistence.antlr.collections.impl.BitSet a)
return this | a in a new set

        BitSet s = (BitSet)this.clone();
        s.orInPlace(a);
        return s;
    
public voidorInPlace(persistence.antlr.collections.impl.BitSet a)

        // If this is smaller than a, grow this first
        if (a.bits.length > bits.length) {
            setSize(a.bits.length);
        }
        int min = Math.min(bits.length, a.bits.length);
        for (int i = min - 1; i >= 0; i--) {
            bits[i] |= a.bits[i];
        }
    
public voidremove(int el)

        int n = wordNumber(el);
        if (n >= bits.length) {
            growToInclude(el);
        }
        bits[n] &= ~bitMask(el);
    
private voidsetSize(int nwords)
Sets the size of a set.

param
nwords how many words the new set should be

        long newbits[] = new long[nwords];
        int n = Math.min(nwords, bits.length);
        System.arraycopy(bits, 0, newbits, 0, n);
        bits = newbits;
    
public intsize()

        return bits.length << LOG_BITS; // num words * bits per word
    
public booleansubset(persistence.antlr.collections.impl.BitSet a)
Is this contained within a?

        if (a == null || !(a instanceof BitSet)) return false;
        return this.and(a).equals(this);
    
public voidsubtractInPlace(persistence.antlr.collections.impl.BitSet a)
Subtract the elements of 'a' from 'this' in-place. Basically, just turn off all bits of 'this' that are in 'a'.

        if (a == null) return;
        // for all words of 'a', turn off corresponding bits of 'this'
        for (int i = 0; i < bits.length && i < a.bits.length; i++) {
            bits[i] &= ~a.bits[i];
        }
    
public int[]toArray()

        int[] elems = new int[degree()];
        int en = 0;
        for (int i = 0; i < (bits.length << LOG_BITS); i++) {
            if (member(i)) {
                elems[en++] = i;
            }
        }
        return elems;
    
public long[]toPackedArray()

        return bits;
    
public java.lang.StringtoString()

        return toString(",");
    
public java.lang.StringtoString(java.lang.String separator)
Transform a bit set into a string by formatting each element as an integer

separator
The string to put in between elements
return
A commma-separated list of values

        String str = "";
        for (int i = 0; i < (bits.length << LOG_BITS); i++) {
            if (member(i)) {
                if (str.length() > 0) {
                    str += separator;
                }
                str = str + i;
            }
        }
        return str;
    
public java.lang.StringtoString(java.lang.String separator, persistence.antlr.CharFormatter formatter)
Transform a bit set into a string of characters.

separator
The string to put in between elements
param
formatter An object implementing the CharFormatter interface.
return
A commma-separated list of character constants.

        String str = "";

        for (int i = 0; i < (bits.length << LOG_BITS); i++) {
            if (member(i)) {
                if (str.length() > 0) {
                    str += separator;
                }
                str = str + formatter.literalChar(i);
            }
        }
        return str;
    
public java.lang.StringtoString(java.lang.String separator, persistence.antlr.collections.impl.Vector vocabulary)
Create a string representation where instead of integer elements, the ith element of vocabulary is displayed instead. Vocabulary is a Vector of Strings.

separator
The string to put in between elements
return
A commma-separated list of character constants.

        if (vocabulary == null) {
            return toString(separator);
        }
        String str = "";
        for (int i = 0; i < (bits.length << LOG_BITS); i++) {
            if (member(i)) {
                if (str.length() > 0) {
                    str += separator;
                }
                if (i >= vocabulary.size()) {
                    str += "<bad element " + i + ">";
                }
                else if (vocabulary.elementAt(i) == null) {
                    str += "<" + i + ">";
                }
                else {
                    str += (String)vocabulary.elementAt(i);
                }
            }
        }
        return str;
    
public java.lang.StringtoStringOfHalfWords()
Dump a comma-separated list of the words making up the bit set. Split each 64 bit number into two more manageable 32 bit numbers. This generates a comma-separated list of C++-like unsigned long constants.

        String s = new String();
        for (int i = 0; i < bits.length; i++) {
            if (i != 0) s += ", ";
            long tmp = bits[i];
            tmp &= 0xFFFFFFFFL;
            s += (tmp + "UL");
            s += ", ";
            tmp = bits[i] >>> 32;
            tmp &= 0xFFFFFFFFL;
            s += (tmp + "UL");
        }
        return s;
    
public java.lang.StringtoStringOfWords()
Dump a comma-separated list of the words making up the bit set. This generates a comma-separated list of Java-like long int constants.

        String s = new String();
        for (int i = 0; i < bits.length; i++) {
            if (i != 0) s += ", ";
            s += (bits[i] + "L");
        }
        return s;
    
public java.lang.StringtoStringWithRanges(java.lang.String separator, persistence.antlr.CharFormatter formatter)
Print out the bit set but collapse char ranges.

        String str = "";
        int[] elems = this.toArray();
        if (elems.length == 0) {
            return "";
        }
        // look for ranges
        int i = 0;
        while (i < elems.length) {
            int lastInRange;
            lastInRange = 0;
            for (int j = i + 1; j < elems.length; j++) {
                if (elems[j] != elems[j - 1] + 1) {
                    break;
                }
                lastInRange = j;
            }
            // found a range
            if (str.length() > 0) {
                str += separator;
            }
            if (lastInRange - i >= 2) {
                str += formatter.literalChar(elems[i]);
                str += "..";
                str += formatter.literalChar(elems[lastInRange]);
                i = lastInRange;	// skip past end of range for next range
            }
            else {	// no range, just print current char and move on
                str += formatter.literalChar(elems[i]);
            }
            i++;
        }
        return str;
    
private static final intwordNumber(int bit)

        return bit >> LOG_BITS; // bit / BITS