Package it.unimi.dsi.big.util

Class TernaryIntervalSearchTree

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<CharSequence>
it.unimi.dsi.big.util.AbstractPrefixMap
it.unimi.dsi.big.util.TernaryIntervalSearchTree
All Implemented Interfaces:
PrefixMap<MutableString>, StringMap<MutableString>, it.unimi.dsi.fastutil.Function<CharSequence,Long>, it.unimi.dsi.fastutil.objects.Object2LongFunction<CharSequence>, it.unimi.dsi.fastutil.Size64, Serializable, Function<CharSequence,Long>, ToLongFunction<CharSequence>
public class TernaryIntervalSearchTree extends AbstractPrefixMap implements 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:

  • Constructor Details

    • TernaryIntervalSearchTree

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

    • TernaryIntervalSearchTree

      public TernaryIntervalSearchTree(Collection<? extends 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 Details

    • getInterval

      protected LongInterval getInterval(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(CharSequence s)

    • getTerm

      protected MutableString getTerm(long index, MutableString s)
      Description copied from class: AbstractPrefixMap
      Writes a string specified by index into a MutableString.
      Specified by:
      getTerm in class AbstractPrefixMap
      Parameters:
      index - the index of a string.
      s - a mutable string.
      Returns:
      string.

    • getIndex

      protected long getIndex(CharSequence s)

    • containsKey

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

    • getLong

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

    • add

      public boolean add(CharSequence s)

    • size

      @Deprecated public int size()
      Deprecated.
      Description copied from interface: StringMap
      Specified by:
      size in interface it.unimi.dsi.fastutil.Function<CharSequence,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(String[] arg) throws IOException, com.martiansoftware.jsap.JSAPException, NoSuchMethodException
      Throws:
      IOException
      com.martiansoftware.jsap.JSAPException
      NoSuchMethodException