Class ImmutableBinaryTrie<T>

  • All Implemented Interfaces:
    it.unimi.dsi.fastutil.Function<T,​java.lang.Long>, it.unimi.dsi.fastutil.objects.Object2LongFunction<T>, java.io.Serializable, java.util.function.Function<T,​java.lang.Long>, java.util.function.ToLongFunction<T>

    public class ImmutableBinaryTrie<T>
    extends it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
    implements java.io.Serializable
    An immutable implementation of binary tries.

    Instance of this class are built starting from a lexicographically ordered list of BitVectors representing binary words. Each word is assigned its position (starting from 0) in the list. The words are then organised in a binary trie with path compression.

    Once the trie has been built, it is possible to ask whether a word w is contained in the trie (getting back its position in the list), the interval given by the words extending w and the approximated interval defined by w.

    Since:
    0.9.2
    Author:
    Sebastiano Vigna
    See Also:
    Serialized Form
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected static class  ImmutableBinaryTrie.Node
      A node in the trie.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected ImmutableBinaryTrie.Node root
      The root of the trie.
      • Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

        defRetValue
    • Constructor Summary

      Constructors 
      Constructor Description
      ImmutableBinaryTrie​(java.lang.Iterable<? extends T> elements, TransformationStrategy<? super T> transformationStrategy)
      Creates a trie from a set of elements.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected ImmutableBinaryTrie.Node buildTrie​(it.unimi.dsi.fastutil.objects.ObjectList<LongArrayBitVector> elements, int pos)
      Builds a trie recursively.
      boolean containsKey​(java.lang.Object element)  
      int get​(it.unimi.dsi.fastutil.booleans.BooleanIterator iterator)
      Return the index of the word returned by the given iterator, or -1 if the word is not in this trie.
      Interval getApproximatedInterval​(it.unimi.dsi.fastutil.booleans.BooleanIterator iterator)
      Returns an approximated prefix interval around the word returned by the specified iterator.
      Interval getApproximatedInterval​(T element)
      Returns an approximated interval around the specified word.
      long getIndex​(java.lang.Object element)  
      Interval getInterval​(BitVector word)
      Returns an interval given by the smallest and the largest word in the trie starting with the specified word.
      Interval getInterval​(it.unimi.dsi.fastutil.booleans.BooleanIterator iterator)
      Returns an interval given by the smallest and the largest word in the trie starting with the word returned by the given iterator.
      long getLong​(java.lang.Object element)  
      int size()
      Returns the number of binary words in this trie.
      java.lang.String toString()  
      • Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

        defaultReturnValue, defaultReturnValue
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface it.unimi.dsi.fastutil.Function

        apply, clear
      • Methods inherited from interface java.util.function.Function

        compose
      • Methods inherited from interface it.unimi.dsi.fastutil.objects.Object2LongFunction

        andThen, andThenByte, andThenChar, andThenDouble, andThenFloat, andThenInt, andThenLong, andThenObject, andThenReference, andThenShort, applyAsLong, composeByte, composeChar, composeDouble, composeFloat, composeInt, composeLong, composeObject, composeReference, composeShort, get, getOrDefault, getOrDefault, put, put, remove, removeLong
    • Constructor Detail

      • ImmutableBinaryTrie

        public ImmutableBinaryTrie​(java.lang.Iterable<? extends T> elements,
                                   TransformationStrategy<? super T> transformationStrategy)
        Creates a trie from a set of elements.
        Parameters:
        elements - a set of elements
        transformationStrategy - a transformation strategy that must turn elements into a list of distinct, lexicographically increasing (in iteration order) binary words.
    • Method Detail

      • buildTrie

        protected ImmutableBinaryTrie.Node buildTrie​(it.unimi.dsi.fastutil.objects.ObjectList<LongArrayBitVector> elements,
                                                     int pos)
        Builds a trie recursively.

        The trie will contain the suffixes of words in words starting at pos.

        Parameters:
        elements - a list of elements.
        pos - a starting position.
        Returns:
        a trie containing the suffixes of words in words starting at pos.
      • size

        public int size()
        Returns the number of binary words in this trie.
        Specified by:
        size in interface it.unimi.dsi.fastutil.Function<T,​java.lang.Long>
        Returns:
        the number of binary words in this trie.
      • getIndex

        public long getIndex​(java.lang.Object element)
      • getLong

        public long getLong​(java.lang.Object element)
        Specified by:
        getLong in interface it.unimi.dsi.fastutil.objects.Object2LongFunction<T>
      • containsKey

        public boolean containsKey​(java.lang.Object element)
        Specified by:
        containsKey in interface it.unimi.dsi.fastutil.Function<T,​java.lang.Long>
      • get

        public int get​(it.unimi.dsi.fastutil.booleans.BooleanIterator iterator)
        Return the index of the word returned by the given iterator, or -1 if the word is not in this trie.
        Parameters:
        iterator - a boolean iterator that will be used to find a word in this trie.
        Returns:
        the index of the specified word, or -1 if the word returned by the iterator is not in this trie.
        See Also:
        getLong(Object)
      • getInterval

        public Interval getInterval​(BitVector word)
        Returns an interval given by the smallest and the largest word in the trie starting with the specified word.
        Parameters:
        word - a word.
        Returns:
        an interval given by the smallest and the largest word in the trie that start with word (thus, the empty inteval if no such words exist).
        See Also:
        getInterval(BooleanIterator)
      • getInterval

        public Interval getInterval​(it.unimi.dsi.fastutil.booleans.BooleanIterator iterator)
        Returns an interval given by the smallest and the largest word in the trie starting with the word returned by the given iterator.
        Parameters:
        iterator - an iterator.
        Returns:
        an interval given by the smallest and the largest word in the trie that start with the word returned by iterator (thus, the empty inteval if no such words exist).
        See Also:
        getInterval(BitVector)
      • getApproximatedInterval

        public Interval getApproximatedInterval​(T element)
        Returns an approximated interval around the specified word.

        Given a word w, the corresponding approximated interval is defined as follows: if the words in the approximator are thought of as left interval extremes in a larger lexicographically ordered set of words, and we number these word intervals using the indices of their left extremes, then the first word extending w would be in the word interval given by the left extreme of the interval returned by this method, whereas the last word extending w would be in the word interval given by the right extreme of the interval returned by this method. If no word in the larger set could possibly extend w (because w is smaller than the lexicographically smallest word in the approximator) the result is just an empty interval.

        Parameters:
        element - an element.
        Returns:
        an approximated interval around the specified word.
        See Also:
        getApproximatedInterval(BooleanIterator)
      • getApproximatedInterval

        public Interval getApproximatedInterval​(it.unimi.dsi.fastutil.booleans.BooleanIterator iterator)
        Returns an approximated prefix interval around the word returned by the specified iterator.
        Parameters:
        iterator - an iterator.
        Returns:
        an approximated interval around the specified word: if the words in this trie are thought of as left interval extremes in a larger lexicographically ordered set of words, and we number these word intervals using the indices of their left extremes, then the first word extending word would be in the word interval given by the left extreme of the Interval returned by this method, whereas the last word extending word would be in the word interval given by the right extreme of the Interval returned by this method.
        See Also:
        getApproximatedInterval(Object)
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object