Class BitSet

  • All Implemented Interfaces:
    WordArray, java.io.Externalizable, java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<java.lang.Integer>

    public class BitSet
    extends java.lang.Object
    implements java.lang.Cloneable, java.lang.Iterable<java.lang.Integer>, java.io.Externalizable, WordArray

    This is an optimized version of Java's BitSet. In many cases, it can be used as a drop-in replacement.

    It differs from the basic Java BitSet class in the following ways:

    • You can iterate over set bits using a simpler syntax for(int bs: myBitset).
    • You can compute the cardinality of an intersection and union without writing it out or modifying your BitSets (see methods such as andcardinality).
    • You can recover wasted memory with trim().
    • It does not implicitly expand: you have to explicitly call resize. This helps to keep memory usage in check.
    • It supports memory-file mapping (see the ImmutableBitSet class).
    • It supports faster and more efficient serialization functions (serialize and deserialize).
    Since:
    0.8.0
    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) long[] data  
      (package private) static long serialVersionUID  
    • Constructor Summary

      Constructors 
      Constructor Description
      BitSet()  
      BitSet​(int sizeInBits)
      Construct a bitset with the specified number of bits (initially all false).
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void and​(WordArray bs)
      Compute bitwise AND.
      int andcardinality​(WordArray bs)
      Compute cardinality of bitwise AND.
      void andNot​(WordArray bs)
      Compute bitwise AND NOT.
      int andNotcardinality​(WordArray bs)
      Compute cardinality of bitwise AND NOT.
      static BitSet bitmapOf​(int... setBits)
      Return a bitmap with the bit set to true at the given positions.
      int cardinality()
      Compute the number of bits set to 1
      void clear()
      Reset all bits to false.
      void clear​(int index)
      Set the bit to false.
      void clear​(int start, int end)
      Set the bits in the range of indexes to false.
      BitSet clone()  
      void deserialize​(java.io.DataInput in)
      Deserialize.
      boolean empty()
      Check whether a bitset contains a set bit.
      boolean equals​(java.lang.Object o)  
      void flip​(int i)
      Flip the bit.
      void flip​(int start, int end)
      Flip the bits in the range of indexes.
      boolean get​(int i)
      Get the value of the bit.
      int getNumberOfWords()
      Get the total number of words contained in this data structure.
      long getWord​(int index)
      Get the word at the given index
      int hashCode()  
      boolean intersects​(WordArray bs)
      Checks whether two bitsets intersect.
      IntIterator intIterator()
      Iterate over the set bits
      java.util.Iterator<java.lang.Integer> iterator()  
      int nextSetBit​(int i)
      Usage: for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) { operate on index i here }
      int nextUnsetBit​(int i)
      Usage: for(int i=bs.nextUnsetBit(0); i>=0; i=bs.nextUnsetBit(i+1)) { operate on index i here }
      void or​(WordArray bs)
      Compute bitwise OR.
      int orcardinality​(WordArray bs)
      Compute cardinality of bitwise OR.
      void readExternal​(java.io.ObjectInput in)  
      void removeWord​(int i)
      Remove a word.
      void resize​(int sizeInBits)
      Resize the bitset
      void serialize​(java.io.DataOutput out)
      Serialize.
      void set​(int i)
      Set to true.
      void set​(int i, boolean b)
      Set to some value.
      void set​(int start, int end)
      Set the bits in the range of indexes true.
      void set​(int start, int end, boolean v)
      Set the bits in the range of indexes to the specified Boolean value.
      int size()
      Query the size
      java.lang.String toString()  
      void trim()
      Recovers wasted memory
      void unset​(int i)
      Set to false
      IntIterator unsetIntIterator()
      Iterate over the unset bits
      void writeExternal​(java.io.ObjectOutput out)  
      void xor​(WordArray bs)
      Compute bitwise XOR.
      int xorcardinality​(WordArray bs)
      Compute cardinality of bitwise XOR.
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator
    • Constructor Detail

      • BitSet

        public BitSet​(int sizeInBits)
        Construct a bitset with the specified number of bits (initially all false). The number of bits is rounded up to the nearest multiple of 64.
        Parameters:
        sizeInBits - the size in bits
      • BitSet

        public BitSet()
    • Method Detail

      • and

        public void and​(WordArray bs)
        Compute bitwise AND.
        Parameters:
        bs - other bitset
      • andcardinality

        public int andcardinality​(WordArray bs)
        Compute cardinality of bitwise AND. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.
        Parameters:
        bs - other bitset
        Returns:
        cardinality
      • andNot

        public void andNot​(WordArray bs)
        Compute bitwise AND NOT. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.
        Parameters:
        bs - other bitset
      • andNotcardinality

        public int andNotcardinality​(WordArray bs)
        Compute cardinality of bitwise AND NOT.
        Parameters:
        bs - other bitset
        Returns:
        cardinality
      • cardinality

        public int cardinality()
        Compute the number of bits set to 1
        Returns:
        the number of bits
      • clear

        public void clear()
        Reset all bits to false. This might be wasteful: a better approach is to create a new empty bitmap.
      • clear

        public void clear​(int index)
        Set the bit to false. See unset(int)
        Parameters:
        index - location of the bit
      • clear

        public void clear​(int start,
                          int end)
        Set the bits in the range of indexes to false. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        start - location of the first bit to set to zero
        end - location of the last bit to set to zero (not included)
      • clone

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

        public boolean equals​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object
      • empty

        public boolean empty()
        Check whether a bitset contains a set bit.
        Returns:
        true if no set bit is found
      • flip

        public void flip​(int i)
        Flip the bit. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        i - index of the bit
      • flip

        public void flip​(int start,
                         int end)
        Flip the bits in the range of indexes. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        start - location of the first bit
        end - location of the last bit (not included)
      • get

        public boolean get​(int i)
        Get the value of the bit. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        i - index
        Returns:
        value of the bit
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • intIterator

        public IntIterator intIterator()
        Iterate over the set bits
        Returns:
        an iterator
      • iterator

        public java.util.Iterator<java.lang.Integer> iterator()
        Specified by:
        iterator in interface java.lang.Iterable<java.lang.Integer>
      • intersects

        public boolean intersects​(WordArray bs)
        Checks whether two bitsets intersect.
        Parameters:
        bs - other bitset
        Returns:
        true if they have a non-empty intersection (result of AND)
      • nextSetBit

        public int nextSetBit​(int i)
        Usage: for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) { operate on index i here }
        Parameters:
        i - current set bit
        Returns:
        next set bit or -1
      • nextUnsetBit

        public int nextUnsetBit​(int i)
        Usage: for(int i=bs.nextUnsetBit(0); i>=0; i=bs.nextUnsetBit(i+1)) { operate on index i here }
        Parameters:
        i - current unset bit
        Returns:
        next unset bit or -1
      • or

        public void or​(WordArray bs)
        Compute bitwise OR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.
        Parameters:
        bs - other bitset
      • orcardinality

        public int orcardinality​(WordArray bs)
        Compute cardinality of bitwise OR. BitSets are not modified.
        Parameters:
        bs - other bitset
        Returns:
        cardinality
      • removeWord

        public void removeWord​(int i)
        Remove a word.
        Parameters:
        i - index of the word to be removed.
      • resize

        public void resize​(int sizeInBits)
        Resize the bitset
        Parameters:
        sizeInBits - new number of bits
      • set

        public void set​(int i)
        Set to true. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        i - index of the bit
      • set

        public void set​(int i,
                        boolean b)
        Set to some value. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        i - index
        b - value of the bit
      • set

        public void set​(int start,
                        int end)
        Set the bits in the range of indexes true. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        start - location of the first bit
        end - location of the last bit (not included)
      • set

        public void set​(int start,
                        int end,
                        boolean v)
        Set the bits in the range of indexes to the specified Boolean value. This might throw an exception if size() is insufficient, consider calling resize().
        Parameters:
        start - location of the first bit
        end - location of the last bit (not included)
        v - Boolean value
      • size

        public int size()
        Query the size
        Returns:
        the size in bits.
      • trim

        public void trim()
        Recovers wasted memory
      • unset

        public void unset​(int i)
        Set to false
        Parameters:
        i - index of the bit
      • unsetIntIterator

        public IntIterator unsetIntIterator()
        Iterate over the unset bits
        Returns:
        an iterator
      • writeExternal

        public void writeExternal​(java.io.ObjectOutput out)
                           throws java.io.IOException
        Specified by:
        writeExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
      • readExternal

        public void readExternal​(java.io.ObjectInput in)
                          throws java.io.IOException,
                                 java.lang.ClassNotFoundException
        Specified by:
        readExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException
      • serialize

        public void serialize​(java.io.DataOutput out)
                       throws java.io.IOException
        Serialize. The current bitmap is not modified.
        Parameters:
        out - the DataOutput stream
        Throws:
        java.io.IOException - Signals that an I/O exception has occurred.
      • deserialize

        public void deserialize​(java.io.DataInput in)
                         throws java.io.IOException
        Deserialize.
        Parameters:
        in - the DataInput stream
        Throws:
        java.io.IOException - Signals that an I/O exception has occurred.
      • xor

        public void xor​(WordArray bs)
        Compute bitwise XOR. The current bitmap is modified. Consider calling trim() to recover wasted memory afterward.
        Parameters:
        bs - other bitset
      • xorcardinality

        public int xorcardinality​(WordArray bs)
        Compute cardinality of bitwise XOR. BitSets are not modified.
        Parameters:
        bs - other bitset
        Returns:
        cardinality
      • getNumberOfWords

        public int getNumberOfWords()
        Description copied from interface: WordArray
        Get the total number of words contained in this data structure.
        Specified by:
        getNumberOfWords in interface WordArray
        Returns:
        the number
      • getWord

        public long getWord​(int index)
        Description copied from interface: WordArray
        Get the word at the given index
        Specified by:
        getWord in interface WordArray
        Parameters:
        index - the index
        Returns:
        the word
      • bitmapOf

        public static BitSet bitmapOf​(int... setBits)
        Return a bitmap with the bit set to true at the given positions. (This is a convenience method.)
        Parameters:
        setBits - list of set bit positions
        Returns:
        the bitmap
      • toString

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