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

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
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 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

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 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

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 a SparseSelect 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 in bits.

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; if pos 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 new SparseSelect 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.