public class SparseBitVector extends Object implements BitVector
DenseBitVector
is more suitable.Long.MAX_VALUE
(i.e.
9223372036854775807). The number of ones that can be stored is limited to
Integer.MAX_VALUE
(which is 2147483647), in which case it uses about
16Gbyte of memory.Constructor and Description 

SparseBitVector(long length)
Creates a new vector with (initially) space for 64 ones and of the
specified length.

SparseBitVector(long length,
int initialCapacity)
Creates a new vector of the specified length and with (initially) space
for the specified number of ones.

SparseBitVector(long length,
long initialCapacity)
Creates a new vector of the specified length and with (initially) space
for the specified number of ones.

SparseBitVector(long length,
long[] oneIndices)
Creates a new instance by taking over the initialization from the passed
array.

SparseBitVector(SparseBitVector clone)
Creates a new instance as copy of the passed argument.

SparseBitVector(String hexString)
Initializes the created bit vector from the hex representation in the
passed string.

Modifier and Type  Method and Description 

SparseBitVector 
and(SparseBitVector bv)
Creates and returns a new bit vector whose bits are set at positions
where both, this and the argument vector have their bits set.

long 
cardinality()
Number of bits set in this bit vector.

(package private) long 
cardinalityOfIntersection(SparseBitVector bitVector)
Computes the cardinality of the intersection with the given bitVector.

(package private) long 
cardinalityOfRelativeComplement(SparseBitVector bitVector)
Computes the cardinality of the complement relative to the given bitVector.

void 
clear(long bitIdx)
Sets the bit at the specified index to one.

SparseBitVector 
concatenate(SparseBitVector bv)
Creates and returns a new bit vector that contains copies of both (this
and the argument vector).

boolean 
equals(Object obj) 
boolean 
get(long bitIdx)
Returns true if the bit at the specified index is set.

long[] 
getAllOneIndices()
Returns a copy of the internal storage of all bit indices.

int 
hashCode() 
boolean 
intersects(SparseBitVector bv)
Returns true, if this and the argument vector have at least one bit set
at the same position.

boolean 
isEmpty()
Returns true if no bits are set in this bit vector.

long 
length()
Returns the number of bits stored in this vector.

long 
nextClearBit(long startIdx)
Finds the next bit not set (that is '0') on or after the specified index.

long 
nextSetBit(long startIdx)
Finds the next bit set to one on or after the specified index.

SparseBitVector 
or(SparseBitVector bv)
Creates and returns a new bit vector whose bits are set at positions
where at least one of the vectors (this or the argument vector) have a
bit set.

void 
set(long bitIdx)
Sets the bit at the specified index to zero.

void 
set(long bitIdx,
boolean value)
Sets the bit at the specified index to the new value.

void 
shrink()
Frees unused memory in the vector.

SparseBitVector 
subSequence(long startIdx,
long endIdx)
Creates and returns a new bit vector that contains a subsequence of this
vector, beginning with the bit at index
startIdx and with
its last bit being this' bit at position endIdx  1 . 
String 
toBinaryString()
Returns the binary string representation of the bits in this vector.

String 
toHexString()
Returns the hex representation of the bits in this vector.

String 
toString()
Returns a string containing (comma separated) indices of the bits set in
this vector and the total number of bits.

SparseBitVector 
xor(SparseBitVector bv)
Creates and returns a new bit vector whose bits are set at positions
where (exactly) one of the vectors (this or the argument vector) have a
bit set.

public SparseBitVector(long length)
length
 the length of the vector to createpublic SparseBitVector(long length, long initialCapacity)
length
 the length of the vector to createinitialCapacity
 space will be allocated to store that many onespublic SparseBitVector(long length, int initialCapacity)
length
 the length of the vector to createinitialCapacity
 space will be allocated to store that many onespublic SparseBitVector(long length, long[] oneIndices)
getAllOneIndices()
method.oneIndices
 the array containing the indices of the ones. MUST be
sorted (lowest index first).length
 the length of the vector. Indices must be smaller than this
number.IllegalArgumentException
 if length is negative or if the array
contains negative numbers or numbers larger than length  or
if the array is not sorted!public SparseBitVector(SparseBitVector clone)
clone
 the vector to copy into the new instancepublic SparseBitVector(String hexString)
'0'  '9'
,
'A'  'F'
and 'a'  'f'
are allowed. The
character at string position (length  1)
represents the
bits with index 0 to 3 in the vector. The character at position 0
represents the bits with the highest indices. The length of the vector
created is the length of the string times 4 (as each character represents
four bits).hexString
 containing the hex value to initialize the vector withIllegalArgumentException
 if hexString
contains
characters other then the hex characters (i.e.
0  9, A  F, and a  f
)public long length()
public void shrink()
public void set(long bitIdx, boolean value)
public void set(long bitIdx)
public void clear(long bitIdx)
public long cardinality()
cardinality
in interface BitVector
public boolean isEmpty()
public boolean intersects(SparseBitVector bv)
bv
 the vector to testpublic boolean get(long bitIdx)
public long nextSetBit(long startIdx)
nextSetBit
in interface BitVector
startIdx
 the first index to look for '1's. (It is allowed to pass
an index larger then the vector's length.)public long nextClearBit(long startIdx)
nextClearBit
in interface BitVector
startIdx
 the first index to look for '0's.public SparseBitVector subSequence(long startIdx, long endIdx)
startIdx
and with
its last bit being this' bit at position endIdx  1
. The
length of the result vector is endIdx  startIdx
. If
startIdx
equals endIdx
a vector of length
zero is returned.startIdx
 the startIdx of the subsequenceendIdx
 the first bit in this vector after startIdx that is not
included in the result sequence.endIdx  startIdx
containing the subsequence of this vector from
startIdx
(included) to endIdx
(not
included anymore).public SparseBitVector and(SparseBitVector bv)
bv
 the vector to AND this one withpublic SparseBitVector or(SparseBitVector bv)
bv
 the vector to OR this one withpublic SparseBitVector xor(SparseBitVector bv)
bv
 the vector to XOR this one withpublic SparseBitVector concatenate(SparseBitVector bv)
bv
 the vector to append at the end of thispublic String toString()
BitVectorValue.MAX_DISPLAY_BITS
. If the output is truncated, the string ends on "... }"public String toHexString()
'0'

'9'
and 'A'
 'F'
). The
character at string position (length  1)
holds the lowest
bits (bit 0 to 3), the character at position 0 represents the bits with
the largest index in the vector. If the length of the vector is larger
than BitVectorValue.MAX_DISPLAY_BITS
, the result is truncated (and ends with ...).toHexString
in interface BitVector
public String toBinaryString()
(length  1)
holds the bit with index 0, the character at position 0 represents the bits with the
largest index in the vector. If the length of the vector is larger than BitVectorValue.MAX_DISPLAY_BITS
,
the result is truncated (and ends with ...).toBinaryString
in interface BitVector
public long[] getAllOneIndices()
long cardinalityOfIntersection(SparseBitVector bitVector)
bitVector
 the other operand for the AND operatorBitVectorUtil.cardinalityOfIntersection(BitVectorValue, BitVectorValue)
long cardinalityOfRelativeComplement(SparseBitVector bitVector)
bitVector
 the other operandBitVectorUtil.cardinalityOfRelativeComplement(BitVectorValue, BitVectorValue)