public class BitSet
extends java.lang.Object
implements java.lang.Cloneable
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.
asIntLookupContainer()
,
asLongLookupContainer()
Modifier and Type | Field and Description |
---|---|
long[] |
bits
Internal representation of bits in this bit set.
|
int |
wlen
The number of words (longs) used in the
bits array. |
Constructor and 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[].
|
Modifier and Type | Method and Description |
---|---|
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() |
static BitSet |
newInstance()
Static constructor-like method similar to other (generic) collections.
|
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.
|
public long[] bits
public int wlen
bits
array.public BitSet()
public BitSet(long numBits)
public BitSet(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 static BitSet newInstance()
public BitSetIterator iterator()
nextSetBit(int)
.public long capacity()
public long size()
cardinality()
.cardinality()
,
BitSet.size()
public long length()
BitSet.length()
public boolean isEmpty()
public boolean get(int index)
public boolean get(long index)
public void set(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 clear()
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 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(BitSet a, BitSet b)
public static long unionCount(BitSet a, BitSet b)
public static long andNotCount(BitSet a, BitSet b)
public static long xorCount(BitSet a, BitSet b)
public int nextSetBit(int index)
public long nextSetBit(long index)
public java.lang.Object clone()
clone
in class java.lang.Object
public void intersect(BitSet other)
public void union(BitSet other)
public void remove(BitSet other)
public void xor(BitSet other)
public void and(BitSet other)
public void or(BitSet other)
public void andNot(BitSet other)
public boolean intersects(BitSet other)
public void ensureCapacityWords(int numWords)
public static long[] grow(long[] array, int minSize)
public static int getNextSize(int targetSize)
public void ensureCapacity(long numBits)
public void trimTrailingZeros()
wlen
, the number of words in use, by checking for trailing zero
words.public static int bits2words(long numBits)
public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public int hashCode()
hashCode
in class java.lang.Object
public java.lang.String toString()
toString
in class java.lang.Object
public IntLookupContainer asIntLookupContainer()
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.
public LongLookupContainer asLongLookupContainer()
LongLookupContainer
. A new
object is always returned, but its methods reflect the current state of the bitset
(the view is not a snapshot).Copyright © 2016 Carrot Search s.c.. All rights reserved.