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<Long>, Select, LongBigList, Serializable, Comparable<List<? extends Long>>, Iterable<Long>, Collection<Long>, List<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

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
protected  boolean fromRank
          Whether this structure was built from a SparseRank structure, and thus shares part of its internal state.
 
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.
  SparseSelect(LongBigList list)
          Creates a new select structure using a big list of longs.
  SparseSelect(LongList list)
          Creates a new select structure using a list of longs.
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.
 boolean equals(Object o)
           
 long getLong(long pos)
           
 SparseRank getRank()
          Creates a new SparseRank structure sharing data with this instance.
 int hashCode()
           
 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.
 int size()
           
 String toString()
           
 
Methods inherited from class it.unimi.dsi.util.AbstractLongBigList
add, ensureIndex, ensureRestrictedIndex, getLong, length, removeLong, set, 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, get, getElements, 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
 
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, get, 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
 

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

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

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

size

public int size()
Specified by:
size in interface Collection<Long>
Specified by:
size in interface List<Long>
Overrides:
size in class AbstractLongBigList

getLong

public long getLong(long pos)
Specified by:
getLong in interface LongBigList
Overrides:
getLong 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.

hashCode

public int hashCode()
Specified by:
hashCode in interface Collection<Long>
Specified by:
hashCode in interface List<Long>
Overrides:
hashCode in class AbstractLongList

equals

public boolean equals(Object o)
Specified by:
equals in interface Collection<Long>
Specified by:
equals in interface List<Long>
Overrides:
equals in class AbstractLongList

toString

public String toString()
Overrides:
toString in class AbstractLongList