Class SparseRank

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected boolean fromSelect
      Whether this structure was built from a SparseSelect structure, and thus shares part of its internal state.
      protected int l
      The number of lower bits.
      protected long[] lowerBits
      The list of lower bits of the position of each one, stored explicitly.
      protected long lowerLBitsMask
      The mask for lower bits.
      protected long m
      The number of ones in the underlying bit array.
      protected long n
      The length of the underlying bit array.
      protected SimpleSelectZero selectZeroUpper
      The rank structure used to extract the upper bits.
      protected it.unimi.dsi.bits.BitVector upperBits
      The upper bits.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        SparseRank​(long[] bits, long length)
      Creates a new rank structure using a long array.
      protected SparseRank​(long n, long m, int l, long[] lowerBits, it.unimi.dsi.bits.BitVector upperBits)  
        SparseRank​(long n, long m, it.unimi.dsi.fastutil.longs.LongIterator iterator)
      Creates a new rank structure using an iterator.
        SparseRank​(it.unimi.dsi.bits.BitVector bitVector)
      Creates a new rank structure using a bit vector.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      it.unimi.dsi.bits.BitVector bitVector()
      Returns the bit vector indexed; since the bits are not stored in this data structure, a copy is built on purpose and returned.
      SparseSelect getSelect()
      Creates a new SparseSelect structure sharing data with this instance.
      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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • n

        protected final long n
        The length of the underlying bit array.
      • m

        protected final long m
        The number of ones in the underlying bit array.
      • l

        protected final int l
        The number of lower bits.
      • lowerLBitsMask

        protected final long lowerLBitsMask
        The mask for lower bits.
      • lowerBits

        protected long[] lowerBits
        The list of lower bits of the position of each one, stored explicitly.
      • upperBits

        protected final it.unimi.dsi.bits.BitVector upperBits
        The upper bits.
      • selectZeroUpper

        protected final SimpleSelectZero selectZeroUpper
        The rank structure used to extract the upper bits.
      • fromSelect

        protected final boolean fromSelect
        Whether this structure was built from a SparseSelect structure, and thus shares part of its internal state.
    • Constructor Detail

      • SparseRank

        public SparseRank​(long[] bits,
                          long length)
        Creates a new rank structure using a long array.

        The resulting structure keeps no reference to the original array.

        Parameters:
        bits - a long array containing the bits.
        length - the number of valid bits in bits.
      • SparseRank

        public SparseRank​(it.unimi.dsi.bits.BitVector bitVector)
        Creates a new rank structure using a bit vector.

        The resulting structure keeps no reference to the original bit vector.

        Parameters:
        bitVector - the input bit vector.
      • SparseRank

        public SparseRank​(long n,
                          long m,
                          it.unimi.dsi.fastutil.longs.LongIterator iterator)
        Creates a new rank structure using an iterator.

        This constructor is particularly useful if the positions of the ones are provided by some sequential source.

        Parameters:
        n - the number of bits in the underlying bit vector.
        m - the number of ones in the underlying bit vector.
        iterator - an iterator returning the positions of the ones in the underlying bit vector in increasing order.
      • SparseRank

        protected SparseRank​(long n,
                             long m,
                             int l,
                             long[] lowerBits,
                             it.unimi.dsi.bits.BitVector upperBits)
    • Method Detail

      • rank

        public long rank​(long pos)
        Description copied from interface: Rank
        Returns the number of ones preceding the specified position.
        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.
      • numBits

        public long numBits()
        Description copied from interface: Rank
        Returns the overall number of bits allocated by this structure.
        Returns:
        the overall number of bits allocated by this structure (not including the bits of the indexed vector).
      • getSelect

        public SparseSelect getSelect()
        Creates a new SparseSelect structure sharing data with this instance.
        Returns:
        a new SparseSelect structure sharing data with this instance.
      • bitVector

        public it.unimi.dsi.bits.BitVector bitVector()
        Returns the bit vector indexed; since the bits are not stored in this data structure, a copy is built on purpose and returned.

        Warning: this method is quite slow, as it has to rebuild all bit positions.

        Returns:
        a copy of the underlying bit vector.