it.unimi.dsi.sux4j.bits
Class RankSelect

java.lang.Object
  it.unimi.dsi.sux4j.bits.RankSelect

All Implemented Interfaces:

Rank, Select, SelectZero, Serializable

public class RankSelect
extends Object
implements Rank, Select, SelectZero, 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. As a commodity, it provides also delegate methods, albeit the suggested usage is deserialisation and extraction of non-null structures.

See Also:

Serialized Form

Field Summary

Rank	rank A rank structure, or null.
Select	select A select structure, or null.
SelectZero	selectZero A zero-select structure, or null.

Constructor Summary

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

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 rank.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

rank

public final Rank rank

A rank structure, or null.

select

public final Select select

A select structure, or null.

selectZero

public final SelectZero selectZero

A zero-select structure, or null.

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, or null.

select - a select structure, or null.

selectZero - a zero-select structure, or null.

RankSelect

public RankSelect(Rank rank,
                  Select select)

Creates a new rank/select container without zero selection using the given structures.

Parameters:

rank - a rank structure, or null.

select - a select structure, or null.

Method Detail

count

public long count()

Description copied from interface: Rank

Returns the number of ones in the bit vector indexed by this class.

Specified by:

count in interface Rank

Returns:

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 interface Rank

Specified by:

numBits in interface Select

Specified by:

numBits in interface SelectZero

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 interface Rank

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.

rank

public long rank(long pos)

Description copied from interface: Rank

Returns the number of ones preceding the specified position.

Specified by:

rank in interface Rank

Parameters:

pos - a position in the bit vector.

Returns:

the number of ones preceding pos.

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 interface Rank

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.

rankZero

public long rankZero(long pos)

Description copied from interface: Rank

Returns the number of zeroes preceding the specified position.

Specified by:

rankZero in interface Rank

Parameters:

pos - a position in the bit vector.

Returns:

the number of zeroes preceding pos.

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.

Specified by:

select in interface Select

Parameters:

rank - a rank.

Returns:

the position of the bit of given rank; if no such position exists, −1 is returned.

selectZero

public long selectZero(long rank)

Description copied from interface: SelectZero

Returns the position of the bit of given rank. Equivalently, returns the greatest position that is preceded by the specified number of ones.

Specified by:

selectZero in interface SelectZero

Parameters:

rank - a rank.

Returns:

the position of the bit of given rank; if no such position exists, −1 is returned.

bitVector

public BitVector bitVector()

Description copied from interface: Rank

Returns the bit vector indexed by this structure.

Note that you are not supposed to modify the returned vector.

Specified by:

bitVector in interface Rank

Specified by:

bitVector in interface Select

Specified by:

bitVector in interface SelectZero

Returns:

the bit vector indexed by this structure.