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

java.lang.Object
  extended by it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
      extended by it.unimi.dsi.sux4j.mph.BitstreamImmutablePaCoTrie<T>
All Implemented Interfaces:
Function<T,java.lang.Long>, Object2LongFunction<T>, java.io.Serializable

public class BitstreamImmutablePaCoTrie<T>
extends AbstractObject2LongFunction<T>

A succinct implementation of a binary partial compacted trie based on a recursive bitstream.

Instances of this class represent a partial compacted trie (PaCo trie). In such a trie, just a prefix of the path at each node is actually stored: then, we just store the number of missing bits.

The main purpose of PaCo tries is to serve as distributors for other data structures: given a set of delimiters D of a set S, a PaCo trie will rank an elements x of S over D, that is, it will return how many elements of D strictly precede x. To do so, a PaCo trie records at each node the smallest possible prefix that make it possible to rank correctly the whole of S: depending on the strings in S, the savings in space can be more or less significant.

An instance of this class stores a trie as a recursive bitstream: a node x with subtrees A and B is stored as

skip pathlen path missing leavesA A B,
where except for path, which is the path at x represented literally, all other components are numbers in δ coding, and the last two components are the recursive encodings of A and B. Leaves are distinguished by having skip equal to zero (in which case, no information after the path is recorded). leavesA is the number of leaves of A.

Author:
Sebastiano Vigna
See Also:
Serialized Form

Field Summary
 
Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defRetValue
 
Constructor Summary
BitstreamImmutablePaCoTrie(java.lang.Iterable<? extends T> elements, int bucketSize, TransformationStrategy<? super T> transformationStrategy)
          Creates a partial compacted trie using given elements, bucket size and transformation strategy.
 
Method Summary
 boolean containsKey(java.lang.Object o)
           
 long getLong(java.lang.Object o)
           
 int numberOfLeaves()
          Returns the number of leaves in this trie.
 long numBits()
           
 int size()
           
 
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

BitstreamImmutablePaCoTrie

public BitstreamImmutablePaCoTrie(java.lang.Iterable<? extends T> elements,
                                  int bucketSize,
                                  TransformationStrategy<? super T> transformationStrategy)
                           throws java.io.IOException
Creates a partial compacted trie using given elements, bucket size and transformation strategy.

Parameters:
elements - the elements among which the trie must be able to rank.
bucketSize - the size of a bucket.
transformationStrategy - a transformation strategy that must turn the elements in elements into a list of distinct, lexicographically increasing (in iteration order) bit vectors.
Throws:
java.io.IOException
Method Detail

getLong

public long getLong(java.lang.Object o)

numBits

public long numBits()

numberOfLeaves

public int numberOfLeaves()
Returns the number of leaves in this trie.

Returns:
the number of leaves in this trie.

containsKey

public boolean containsKey(java.lang.Object o)

size

public int size()