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:
  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    protected static final class 
     
    protected static final class 
    A linear-probing hash map that compares keys using signatures as a first try.
    protected static final class 
    A internal node.
    protected static final class 
    An external node, a.k.a. leaf.
    protected static class 
    A node of the trie.
    protected static final class 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    A dictionary mapping handles to the corresponding internal nodes.
    static final long
     
  • 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)
     
    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>
     
    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
     
    fatBinarySearch(it.unimi.dsi.bits.LongArrayBitVector v, long[] state, long b)
    Performs a non-exact fat binary search.
    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.
     
    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.
    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)
     
    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>
     
    it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator<T>
    iterator(T from)
     
     
    lower(T upperBound)
    Returns the first element in the trie that is smaller than the provided bound.
    static void
    main(String[] arg)
     
    predecessor(T upperBound)
    Returns the first element in the trie that is smaller than the provided bound.
    boolean
     
    int
     
    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)
     
    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.
    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 java.util.AbstractCollection

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

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface java.util.Collection

    parallelStream, removeIf, stream, toArray

    Methods inherited from interface java.lang.Iterable

    forEach

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

    spliterator

    Methods inherited from interface java.util.Set

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

    Methods inherited from interface java.util.SortedSet

    addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed
  • Field Details

    • serialVersionUID

      public static final long serialVersionUID
      See Also:
    • 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 ≪ λ(ab), 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