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

java.lang.Object
  extended by it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<K>
      extended by it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
          extended by 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 2r − 1 most frequent values can be stored in a MWHCFunction and suitably remapped when read. The function uses 2r − 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<BitVector> firstFunction
          The first function, or null.
protected  int n
          The number of elements.
protected  long[] remap
          A mapping from values of the first function to actual values, provided that there is a first function.
protected  MWHCFunction<BitVector> secondFunction
          The second function.
static long serialVersionUID
           
protected  TransformationStrategy<? super T> transform
          The transformation strategy to turn objects of type T into bit vectors.
 
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.
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 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<BitVector> firstFunction
The first function, or null. The special output value escape denotes that secondFunction should be queried instead.


secondFunction

protected final MWHCFunction<BitVector> 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.

Constructor Detail

TwoStepsMWHCFunction

public TwoStepsMWHCFunction(Iterable<? extends T> elements,
                            TransformationStrategy<? super T> transform,
                            LongList values)
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.

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>

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.