public class OpenBitSet extends DocIdSet implements Cloneable, Serializable, Bits
OpenBitSet
is faster than java.util.BitSet
in most operations
and *much* faster at calculating cardinality of sets and results of set operations.
It can also handle sets of larger cardinality (up to 64 * 2**32-1)
The goals of OpenBitSet
are the fastest implementation possible, and
maximum code reuse. Extra safety and encapsulation
may always be built on top, but if that's built in, the cost can never be removed (and
hence people re-implement their own version in order to get better performance).
If you want a "safe", totally encapsulated (and slower and limited) BitSet
class, use java.util.BitSet
.
cardinality | intersect_count | union | nextSetBit | get | iterator | |
---|---|---|---|---|---|---|
50% full | 3.36 | 3.96 | 1.44 | 1.46 | 1.99 | 1.58 |
1% full | 3.31 | 3.90 | 1.04 | 0.99 |
cardinality | intersect_count | union | nextSetBit | get | iterator | |
---|---|---|---|---|---|---|
50% full | 2.50 | 3.50 | 1.00 | 1.03 | 1.12 | 1.25 |
1% full | 2.51 | 3.49 | 1.00 | 1.02 |
Bits.MatchAllBits, Bits.MatchNoBits
Modifier and Type | Field and Description |
---|---|
protected long[] |
bits |
protected int |
wlen |
EMPTY_DOCIDSET
EMPTY_ARRAY
Constructor and Description |
---|
OpenBitSet() |
OpenBitSet(long numBits)
Constructs an OpenBitSet large enough to hold numBits.
|
OpenBitSet(long[] bits,
int numWords)
Constructs an OpenBitSet from an existing long[].
|
Modifier and Type | Method and Description |
---|---|
void |
and(OpenBitSet other) |
void |
andNot(OpenBitSet other) |
static long |
andNotCount(OpenBitSet a,
OpenBitSet b)
Returns the popcount or cardinality of "a and not b"
or "intersection(a, not(b))".
|
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(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.
|
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(Object o)
returns true if both sets have the same bits set
|
protected int |
expandingWordNum(long index) |
void |
fastClear(int index)
clears a bit.
|
void |
fastClear(long index)
clears a bit.
|
void |
fastFlip(int index)
flips a bit.
|
void |
fastFlip(long index)
flips a bit.
|
boolean |
fastGet(int index)
Returns true or false for the specified bit index.
|
boolean |
fastGet(long index)
Returns true or false for the specified bit index.
|
void |
fastSet(int index)
Sets the bit at the specified index.
|
void |
fastSet(long index)
Sets the bit at the specified 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.
|
int |
getBit(int index)
returns 1 if the bit is set, 0 if not.
|
long[] |
getBits()
Expert: returns the long[] storing the bits
|
int |
getNumWords()
Expert: gets the number of longs in the array that are in use
|
int |
hashCode() |
void |
intersect(OpenBitSet other)
this = this AND other
|
static long |
intersectionCount(OpenBitSet a,
OpenBitSet b)
Returns the popcount or cardinality of the intersection of the two sets.
|
boolean |
intersects(OpenBitSet other)
returns true if the sets have any elements in common
|
boolean |
isCacheable()
This DocIdSet implementation is cacheable.
|
boolean |
isEmpty()
Returns true if there are no set bits
|
DocIdSetIterator |
iterator()
Provides a
DocIdSetIterator to access the set. |
int |
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(OpenBitSet other) |
int |
prevSetBit(int index)
Returns the index of the first set bit starting downwards at
the index specified
|
long |
prevSetBit(long index)
Returns the index of the first set bit starting downwards at
the index specified
|
void |
remove(OpenBitSet other)
Remove all elements set in other. this = this AND_NOT 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
|
void |
setBits(long[] bits)
Expert: sets a new long[] to use as the bit storage
|
void |
setNumWords(int nWords)
Expert: sets the number of longs in the array that are in use
|
long |
size()
Returns the current capacity of this set.
|
void |
trimTrailingZeros()
Lowers numWords, the number of words in use,
by checking for trailing zero words.
|
void |
union(OpenBitSet other)
this = this OR other
|
static long |
unionCount(OpenBitSet a,
OpenBitSet b)
Returns the popcount or cardinality of the union of the two sets.
|
void |
xor(OpenBitSet other)
this = this XOR other
|
static long |
xorCount(OpenBitSet a,
OpenBitSet b)
Returns the popcount or cardinality of the exclusive-or of the two sets.
|
public OpenBitSet(long numBits)
numBits
- public OpenBitSet()
public OpenBitSet(long[] bits, int numWords)
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.
public DocIdSetIterator iterator()
DocIdSet
DocIdSetIterator
to access the set.
This implementation can return null
or
DocIdSet.EMPTY_DOCIDSET.iterator()
if there
are no docs that match.public boolean isCacheable()
isCacheable
in class DocIdSet
public long capacity()
public long size()
cardinality()
public boolean isEmpty()
public long[] getBits()
public void setBits(long[] bits)
public int getNumWords()
public void setNumWords(int nWords)
public boolean get(int index)
public boolean fastGet(int index)
public boolean get(long index)
public boolean fastGet(long index)
public int getBit(int index)
public void set(long index)
public void fastSet(int index)
public void fastSet(long index)
public void set(long startIndex, long endIndex)
startIndex
- lower indexendIndex
- one-past the last bit to setprotected int expandingWordNum(long index)
public void fastClear(int index)
public void fastClear(long index)
public void clear(long index)
public void clear(int startIndex, int endIndex)
startIndex
- lower indexendIndex
- one-past the last bit to clearpublic void clear(long startIndex, long endIndex)
startIndex
- lower indexendIndex
- one-past the last bit to clearpublic boolean getAndSet(int index)
public boolean getAndSet(long index)
public void fastFlip(int index)
public void fastFlip(long index)
public void flip(long index)
public boolean flipAndGet(int index)
public boolean flipAndGet(long index)
public void flip(long startIndex, long endIndex)
startIndex
- lower indexendIndex
- one-past the last bit to flippublic long cardinality()
public static long intersectionCount(OpenBitSet a, OpenBitSet b)
public static long unionCount(OpenBitSet a, OpenBitSet b)
public static long andNotCount(OpenBitSet a, OpenBitSet b)
public static long xorCount(OpenBitSet a, OpenBitSet b)
public int nextSetBit(int index)
public long nextSetBit(long index)
public int prevSetBit(int index)
public long prevSetBit(long index)
public void intersect(OpenBitSet other)
public void union(OpenBitSet other)
public void remove(OpenBitSet other)
public void xor(OpenBitSet other)
public void and(OpenBitSet other)
public void or(OpenBitSet other)
public void andNot(OpenBitSet other)
public boolean intersects(OpenBitSet other)
public void ensureCapacityWords(int numWords)
public void ensureCapacity(long numBits)
public void trimTrailingZeros()
public static int bits2words(long numBits)
public boolean equals(Object o)