SuffixTrie.java

packagecom.jwetherell.algorithms.data_structures;

importjava.util.Set;
importjava.util.TreeSet;

importcom.jwetherell.algorithms.data_structures.Trie.Node;
importcom.jwetherell.algorithms.data_structures.interfaces.ISuffixTree;

/**
 * A suffix trie is a data structure that presents the suffixes of a given
 * string in a way that allows for a particularly fast implementation of many
 * important string operations.
 * <p>
 * This implementation is based upon a Trie which is NOT a compact trie.
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Suffix_trie">Suffix Trie (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
@SuppressWarnings("unchecked")
publicclassSuffixTrie<CextendsCharSequence> implementsISuffixTree<C> {

privateTrie<C> tree;

/**
 * Create a suffix trie from sequence
 * 
 * @param sequence
 * to create a suffix trie from.
 */
publicSuffixTrie(Csequence) {
tree = newTrie<C>();
intlength = sequence.length();
for (inti = 0; i < length; i++) {
CharSequenceseq = sequence.subSequence(i, length);
tree.add((C) seq);
 }
 }

/**
 * Add character sequence to the suffix trie.
 * 
 * @param sequence
 * to add to trie.
 * @return True if added successfully.
 */
publicbooleanadd(Csequence) {
intlength = sequence.length();
for (inti = 0; i < length; i++) {
CharSequenceseq = sequence.subSequence(i, length);
tree.add((C) seq);
 }
returntrue;
 }

/**
 * Does the sequence exists in the trie.
 * 
 * @param sequence
 * to locate in the trie.
 * @return True if sequence exists in trie.
 */
@Override
publicbooleandoesSubStringExist(Csequence) {
char[] chars = sequence.toString().toCharArray();
intlength = chars.length;
Trie.Nodecurrent = tree.root;
for (inti = 0; i < length; i++) {
intidx = current.childIndex(chars[i]);
if (idx < 0)
returnfalse;
current = current.getChild(idx);
 }
returntrue;
 }

/**
 * Get all suffixes in the trie.
 * 
 * @return set of suffixes in trie.
 */
@Override
publicSet<String> getSuffixes() {
returnthis.getSuffixes(tree.root);
 }

/**
 * Get all suffixes at node.
 * 
 * @param node
 * to get all suffixes at.
 * @return set of suffixes in trie at node.
 */
privateSet<String> getSuffixes(Trie.Nodenode) {
StringBuilderbuilder = newStringBuilder();
if (node.character != Node.SENTINAL) builder.append(node.character);
Set<String> set = newTreeSet<String>();
if (node.isWord) {
set.add(builder.toString());
 }
for (inti = 0; i < node.getChildrenSize(); i++) {
Trie.Nodec = node.getChild(i);
set.addAll(getSuffixes(c, builder.toString()));
 }
returnset;
 }

/**
 * Get all suffixes at node and prepend the prefix.
 * 
 * @param node
 * to get all suffixes from.
 * @param prefix
 * to prepend to suffixes.
 * @return set of suffixes in trie at node.
 */
privateSet<String> getSuffixes(Trie.Nodenode, Stringprefix) {
StringBuilderbuilder = newStringBuilder(prefix);
if (node.character != Node.SENTINAL) builder.append(node.character);
Set<String> set = newTreeSet<String>();
if (node.isWord) {
set.add(builder.toString());
 }
for (inti = 0; i < node.getChildrenSize(); i++) {
Trie.Nodec = node.getChild(i);
set.addAll(getSuffixes(c, builder.toString()));
 }
returnset;
 }

/**
 * {@inheritDoc}
 */
@Override
publicStringtoString() {
returnTrie.TriePrinter.getString(tree);
 }
}