it.unimi.dsi.mg4j.util
Class TernaryIntervalSearchTree

java.lang.Object
  extended by it.unimi.dsi.fastutil.objects.AbstractObjectCollection<K>
      extended by it.unimi.dsi.fastutil.objects.AbstractObjectList<CharSequence>
          extended by it.unimi.dsi.mg4j.util.TernaryIntervalSearchTree
All Implemented Interfaces:
ObjectCollection<CharSequence>, ObjectIterable<CharSequence>, ObjectList<CharSequence>, Stack<CharSequence>, PrefixMap, TermMap, ImmutableExternalPrefixDictionary.IntervalApproximator, Serializable, Comparable<List<? extends CharSequence>>, Iterable<CharSequence>, Collection<CharSequence>, List<CharSequence>

Deprecated. Moved to dsiutils.

@Deprecated
public class TernaryIntervalSearchTree
extends AbstractObjectList<CharSequence>
implements PrefixMap, TermMap, ImmutableExternalPrefixDictionary.IntervalApproximator, 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

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

TernaryIntervalSearchTree

public TernaryIntervalSearchTree()
Deprecated. 
Creates a new empty ternary search tree.


TernaryIntervalSearchTree

public TernaryIntervalSearchTree(Collection<? extends CharSequence> c)
Deprecated. 
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

public Interval getInterval(CharSequence s)
Deprecated. 
Description copied from interface: PrefixMap
Returns the interval of terms starting with the given prefix.

Specified by:
getInterval in interface PrefixMap
Parameters:
s - a prefix.
Returns:
the interval of terms starting with prefix (Intervals.EMPTY_INTERVAL in case no term starts with prefix).

getApproximatedInterval

public Interval getApproximatedInterval(CharSequence s)
Deprecated. 
Description copied from interface: ImmutableExternalPrefixDictionary.IntervalApproximator
Returns an approximated prefix interval around the specified word.

Specified by:
getApproximatedInterval in interface ImmutableExternalPrefixDictionary.IntervalApproximator
Parameters:
s - a word.
Returns:
an approximated prefix interval for word

contains

public boolean contains(CharSequence s)
Deprecated. 

contains

public boolean contains(Object o)
Deprecated. 
Specified by:
contains in interface Collection<CharSequence>
Specified by:
contains in interface List<CharSequence>
Overrides:
contains in class AbstractObjectList<CharSequence>

getTerm

public CharSequence getTerm(int index)
Deprecated. 
Description copied from interface: TermMap
Returns the term corresponding to the given ordinal number (optional operation).

Specified by:
getTerm in interface TermMap
Parameters:
index - a term ordinal number.
Returns:
the corresponding term, or possibly (but not necessarily) null if the term was not indexed.

getTerm

public MutableString getTerm(int index,
                             MutableString s)
Deprecated. 
Description copied from interface: TermMap
Writes in the given mutable string the term corresponding to the given ordinal number (optional operation).

Specified by:
getTerm in interface TermMap
Parameters:
index - a term ordinal number.
s - a mutable string that will be filled with the corresponding term.
Returns:
term, or possibly (but not necessarily) null if the term was not indexed.

get

public CharSequence get(int index)
Deprecated. 
Specified by:
get in interface List<CharSequence>

getIndex

@Deprecated
public int getIndex(CharSequence s)
Deprecated. 


getNumber

public int getNumber(CharSequence s)
Deprecated. 
Description copied from interface: TermMap
Returns the ordinal number corresponding to the given term, or possibly (but not necessarily) -1 if the term was not indexed.

We intentionally prefer “ordinal number” to “index” because of the obvious confusion that the latter term can cause.

Specified by:
getNumber in interface TermMap
Parameters:
s - a term.
Returns:
its ordinal number, or possibly (but not necessarily) -1 if the term was not indexed.

add

public boolean add(CharSequence s)
Deprecated. 
Specified by:
add in interface Collection<CharSequence>
Specified by:
add in interface List<CharSequence>
Overrides:
add in class AbstractObjectList<CharSequence>

getPrefix

public CharSequence getPrefix(Interval interval)
Deprecated. 
Description copied from interface: PrefixMap
Returns the maximum prefix common to all terms in the given nonempty interval (optional operation).

Specified by:
getPrefix in interface PrefixMap
Parameters:
interval - an interval.
Returns:
the maximum prefix common to all terms in the given nonempty interval.

getPrefix

public MutableString getPrefix(Interval interval,
                               MutableString prefix)
Deprecated. 
Description copied from interface: PrefixMap
Writes in the given mutable string the maximum prefix common to all terms in the given nonempty interval (optional operation).

Specified by:
getPrefix in interface PrefixMap
Parameters:
interval - an interval.
prefix - a mutable string that will be filled with the maximum prefix common to all terms in the given nonempty interval.
Returns:
prefix.

size

public int size()
Deprecated. 
Description copied from interface: PrefixMap
Returns the number of terms in this prefix map.

Specified by:
size in interface PrefixMap
Specified by:
size in interface TermMap
Specified by:
size in interface Collection<CharSequence>
Specified by:
size in interface List<CharSequence>
Returns:
the number of terms in this prefix map.

hasPrefixes

public boolean hasPrefixes()
Deprecated. 
Description copied from interface: PrefixMap
Returns true if this prefix map supports prefix retrieval.

Specified by:
hasPrefixes in interface PrefixMap
Returns:
true if this prefix map supports prefix retrieval.

hasTerms

public boolean hasTerms()
Deprecated. 
Description copied from interface: TermMap
Returns true if this prefix map supports term retrieval.

Specified by:
hasTerms in interface TermMap
Returns:
true if this prefix map supports term retrieval.

main

public static void main(String[] arg)
                 throws IOException,
                        com.martiansoftware.jsap.JSAPException,
                        NoSuchMethodException
Deprecated. 
Throws:
IOException
com.martiansoftware.jsap.JSAPException
NoSuchMethodException