Package it.unimi.dsi.sux4j.bits

Class Rank9

  • All Implemented Interfaces:
    Rank, java.io.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:
    Serialized Form

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected long[] bits  
      protected it.unimi.dsi.bits.BitVector bitVector  
      protected long[] count  
      protected long lastOne  
      protected long numOnes  
      protected int numWords  

    • Constructor Summary

      Constructors 
      Constructor Description
      Rank9​(long[] bits, long length)  
      Rank9​(it.unimi.dsi.bits.BitVector bitVector)  

    • 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 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 java.lang.Object

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

    • Field Detail

      • bits

        protected transient long[] bits

      • bitVector

        protected final it.unimi.dsi.bits.BitVector bitVector

      • count

        protected final long[] count

      • numWords

        protected final int numWords

      • numOnes

        protected final long numOnes

      • lastOne

        protected final long lastOne

    • Constructor Detail

      • Rank9

        public Rank9​(long[] bits,
             long length)

      • Rank9

        public Rank9​(it.unimi.dsi.bits.BitVector bitVector)

    • Method Detail

      • 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:
        rank(long)

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

        Specified by:
        bitVector in interface Rank
        Returns:
        the bit vector indexed by this structure.