it.unimi.dsi.util
Class TernaryIntervalSearchTree

java.lang.Object
  extended by it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<java.lang.CharSequence>
      extended by it.unimi.dsi.util.AbstractPrefixMap
          extended by it.unimi.dsi.util.TernaryIntervalSearchTree
All Implemented Interfaces:
Function<java.lang.CharSequence,java.lang.Long>, Object2LongFunction<java.lang.CharSequence>, PrefixMap<MutableString>, StringMap<MutableString>, java.io.Serializable

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.

See Also:
Serialized Form

Field Summary
 
Fields inherited from class it.unimi.dsi.util.AbstractPrefixMap
list, prefixMap, rangeMap
 
Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defRetValue
 
Constructor Summary
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
 boolean add(java.lang.CharSequence s)
           
 boolean containsKey(java.lang.Object o)
           
 Interval getApproximatedInterval(java.lang.CharSequence s)
           
protected  long getIndex(java.lang.CharSequence s)
           
protected  Interval getInterval(java.lang.CharSequence s)
          Returns the range of strings having a given prefix.
 long getLong(java.lang.Object o)
           
protected  MutableString getTerm(int index, MutableString s)
          Writes a string specified by index into a MutableString.
static void main(java.lang.String[] arg)
           
 int size()
           
 
Methods inherited from class it.unimi.dsi.util.AbstractPrefixMap
list, prefixMap, rangeMap
 
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
clear, defaultReturnValue, defaultReturnValue, get, put, put, remove, removeLong
 
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.objects.Object2LongFunction
defaultReturnValue, defaultReturnValue, put, removeLong
 
Methods inherited from interface it.unimi.dsi.fastutil.Function
clear, get, put, remove
 

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 Interval 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 Interval getApproximatedInterval(java.lang.CharSequence s)

getTerm

protected MutableString getTerm(int 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(java.lang.CharSequence s)

containsKey

public boolean containsKey(java.lang.Object o)
Specified by:
containsKey in interface Function<java.lang.CharSequence,java.lang.Long>

getLong

public long getLong(java.lang.Object o)
Specified by:
getLong in interface Object2LongFunction<java.lang.CharSequence>

add

public boolean add(java.lang.CharSequence s)

size

public int size()
Specified by:
size in interface Function<java.lang.CharSequence,java.lang.Long>

main

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