Package com.carrotsearch.hppc
Class BitSet
- java.lang.Object
-
- 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 along
. There are adapter methods that return views compatible withLongLookupContainer
andIntLookupContainer
interfaces.- See Also:
asIntLookupContainer()
,asLongLookupContainer()
-
-
Field Summary
Fields Modifier and Type Field Description long[]
bits
Internal representation of bits in this bit set.private static long
DEFAULT_NUM_BITS
The initial default number of bits (64L).int
wlen
The number of words (longs) used in thebits
array.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
and(BitSet other)
void
andNot(BitSet other)
static long
andNotCount(BitSet a, BitSet b)
IntLookupContainer
asIntLookupContainer()
Returns a view over this bitset data compatible withIntLookupContainer
.LongLookupContainer
asLongLookupContainer()
Returns a view over this bitset data compatible withLongLookupContainer
.static int
bits2words(long numBits)
long
capacity()
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)
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
intersect(BitSet other)
this = this AND otherstatic long
intersectionCount(BitSet a, BitSet b)
boolean
intersects(BitSet other)
boolean
isEmpty()
BitSetIterator
iterator()
long
length()
static BitSet
newInstance()
Static constructor-like method similar to other (generic) collections.int
nextSetBit(int index)
long
nextSetBit(long index)
void
or(BitSet other)
void
remove(BitSet other)
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()
java.lang.String
toString()
void
trimTrailingZeros()
Lowerswlen
, the number of words in use, by checking for trailing zero words.void
union(BitSet other)
this = this OR otherstatic long
unionCount(BitSet a, BitSet b)
void
xor(BitSet other)
this = this XOR otherstatic long
xorCount(BitSet a, BitSet b)
-
-
-
Field Detail
-
DEFAULT_NUM_BITS
private static final long DEFAULT_NUM_BITS
The initial default number of bits (64L).- See Also:
- Constant Field Values
-
bits
public long[] bits
Internal representation of bits in this bit set.
-
wlen
public int wlen
The number of words (longs) used in thebits
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 buffernumWords
- 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 theBitSet
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 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
public static long intersectionCount(BitSet a, BitSet b)
- 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
public static long unionCount(BitSet a, BitSet b)
- 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
public static long andNotCount(BitSet a, BitSet b)
- 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
public static long xorCount(BitSet a, BitSet b)
- 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
public java.lang.Object clone()
- Overrides:
clone
in classjava.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()
Lowerswlen
, 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 classjava.lang.Object
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
asIntLookupContainer
public IntLookupContainer 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
public LongLookupContainer 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
.
-
-