Package it.unimi.dsi.sux4j.bits

Class SparseSelect

java.lang.Object
java.util.AbstractCollection<Long>
it.unimi.dsi.fastutil.longs.AbstractLongCollection
it.unimi.dsi.fastutil.longs.AbstractLongBigList
it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
it.unimi.dsi.sux4j.bits.SparseSelect
All Implemented Interfaces:
BigList<Long>, LongBigList, LongCollection, LongIterable, LongStack, Size64, Stack<Long>, Select, Serializable, Comparable<BigList<? extends Long>>, Iterable<Long>, Collection<Long>
public class SparseSelect extends EliasFanoMonotoneLongBigList implements Select
A select implementation for sparse bit arrays based on the Elias–Fano representation of monotone functions.

Instances of this classes do not add support to a bit vector: rather, they replace the bit vector with a succinct representation of the positions of the ones in the bit vector.

Note that some data may be shared with SparseRank: just use the factory method SparseRank.getSelect() to obtain an instance. In that case, numBits() counts just the new data used to build the class, and not the shared part.

See Also:

  • Field Details

    • fromRank

      protected final boolean fromRank
      Whether this structure was built from a SparseRank structure, and thus shares part of its internal state.

  • Constructor Details

    • SparseSelect

      public SparseSelect(long[] bits, long length)
      Creates a new select 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.

    • SparseSelect

      public SparseSelect(BitVector bitVector)
      Creates a new select structure using a bit vector.

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

      Parameters:
      bitVector - the input bit vector.

    • SparseSelect

      public SparseSelect(long n, long m, LongIterator iterator)
      Creates a new select 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.

    • SparseSelect

      public SparseSelect(LongList list)
      Creates a new select structure using a list of longs.
      Parameters:
      list - the list of the positions of ones.

    • SparseSelect

      public SparseSelect(LongBigList list)
      Creates a new select structure using a big list of longs.

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

      Parameters:
      list - the list of the positions of ones.

    • SparseSelect

      protected SparseSelect(long n, long m, int l, long[] lowerBits, SimpleSelect selectUpper)

  • Method Details