|
|||||||||
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.
Field Summary | |
---|---|
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
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 |