Class TernaryIntervalSearchTree
- java.lang.Object
-
- it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<java.lang.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<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.big.util.AbstractPrefixMap
list, prefixMap, rangeMap
-
-
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 aMutableString
.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.big.util.AbstractPrefixMap
list, prefixMap, rangeMap
-
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.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 classAbstractPrefixMap
- Parameters:
s
- a prefix.- Returns:
- the corresponding range of strings as an interval.
-
getApproximatedInterval
public LongInterval getApproximatedInterval(java.lang.CharSequence s)
-
getTerm
protected MutableString getTerm(long index, MutableString s)
Description copied from class:AbstractPrefixMap
Writes a string specified by index into aMutableString
.- Specified by:
getTerm
in classAbstractPrefixMap
- 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 interfaceit.unimi.dsi.fastutil.Function<java.lang.CharSequence,java.lang.Long>
-
getLong
public long getLong(java.lang.Object o)
- Specified by:
getLong
in interfaceit.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 interfaceit.unimi.dsi.fastutil.Function<java.lang.CharSequence,java.lang.Long>
- Specified by:
size
in interfaceit.unimi.dsi.fastutil.Size64
- Specified by:
size
in interfaceStringMap<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 interfaceit.unimi.dsi.fastutil.Size64
- Specified by:
size64
in interfaceStringMap<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
-
-