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.

    There is some variance in the literature about the exact semantics of ranking—in most cases, it is a matter of off-by-ones. 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. The rank(long) of a bit is the number of ones that precede it (the bit itself is not included).

    The following properties always hold:

    • rank(0)=0;
    • rank(length()) is the number of ones in the bit vector.
    See Also:
    Select
    • 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 Detail

      • 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.
        Returns:
        the number of ones preceding pos.
      • rank

        long rank​(long from,
                  long to)
        Returns the number of ones in the specified interval.
        Parameters:
        from - a position in the bit vector.
        to - a position in the bit vector.
        Returns:
        the number of ones between from (inclusive) and to (exclusive); if to is smaller than from, 0 is returned.
      • rankZero

        long rankZero​(long pos)
        Returns the number of zeroes preceding the specified position.
        Parameters:
        pos - a position in the bit vector.
        Returns:
        the number of zeroes preceding pos.
      • rankZero

        long rankZero​(long from,
                      long to)
        Returns the number of zeroes in the specified interval.
        Parameters:
        from - a position in the bit vector.
        to - a position in the bit vector.
        Returns:
        the number of zeroes between from (inclusive) and to (exclusive); if to is smaller than from, 0 is returned.
      • bitVector

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

        Note that you are not supposed to 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).