Package it.unimi.dsi.sux4j.bits

Class SparseSelect

  • All Implemented Interfaces:
    it.unimi.dsi.fastutil.BigList<java.lang.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<java.lang.Long>, Select, java.io.Serializable, java.lang.Comparable<it.unimi.dsi.fastutil.BigList<? extends java.lang.Long>>, java.lang.Iterable<java.lang.Long>, java.util.Collection<java.lang.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:
    Serialized Form

    • 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

      All Methods Instance Methods Concrete Methods Deprecated 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.
      boolean equals​(java.lang.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()  
      java.lang.String toString()  

      • 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 java.util.AbstractCollection

        isEmpty, toArray, toArray

      • Methods inherited from class java.lang.Object

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

      • Methods inherited from interface java.util.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 it.unimi.dsi.fastutil.Stack

        isEmpty

    • Field Detail

      • fromRank

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

    • Constructor Detail

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

      • getRank

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

      • size

        @Deprecated
public int size()
        Deprecated.
        Specified by:
        size in interface it.unimi.dsi.fastutil.BigList<java.lang.Long>
        Specified by:
        size in interface java.util.Collection<java.lang.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 java.util.Collection<java.lang.Long>
        Overrides:
        hashCode in class it.unimi.dsi.fastutil.longs.AbstractLongBigList

      • equals

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

      • toString

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