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

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

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 final LongBigList lowerBits

The list of lower bits of the position of each one, stored explicitly.

upperBits

protected final 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(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,
                  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,
                     LongBigList lowerBits,
                     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.

Returns:

the number of ones preceding pos.

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 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 very slow, as the only way to recover the original bit array is to rank each position in the bit vector.

Returns:

a copy of the underlying bit vector.