|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.sux4j.bits.AbstractRank
it.unimi.dsi.sux4j.bits.SparseRank
public class SparseRank
A rank implementation for sparse bit arrays based on the Elias–Fano representation of monotone functions.
Note that some data may be shared with SparseSelect
: just use the factory method SparseSelect.getRank()
to obtain an instance. In that
case, numBits()
counts just the new data used to build the class, and not the shared part.
Field Summary | |
---|---|
protected boolean |
fromSelect
Whether this structure was built from a SparseSelect structure, and thus shares part of its internal state. |
protected int |
l
The number of lower bits. |
protected LongBigList |
lowerBits
The list of lower bits of the position of each one, stored explicitly. |
protected long |
lowerLBitsMask
The mask for lower bits. |
protected long |
m
The number of ones in the underlying bit array. |
protected long |
n
The length of the underlying bit array. |
protected SimpleSelectZero |
selectZeroUpper
The rank structure used to extract the upper bits. |
protected BitVector |
upperBits
The upper bits. |
Constructor Summary | |
---|---|
|
SparseRank(BitVector bitVector)
Creates a new rank structure using a bit vector. |
|
SparseRank(long[] bits,
long length)
Creates a new rank structure using a long array. |
protected |
SparseRank(long n,
long m,
int l,
LongBigList lowerBits,
BitVector upperBits)
|
|
SparseRank(long n,
long m,
LongIterator iterator)
Creates a new rank structure using an iterator. |
Method Summary | |
---|---|
BitVector |
bitVector()
Returns the bit vector indexed; since the bits are not stored in this data structure, a copy is built on purpose and returned. |
SparseSelect |
getSelect()
Creates a new SparseSelect structure sharing data with this instance. |
long |
numBits()
Returns the overall number of bits allocated by this structure. |
long |
rank(long pos)
Returns the number of ones preceding the specified position. |
Methods inherited from class it.unimi.dsi.sux4j.bits.AbstractRank |
---|
count, rank, rankZero, rankZero |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected final long n
protected final long m
protected final int l
protected final long lowerLBitsMask
protected final LongBigList lowerBits
protected final BitVector upperBits
protected final SimpleSelectZero selectZeroUpper
protected final boolean fromSelect
SparseSelect
structure, and thus shares part of its internal state.
Constructor Detail |
---|
public SparseRank(long[] bits, long length)
The resulting structure keeps no reference to the original array.
bits
- a long array containing the bits.length
- the number of valid bits in bits
.public SparseRank(BitVector bitVector)
The resulting structure keeps no reference to the original bit vector.
bitVector
- the input bit vector.public SparseRank(long n, long m, LongIterator iterator)
This constructor is particularly useful if the positions of the ones are provided by some sequential source.
n
- the number of bits in the underlying bit vector.m
- the number of ones in the underlying bit vector.iterator
- an iterator returning the positions of the ones in the underlying bit vector in increasing order.protected SparseRank(long n, long m, int l, LongBigList lowerBits, BitVector upperBits)
Method Detail |
---|
public long rank(long pos)
Rank
pos
- a position in the bit vector.
pos
.public long numBits()
Rank
public SparseSelect getSelect()
SparseSelect
structure sharing data with this instance.
SparseSelect
structure sharing data with this instance.public BitVector bitVector()
Warning: this method is very slow, as the only way to recover the original bit array is to rank each position in the bit vector.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |