Interface Rank

  • All Superinterfaces:
    java.io.Serializable
    All Known Implementing Classes:
    AbstractRank, Rank11, Rank11Original, Rank12, Rank16, Rank9, Rank9GogPetri, RankSelect, SparseRank

    public interface Rank
    extends java.io.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:
    Select
    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      it.unimi.dsi.bits.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 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

        it.unimi.dsi.bits.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).