Class TernaryIntervalSearchTree

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

    public class TernaryIntervalSearchTree
    extends AbstractPrefixMap
    implements java.io.Serializable
    Ternary interval search trees.

    Ternary search trees are a data structure used to store words over an alphabet; they are a useful alternatives to tries when the alphabet is large.

    Ternary interval search trees have the additional properties of being able to locate quickly intervals of words extending a given prefix (where “quickly” means that no more successful character comparisons than the prefix length are performed). They do so by storing at each node the number of words covered by that node.

    This implementation exposes a number of interfaces: in particular, the set of words is seen as a lexicographically ordered ObjectList.

    This class is mutable, but for the time it implements only add(CharSequence). Words cannot be removed.

    Since:
    2.0
    See Also:
    Serialized Form
    • Field Summary

      • Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

        defRetValue
    • Constructor Summary

      Constructors 
      Constructor Description
      TernaryIntervalSearchTree()
      Creates a new empty ternary search tree.
      TernaryIntervalSearchTree​(java.util.Collection<? extends java.lang.CharSequence> c)
      Creates a new empty ternary search tree and populates it with a given collection of character sequences.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      boolean add​(java.lang.CharSequence s)  
      boolean containsKey​(java.lang.Object o)  
      LongInterval getApproximatedInterval​(java.lang.CharSequence s)  
      protected long getIndex​(java.lang.CharSequence s)  
      protected LongInterval getInterval​(java.lang.CharSequence s)
      Returns the range of strings having a given prefix.
      long getLong​(java.lang.Object o)  
      protected MutableString getTerm​(long index, MutableString s)
      Writes a string specified by index into a MutableString.
      static void main​(java.lang.String[] arg)  
      int size()
      Deprecated.
      long size64()
      Returns the intended number of keys in this function, or -1 if no such number exists.
      • 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, toString, 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, defaultReturnValue, defaultReturnValue, get, getOrDefault, getOrDefault, put, put, remove, removeLong
    • Constructor Detail

      • TernaryIntervalSearchTree

        public TernaryIntervalSearchTree()
        Creates a new empty ternary search tree.
      • TernaryIntervalSearchTree

        public TernaryIntervalSearchTree​(java.util.Collection<? extends java.lang.CharSequence> c)
        Creates a new empty ternary search tree and populates it with a given collection of character sequences.
        Parameters:
        c - a collection of character sequences.
    • Method Detail

      • getInterval

        protected LongInterval getInterval​(java.lang.CharSequence s)
        Description copied from class: AbstractPrefixMap
        Returns the range of strings having a given prefix.
        Specified by:
        getInterval in class AbstractPrefixMap
        Parameters:
        s - a prefix.
        Returns:
        the corresponding range of strings as an interval.
      • getApproximatedInterval

        public LongInterval getApproximatedInterval​(java.lang.CharSequence s)
      • getIndex

        protected long getIndex​(java.lang.CharSequence s)
      • containsKey

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

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

        public boolean add​(java.lang.CharSequence s)
      • size

        @Deprecated
        public int size()
        Deprecated.
        Description copied from interface: StringMap
        Specified by:
        size in interface it.unimi.dsi.fastutil.Function<java.lang.CharSequence,​java.lang.Long>
        Specified by:
        size in interface it.unimi.dsi.fastutil.Size64
        Specified by:
        size in interface StringMap<MutableString>
      • size64

        public long size64()
        Description copied from interface: StringMap
        Returns the intended number of keys in this function, or -1 if no such number exists.

        Most function implementations will have some knowledge of the intended number of keys in their domain. In some cases, however, this might not be possible. This default implementation, in particular, returns -1.

        Specified by:
        size64 in interface it.unimi.dsi.fastutil.Size64
        Specified by:
        size64 in interface StringMap<MutableString>
        Returns:
        the intended number of keys in this function, or -1 if that number is not available.
      • main

        public static void main​(java.lang.String[] arg)
                         throws java.io.IOException,
                                com.martiansoftware.jsap.JSAPException,
                                java.lang.NoSuchMethodException
        Throws:
        java.io.IOException
        com.martiansoftware.jsap.JSAPException
        java.lang.NoSuchMethodException