Class BitSet

  • All Implemented Interfaces:
    java.lang.Cloneable

    public class BitSet
    extends java.lang.Object
    implements 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,
    Pete Wells
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected long[] bits
      The actual data bits
      protected static int BITS  
      protected static int LOG_BITS  
      protected static int MOD_MASK  
      protected static int NIBBLE  
    • Constructor Summary

      Constructors 
      Constructor Description
      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

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int el)
      or this element into this set (grow as necessary to accommodate)
      BitSet and​(BitSet a)  
      void andInPlace​(BitSet a)  
      void clear()  
      void clear​(int el)  
      java.lang.Object clone()  
      int degree()  
      boolean equals​(java.lang.Object obj)
      code "inherited" from java.util.BitSet
      static Vector getRanges​(int[] elems)
      Find ranges in a set element array.
      void growToInclude​(int bit)
      Grows the set to a larger number of bits.
      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)  
      boolean nil()  
      BitSet not()  
      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.
      static BitSet of​(int el)  
      BitSet or​(BitSet a)
      return this | a in a new set
      void orInPlace​(BitSet a)  
      void remove​(int el)  
      int size()  
      boolean subset​(BitSet a)
      Is this contained within a?
      void subtractInPlace​(BitSet a)
      Subtract the elements of 'a' from 'this' in-place.
      int[] toArray()  
      long[] toPackedArray()  
      java.lang.String toString()  
      java.lang.String toString​(java.lang.String separator)
      Transform a bit set into a string by formatting each element as an integer
      java.lang.String toString​(java.lang.String separator, CharFormatter formatter)
      Transform a bit set into a string of characters.
      java.lang.String toString​(java.lang.String separator, Vector 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​(java.lang.String separator, CharFormatter formatter)
      Print out the bit set but collapse char ranges.
      • Methods inherited from class java.lang.Object

        finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • 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)
      • 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
      • degree

        public int degree()
      • equals

        public boolean equals​(java.lang.Object obj)
        code "inherited" from java.util.BitSet
        Overrides:
        equals in class java.lang.Object
      • getRanges

        public static Vector getRanges​(int[] elems)
        Find ranges in a set element array. @param elems The array of elements representing the set, usually from Bit Set.toArray().
        Returns:
        Vector of ranges.
      • 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)
      • nil

        public boolean nil()
      • 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)
      • or

        public BitSet or​(BitSet a)
        return this | a in a new set
      • orInPlace

        public void orInPlace​(BitSet a)
      • remove

        public void remove​(int el)
      • size

        public int size()
      • 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'.
      • toArray

        public int[] toArray()
      • toPackedArray

        public long[] toPackedArray()
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • toString

        public java.lang.String toString​(java.lang.String separator)
        Transform a bit set into a string by formatting each element as an integer
        Returns:
        A commma-separated list of values
      • toString

        public java.lang.String toString​(java.lang.String separator,
                                         CharFormatter formatter)
        Transform a bit set into a string of characters.
        Parameters:
        formatter - An object implementing the CharFormatter interface.
        Returns:
        A commma-separated list of character constants.
      • toString

        public java.lang.String toString​(java.lang.String separator,
                                         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.
        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​(java.lang.String separator,
                                                   CharFormatter formatter)
        Print out the bit set but collapse char ranges.