Package it.unimi.dsi.sux4j.bits
Class RankSelect
- java.lang.Object
-
- it.unimi.dsi.sux4j.bits.RankSelect
-
- All Implemented Interfaces:
Rank
,Select
,SelectZero
,java.io.Serializable
public class RankSelect extends java.lang.Object implements Rank, Select, SelectZero, java.io.Serializable
A serialisation-oriented container for associated rank/select(zero) structures.Since structures in Sux4J serialise all contained data, including, if necessary, the underlying bit vector, serialising separately a rank and a select structure might result in storing the underlying bit vector twice. This class provide a simple solution by allowing one-shot serialisation of all structures related to a bit vector. For convenience, it provides also delegate methods, albeit the suggested usage is deserialisation and extraction of non-
null
structures.- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description Rank
rank
A rank structure, ornull
.Select
select
A select structure, ornull
.SelectZero
selectZero
A zero-select structure, ornull
.
-
Constructor Summary
Constructors Constructor Description RankSelect(Rank rank, Select select)
Creates a new rank/select container without zero selection using the given structures.RankSelect(Rank rank, Select select, SelectZero selectZero)
Creates a new rank/select container using the given structures.
-
Method Summary
All Methods Instance Methods Concrete 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.long
select(long rank)
Returns the position of the bit of given rank.long
selectZero(long rank)
Returns the position of the bit of given zero rank.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface it.unimi.dsi.sux4j.bits.SelectZero
selectZero, selectZero
-
-
-
-
Field Detail
-
rank
public final Rank rank
A rank structure, ornull
.
-
select
public final Select select
A select structure, ornull
.
-
selectZero
public final SelectZero selectZero
A zero-select structure, ornull
.
-
-
Constructor Detail
-
RankSelect
public RankSelect(Rank rank, Select select, SelectZero selectZero)
Creates a new rank/select container using the given structures.- Parameters:
rank
- a rank structure, ornull
.select
- a select structure, ornull
.selectZero
- a zero-select structure, ornull
.
-
-
Method Detail
-
count
public long count()
Description copied from interface:Rank
Returns the number of ones in the bit vector indexed by this class.
-
numBits
public long numBits()
Description copied from interface:Rank
Returns the overall number of bits allocated by this structure.- Specified by:
numBits
in interfaceRank
- Specified by:
numBits
in interfaceSelect
- Specified by:
numBits
in interfaceSelectZero
- Returns:
- the overall number of bits allocated by this structure (not including the bits of the indexed vector).
-
rank
public long rank(long from, long to)
Description copied from interface:Rank
Returns the number of ones in the specified interval.- Specified by:
rank
in interfaceRank
- 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 tofrom
.- Returns:
- the number of ones between
from
(inclusive) andto
(exclusive); if the parameters are out of bounds, behavior is undefined.
-
rank
public long rank(long pos)
Description copied from interface:Rank
Returns the number of ones preceding the specified position.
-
rankZero
public long rankZero(long from, long to)
Description copied from interface:Rank
Returns the number of zeroes in the specified interval.- Specified by:
rankZero
in interfaceRank
- 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 tofrom
.- Returns:
- the number of zeros between
from
(inclusive) andto
(exclusive); if the parameters are out of bounds, behavior is undefined (might throw an exception).
-
rankZero
public long rankZero(long pos)
Description copied from interface:Rank
Returns the number of zeroes preceding the specified position.
-
select
public long select(long rank)
Description copied from interface:Select
Returns the position of the bit of given rank. Equivalently, returns the greatest position that is preceded by the specified number of ones.
-
selectZero
public long selectZero(long rank)
Description copied from interface:SelectZero
Returns the position of the bit of given zero rank. Equivalently, returns the greatest position that is preceded by the specified number of zeroes.- Specified by:
selectZero
in interfaceSelectZero
- Parameters:
rank
- a zero rank.- Returns:
- the position of the bit of given zero rank; if no such bit exists, behavior is undefined .
-
bitVector
public it.unimi.dsi.bits.BitVector bitVector()
Description copied from interface:Rank
Returns the bit vector indexed by this structure.Note that you must not modify the returned vector.
-
-