it.unimi.dsi.util
Class TernaryIntervalSearchTree
java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<java.lang.CharSequence>
it.unimi.dsi.util.AbstractPrefixMap
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
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. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
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.
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