|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface Rank
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.
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 |
---|
long count()
long rank(long pos)
pos
- a position in the bit vector.
pos
.long rank(long from, long to)
from
- a position in the bit vector.to
- a position in the bit vector.
from
(inclusive) and to
(exclusive); if
to
is smaller than from
, 0 is returned.long rankZero(long pos)
pos
- a position in the bit vector.
pos
.long rankZero(long from, long to)
from
- a position in the bit vector.to
- a position in the bit vector.
from
(inclusive) and to
(exclusive); if
to
is smaller than from
, 0 is returned.BitVector bitVector()
Note that you are not supposed to modify the returned vector.
long numBits()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |