Package com.googlecode.javaewah.datastructure

Class BitSet

java.lang.Object
com.googlecode.javaewah.datastructure.BitSet
All Implemented Interfaces:
WordArray, Externalizable, Serializable, Cloneable, Iterable<Integer>
public class BitSet extends Object implements Cloneable, Iterable<Integer>, 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:

  • Field Details

    • data

      long[] data

    • serialVersionUID

      static final long serialVersionUID
      See Also:

  • Constructor Details

    • 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 Details

    • 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 Object

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class 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 Object

    • intIterator

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

    • iterator

      public Iterator<Integer> iterator()
      Specified by:
      iterator in interface Iterable<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(ObjectOutput out) throws IOException
      Specified by:
      writeExternal in interface Externalizable
      Throws:
      IOException

    • readExternal

      public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
      Specified by:
      readExternal in interface Externalizable
      Throws:
      IOException
      ClassNotFoundException

    • serialize

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

    • deserialize

      public void deserialize(DataInput in) throws IOException
      Deserialize.
      Parameters:
      in - the DataInput stream
      Throws:
      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 String toString()
      Overrides:
      toString in class Object