it.unimi.dsi.sux4j.bits
Class SparseRank

java.lang.Object
  extended by it.unimi.dsi.sux4j.bits.AbstractRank
      extended by 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.

See Also:
Serialized Form

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

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.

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.