Package it.unimi.dsi.sux4j.bits

Interface Rank

All Superinterfaces:
Serializable
All Known Implementing Classes:
AbstractRank, Rank11, Rank16, Rank9, RankSelect, SparseRank
public interface Rank extends Serializable
A data structure providing ranking over a bit array.

Ranking is a basic building blocks for most succinct data structures. Usually, instances of this class class provide quick (e.g., constant-time) ranking.

This interface specifies a zero-based ranking. More precisely, rank is applied to a bit vector in which bits positions are numbered starting from zero. Then, rank(p) is the number of of ones that precede position p (the bit at position p is not included in the count).

The following properties always hold:

  • rank(0)=0;
  • rank(length()) is the number of ones in the bit vector.
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    BitVector
    bitVector()
    Returns the bit vector indexed by this structure.
    long
    count()
    Returns the number of ones in the bit vector indexed by this class.
    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.
    long
    rank(long from, long to)
    Returns the number of ones in the specified interval.
    long
    rankZero(long pos)
    Returns the number of zeroes preceding the specified position.
    long
    rankZero(long from, long to)
    Returns the number of zeroes in the specified interval.

  • Method Details

    • count

      long count()
      Returns the number of ones in the bit vector indexed by this class.
      Returns:
      number of ones in the bit vector indexed by this class.

    • rank

      long rank(long pos)
      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.

    • rank

      long rank(long from, long to)
      Returns the number of ones in the specified interval.
      Parameters:
      from - a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive).
      to - a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive); must be greater than or equal to from.
      Returns:
      the number of ones between from (inclusive) and to (exclusive); if the parameters are out of bounds, behavior is undefined.

    • rankZero

      long rankZero(long pos)
      Returns the number of zeroes 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 zeroes preceding pos; if pos is out of bounds, behavior is undefined.

    • rankZero

      long rankZero(long from, long to)
      Returns the number of zeroes in the specified interval.
      Parameters:
      from - a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive).
      to - a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive); must be greater than or equal to from.
      Returns:
      the number of zeros between from (inclusive) and to (exclusive); if the parameters are out of bounds, behavior is undefined (might throw an exception).

    • bitVector

      BitVector bitVector()
      Returns the bit vector indexed by this structure.

      Note that you must not modify the returned vector.

      Returns:
      the bit vector indexed by this structure.

    • numBits

      long numBits()
      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).