|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.fastutil.objects.AbstractObjectCollection<K>
it.unimi.dsi.fastutil.objects.AbstractObjectList<CharSequence>
it.unimi.dsi.mg4j.util.TernaryIntervalSearchTree
dsiutils
.
@Deprecated 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.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectList |
---|
AbstractObjectList.ObjectSubList<K> |
Constructor Summary | |
---|---|
TernaryIntervalSearchTree()
Deprecated. Creates a new empty ternary search tree. |
|
TernaryIntervalSearchTree(Collection<? extends CharSequence> c)
Deprecated. Creates a new empty ternary search tree and populates it with a given collection of character sequences. |
Method Summary | |
---|---|
boolean |
add(CharSequence s)
Deprecated. |
boolean |
contains(CharSequence s)
Deprecated. |
boolean |
contains(Object o)
Deprecated. |
CharSequence |
get(int index)
Deprecated. |
Interval |
getApproximatedInterval(CharSequence s)
Deprecated. Returns an approximated prefix interval around the specified word. |
int |
getIndex(CharSequence s)
Deprecated. |
Interval |
getInterval(CharSequence s)
Deprecated. Returns the interval of terms starting with the given prefix. |
int |
getNumber(CharSequence s)
Deprecated. Returns the ordinal number corresponding to the given term, or possibly (but not necessarily) -1 if the term was not indexed. |
CharSequence |
getPrefix(Interval interval)
Deprecated. Returns the maximum prefix common to all terms in the given nonempty interval (optional operation). |
MutableString |
getPrefix(Interval interval,
MutableString prefix)
Deprecated. Writes in the given mutable string the maximum prefix common to all terms in the given nonempty interval (optional operation). |
CharSequence |
getTerm(int index)
Deprecated. Returns the term corresponding to the given ordinal number (optional operation). |
MutableString |
getTerm(int index,
MutableString s)
Deprecated. Writes in the given mutable string the term corresponding to the given ordinal number (optional operation). |
boolean |
hasPrefixes()
Deprecated. Returns true if this prefix map supports prefix retrieval. |
boolean |
hasTerms()
Deprecated. Returns true if this prefix map supports term retrieval. |
static void |
main(String[] arg)
Deprecated. |
int |
size()
Deprecated. Returns the number of terms in this prefix map. |
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectList |
---|
add, addAll, addAll, addElements, addElements, compareTo, ensureIndex, ensureRestrictedIndex, equals, getElements, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, objectListIterator, objectListIterator, objectSubList, peek, pop, push, remove, removeElements, set, size, subList, top, toString |
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectCollection |
---|
clear, containsAll, isEmpty, objectIterator, remove, removeAll, retainAll, toArray, toArray |
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface java.util.List |
---|
clear, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray |
Methods inherited from interface it.unimi.dsi.fastutil.objects.ObjectCollection |
---|
objectIterator, toArray |
Methods inherited from interface it.unimi.dsi.fastutil.Stack |
---|
isEmpty |
Constructor Detail |
---|
public TernaryIntervalSearchTree()
public TernaryIntervalSearchTree(Collection<? extends CharSequence> c)
c
- a collection of character sequences.Method Detail |
---|
public Interval getInterval(CharSequence s)
PrefixMap
getInterval
in interface PrefixMap
s
- a prefix.
prefix
(Intervals.EMPTY_INTERVAL
in case no term starts with prefix
).public Interval getApproximatedInterval(CharSequence s)
ImmutableExternalPrefixDictionary.IntervalApproximator
getApproximatedInterval
in interface ImmutableExternalPrefixDictionary.IntervalApproximator
s
- a word.
word
public boolean contains(CharSequence s)
public boolean contains(Object o)
contains
in interface Collection<CharSequence>
contains
in interface List<CharSequence>
contains
in class AbstractObjectList<CharSequence>
public CharSequence getTerm(int index)
TermMap
getTerm
in interface TermMap
index
- a term ordinal number.
null
if the term was not indexed.public MutableString getTerm(int index, MutableString s)
TermMap
getTerm
in interface TermMap
index
- a term ordinal number.s
- a mutable string that will be filled with the corresponding term.
term
, or possibly (but not necessarily) null
if the term was not indexed.public CharSequence get(int index)
get
in interface List<CharSequence>
@Deprecated public int getIndex(CharSequence s)
public int getNumber(CharSequence s)
TermMap
We intentionally prefer “ordinal number” to “index” because of the obvious confusion that the latter term can cause.
getNumber
in interface TermMap
s
- a term.
public boolean add(CharSequence s)
add
in interface Collection<CharSequence>
add
in interface List<CharSequence>
add
in class AbstractObjectList<CharSequence>
public CharSequence getPrefix(Interval interval)
PrefixMap
getPrefix
in interface PrefixMap
interval
- an interval.
public MutableString getPrefix(Interval interval, MutableString prefix)
PrefixMap
getPrefix
in interface PrefixMap
interval
- an interval.prefix
- a mutable string that will be filled with the maximum prefix common to all terms in the given nonempty interval.
prefix
.public int size()
PrefixMap
size
in interface PrefixMap
size
in interface TermMap
size
in interface Collection<CharSequence>
size
in interface List<CharSequence>
public boolean hasPrefixes()
PrefixMap
hasPrefixes
in interface PrefixMap
public boolean hasTerms()
TermMap
hasTerms
in interface TermMap
public static void main(String[] arg) throws IOException, com.martiansoftware.jsap.JSAPException, NoSuchMethodException
IOException
com.martiansoftware.jsap.JSAPException
NoSuchMethodException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |