it.unimi.dsi.sux4j.bits
Class SparseSelect

java.lang.Object
  it.unimi.dsi.fastutil.longs.AbstractLongCollection
      it.unimi.dsi.fastutil.longs.AbstractLongList
          it.unimi.dsi.util.AbstractLongBigList
              it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
                  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