Package com.abstractkamen.datastructures.impl.trees.search

Class ReversePrefixTrie

java.lang.Object

com.abstractkamen.datastructures.impl.trees.search.PrefixTrieImpl

com.abstractkamen.datastructures.impl.trees.search.ReversePrefixTrie

All Implemented Interfaces:

PrefixTrie, SuffixTrie

public class ReversePrefixTrie
extends PrefixTrieImpl
implements SuffixTrie

This implementation uses the same insert/delete/search algorithm as the PrefixTrieImpl. In order to implement the SuffixTrie it reverses the input string. The cost of insert/delete/search is double that of the PrefixTrieImpl, but is still O(m) where m is the length of the input string.

Nested Class Summary

Nested classes/interfaces inherited from class com.abstractkamen.datastructures.impl.trees.search.PrefixTrieImpl

PrefixTrieImpl.PrefixTrieNode

Constructor Summary

Constructors

Constructor	Description
ReversePrefixTrie()

Method Summary

Modifier and Type	Method	Description
boolean	delete(String string)	Deletes a word from the trie.
Collection<String>	endsWith(String suffix, int limit)	Try to find strings which end with suffix.
boolean	insert(String string)	Inserts a word into the trie.
boolean	isPrefix(String prefix)	Checks if prefix is present in this trie.
boolean	isSuffix(String suffix)	Checks if suffix is present in this trie.
protected boolean	shouldDecrementWordOnDelete(PrefixTrieImpl.PrefixTrieNode n)	PrefixTrieImpl.completeWords decrementing condition.
Collection<String>	startsWith(String prefix, int limit)	Try to find strings which start with prefix.
String	toString()
protected void	visitWordNode(PrefixTrieImpl.PrefixTrieNode node, StringBuilder visitor, StringBuilder currentChars)	Visit a node which we know is a word.

Methods inherited from class com.abstractkamen.datastructures.impl.trees.search.PrefixTrieImpl

completeWords, contains, delete, getRoot, insert, prettyString, search, size

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.abstractkamen.datastructures.api.trees.search.PrefixTrie

completeWords, contains, prettyString, size

Constructor Details

ReversePrefixTrie

public ReversePrefixTrie()

Method Details

shouldDecrementWordOnDelete

protected boolean shouldDecrementWordOnDelete(PrefixTrieImpl.PrefixTrieNode n)

Description copied from class: PrefixTrieImpl

PrefixTrieImpl.completeWords decrementing condition. Can be overridden in extensions.

Overrides:

shouldDecrementWordOnDelete in class PrefixTrieImpl

Parameters:

n - word node

Returns:

true if PrefixTrieImpl.completeWords should be decremented

visitWordNode

protected void visitWordNode(PrefixTrieImpl.PrefixTrieNode node,
 StringBuilder visitor,
 StringBuilder currentChars)

Description copied from class: PrefixTrieImpl

Visit a node which we know is a word.

Overrides:

visitWordNode in class PrefixTrieImpl

Parameters:

node - word node

visitor - sb visitor

currentChars - word so far

insert

public boolean insert(String string)

Description copied from interface: PrefixTrie

Inserts a word into the trie. Duplicate words will be ignored.

Specified by:

insert in interface PrefixTrie

Overrides:

insert in class PrefixTrieImpl

Parameters:

string - word to be inserted

Returns:

true if the word was inserted false if it already existed

delete

public boolean delete(String string)

Description copied from interface: PrefixTrie

Deletes a word from the trie. The number of complete words will be decremented by one and the size of the trie will shrink by the number of unique characters and their placements in the deleted word if they aren't used by a different word.

Specified by:

delete in interface PrefixTrie

Overrides:

delete in class PrefixTrieImpl

Parameters:

string - to be deleted

Returns:

true if word is successfully deleted false if word was not in the trie

endsWith

public Collection<String> endsWith(String suffix,
 int limit)

Description copied from interface: SuffixTrie

Try to find strings which end with suffix. Matching strings are always in arbitrary order.

Specified by:

endsWith in interface SuffixTrie

Parameters:

suffix - to look for

limit - maximum number of found strings

Returns:

collection of words with the same suffix

isSuffix

public boolean isSuffix(String suffix)

Description copied from interface: SuffixTrie

Checks if suffix is present in this trie.

Specified by:

isSuffix in interface SuffixTrie

Parameters:

suffix - to check

Returns:

true if suffix exists

isPrefix

public boolean isPrefix(String prefix)

Description copied from interface: PrefixTrie

Checks if prefix is present in this trie.

Specified by:

isPrefix in interface PrefixTrie

Overrides:

isPrefix in class PrefixTrieImpl

Parameters:

prefix - to check

Returns:

true if prefix exists

startsWith

public Collection<String> startsWith(String prefix,
 int limit)

Description copied from interface: PrefixTrie

Try to find strings which start with prefix. Matching strings are always in lexicographical order.

Specified by:

startsWith in interface PrefixTrie

Overrides:

startsWith in class PrefixTrieImpl

Parameters:

prefix - to look for

limit - maximum number of found strings

Returns:

collection of words with the same prefix

toString

public String toString()

Overrides:

toString in class PrefixTrieImpl