Package it.unimi.dsi.sux4j.bits

Class Rank9

java.lang.Object
it.unimi.dsi.sux4j.bits.AbstractRank
it.unimi.dsi.sux4j.bits.Rank9
All Implemented Interfaces:
Rank, Serializable
public class Rank9 extends AbstractRank implements Rank
A rank9 implementation.

rank9 is a ranking structure using 25% additional space and providing exceptionally fast ranking.

See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected long[]
    bits
     
    protected final BitVector
    bitVector
     
    protected final long[]
    count
     
    protected final long
    lastOne
     
    protected final long
    numOnes
     
    protected final int
    numWords
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    Rank9(long[] bits, long length)
     
    Rank9(BitVector bitVector)
     

  • 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
    lastOne()
     
    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
    rankStrict(long pos)
    Returns the rank at the given position assuming that the argument is less than the length of the bit vector.

    Methods inherited from class it.unimi.dsi.sux4j.bits.AbstractRank

    rankZero, rankZero

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

    rankZero, rankZero

  • Field Details

    • bits

      protected transient long[] bits

    • bitVector

      protected final BitVector bitVector

    • count

      protected final long[] count

    • numWords

      protected final int numWords

    • numOnes

      protected final long numOnes

    • lastOne

      protected final long lastOne

  • Constructor Details

    • Rank9

      public Rank9(long[] bits, long length)

    • Rank9

      public Rank9(BitVector bitVector)

  • Method Details

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

    • rankStrict

      public long rankStrict(long pos)
      Returns the rank at the given position assuming that the argument is less than the length of the bit vector.

      This method is slightly faster than rank(long), as it avoids a check, but its behavior when the argument is equal to the length of the underlying bit vector is undefined.

      If the array of longs representing the bit vector has a free bit at the end, this method will work correctly even when pos is equal to the length of the bit vector.

      Parameters:
      pos - a position in the bit vector between 0 (inclusive) and the length of the bit vector (exclusive).
      Returns:
      the number of ones preceding position pos; if pos is out of bounds, behavior is undefined.
      See Also:

    • 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
      Returns:
      the overall number of bits allocated by this structure (not including the bits of the indexed vector).

    • 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
      Overrides:
      count in class AbstractRank
      Returns:
      number of ones in the bit vector indexed by this class.

    • 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
      Overrides:
      rank in class AbstractRank
      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.

    • lastOne

      public long lastOne()

    • 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
      Returns:
      the bit vector indexed by this structure.