Class ZFastTrie<T>

java.lang.Object

java.util.AbstractCollection<T>

it.unimi.dsi.fastutil.objects.AbstractObjectCollection<T>

it.unimi.dsi.fastutil.objects.AbstractObjectSet<T>

it.unimi.dsi.fastutil.objects.AbstractObjectSortedSet<T>

it.unimi.dsi.sux4j.util.ZFastTrie<T>

All Implemented Interfaces:

it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterable<T>, it.unimi.dsi.fastutil.objects.ObjectCollection<T>, it.unimi.dsi.fastutil.objects.ObjectIterable<T>, it.unimi.dsi.fastutil.objects.ObjectSet<T>, it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>, Serializable, Cloneable, Iterable<T>, Collection<T>, SequencedCollection<T>, SequencedSet<T>, Set<T>, SortedSet<T>

public class ZFastTrie<T>
extends it.unimi.dsi.fastutil.objects.AbstractObjectSortedSet<T>
implements Serializable

A z-fast trie, that is, a predecessor/successor data structure using low linear (in the number of keys) additional space and answering to the query string x in time |x|/w + log(max{|x|, |x^-|, |x⁺|}) with high probability, where w is the machine word size, and x^-/x⁺ are the predecessor/successor of x in the currently stored set, respectively.

In rough terms, the z-fast trie uses time |x|/w (which is optimal) to actually look at the string content, and log(max{|x|, |x^-|, |x⁺|}) to perform the search. This is known to be (essentially) optimal. String lengths are up to Integer.MAX_VALUE, and not limited to be a constant multiple of w for the bounds to hold.

The linear overhead of a z-fast trie is very low. For n keys we allocate 2n − 1 nodes containing six references and two longs, plus a dictionary containing n − 1 nodes (thus using around 2n references and 2n longs).

See Also:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static final class	ZFastTrie.ExitData<U>
protected static final class	ZFastTrie.Handle2NodeMap<U>	A linear-probing hash map that compares keys using signatures as a first try.
protected static final class	ZFastTrie.InternalNode<U>	A internal node.
protected static final class	ZFastTrie.Leaf<U>	An external node, a.k.a. leaf.
protected static class	ZFastTrie.Node<U>	A node of the trie.
protected static final class	ZFastTrie.ParexData<U>

Field Summary

Fields

Modifier and Type	Field	Description
ZFastTrie.Handle2NodeMap<T>	handle2Node	A dictionary mapping handles to the corresponding internal nodes.
static final long	serialVersionUID

Constructor Summary

Constructors

Constructor	Description
ZFastTrie(it.unimi.dsi.bits.TransformationStrategy<? super T> transform)	Creates a new z-fast trie using the given transformation strategy.
ZFastTrie(Iterable<? extends T> elements, it.unimi.dsi.bits.TransformationStrategy<? super T> transform)	Creates a new z-fast trie using the given elements and transformation strategy.
ZFastTrie(Iterator<? extends T> elements, it.unimi.dsi.bits.TransformationStrategy<? super T> transform)	Creates a new z-fast trie using the given elements and transformation strategy.

Method Summary

Modifier and Type	Method	Description
boolean	add(T k)
T	ceiling(T lowerBound)	Returns the first element in the trie that is greater than or equal to the provided bound.
static final long	checkMask(long b)	Returns the mask used for check for 2-fattest numbers when the left extreme of the interval is −1.
static final long	checkMask(long a, long b)	Returns the mask used for check for 2-fattest numbers when the left extreme of the interval is not -1.
Comparator<? super T>	comparator()
protected void	completeFatBinarySearchStack(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack, long a, long b)	Completes the stack of a previous successful fat binary search.
boolean	contains(Object o)
protected ZFastTrie.InternalNode<T>	fatBinarySearch(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, long b)	Performs a non-exact fat binary search.
protected ZFastTrie.InternalNode<T>	fatBinarySearchExact(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, long b)	Performs an exact fat binary search.
protected void	fatBinarySearchStack(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack, long b)	Performs a non-exact fat binary search with stack.
protected void	fatBinarySearchStackExact(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack, long b)	Performs an exact fat binary search with stack.
T	first()
T	floor(T upperBound)	Returns the first element in the trie that is smaller than or equal to the provided bound.
void	getGrandParentExitNode(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack)	Returns the grandparent of the exit node of a given bit vector.
ZFastTrie.ParexData<T>	getParentExitNode(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack)	Returns the parent of the exit node of a given bit vector.
it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>	headSet(T arg0)
T	higher(T lowerBound)	Returns the first element in the trie that is greater than the provided bound.
boolean	isNonempty(T lowerBound, T upperBound)	Returns whether there is an element between the given bounds.
it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator<T>	iterator()
it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator<T>	iterator(T from)
T	last()
T	lower(T upperBound)	Returns the first element in the trie that is smaller than the provided bound.
static void	main(String[] arg)
T	predecessor(T upperBound)	Returns the first element in the trie that is smaller than the provided bound.
boolean	remove(Object k)
int	size()
T	strictSuccessor(T lowerBound)	Returns the first element in the trie that is greater than the provided bound.
it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>	subSet(T arg0, T arg1)
T	successor(T lowerBound)	Returns the first element in the trie that is greater than or equal to the provided bound.
it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>	tailSet(T arg0)
static final long	twoFattest(long a, long b)	Returns the 2-fattest number in an interval.
T	weakPredecessor(T upperBound)	Returns the first element in the trie that is smaller than or equal to the provided bound.

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

equals, hashCode

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

toString

Methods inherited from class AbstractCollection

addAll, clear, containsAll, isEmpty, removeAll, retainAll, toArray, toArray

Methods inherited from class Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface Iterable

forEach

Methods inherited from interface it.unimi.dsi.fastutil.objects.ObjectSortedSet

spliterator

Methods inherited from interface Set

addAll, clear, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

Methods inherited from interface SortedSet

addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed

Field Details

serialVersionUID

public static final long serialVersionUID

See Also:

• Constant Field Values

handle2Node

public transient ZFastTrie.Handle2NodeMap<T> handle2Node

A dictionary mapping handles to the corresponding internal nodes.

Constructor Details

ZFastTrie

public ZFastTrie(it.unimi.dsi.bits.TransformationStrategy<? super T> transform)

Creates a new z-fast trie using the given transformation strategy.

Parameters:

transform - a transformation strategy that must turn distinct elements into distinct, prefix-free bit vectors.

ZFastTrie

public ZFastTrie(Iterator<? extends T> elements,
 it.unimi.dsi.bits.TransformationStrategy<? super T> transform)

Creates a new z-fast trie using the given elements and transformation strategy.

Parameters:

elements - an iterator returning the elements to be inserted in the trie.

transform - a transformation strategy that must turn distinct elements into distinct, prefix-free bit vectors.

ZFastTrie

public ZFastTrie(Iterable<? extends T> elements,
 it.unimi.dsi.bits.TransformationStrategy<? super T> transform)

Creates a new z-fast trie using the given elements and transformation strategy.

Parameters:

elements - an iterator returning the elements to be inserted in the trie.

transform - a transformation strategy that must turn distinct elements into distinct, prefix-free bit vectors.

Method Details

size

public int size()

Specified by:

size in interface Collection<T>

Specified by:

size in interface Set<T>

Specified by:

size in class AbstractCollection<T>

twoFattest

public static final long twoFattest(long a,
 long b)

Returns the 2-fattest number in an interval.

Note that to get the length of the handle of a node you must call this function passing the length of the extent of the parent (one less than the node name) and the length of the extent of the node.

Parameters:

a - left extreme, ≥-1 (excluded).

b - right extreme, ≥ 0 (included).

Returns:

the 2-fattest number in (a..b].

checkMask

public static final long checkMask(long a,
 long b)

Returns the mask used for check for 2-fattest numbers when the left extreme of the interval is not -1.

Note that to get the length of the handle of a node you must call this function passing the length of the extent of the parent (one less than the node name) and the length of the extent of the node.

Parameters:

a - left extreme, ≥-1 (excluded).

b - right extreme, ≥ 0 (included).

Returns:

−1 ≪ λ(a ⊕ b), the initial mask for fat binary search in (a..b].

checkMask

public static final long checkMask(long b)

Returns the mask used for check for 2-fattest numbers when the left extreme of the interval is −1.

Parameters:

b - right extreme, ≥ 0 (included).

Returns:

−1 ≪ λb + 1, the initial mask for fat binary search in (-1..b].

add

public boolean add(T k)

Specified by:

add in interface Collection<T>

Specified by:

add in interface Set<T>

Overrides:

add in class AbstractCollection<T>

remove

public boolean remove(Object k)

Specified by:

remove in interface Collection<T>

Specified by:

remove in interface Set<T>

Overrides:

remove in class AbstractCollection<T>

getParentExitNode

public ZFastTrie.ParexData<T> getParentExitNode(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack)

Returns the parent of the exit node of a given bit vector.

Parameters:

v - a bit vector.

state - the hash state of v precomputed by Hashes.preprocessMurmur(BitVector, long).

stack - a stack that will be filled with the 2-fat ancestors.

Returns:

the parent of the exit node of v, or null if the exit node is the root.

getGrandParentExitNode

public void getGrandParentExitNode(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack)

Returns the grandparent of the exit node of a given bit vector.

Parameters:

v - a bit vector.

state - the hash state of v precomputed by Hashes.preprocessMurmur(BitVector, long).

stack - a nonempty stack as filled by getParentExitNode(LongArrayBitVector, long[], ObjectArrayList); the top of the stack must not be the root.

fatBinarySearchStack

protected void fatBinarySearchStack(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack,
 long b)

Performs a non-exact fat binary search with stack.

Parameters:

v - the bit vector on which to perform the search.

state - preprocessed MurmurHash state for v.

stack - a stack where the results of the search will be cumulated.

b - the right extreme of the search interval, ≥ −1 (included).

fatBinarySearchStackExact

protected void fatBinarySearchStackExact(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack,
 long b)

Performs an exact fat binary search with stack.

Parameters:

v - the bit vector on which to perform the search.

state - preprocessed MurmurHash state for v.

stack - a stack where the results of the search will be cumulated.

b - the right extreme of the search interval, ≥ −1 (included).

completeFatBinarySearchStack

protected void completeFatBinarySearchStack(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 it.unimi.dsi.fastutil.objects.ObjectArrayList<ZFastTrie.InternalNode<T>> stack,
 long a,
 long b)

Completes the stack of a previous successful fat binary search.

Parameters:

v - the bit vector on which to perform the search.

state - preprocessed MurmurHash state for v.

stack - a stack where the results of the completion will be cumulated.

a - the left extreme of the completion interval, ≥ −1 (excluded)

b - the right extreme of the completion interval, ≥ a (included).

fatBinarySearch

protected ZFastTrie.InternalNode<T> fatBinarySearch(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 long b)

Performs a non-exact fat binary search.

Parameters:

v - the bit vector on which to perform the search.

state - preprocessed MurmurHash state for v.

b - the right extreme of the search interval, ≥ −1 (included).

Returns:

the parent of the exit node or the exit node, in case of success; an arbitrary node otherwise.

fatBinarySearchExact

protected ZFastTrie.InternalNode<T> fatBinarySearchExact(it.unimi.dsi.bits.LongArrayBitVector v,
 long[] state,
 long b)

Performs an exact fat binary search.

Parameters:

v - the bit vector on which to perform the search.

state - preprocessed MurmurHash state for v.

b - the right extreme of the search interval, ≥ −1 (included).

Returns:

the parent of the exit node.

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<T>

Specified by:

contains in interface Set<T>

Overrides:

contains in class AbstractCollection<T>

successor

public T successor(T lowerBound)

Returns the first element in the trie that is greater than or equal to the provided bound.

Parameters:

lowerBound - a lower bound on the returned value.

Returns:

the first element in the trie that is greater than or equal to lowerBound, or null if no such element exists.

ceiling

public T ceiling(T lowerBound)

Returns the first element in the trie that is greater than or equal to the provided bound.

Parameters:

lowerBound - a lower bound on the returned value.

Returns:

the first element in the trie that is greater than or equal to lowerBound, or null if no such element exists.

Implementation Specification:

This method just delegates to successor(Object).

strictSuccessor

public T strictSuccessor(T lowerBound)

Returns the first element in the trie that is greater than the provided bound.

Parameters:

lowerBound - a strict lower bound on the returned value.

Returns:

the first element in the trie that is greater than lowerBound, or tail if no such element exists.

higher

public T higher(T lowerBound)

Returns the first element in the trie that is greater than the provided bound.

Parameters:

lowerBound - a strict lower bound on the returned value.

Returns:

the first element in the trie that is greater than lowerBound, or tail if no such element exists.

Implementation Specification:

This method just delegates to strictSuccessor(Object).

predecessor

public T predecessor(T upperBound)

Returns the first element in the trie that is smaller than the provided bound.

Parameters:

upperBound - a strict upper bound on the returned value.

Returns:

the first element in the trie that is smaller than upperBound, or head if no such element exists.

lower

public T lower(T upperBound)

Returns the first element in the trie that is smaller than the provided bound.

Parameters:

upperBound - a strict upper bound on the returned value.

Returns:

the first element in the trie that is smaller than upperBound, or head if no such element exists.

Implementation Specification:

This method just delegates to predecessor(Object).

weakPredecessor

public T weakPredecessor(T upperBound)

Returns the first element in the trie that is smaller than or equal to the provided bound.

Parameters:

upperBound - an upper bound on the returned value.

Returns:

the first element in the trie that is smaller than or equal to upperBound, or head if no such element exists.

floor

public T floor(T upperBound)

Returns the first element in the trie that is smaller than or equal to the provided bound.

Parameters:

upperBound - an upper bound on the returned value.

Returns:

the first element in the trie that is smaller than or equal to upperBound, or head if no such element exists.

Implementation Specification:

This method just delegates to weakPredecessor(Object).

isNonempty

public boolean isNonempty(T lowerBound,
 T upperBound)

Returns whether there is an element between the given bounds.

Parameters:

lowerBound - a lower bound.

upperBound - an upper bound.

Returns:

true if there is an element in the interval [lowerBound...upperBound).

iterator

public it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator<T> iterator()

Specified by:

iterator in interface Collection<T>

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterable<T>

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectCollection<T>

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectIterable<T>

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectSet<T>

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>

Specified by:

iterator in interface Set<T>

Specified by:

iterator in class it.unimi.dsi.fastutil.objects.AbstractObjectSortedSet<T>

iterator

public it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator<T> iterator(T from)

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>

comparator

public Comparator<? super T> comparator()

Specified by:

comparator in interface SortedSet<T>

first

public T first()

Specified by:

first in interface SortedSet<T>

last

public T last()

Specified by:

last in interface SortedSet<T>

headSet

public it.unimi.dsi.fastutil.objects.ObjectSortedSet<T> headSet(T arg0)

Specified by:

headSet in interface it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>

Specified by:

headSet in interface SortedSet<T>

subSet

public it.unimi.dsi.fastutil.objects.ObjectSortedSet<T> subSet(T arg0,
 T arg1)

Specified by:

subSet in interface it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>

Specified by:

subSet in interface SortedSet<T>

tailSet

public it.unimi.dsi.fastutil.objects.ObjectSortedSet<T> tailSet(T arg0)

Specified by:

tailSet in interface it.unimi.dsi.fastutil.objects.ObjectSortedSet<T>

Specified by:

tailSet in interface SortedSet<T>

main

public static void main(String[] arg)
                 throws NoSuchMethodException,
IOException,
com.martiansoftware.jsap.JSAPException

Throws:

NoSuchMethodException

IOException

com.martiansoftware.jsap.JSAPException