it.unimi.dsi.sux4j.mph
Class HollowTrie<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.HollowTrie<T>
All Implemented Interfaces:
Function<T,Long>, Object2LongFunction<T>, Serializable

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

A hollow trie, that is, a compacted trie recording just the length of the paths associated to the internal nodes.

Instances of this class can be used to compute a monotone minimal perfect hashing of the keys.

See Also:
Serialized Form

Field Summary
 
Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defRetValue
 
Constructor Summary
HollowTrie(Iterable<? extends T> iterable, TransformationStrategy<? super T> transform)
           
HollowTrie(Iterator<? extends T> iterator, TransformationStrategy<? super T> transform)
           
 
Method Summary
protected  it.unimi.dsi.sux4j.mph.HollowTrie.Node buildTrie(ObjectList<BitVector> elements, ObjectList<BitVector> ends, int pos, Reference2LongMap<BitVector> original)
          Builds a trie recursively.
 long getLong(Object object)
           
static void main(String[] arg)
           
 long numBits()
           
 int size()
           
 
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
 

Constructor Detail

HollowTrie

public HollowTrie(Iterable<? extends T> iterable,
                  TransformationStrategy<? super T> transform)

HollowTrie

public HollowTrie(Iterator<? extends T> iterator,
                  TransformationStrategy<? super T> transform)
Method Detail

getLong

public long getLong(Object object)
Specified by:
getLong in interface Object2LongFunction<T>

buildTrie

protected it.unimi.dsi.sux4j.mph.HollowTrie.Node buildTrie(ObjectList<BitVector> elements,
                                                           ObjectList<BitVector> ends,
                                                           int pos,
                                                           Reference2LongMap<BitVector> original)
Builds a trie recursively.

The trie will contain the suffixes of words in words starting at pos.

Parameters:
elements - a list of elements.
pos - a starting position.
Returns:
a trie containing the suffixes of words in words starting at pos.

size

public int size()
Specified by:
size in interface Function<T,Long>
Overrides:
size in class AbstractHashFunction<T>

numBits

public long numBits()

main

public static void main(String[] arg)
                 throws NoSuchMethodException,
                        IOException,
                        JSAPException
Throws:
NoSuchMethodException
IOException
JSAPException