wwwordz.puzzle

Class Trie

java.lang.Object

wwwordz.puzzle.Trie

All Implemented Interfaces:

java.lang.Iterable<java.lang.String>

public class Trie
extends java.lang.Object
implements java.lang.Iterable<java.lang.String>

A trie is data structure to store words efficiently using a tree. Each tree node represents prefix that may be a a complete word. The descendants of a node are indexed by a letter, representing a possible continuation of that prefix followed by that letter.

Author:

José Paulo Leal

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	Trie.NodeIterator Iterator over strings stored in the internal node structure It traverses the node tree depth first, using coroutine with threads, and collects all possible words in no particular order.
static class	Trie.Search A position in the node structure when looking for a word.

Constructor Summary

Constructors

Constructor and Description
Trie()

Method Summary

Modifier and Type	Method and Description
java.lang.String	getRandomLargeWord() Performs a random walk in the data structure, randomly selecting a path in each node, until reaching a leaf (a node with no descendants).
java.util.Iterator<java.lang.String>	iterator() Returns an iterator over the strings stored in the trie
void	put(java.lang.String word) Insert a word in the structure, starting from the root.
Trie.Search	startSearch() Start a word search from the root.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

Trie

public Trie()

Method Detail

put

public void put(java.lang.String word)

Insert a word in the structure, starting from the root. Suggestion: call a recursive method on the root node.

Parameters:

word - to be inserted

startSearch

public Trie.Search startSearch()

Start a word search from the root.

Returns:

Trie.Search instance

getRandomLargeWord

public java.lang.String getRandomLargeWord()

Performs a random walk in the data structure, randomly selecting a path in each node, until reaching a leaf (a node with no descendants).

Suggestion: Use a StringBuffer to pass it recursively to a Node method to collect the word's characters

Returns:

word as a String

iterator

public java.util.Iterator<java.lang.String> iterator()

Returns an iterator over the strings stored in the trie

Specified by:

iterator in interface java.lang.Iterable<java.lang.String>