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

public class LcpMonotoneMinimalPerfectHashFunction<T>
extends AbstractHashFunction<T>
implements java.io.Serializable

A monotone minimal perfect hash implementation based on fixed-size bucketing that uses longest common prefixes as distributors.

See Also:
Serialized Form

Field Summary
protected  int bucketSize
          The size of a bucket.
protected  int bucketSizeMask
          The mask for log2BucketSize bits.
protected  MWHCFunction<BitVector> lcp2Bucket
          A function mapping each longest common prefix to its bucket.
protected  int log2BucketSize
          Fast.ceilLog2(int) of bucketSize.
protected  int n
          The number of elements.
protected  MWHCFunction<BitVector> offsetLcpLength
          A function mapping each element to the offset inside its bucket (lowest log2BucketSize bits) and to the length of the longest common prefix of its bucket (remaining bits).
static long serialVersionUID
           
protected  TransformationStrategy<? super T> transform
          The transformation strategy.
 
Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defRetValue
 
Constructor Summary
LcpMonotoneMinimalPerfectHashFunction(java.lang.Iterable<? extends T> iterable, TransformationStrategy<? super T> transform)
           
 
Method Summary
 long getLong(java.lang.Object o)
           
 boolean hasTerms()
           
static void main(java.lang.String[] arg)
           
 long numBits()
          Returns the number of bits used by this structure.
 int size()
          Returns the number of terms hashed.
 
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.


bucketSize

protected final int bucketSize
The size of a bucket.


log2BucketSize

protected final int log2BucketSize
Fast.ceilLog2(int) of bucketSize.


bucketSizeMask

protected final int bucketSizeMask
The mask for log2BucketSize bits.


offsetLcpLength

protected final MWHCFunction<BitVector> offsetLcpLength
A function mapping each element to the offset inside its bucket (lowest log2BucketSize bits) and to the length of the longest common prefix of its bucket (remaining bits).


lcp2Bucket

protected final MWHCFunction<BitVector> lcp2Bucket
A function mapping each longest common prefix to its bucket.


transform

protected final TransformationStrategy<? super T> transform
The transformation strategy.

Constructor Detail

LcpMonotoneMinimalPerfectHashFunction

public LcpMonotoneMinimalPerfectHashFunction(java.lang.Iterable<? extends T> iterable,
                                             TransformationStrategy<? super T> transform)
Method Detail

getLong

public long getLong(java.lang.Object o)
Specified by:
getLong in interface Object2LongFunction<T>

size

public int size()
Returns the number of terms hashed.

Specified by:
size in interface Function<T,java.lang.Long>
Overrides:
size in class AbstractHashFunction<T>
Returns:
the number of terms hashed.

numBits

public long numBits()
Returns the number of bits used by this structure.

Returns:
the number of bits used by this structure.

hasTerms

public boolean hasTerms()

main

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