it.unimi.dsi.sux4j.mph
Class TwoStepsMWHCFunction<T>

java.lang.Object
  it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<K>
      it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
          it.unimi.dsi.sux4j.mph.TwoStepsMWHCFunction<T>

All Implemented Interfaces:

Function<T,Long>, Object2LongFunction<T>, Serializable

public class TwoStepsMWHCFunction<T>
extends AbstractHashFunction<T>
implements Serializable

A read-only function stored using two Majewski-Wormald-Havas-Czech functions—one for frequent values, and one for infrequent values.

The constructor of this class performs a pre-scan of the values to be assigned. If possible, it finds the best possible r such that the 2^r − 1 most frequent values can be stored in a MWHCFunction and suitably remapped when read. The function uses 2^r − 1 as an escape symbol for all other values, which are stored in a separate function.

Since:

1.0.2

Author:

Sebastiano Vigna

See Also:

Serialized Form

Field Summary

protected int	escape The escape value returned by firstFunction to suggest that secondFunction should be queried instead, provided that there is a first function.
protected MWHCFunction<T>	firstFunction The first function, or null.
protected int	n The number of elements.
double	rankMean The mean of the rank distribution.
protected long[]	remap A mapping from values of the first function to actual values, provided that there is a first function.
protected MWHCFunction<T>	secondFunction The second function.
static long	serialVersionUID
protected TransformationStrategy<? super T>	transform The transformation strategy to turn objects of type T into bit vectors.
int	width The width of the output of this function, in bits.

Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

defRetValue

Constructor Summary

	TwoStepsMWHCFunction(Iterable<? extends T> elements, TransformationStrategy<? super T> transform, LongList values) Creates a new two-step function for the given elements and values.
	TwoStepsMWHCFunction(Iterable<? extends T> elements, TransformationStrategy<? super T> transform, LongList values, ChunkedHashStore<T> chunkedHashStore) Creates a new two-step function for the given elements and values.
protected	TwoStepsMWHCFunction(TwoStepsMWHCFunction<T> function) Creates a new function by copying a given one; non-transient fields are (shallow) copied.

Method Summary

long	getLong(Object o)
long	getLongByTriple(long[] triple)
long	numBits() Returns the number of bits used by this structure.
int	size() Returns the number of elements in the function domain.

Methods inherited from class it.unimi.dsi.sux4j.mph.AbstractHashFunction

containsKey

Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

clear, defaultReturnValue, defaultReturnValue, get, put, put, remove, removeLong

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

serialVersionUID

public static final long serialVersionUID

See Also:

Constant Field Values

n

protected final int n

The number of elements.

transform

protected final TransformationStrategy<? super T> transform

The transformation strategy to turn objects of type T into bit vectors.

firstFunction

protected final MWHCFunction<T> firstFunction

The first function, or null. The special output value escape denotes that secondFunction should be queried instead.

secondFunction

protected final MWHCFunction<T> secondFunction

The second function. All queries for which firstFunction returns escape (or simply all queries, if firstFunction is null) will be rerouted here.

remap

protected final long[] remap

A mapping from values of the first function to actual values, provided that there is a first function.

escape

protected final int escape

The escape value returned by firstFunction to suggest that secondFunction should be queried instead, provided that there is a first function.

rankMean

public final double rankMean

The mean of the rank distribution.

width

public final int width

The width of the output of this function, in bits.

Constructor Detail

TwoStepsMWHCFunction

public TwoStepsMWHCFunction(Iterable<? extends T> elements,
                            TransformationStrategy<? super T> transform,
                            LongList values)
                     throws IOException

Creates a new two-step function for the given elements and values.

Parameters:

elements - the elements in the domain of the function.

transform - a transformation strategy for the elements.

values - values to be assigned to each element, in the same order of the iterator returned by elements; if null, the assigned value will the the ordinal number of each element.

Throws:

IOException

TwoStepsMWHCFunction

public TwoStepsMWHCFunction(Iterable<? extends T> elements,
                            TransformationStrategy<? super T> transform,
                            LongList values,
                            ChunkedHashStore<T> chunkedHashStore)
                     throws IOException

Creates a new two-step function for the given elements and values.

Parameters:

elements - the elements in the domain of the function.

transform - a transformation strategy for the elements.

values - values to be assigned to each element, in the same order of the iterator returned by elements; if null, the assigned value will the the ordinal number of each element.

Throws:

IOException

TwoStepsMWHCFunction

protected TwoStepsMWHCFunction(TwoStepsMWHCFunction<T> function)

Creates a new function by copying a given one; non-transient fields are (shallow) copied.

Parameters:

function - the function to be copied.

Method Detail

getLong

public long getLong(Object o)

Specified by:

getLong in interface Object2LongFunction<T>

getLongByTriple

public long getLongByTriple(long[] triple)

size

public int size()

Returns the number of elements in the function domain.

Specified by:

size in interface Function<T,Long>

Overrides:

size in class AbstractHashFunction<T>

Returns:

the number of the elements in the function domain.

numBits

public long numBits()

Returns the number of bits used by this structure.

Returns:

the number of bits used by this structure.