it.unimi.dsi.sux4j.bits
Class SparseSelect

java.lang.Object
  extended by it.unimi.dsi.fastutil.longs.AbstractLongCollection
      extended by it.unimi.dsi.fastutil.longs.AbstractLongList
          extended by it.unimi.dsi.util.AbstractLongBigList
              extended by it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
                  extended by it.unimi.dsi.sux4j.bits.SparseSelect
All Implemented Interfaces:
LongCollection, LongIterable, LongList, LongStack, Stack<java.lang.Long>, Select, LongBigList, java.io.Serializable, java.lang.Comparable<java.util.List<? extends java.lang.Long>>, java.lang.Iterable<java.lang.Long>, java.util.Collection<java.lang.Long>, java.util.List<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.

See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.util.AbstractLongBigList
AbstractLongBigList.LongSubBigList
 
Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongList
AbstractLongList.LongSubList
 
Field Summary
 
Fields inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
l, length, lowerBits, selectUpper
 
Constructor Summary
  SparseSelect(BitVector bitVector)
          Creates a new select structure using a bit vector.
  SparseSelect(long[] bits, long length)
          Creates a new select structure using a long array.
protected SparseSelect(long n, long m, int l, LongBigList lowerBits, SimpleSelect selectUpper)
           
  SparseSelect(long n, long m, LongIterator iterator)
          Creates a new select structure using an iterator.
 
Method Summary
 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.
 SparseRank getRank()
          Creates a new SparseRank structure sharing data with this instance.
 long length()
           
 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.
 
Methods inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
getLong
 
Methods inherited from class it.unimi.dsi.util.AbstractLongBigList
add, ensureIndex, ensureRestrictedIndex, getLong, length, removeLong, set, size, subList
 
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongList
add, add, add, addAll, addAll, addAll, addAll, addAll, addAll, addElements, addElements, compareTo, contains, ensureIndex, ensureRestrictedIndex, equals, get, getElements, hashCode, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, longListIterator, longListIterator, longSubList, peek, peekLong, pop, popLong, push, push, rem, remove, remove, removeElements, removeLong, set, set, size, subList, top, topLong, toString
 
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongCollection
add, clear, contains, containsAll, containsAll, isEmpty, longIterator, rem, removeAll, removeAll, retainAll, retainAll, toArray, toArray, toArray, toLongArray, toLongArray
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface it.unimi.dsi.fastutil.longs.LongList
add, addAll, addAll, addAll, addElements, addElements, getElements, indexOf, iterator, lastIndexOf, listIterator, listIterator, longListIterator, longListIterator, longSubList, removeElements, removeLong, set, size, subList
 
Methods inherited from interface java.util.List
add, add, addAll, addAll, clear, contains, containsAll, equals, get, hashCode, indexOf, isEmpty, lastIndexOf, remove, remove, removeAll, retainAll, set, toArray, toArray
 
Methods inherited from interface java.lang.Comparable
compareTo
 
Methods inherited from interface it.unimi.dsi.fastutil.longs.LongCollection
add, addAll, contains, containsAll, longIterator, rem, removeAll, retainAll, toArray, toArray, toLongArray, toLongArray
 
Methods inherited from interface it.unimi.dsi.fastutil.Stack
isEmpty
 

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(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

protected SparseSelect(long n,
                       long m,
                       int l,
                       LongBigList 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.

length

public long length()
Specified by:
length in interface LongBigList
Overrides:
length in class EliasFanoMonotoneLongBigList

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 position exists, −1 is returned.

bitVector

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