Class ZFastTrie<T>
- java.lang.Object
-
- java.util.AbstractCollection<K>
-
- it.unimi.dsi.fastutil.objects.AbstractObjectCollection<K>
-
- it.unimi.dsi.fastutil.objects.AbstractObjectSet<K>
-
- 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>
,java.io.Serializable
,java.lang.Cloneable
,java.lang.Iterable<T>
,java.util.Collection<T>
,java.util.Set<T>
,java.util.SortedSet<T>
public class ZFastTrie<T> extends it.unimi.dsi.fastutil.objects.AbstractObjectSortedSet<T> implements java.io.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 class
ZFastTrie.ExitData<U>
protected static class
ZFastTrie.Handle2NodeMap<U>
A linear-probing hash map that compares keys using signatures as a first try.protected static class
ZFastTrie.InternalNode<U>
A internal node.protected static class
ZFastTrie.Leaf<U>
An external node, a.k.a. leaf.protected static class
ZFastTrie.Node<U>
A node of the trie.protected static 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 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(java.lang.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(java.util.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
All Methods Static Methods Instance Methods Concrete Methods 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 long
checkMask(long b)
Returns the mask used for check for 2-fattest numbers when the left extreme of the interval is −1.static 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.java.util.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(java.lang.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(java.lang.String[] arg)
T
predecessor(T upperBound)
Returns the first element in the trie that is smaller than the provided bound.boolean
remove(java.lang.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 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 java.util.AbstractCollection
addAll, clear, containsAll, isEmpty, removeAll, retainAll, toArray, toArray
-
-
-
-
Field Detail
-
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 Detail
-
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(java.util.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(java.lang.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 Detail
-
size
public int size()
-
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)
-
remove
public boolean remove(java.lang.Object k)
-
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 ofv
precomputed byHashes.preprocessMurmur(BitVector, long)
.stack
- a stack that will be filled with the 2-fat ancestors.- Returns:
- the parent of the exit node of
v
, ornull
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 ofv
precomputed byHashes.preprocessMurmur(BitVector, long)
.stack
- a nonempty stack as filled bygetParentExitNode(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 forv
.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 forv
.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 forv
.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 forv
.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 forv
.b
- the right extreme of the search interval, ≥ −1 (included).- Returns:
- the parent of the exit node.
-
contains
public boolean contains(java.lang.Object o)
-
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
, ornull
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
, ornull
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
, ortail
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
, ortail
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
, orhead
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
, orhead
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
, orhead
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
, orhead
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 interfacejava.util.Collection<T>
- Specified by:
iterator
in interfacejava.lang.Iterable<T>
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.objects.ObjectBidirectionalIterable<T>
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.objects.ObjectCollection<T>
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.objects.ObjectIterable<T>
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.objects.ObjectSet<T>
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.objects.ObjectSortedSet<T>
- Specified by:
iterator
in interfacejava.util.Set<T>
- Specified by:
iterator
in classit.unimi.dsi.fastutil.objects.AbstractObjectSortedSet<T>
-
iterator
public it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator<T> iterator(T from)
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.objects.ObjectSortedSet<T>
-
comparator
public java.util.Comparator<? super T> comparator()
- Specified by:
comparator
in interfacejava.util.SortedSet<T>
-
main
public static void main(java.lang.String[] arg) throws java.lang.NoSuchMethodException, java.io.IOException, com.martiansoftware.jsap.JSAPException
- Throws:
java.lang.NoSuchMethodException
java.io.IOException
com.martiansoftware.jsap.JSAPException
-
-