net.sourceforge.suggesttree
Class SuggestTree

java.lang.Object
  net.sourceforge.suggesttree.SuggestTree

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<SuggestTree.Entry>

public final class SuggestTree
extends java.lang.Object
implements java.lang.Iterable<SuggestTree.Entry>, java.io.Serializable

A data structure for rank-sensitive autocompletion. It stores suggestions, each with an associated score, and provides fast access to the highest scored completions for a given prefix. Note that suggest trees are not appropriate for rankings based on the lexicographic order of the suggestions.

This implementation is not synchronized. If multiple threads access the tree concurrently, and at least one of the threads modifies the tree (by inserting/removing a suggestion or by changing the score of a suggestion), it must be synchronized externally.

See Also:

Serialized Form

Nested Class Summary

static interface

SuggestTree.Entry A suggest tree entry (a suggestion and its score).

Constructor Summary

SuggestTree()
Creates a new, empty suggest tree.

Method Summary

void	clear() Removes all suggestions from the tree.
SuggestTree.Entry	entry(java.lang.String suggestion) Returns the entry for the specified suggestion, or null if the tree does not contain this suggestion.
java.util.Iterator<SuggestTree.Entry>	iterator() Returns an iterator over the entries in the tree.
void	put(java.lang.String suggestion, int score) Inserts the specified suggestion with the specified score into the tree, or updates the score if the tree already contains this suggestion.
void	remove(java.lang.String suggestion) Removes the specified suggestion from the tree if present.
int	size() Returns the number of suggestions in the tree.
java.util.Iterator<SuggestTree.Entry>	suggestions(java.lang.String prefix, int topK) Returns an iterator over the topK highest scored entries in the tree that start with the specified prefix.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SuggestTree

public SuggestTree()

Creates a new, empty suggest tree.

Method Detail

size

public int size()

Returns the number of suggestions in the tree.

Returns:

the number of suggestions in the tree

clear

public void clear()

Removes all suggestions from the tree.

suggestions

public java.util.Iterator<SuggestTree.Entry> suggestions(java.lang.String prefix,
                                                         int topK)

Returns an iterator over the topK highest scored entries in the tree that start with the specified prefix. The iterator will return the entries in descending order of score.

If the tree is modified while an iteration is in progress, the results of the iteration are undefined.

Parameters:

prefix - the string to be completed

topK - the maximum number of entries to be returned by the iterator

Returns:

an iterator over the topK highest scored entries in the tree that start with the specified prefix

Throws:

java.lang.IllegalArgumentException - if topK is less than 1

entry

public SuggestTree.Entry entry(java.lang.String suggestion)

Returns the entry for the specified suggestion, or null if the tree does not contain this suggestion.

Parameters:

suggestion - the suggestion whose entry is to be returned

Returns:

the entry for the specified suggestion, or null if the tree does not contain this suggestion

put

public void put(java.lang.String suggestion,
                int score)

Inserts the specified suggestion with the specified score into the tree, or updates the score if the tree already contains this suggestion.

Parameters:

suggestion - the suggestion to be inserted or newly weighted

score - the score to be associated with the suggestion

Throws:

java.lang.IllegalArgumentException - if suggestion is the empty string

remove

public void remove(java.lang.String suggestion)

Removes the specified suggestion from the tree if present.

Parameters:

suggestion - the suggestion to be removed from the tree

iterator

public java.util.Iterator<SuggestTree.Entry> iterator()

Returns an iterator over the entries in the tree. The iterator will return the entries in lexicographic order.

Specified by:

iterator in interface java.lang.Iterable<SuggestTree.Entry>

Returns:

an iterator over the entries in the tree