com.carrotsearch.hppc
Class BitSet

java.lang.Object
  extended by com.carrotsearch.hppc.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.

Author:
"Original implementation from the Lucene project."
See Also:
asIntLookupContainer(), asLongLookupContainer()

Field Summary
 long[] bits
          Internal representation of bits in this bit set.
 int wlen
          The number of words (longs) used in the bits array.
 
Constructor Summary
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[].
 
Method Summary
 void and(BitSet other)
           
 void andNot(BitSet other)
           
static long andNotCount(BitSet a, BitSet b)
          Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))".
 IntLookupContainer asIntLookupContainer()
          Returns a view over this bitset data compatible with IntLookupContainer.
 LongLookupContainer asLongLookupContainer()
          Returns a view over this bitset data compatible with LongLookupContainer.
static int bits2words(long numBits)
          returns the number of 64 bit words it would take to hold numBits
 long capacity()
          Returns the current capacity in bits (1 greater than the index of the last bit).
 long cardinality()
           
 void clear()
          Clears all bits.
 void clear(int startIndex, int endIndex)
          Clears a range of bits.
 void clear(long index)
          clears a bit, allowing access beyond the current set size without changing the size.
 void clear(long startIndex, long endIndex)
          Clears a range of bits.
 java.lang.Object clone()
           
 void ensureCapacity(long numBits)
          Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
 void ensureCapacityWords(int numWords)
          Expand the long[] with the size given as a number of words (64 bit longs).
 boolean equals(java.lang.Object o)
          returns true if both sets have the same bits set
protected  int expandingWordNum(long index)
           
 void flip(long index)
          Flips a bit, expanding the set size if necessary.
 void flip(long startIndex, long endIndex)
          Flips a range of bits, expanding the set size if necessary
 boolean flipAndGet(int index)
          flips a bit and returns the resulting bit value.
 boolean flipAndGet(long index)
          flips a bit and returns the resulting bit value.
 boolean get(int index)
          Returns true or false for the specified bit index.
 boolean get(long index)
          Returns true or false for the specified bit index.
 boolean getAndSet(int index)
          Sets a bit and returns the previous value.
 boolean getAndSet(long index)
          Sets a bit and returns the previous value.
static int getNextSize(int targetSize)
           
static long[] grow(long[] array, int minSize)
           
 int hashCode()
           
 void intersect(BitSet other)
          this = this AND other
static long intersectionCount(BitSet a, BitSet b)
          Returns the popcount or cardinality of the intersection of the two sets.
 boolean intersects(BitSet other)
          returns true if the sets have any elements in common
 boolean isEmpty()
          Returns true if there are no set bits
 BitSetIterator iterator()
           
 long length()
           
 int nextSetBit(int index)
          Returns the index of the first set bit starting at the index specified.
 long nextSetBit(long index)
          Returns the index of the first set bit starting at the index specified.
 void or(BitSet other)
           
 void remove(BitSet other)
          Remove all elements set in other.
 void set(long index)
          Sets a bit, expanding the set size if necessary.
 void set(long startIndex, long endIndex)
          Sets a range of bits, expanding the set size if necessary
 long size()
          Returns the current capacity of this set.
 java.lang.String toString()
           
 void trimTrailingZeros()
          Lowers wlen, the number of words in use, by checking for trailing zero words.
 void union(BitSet other)
          this = this OR other
static long unionCount(BitSet a, BitSet b)
          Returns the popcount or cardinality of the union of the two sets.
 void xor(BitSet other)
          this = this XOR other
static long xorCount(BitSet a, BitSet b)
          Returns the popcount or cardinality of the exclusive-or of the two sets.
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

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.


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.

Method Detail

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 the current capacity in bits (1 greater than the index of the last bit).


size

public long size()
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()
See Also:
BitSet.length()

isEmpty

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


get

public boolean get(int index)
Returns true or false for the specified bit index.


get

public boolean get(long index)
Returns true or false for the specified bit index.


set

public void set(long index)
Sets a bit, expanding the set size if necessary.


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.


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.


getAndSet

public boolean getAndSet(long index)
Sets a bit and returns the previous value. The index should be less than the BitSet size.


flip

public void flip(long index)
Flips a bit, expanding the set size if necessary.


flipAndGet

public boolean flipAndGet(int index)
flips a bit and returns the resulting bit value. The index should be less than the BitSet size.


flipAndGet

public boolean flipAndGet(long index)
flips a bit and returns the resulting bit value. The index should be less than the BitSet size.


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)
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)
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)
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)
Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.


nextSetBit

public int nextSetBit(int index)
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)
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


union

public void union(BitSet other)
this = this OR other


remove

public void remove(BitSet other)
Remove all elements set in other. this = this AND_NOT other


xor

public void xor(BitSet other)
this = this XOR other


and

public void and(BitSet other)

or

public void or(BitSet other)

andNot

public void andNot(BitSet other)

intersects

public boolean intersects(BitSet other)
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.


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.


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)
returns the number of 64 bit words it would take to hold numBits


equals

public boolean equals(java.lang.Object o)
returns true if both sets have the same bits set

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.


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).



Copyright © 2011 Carrot Search s.c.. All Rights Reserved.