Package com.carrotsearch.hppc
Class BitSet
java.lang.Object
com.carrotsearch.hppc.BitSet
- All Implemented Interfaces:
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.
-
Field Summary
FieldsModifier and TypeFieldDescriptionlong[]
Internal representation of bits in this bit set.private static final long
The initial default number of bits (64L).int
The number of words (longs) used in thebits
array. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
void
static long
andNotCount
(BitSet a, BitSet b) Returns a view over this bitset data compatible withIntLookupContainer
.Returns a view over this bitset data compatible withLongLookupContainer
.static int
bits2words
(long numBits) long
capacity()
long
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.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
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 necessaryboolean
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) boolean
get
(long 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
this = this AND otherstatic long
intersectionCount
(BitSet a, BitSet b) boolean
intersects
(BitSet other) boolean
isEmpty()
iterator()
long
length()
static BitSet
Static constructor-like method similar to other (generic) collections.int
nextSetBit
(int index) long
nextSetBit
(long index) void
void
Remove all elements set in other: this = this AND_NOT othervoid
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 necessarylong
size()
toString()
void
Lowerswlen
, the number of words in use, by checking for trailing zero words.void
this = this OR otherstatic long
unionCount
(BitSet a, BitSet b) void
this = this XOR otherstatic long
-
Field Details
-
DEFAULT_NUM_BITS
private static final long DEFAULT_NUM_BITSThe initial default number of bits (64L).- See Also:
-
bits
public long[] bitsInternal representation of bits in this bit set. -
wlen
public int wlenThe number of words (longs) used in thebits
array.
-
-
Constructor Details
-
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 buffernumWords
- the number of elements in the array that contain set bits
-
-
Method Details
-
newInstance
Static constructor-like method similar to other (generic) collections.- Returns:
- New instance.
-
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:
-
length
public long length()- Returns:
- Returns the "logical size" of this
BitSet
: the index of the highest set bit in theBitSet
plus one. - See Also:
-
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 indexendIndex
- 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 indexendIndex
- 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 indexendIndex
- 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 indexendIndex
- one-past the last bit to flip
-
cardinality
public long cardinality()- Returns:
- the number of set bits
-
intersectionCount
- Parameters:
a
- The first setb
- The second set- Returns:
- Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.
-
unionCount
- Parameters:
a
- The first setb
- The second set- Returns:
- Returns the popcount or cardinality of the union of the two sets. Neither set is modified.
-
andNotCount
- Parameters:
a
- The first setb
- The second set- Returns:
- Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.
-
xorCount
- Parameters:
a
- The first setb
- 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
-
intersect
this = this AND other- Parameters:
other
- The bitset to intersect with.
-
union
this = this OR other- Parameters:
other
- The bitset to union with.
-
remove
Remove all elements set in other: this = this AND_NOT other- Parameters:
other
- The other bitset.
-
xor
this = this XOR other- Parameters:
other
- The other bitset.
-
and
-
or
-
andNot
-
intersects
- 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()Lowerswlen
, the number of words in use, by checking for trailing zero words. -
bits2words
public static int bits2words(long numBits) -
equals
-
hashCode
public int hashCode() -
toString
-
asIntLookupContainer
Returns a view over this bitset data compatible withIntLookupContainer
. 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 aRuntimeException
if the cardinality of this bitset exceeds the int range.- Returns:
- The view of this bitset as
IntLookupContainer
.
-
asLongLookupContainer
Returns a view over this bitset data compatible withLongLookupContainer
. 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
.
-