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

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final boolean
    fromSelect
    Whether this structure was built from a SparseSelect structure, and thus shares part of its internal state.
    protected final int
    l
    The number of lower bits.
    protected long[]
    lowerBits
    The list of lower bits of the position of each one, stored explicitly.
    protected final long
    lowerLBitsMask
    The mask for lower bits.
    protected final long
    m
    The number of ones in the underlying bit array.
    protected final long
    n
    The length of the underlying bit array.
    protected final SimpleSelectZero
    selectZeroUpper
    The rank structure used to extract the upper bits.
    protected final 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, BitVector upperBits)
     
     
    SparseRank(long n, long m, LongIterator iterator)
    Creates a new rank structure using an iterator.
     
    SparseRank(BitVector bitVector)
    Creates a new rank structure using a bit vector.

  • Method Summary

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

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

    • 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, long[] lowerBits, BitVector upperBits)

  • Method Details

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