Class BitSet

  • All Implemented Interfaces:
    java.lang.Cloneable

    public class BitSet
    extends java.lang.Object
    implements java.lang.Cloneable
    An "open" BitSet implementation that allows direct access to the array of words storing the bits.

    Unlike java.util.bitset, the fact that bits are packed into an array of longs is part of the interface. This allows efficient implementation of other algorithms by someone other than the author. It also allows one to efficiently implement alternate serialization or interchange formats.

    The index range for a bitset can easily exceed positive int range in Java (0x7fffffff), so many methods in this class accept or return a long. There are adapter methods that return views compatible with LongLookupContainer and IntLookupContainer interfaces.

    See Also:
    asIntLookupContainer(), asLongLookupContainer()
    • Field Summary

      Fields 
      Modifier and Type Field Description
      long[] bits
      Internal representation of bits in this bit set.
      int wlen
      The number of words (longs) used in the bits array.
    • Constructor Summary

      Constructors 
      Constructor Description
      BitSet()
      Constructs a bit set with the default capacity.
      BitSet​(long numBits)
      Constructs an BitSet large enough to hold numBits.
      BitSet​(long[] bits, int numWords)
      Constructs an BitSet from an existing long[].
    • Field Detail

      • bits

        public long[] bits
        Internal representation of bits in this bit set.
      • wlen

        public int wlen
        The number of words (longs) used in the bits array.
    • Constructor Detail

      • BitSet

        public BitSet()
        Constructs a bit set with the default capacity.
      • BitSet

        public BitSet​(long numBits)
        Constructs an BitSet large enough to hold numBits.
        Parameters:
        numBits - Number of bits
      • BitSet

        public BitSet​(long[] bits,
                      int numWords)
        Constructs an BitSet from an existing long[]. The first 64 bits are in long[0], with bit index 0 at the least significant bit, and bit index 63 at the most significant. Given a bit index, the word containing it is long[index/64], and it is at bit number index%64 within that word. numWords are the number of elements in the array that contain set bits (non-zero longs). numWords should be <= bits.length, and any existing words in the array at position >= numWords should be zero.
        Parameters:
        bits - underlying bits buffer
        numWords - the number of elements in the array that contain set bits
    • Method Detail

      • newInstance

        public static BitSet newInstance()
        Static constructor-like method similar to other (generic) collections.
        Returns:
        New instance.
      • iterator

        public BitSetIterator iterator()
        Returns:
        Returns an iterator over all set bits of this bitset. The iterator should be faster than using a loop around nextSetBit(int).
      • capacity

        public long capacity()
        Returns:
        Returns the current capacity in bits (1 greater than the index of the last bit).
      • size

        public long size()
        Returns:
        Returns the current capacity of this set. Included for compatibility. This is not equal to cardinality().
        See Also:
        cardinality(), BitSet.size()
      • length

        public long length()
        Returns:
        Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.
        See Also:
        BitSet.length()
      • isEmpty

        public boolean isEmpty()
        Returns:
        Returns true if there are no set bits
      • get

        public boolean get​(int index)
        Parameters:
        index - The index.
        Returns:
        Returns true or false for the specified bit index.
      • get

        public boolean get​(long index)
        Parameters:
        index - The index.
        Returns:
        Returns true or false for the specified bit index.
      • set

        public void set​(long index)
        Sets a bit, expanding the set size if necessary.
        Parameters:
        index - the index to set
      • set

        public void set​(long startIndex,
                        long endIndex)
        Sets a range of bits, expanding the set size if necessary
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to set
      • expandingWordNum

        protected int expandingWordNum​(long index)
      • clear

        public void clear()
        Clears all bits.
      • clear

        public void clear​(long index)
        clears a bit, allowing access beyond the current set size without changing the size.
        Parameters:
        index - the index to clear
      • clear

        public void clear​(int startIndex,
                          int endIndex)
        Clears a range of bits. Clearing past the end does not change the size of the set.
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to clear
      • clear

        public void clear​(long startIndex,
                          long endIndex)
        Clears a range of bits. Clearing past the end does not change the size of the set.
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to clear
      • getAndSet

        public boolean getAndSet​(int index)
        Sets a bit and returns the previous value. The index should be less than the BitSet size.
        Parameters:
        index - the index to set
        Returns:
        previous state of the index
      • getAndSet

        public boolean getAndSet​(long index)
        Sets a bit and returns the previous value. The index should be less than the BitSet size.
        Parameters:
        index - the index to set
        Returns:
        previous state of the index
      • flip

        public void flip​(long index)
        Flips a bit, expanding the set size if necessary.
        Parameters:
        index - the index to flip
      • flipAndGet

        public boolean flipAndGet​(int index)
        flips a bit and returns the resulting bit value. The index should be less than the BitSet size.
        Parameters:
        index - the index to flip
        Returns:
        previous state of the index
      • flipAndGet

        public boolean flipAndGet​(long index)
        flips a bit and returns the resulting bit value. The index should be less than the BitSet size.
        Parameters:
        index - the index to flip
        Returns:
        previous state of the index
      • flip

        public void flip​(long startIndex,
                         long endIndex)
        Flips a range of bits, expanding the set size if necessary
        Parameters:
        startIndex - lower index
        endIndex - one-past the last bit to flip
      • cardinality

        public long cardinality()
        Returns:
        the number of set bits
      • intersectionCount

        public static long intersectionCount​(BitSet a,
                                             BitSet b)
        Parameters:
        a - The first set
        b - The second set
        Returns:
        Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.
      • unionCount

        public static long unionCount​(BitSet a,
                                      BitSet b)
        Parameters:
        a - The first set
        b - The second set
        Returns:
        Returns the popcount or cardinality of the union of the two sets. Neither set is modified.
      • andNotCount

        public static long andNotCount​(BitSet a,
                                       BitSet b)
        Parameters:
        a - The first set
        b - The second set
        Returns:
        Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.
      • xorCount

        public static long xorCount​(BitSet a,
                                    BitSet b)
        Parameters:
        a - The first set
        b - The second set
        Returns:
        Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.
      • nextSetBit

        public int nextSetBit​(int index)
        Parameters:
        index - The index to start scanning from, inclusive.
        Returns:
        Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
      • nextSetBit

        public long nextSetBit​(long index)
        Parameters:
        index - The index to start scanning from, inclusive.
        Returns:
        Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
      • clone

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

        public void intersect​(BitSet other)
        this = this AND other
        Parameters:
        other - The bitset to intersect with.
      • union

        public void union​(BitSet other)
        this = this OR other
        Parameters:
        other - The bitset to union with.
      • remove

        public void remove​(BitSet other)
        Remove all elements set in other: this = this AND_NOT other
        Parameters:
        other - The other bitset.
      • xor

        public void xor​(BitSet other)
        this = this XOR other
        Parameters:
        other - The other bitset.
      • and

        public void and​(BitSet other)
      • or

        public void or​(BitSet other)
      • andNot

        public void andNot​(BitSet other)
      • intersects

        public boolean intersects​(BitSet other)
        Parameters:
        other - The other bitset.
        Returns:
        true if the sets have any elements in common
      • ensureCapacityWords

        public void ensureCapacityWords​(int numWords)
        Expand the long[] with the size given as a number of words (64 bit longs). getNumWords() is unchanged by this call.
        Parameters:
        numWords - The size to expand to (64-bit long words)
      • grow

        public static long[] grow​(long[] array,
                                  int minSize)
      • getNextSize

        public static int getNextSize​(int targetSize)
      • ensureCapacity

        public void ensureCapacity​(long numBits)
        Ensure that the long[] is big enough to hold numBits, expanding it if necessary. getNumWords() is unchanged by this call.
        Parameters:
        numBits - The number of bits to expand to
      • trimTrailingZeros

        public void trimTrailingZeros()
        Lowers wlen, the number of words in use, by checking for trailing zero words.
      • bits2words

        public static int bits2words​(long numBits)
      • equals

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

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

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

        public IntLookupContainer asIntLookupContainer()
        Returns a view over this bitset data compatible with IntLookupContainer. A new object is always returned, but its methods reflect the current state of the bitset (the view is not a snapshot).

        Methods of the returned IntLookupContainer may throw a RuntimeException if the cardinality of this bitset exceeds the int range.

        Returns:
        The view of this bitset as IntLookupContainer.
      • asLongLookupContainer

        public LongLookupContainer asLongLookupContainer()
        Returns a view over this bitset data compatible with LongLookupContainer. A new object is always returned, but its methods reflect the current state of the bitset (the view is not a snapshot).
        Returns:
        The view of this bitset as LongLookupContainer.