it.unimi.dsi.sux4j.bits
Interface Rank

All Superinterfaces:
Serializable
All Known Implementing Classes:
AbstractRank, 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:

See Also:
Select

Method Summary
 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).