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.
There is some variance in the literature about the exact semantics of ranking—in most cases, it is a matter of offbyones. This interface specifies a zerobased 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) andto
(exclusive); ifto
is smaller thanfrom
, 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) andto
(exclusive); ifto
is smaller thanfrom
, 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).

