Package it.unimi.dsi.sux4j.bits
Class SparseRank
- java.lang.Object
-
- it.unimi.dsi.sux4j.bits.AbstractRank
-
- it.unimi.dsi.sux4j.bits.SparseRank
-
- All Implemented Interfaces:
Rank
,java.io.Serializable
public class SparseRank extends AbstractRank
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 methodSparseSelect.getRank()
to obtain an instance. In that case,numBits()
counts just the new data used to build the class, and not the shared part.- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description protected boolean
fromSelect
Whether this structure was built from aSparseSelect
structure, and thus shares part of its internal state.protected int
l
The number of lower bits.protected long[]
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 it.unimi.dsi.bits.BitVector
upperBits
The upper bits.
-
Constructor Summary
Constructors Modifier Constructor Description SparseRank(long[] bits, long length)
Creates a new rank structure using a long array.protected
SparseRank(long n, long m, int l, long[] lowerBits, it.unimi.dsi.bits.BitVector upperBits)
SparseRank(long n, long m, it.unimi.dsi.fastutil.longs.LongIterator iterator)
Creates a new rank structure using an iterator.SparseRank(it.unimi.dsi.bits.BitVector bitVector)
Creates a new rank structure using a bit vector.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description it.unimi.dsi.bits.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 newSparseSelect
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
-
-
-
-
Field Detail
-
n
protected final long n
The length of the underlying bit array.
-
m
protected final long m
The number of ones in the underlying bit array.
-
l
protected final int l
The number of lower bits.
-
lowerLBitsMask
protected final long lowerLBitsMask
The mask for lower bits.
-
lowerBits
protected long[] lowerBits
The list of lower bits of the position of each one, stored explicitly.
-
upperBits
protected final it.unimi.dsi.bits.BitVector upperBits
The upper bits.
-
selectZeroUpper
protected final SimpleSelectZero selectZeroUpper
The rank structure used to extract the upper bits.
-
fromSelect
protected final boolean fromSelect
Whether this structure was built from aSparseSelect
structure, and thus shares part of its internal state.
-
-
Constructor Detail
-
SparseRank
public SparseRank(long[] bits, long length)
Creates a new rank structure using a long array.The resulting structure keeps no reference to the original array.
- Parameters:
bits
- a long array containing the bits.length
- the number of valid bits inbits
.
-
SparseRank
public SparseRank(it.unimi.dsi.bits.BitVector bitVector)
Creates a new rank structure using a bit vector.The resulting structure keeps no reference to the original bit vector.
- Parameters:
bitVector
- the input bit vector.
-
SparseRank
public SparseRank(long n, long m, it.unimi.dsi.fastutil.longs.LongIterator iterator)
Creates a new rank structure using an iterator.This constructor is particularly useful if the positions of the ones are provided by some sequential source.
- Parameters:
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.
-
SparseRank
protected SparseRank(long n, long m, int l, long[] lowerBits, it.unimi.dsi.bits.BitVector upperBits)
-
-
Method Detail
-
rank
public long rank(long pos)
Description copied from interface:Rank
Returns the number of ones preceding the specified position.- Parameters:
pos
- a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive).- Returns:
- the number of ones preceding position
pos
; ifpos
is out of bounds, behavior is undefined.
-
numBits
public long numBits()
Description copied from interface:Rank
Returns the overall number of bits allocated by this structure.- Returns:
- the overall number of bits allocated by this structure (not including the bits of the indexed vector).
-
getSelect
public SparseSelect getSelect()
Creates a newSparseSelect
structure sharing data with this instance.- Returns:
- a new
SparseSelect
structure sharing data with this instance.
-
bitVector
public it.unimi.dsi.bits.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.Warning: this method is quite slow, as it has to rebuild all bit positions.
- Returns:
- a copy of the underlying bit vector.
-
-