org.antlr.misc
Class BitSet

java.lang.Object
  extended by org.antlr.misc.BitSet
All Implemented Interfaces:
java.lang.Cloneable, IntSet

public class BitSet
extends java.lang.Object
implements IntSet, java.lang.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

Field Summary
protected  long[] bits
          The actual data bits
protected static int BITS
           
protected static int LOG_BITS
           
protected static int MOD_MASK
           
 
Constructor Summary
BitSet()
          Construct a bitset of size one word (64 bits)
BitSet(int nbits)
          Construct a bitset given the size
BitSet(long[] bits_)
          Construction from a static array of longs
 
Method Summary
 void add(int el)
          or this element into this set (grow as necessary to accommodate)
 void addAll(int[] elements)
           
 void addAll(IntSet set)
          Add all elements from incoming set to this set.
 void addAll(java.lang.Iterable elements)
           
 IntSet and(IntSet a)
          Return the intersection of this set with the argument, creating a new set.
 void andInPlace(BitSet a)
           
 void clear()
           
 void clear(int el)
           
 java.lang.Object clone()
           
 IntSet complement()
           
 IntSet complement(IntSet set)
           
 boolean equals(java.lang.Object other)
           
 int getSingleElement()
          Get the first element you find and return it.
 void growToInclude(int bit)
          Grows the set to a larger number of bits.
 boolean isNil()
           
 int lengthInLongWords()
          return how much space is being used by the bits array not how many actually have member bits on.
 boolean member(int el)
           
 void notInPlace()
           
 void notInPlace(int maxBit)
          complement bits in the range 0..maxBit.
 void notInPlace(int minBit, int maxBit)
          complement bits in the range minBit..maxBit.
 int numBits()
           
static BitSet of(java.util.Collection elements)
           
static BitSet of(int el)
           
static BitSet of(IntSet set)
           
static BitSet of(java.util.Map elements)
           
 IntSet or(IntSet a)
          return this | a in a new set
 void orInPlace(BitSet a)
           
static BitSet range(int a, int b)
           
 void remove(int el)
          remove this element from this set
 int size()
          Return the size of this set (not the underlying implementation's allocated memory size, for example).
 boolean subset(BitSet a)
          Is this contained within a?
 IntSet subtract(IntSet a)
           
 void subtractInPlace(BitSet a)
          Subtract the elements of 'a' from 'this' in-place.
 int[] toArray()
           
 java.util.List toList()
           
 long[] toPackedArray()
           
 java.lang.String toString()
           
 java.lang.String toString(Grammar g)
          Transform a bit set into a string by formatting each element as an integer separator The string to put in between elements
 java.lang.String toString(java.lang.String separator, java.util.List vocabulary)
          Create a string representation where instead of integer elements, the ith element of vocabulary is displayed instead.
 java.lang.String toStringOfHalfWords()
          Dump a comma-separated list of the words making up the bit set.
 java.lang.String toStringOfWords()
          Dump a comma-separated list of the words making up the bit set.
 java.lang.String toStringWithRanges()
           
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

BITS

protected static final int BITS
See Also:
Constant Field Values

LOG_BITS

protected static final int LOG_BITS
See Also:
Constant Field Values

MOD_MASK

protected static final int MOD_MASK
See Also:
Constant Field Values

bits

protected long[] bits
The actual data bits

Constructor Detail

BitSet

public BitSet()
Construct a bitset of size one word (64 bits)


BitSet

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


BitSet

public BitSet(int nbits)
Construct a bitset given the size

Parameters:
nbits - The size of the bitset in bits
Method Detail

add

public void add(int el)
or this element into this set (grow as necessary to accommodate)

Specified by:
add in interface IntSet

addAll

public void addAll(IntSet set)
Description copied from interface: IntSet
Add all elements from incoming set to this set. Can limit to set of its own type.

Specified by:
addAll in interface IntSet

addAll

public void addAll(int[] elements)

addAll

public void addAll(java.lang.Iterable elements)

and

public IntSet and(IntSet a)
Description copied from interface: IntSet
Return the intersection of this set with the argument, creating a new set.

Specified by:
and in interface IntSet

andInPlace

public void andInPlace(BitSet a)

clear

public void clear()

clear

public void clear(int el)

clone

public java.lang.Object clone()
Overrides:
clone in class java.lang.Object

size

public int size()
Description copied from interface: IntSet
Return the size of this set (not the underlying implementation's allocated memory size, for example).

Specified by:
size in interface IntSet

equals

public boolean equals(java.lang.Object other)
Specified by:
equals in interface IntSet
Overrides:
equals in class java.lang.Object

growToInclude

public void growToInclude(int bit)
Grows the set to a larger number of bits.

Parameters:
bit - element that must fit in set

member

public boolean member(int el)
Specified by:
member in interface IntSet

getSingleElement

public int getSingleElement()
Get the first element you find and return it. Return Label.INVALID otherwise.

Specified by:
getSingleElement in interface IntSet

isNil

public boolean isNil()
Specified by:
isNil in interface IntSet

complement

public IntSet complement()

complement

public IntSet complement(IntSet set)
Specified by:
complement in interface IntSet

notInPlace

public void notInPlace()

notInPlace

public void notInPlace(int maxBit)
complement bits in the range 0..maxBit.


notInPlace

public void notInPlace(int minBit,
                       int maxBit)
complement bits in the range minBit..maxBit.


of

public static BitSet of(int el)

of

public static BitSet of(java.util.Collection elements)

of

public static BitSet of(IntSet set)

of

public static BitSet of(java.util.Map elements)

range

public static BitSet range(int a,
                           int b)

or

public IntSet or(IntSet a)
return this | a in a new set

Specified by:
or in interface IntSet

orInPlace

public void orInPlace(BitSet a)

remove

public void remove(int el)
Description copied from interface: IntSet
remove this element from this set

Specified by:
remove in interface IntSet

numBits

public int numBits()

lengthInLongWords

public int lengthInLongWords()
return how much space is being used by the bits array not how many actually have member bits on.


subset

public boolean subset(BitSet a)
Is this contained within a?


subtractInPlace

public void subtractInPlace(BitSet a)
Subtract the elements of 'a' from 'this' in-place. Basically, just turn off all bits of 'this' that are in 'a'.


subtract

public IntSet subtract(IntSet a)
Specified by:
subtract in interface IntSet

toList

public java.util.List toList()
Specified by:
toList in interface IntSet

toArray

public int[] toArray()

toPackedArray

public long[] toPackedArray()

toString

public java.lang.String toString()
Specified by:
toString in interface IntSet
Overrides:
toString in class java.lang.Object

toString

public java.lang.String toString(Grammar g)
Transform a bit set into a string by formatting each element as an integer separator The string to put in between elements

Specified by:
toString in interface IntSet
Returns:
A commma-separated list of values

toString

public java.lang.String toString(java.lang.String separator,
                                 java.util.List 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

Returns:
A commma-separated list of character constants.

toStringOfHalfWords

public java.lang.String toStringOfHalfWords()
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.


toStringOfWords

public java.lang.String toStringOfWords()
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.


toStringWithRanges

public java.lang.String toStringWithRanges()