Package it.unimi.dsi.util

Class TernaryIntervalSearchTree

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

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