Package it.unimi.dsi.sux4j.util

Class 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

    • 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 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

    • 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()
        Specified by:
        size in interface java.util.Collection<T>
        Specified by:
        size in interface java.util.Set<T>
        Specified by:
        size in class java.util.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 java.util.Collection<T>
        Specified by:
        add in interface java.util.Set<T>
        Overrides:
        add in class java.util.AbstractCollection<T>

      • remove

        public boolean remove​(java.lang.Object k)
        Specified by:
        remove in interface java.util.Collection<T>
        Specified by:
        remove in interface java.util.Set<T>
        Overrides:
        remove in class java.util.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.

      • 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​(java.lang.Object o)
        Specified by:
        contains in interface java.util.Collection<T>
        Specified by:
        contains in interface java.util.Set<T>
        Overrides:
        contains in class java.util.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 java.util.Collection<T>
        Specified by:
        iterator in interface java.lang.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 java.util.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 java.util.Comparator<? super T> comparator()
        Specified by:
        comparator in interface java.util.SortedSet<T>

      • first

        public T first()
        Specified by:
        first in interface java.util.SortedSet<T>

      • last

        public T last()
        Specified by:
        last in interface java.util.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 java.util.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 java.util.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 java.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