Package it.unimi.dsi.sux4j.bits

Class SimpleSelect

java.lang.Object
it.unimi.dsi.sux4j.bits.SimpleSelect
All Implemented Interfaces:
Select, Serializable
public class SimpleSelect extends Object implements Select
A simple select implementation based on a two-level inventory, a spill list and broadword bit search.

This implementation uses around 13.75% additional space on evenly distributed bit arrays, and, under the same conditions, provide very fast selects. For very unevenly distributed arrays the space occupancy will grow significantly, and access time might vary wildly.

See Also:
Implementation Notes:
The bulk methods makes it possible to select several consecutive bits at high speed, if the array is reasonably uniform. This is the typical case when this structure is backing an EliasFanoMonotoneLongBigList.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SimpleSelect(long[] bits, long length)
    Creates a new selection structure using a bit vector specified by an array of longs and a number of bits.
    SimpleSelect(BitVector bitVector)
    Creates a new selection structure using the specified bit vector.

  • Method Summary

    Modifier and Type
    Method
    Description
    BitVector
    bitVector()
    Returns the bit vector indexed by this structure.
    long
    numBits()
    Returns the overall number of bits allocated by this structure.
    long
    select(long rank)
    Returns the position of the bit of given rank.
    long[]
    select(long rank, long[] dest)
    Performs a bulk select of consecutive ranks into a given array.
    long[]
    select(long rank, long[] dest, int offset, int length)
    Performs a bulk select of consecutive ranks into a given array fragment.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • SimpleSelect

      public SimpleSelect(long[] bits, long length)
      Creates a new selection structure using a bit vector specified by an array of longs and a number of bits.
      Parameters:
      bits - an array of longs representing a bit array.
      length - the number of bits to use from bits.

    • SimpleSelect

      public SimpleSelect(BitVector bitVector)
      Creates a new selection structure using the specified bit vector.
      Parameters:
      bitVector - a bit vector.

  • Method Details

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

    • select

      public long[] select(long rank, long[] dest, int offset, int length)
      Performs a bulk select of consecutive ranks into a given array fragment.
      Specified by:
      select in interface Select
      Parameters:
      rank - the first rank to select.
      dest - the destination array; it will be filled with length positions of consecutive bits starting at position offset; must be of length greater than offset.
      offset - the first bit position written in dest.
      length - the number of bit positions in dest starting at offset.
      Returns:
      dest
      See Also:
      Implementation Notes:
      dest must be of length greater than offset even if length is zero.

    • select

      public long[] select(long rank, long[] dest)
      Performs a bulk select of consecutive ranks into a given array.
      Specified by:
      select in interface Select
      Parameters:
      rank - the first rank to select.
      dest - the destination array; it will be filled with position of consecutive bits; must be of length greater than zero.
      Returns:
      dest
      See Also:
      Implementation Notes:
      dest must be of length greater than zero.

    • numBits

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

    • bitVector

      public BitVector bitVector()
      Description copied from interface: Select
      Returns the bit vector indexed by this structure.

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

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