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:
it.unimi.dsi.fastutil.BigList<Long>, it.unimi.dsi.fastutil.longs.LongBigList, it.unimi.dsi.fastutil.longs.LongCollection, it.unimi.dsi.fastutil.longs.LongIterable, it.unimi.dsi.fastutil.longs.LongStack, it.unimi.dsi.fastutil.Size64, it.unimi.dsi.fastutil.Stack<Long>, Select, Serializable, Comparable<it.unimi.dsi.fastutil.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:

  • Nested Class Summary

    Nested classes/interfaces inherited from class EliasFanoMonotoneLongBigList

    EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator

    Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    it.unimi.dsi.fastutil.longs.AbstractLongBigList.LongRandomAccessSubList, it.unimi.dsi.fastutil.longs.AbstractLongBigList.LongSubList

  • Field Summary

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

    Fields inherited from class EliasFanoMonotoneLongBigList

    l, length, lowerBits, lowerBitsMask, selectUpper, upperBits

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
     
    SparseSelect(long[] bits, long length)
    Creates a new select structure using a long array.
    protected
    SparseSelect(long n, long m, int l, long[] lowerBits, SimpleSelect selectUpper)
     
     
    SparseSelect(long n, long m, it.unimi.dsi.fastutil.longs.LongIterator iterator)
    Creates a new select structure using an iterator.
     
    SparseSelect(it.unimi.dsi.bits.BitVector bitVector)
    Creates a new select structure using a bit vector.
     
    SparseSelect(it.unimi.dsi.fastutil.longs.LongBigList list)
    Creates a new select structure using a big list of longs.
     
    SparseSelect(it.unimi.dsi.fastutil.longs.LongList list)
    Creates a new select structure using a list of longs.

  • Method Summary

    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.
    boolean
    equals(Object o)
     
    long
    getLong(long pos)
    Returns the element at the specified position.
    SparseRank
    getRank()
    Creates a new SparseRank structure sharing data with this instance.
    int
    hashCode()
     
    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.
    int
    size()
    Deprecated.
    long
    size64()
     
    String
    toString()
     

    Methods inherited from class EliasFanoMonotoneLongBigList

    dump, dump, fits, get, get, getDelta, iterator, listIterator, listIterator

    Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    add, add, add, addAll, addAll, addAll, addAll, addElements, addElements, clear, compareTo, contains, ensureIndex, ensureRestrictedIndex, forEach, get, getElements, indexOf, indexOf, lastIndexOf, lastIndexOf, peek, peekLong, pop, popLong, push, push, rem, remove, removeElements, removeLong, set, set, setElements, size, subList, top, topLong

    Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongCollection

    add, contains, containsAll, containsAll, forEach, remove, removeAll, removeAll, removeIf, retainAll, retainAll, toArray, toLongArray, toLongArray

    Methods inherited from class AbstractCollection

    isEmpty, toArray, toArray

    Methods inherited from class Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface Collection

    containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toArray

    Methods inherited from interface it.unimi.dsi.fastutil.longs.LongBigList

    addAll, addAll, addAll, addAll, getElements, setElements, setElements, spliterator

    Methods inherited from interface it.unimi.dsi.fastutil.longs.LongCollection

    add, contains, containsAll, longIterator, longParallelStream, longSpliterator, longStream, parallelStream, remove, removeAll, removeIf, removeIf, removeIf, retainAll, stream, toArray, toLongArray, toLongArray

    Methods inherited from interface it.unimi.dsi.fastutil.longs.LongIterable

    forEach, forEach

    Methods inherited from interface Select

    select, select

    Methods inherited from interface it.unimi.dsi.fastutil.Stack

    isEmpty

  • 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(it.unimi.dsi.bits.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, it.unimi.dsi.fastutil.longs.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(it.unimi.dsi.fastutil.longs.LongList list)
      Creates a new select structure using a list of longs.
      Parameters:
      list - the list of the positions of ones.

    • SparseSelect

      public SparseSelect(it.unimi.dsi.fastutil.longs.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

    • getRank

      public SparseRank getRank()
      Creates a new SparseRank structure sharing data with this instance.
      Returns:
      a new SparseRank structure sharing data with this instance.

    • size64

      public long size64()
      Specified by:
      size64 in interface it.unimi.dsi.fastutil.Size64
      Overrides:
      size64 in class EliasFanoMonotoneLongBigList

    • size

      @Deprecated public int size()
      Deprecated.
      Specified by:
      size in interface it.unimi.dsi.fastutil.BigList<Long>
      Specified by:
      size in interface Collection<Long>
      Specified by:
      size in interface it.unimi.dsi.fastutil.Size64
      Overrides:
      size in class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    • getLong

      public long getLong(long pos)
      Description copied from class: EliasFanoMonotoneLongBigList
      Returns the element at the specified position.
      Specified by:
      getLong in interface it.unimi.dsi.fastutil.longs.LongBigList
      Overrides:
      getLong in class EliasFanoMonotoneLongBigList
      Parameters:
      pos - a position in the list.
      Returns:
      the element at the specified position; if index is out of bounds, behavior is undefined.

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

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

    • 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.
      Specified by:
      bitVector in interface Select
      Returns:
      a copy of the underlying bit vector.

    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface Collection<Long>
      Overrides:
      hashCode in class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    • equals

      public boolean equals(Object o)
      Specified by:
      equals in interface Collection<Long>
      Overrides:
      equals in class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    • toString

      public String toString()
      Overrides:
      toString in class it.unimi.dsi.fastutil.longs.AbstractLongBigList