|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<CharSequence>
it.unimi.dsi.big.util.AbstractPrefixMap
it.unimi.dsi.big.util.TernaryIntervalSearchTree
public class TernaryIntervalSearchTree
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.
Field Summary |
---|
Fields inherited from class it.unimi.dsi.big.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(Collection<? extends CharSequence> c)
Creates a new empty ternary search tree and populates it with a given collection of character sequences. |
Method Summary | |
---|---|
boolean |
add(CharSequence s)
|
boolean |
containsKey(Object o)
|
LongInterval |
getApproximatedInterval(CharSequence s)
|
protected long |
getIndex(CharSequence s)
|
protected LongInterval |
getInterval(CharSequence s)
Returns the range of strings having a given prefix. |
long |
getLong(Object o)
|
protected MutableString |
getTerm(long index,
MutableString s)
Writes a string specified by index into a MutableString . |
static void |
main(String[] arg)
|
int |
size()
Deprecated. |
long |
size64()
|
Methods inherited from class it.unimi.dsi.big.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 |
---|
public TernaryIntervalSearchTree()
public TernaryIntervalSearchTree(Collection<? extends CharSequence> c)
c
- a collection of character sequences.Method Detail |
---|
protected LongInterval getInterval(CharSequence s)
AbstractPrefixMap
getInterval
in class AbstractPrefixMap
s
- a prefix.
public LongInterval getApproximatedInterval(CharSequence s)
protected MutableString getTerm(long index, MutableString s)
AbstractPrefixMap
MutableString
.
getTerm
in class AbstractPrefixMap
index
- the index of a string.s
- a mutable string.
string
.protected long getIndex(CharSequence s)
public boolean containsKey(Object o)
containsKey
in interface Function<CharSequence,Long>
public long getLong(Object o)
getLong
in interface Object2LongFunction<CharSequence>
public boolean add(CharSequence s)
@Deprecated public int size()
size
in interface Function<CharSequence,Long>
size
in interface Size64
public long size64()
size64
in interface Size64
public static void main(String[] arg) throws IOException, JSAPException, NoSuchMethodException
IOException
JSAPException
NoSuchMethodException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |