Package it.unimi.dsi.sux4j.util

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:
ObjectBidirectionalIterable<T>, ObjectCollection<T>, ObjectIterable<T>, ObjectSet<T>, ObjectSortedSet<T>, Serializable, Cloneable, Iterable<T>, Collection<T>, Set<T>, SortedSet<T>
public class ZFastTrie<T> extends 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:

  • 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(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, 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, 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(LongArrayBitVector v, long[] state, 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(LongArrayBitVector v, long[] state, 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(LongArrayBitVector v, long[] state, 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(LongArrayBitVector v, long[] state, 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(LongArrayBitVector v, long[] state, 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(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(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 ObjectBidirectionalIterator<T> iterator()
      Specified by:
      iterator in interface Collection<T>
      Specified by:
      iterator in interface Iterable<T>
      Specified by:
      iterator in interface ObjectBidirectionalIterable<T>
      Specified by:
      iterator in interface ObjectCollection<T>
      Specified by:
      iterator in interface ObjectIterable<T>
      Specified by:
      iterator in interface ObjectSet<T>
      Specified by:
      iterator in interface ObjectSortedSet<T>
      Specified by:
      iterator in interface Set<T>
      Specified by:
      iterator in class AbstractObjectSortedSet<T>

    • iterator

      public ObjectBidirectionalIterator<T> iterator(T from)
      Specified by:
      iterator in interface 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 ObjectSortedSet<T> headSet(T arg0)
      Specified by:
      headSet in interface ObjectSortedSet<T>
      Specified by:
      headSet in interface SortedSet<T>

    • subSet

      public ObjectSortedSet<T> subSet(T arg0, T arg1)
      Specified by:
      subSet in interface ObjectSortedSet<T>
      Specified by:
      subSet in interface SortedSet<T>

    • tailSet

      public ObjectSortedSet<T> tailSet(T arg0)
      Specified by:
      tailSet in interface ObjectSortedSet<T>
      Specified by:
      tailSet in interface SortedSet<T>

    • main

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