Package 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. For convenience, it provides also delegate methods, albeit the suggested usage is deserialisation and extraction of non-null structures.

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final Rank
    rank
    A rank structure, or null.
    final Select
    select
    A select structure, or null.
    final SelectZero
    selectZero
    A zero-select structure, or null.

  • 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

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

    select, select

    Methods inherited from interface it.unimi.dsi.sux4j.bits.SelectZero

    selectZero, selectZero

  • Field Details

    • 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 Details

    • 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 Details

    • 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 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 to from.
      Returns:
      the number of ones between from (inclusive) and to (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.
      Specified by:
      rank in interface Rank
      Parameters:
      pos - a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive).
      Returns:
      the number of ones preceding position pos; if pos is out of bounds, behavior is undefined.

    • 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 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 to from.
      Returns:
      the number of zeros between from (inclusive) and to (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.
      Specified by:
      rankZero in interface Rank
      Parameters:
      pos - a position in the bit vector between 0 (inclusive) and the length of the bit vector (inclusive).
      Returns:
      the number of zeroes preceding pos; if pos is out of bounds, behavior is undefined.

    • 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 bit exists, behavior is undefined .

    • 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 interface SelectZero
      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 BitVector bitVector()
      Description copied from interface: Rank
      Returns the bit vector indexed by this structure.

      Note that you must not 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.