import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/********************************************************************************
* @author Evan Bechtol (ecb120030)
* <h1>Project: Trie Structure</h1>
* <p>Program builds and implements a Trie to manipulate a dictionary and spell-checker.
* Identifies the total amount of words currently present, can also delete and search
* for specific words.</p>
* @since 2015-3-06
* @see https://community.oracle.com/thread/2070706
* @see en.wikipedia.org/wiki/Trie
* @see logos.cs.uic.edu/340/assignments/Solutions/Graphicalwordpopup/cvelazqu/WordPop2/
* @see http://crunchify.com/a-simple-singly-linked-list-implementation-in-java/
*
********************************************************************************/
/*
* Node class is the container class for the Trie. Each child index represents one of the 27 letters of the
* English alphabet. Only lower-case letters are used, digits are not considered. outDegree represents the
* number of children that are initialized for that node.
*/
class Node {
private boolean terminal; //Designates character as end of word
private int outDegree; //Specifies character position in the word
private Node [] children; //Holds references to 26 potential character children
/*
* Constructor for root node
*/
Node () {
terminal = false;
outDegree = 0;
children = new Node[26];
// All children are set to null initially, they are populated as needed
for (int i = 0; i < 26; i++) {
children[i] = null;
}
}
/*
* Set the terminal value
*/
public void setTerminal (boolean terminal) {
this.terminal = terminal;
}
/*
* Set the outDegree of node
*/
public void setOutDegree (int outDegree) {
this.outDegree = outDegree;
}
/*
* If the node is not null, it returns that node
* else null is returned
*/
public Node getChild (char c) {
return children [c - 'a'];
}
/*
* Returns the outDegree of the current node
*/
public int getOutDegree () {
return outDegree;
}
/*
* Return the status of terminal variable.
* True = node is end of word
* False = not end of word
*/
public boolean getTerminal () {
return terminal;
}
/*
* Attempts to insert a word into the list
*/
public boolean insert (String word) {
char character = word.charAt(0);
int index = character - 'a';
if (!childExists(index)) {
children[index] = new Node ();
this.setOutDegree(++outDegree);
}
if (word.length() > 1) {
getChild(character).insert(word.substring(1));
}
else {
getChild(character).setTerminal(true);
return true;
}
return true;
}
/*
* Recursively traverse down the Trie until we reach the last character of the word
* and it's corresponding Node in the tree.
*/
public boolean delete (String word) {
char character = word.charAt(0);
int index = character - 'a';
if (!childExists(index)) {
return false;
}
// The last character in the word does not have children
if (getChild(character).getTerminal() && getChild(character).getOutDegree() == 0) {
this.children[index] = null;
this.setOutDegree(--outDegree);
return true;
}
// If there are more characters in the word, we keep traversing
if (word.length() > 1) {
getChild(character).delete(word.substring(1));
}
// There are no more letters in the word and it has children
else {
getChild(character).setTerminal(false);
}
return true;
}
/*
* Determines if the word is currently in the Trie
*/
public boolean isPresent (String word) {
char character = word.charAt(0);
int index = character - 'a';
// If the child does not exist, return false
if (!childExists(index)) {
return false;
}
if (childExists(index) && word.length() > 1) {
return getChild(character).isPresent(word.substring(1));
}
// We reach the end of the word
else if (getChild(character).getTerminal() && word.length() == 1) {
return true;
}
return false;
}
/*
* Determines whether a node is populated or not
* Returns true if it exists, false otherwise
*/
public boolean childExists (int index) {
return this.children[index] != null;
}
} // End Node
/*
* The Trie class is responsible for storing and manipulating the Trie structure. It utilizes the Node container class
* to carry out specific functions; insertion/deletion/searching
*/
class Trie {
private final Node root;
private int words; // Maintains number of words in the Trie
/*
* Default constructor for Trie
*/
Trie () {
root = new Node();
words = 0;
}
/*
* Returns the root of the Trie
*/
public Node getRoot () {
if (isEmpty()) {
return null;
}
return root;
}
/*
* Set the number of words in the Trie
*/
public void setWords (int numWords) {
this.words = numWords;
}
/*
* Returns number of words in the Trie
*/
public int membership () {
return words;
}
/*
* Returns false if word is already present, true otherwise
*/
public boolean insert (String word) {
if(!root.isPresent(word) && root.insert(word.toLowerCase())) {
this. setWords(++words);
return true;
}
return false;
}
/*
* Returns true if present, false otherwise
*/
public boolean isPresent (String word) {
return root.isPresent(word);
}
/*
* If word is present recursive delete is called,
* else the word is not present for deletion
*/
public boolean delete (String word) {
if (root.isPresent(word) && root.delete(word.toLowerCase())) {
this.setWords(--words);
return true;
}
return false;
}
/*
* Returns true if the Trie is completely empty
*/
public boolean isEmpty () {
return root == null;
}
/*
* Recursively iterates through all nodes and all children to print words
* that are present in the Trie
*/
public void listAll(Node current, String word) {
if (current.getTerminal() && current.getOutDegree() >= 1) {
System.out.println(word);
}
if(current.getTerminal() && current.getOutDegree() == 0){
System.out.println(word);
}
// Our child is not a word yet, we iterate though again
else {
// Iterate through all potential letters, looking for the next child
for(int i = 0; i < 26; ++i) {
if(!current.childExists(i)) {
continue;
}
// Our child exists and we recursively call listAll to get the word to print
// cast it as a char to get the character representation of the index value
else {
listAll(current.getChild((char)(i + 'a')), word + (char)(i + 'a'));
}
}
}
}
/*
* Identifies potential spelling errors in the word
*/
public void spellCheck (String word) {
if (!root.isPresent(word)) {
System.out.println ("Spelling mistake " + word);
}
}
} // End Trie
Trie Class
/*
* The Trie class is responsible for storing and manipulating the Trie structure. It utilizes the Node container class
* to carry out specific functions; insertion/deletion/searching
*/
class Trie {
private final Node root;
private int words; // Maintains number of words in the Trie
/*
* Default constructor for Trie
*/
Trie () {
root = new Node();
words = 0;
}
/*
* Returns the root of the Trie
*/
public Node getRoot () {
if (isEmpty()) {
return null;
}
return root;
}
/*
* Set the number of words in the Trie
*/
public void setWords (int numWords) {
this.words = numWords;
}
/*
* Returns number of words in the Trie
*/
public int membership () {
return words;
}
/*
* Returns false if word is already present, true otherwise
*/
public boolean insert (String word) {
if(!root.isPresent(word) && root.insert(word.toLowerCase())) {
this. setWords(++words);
return true;
}
return false;
}
/*
* Returns true if present, false otherwise
*/
public boolean isPresent (String word) {
return root.isPresent(word);
}
/*
* If word is present recursive delete is called,
* else the word is not present for deletion
*/
public boolean delete (String word) {
if (root.isPresent(word) && root.delete(word.toLowerCase())) {
this.setWords(--words);
return true;
}
return false;
}
/*
* Returns true if the Trie is completely empty
*/
public boolean isEmpty () {
return root == null;
}
/*
* Recursively iterates through all nodes and all children to print words
* that are present in the Trie
*/
public void listAll(Node current, String word) {
if (current.getTerminal() && current.getOutDegree() >= 1) {
System.out.println(word);
}
if(current.getTerminal() && current.getOutDegree() == 0){
System.out.println(word);
}
// Our child is not a word yet, we iterate though again
else {
// Iterate through all potential letters, looking for the next child
for(int i = 0; i < 26; ++i) {
if(!current.childExists(i)) {
continue;
}
// Our child exists and we recursively call listAll to get the word to print
// cast it as a char to get the character representation of the index value
else {
listAll(current.getChild((char)(i + 'a')), word + (char)(i + 'a'));
}
}
}
}
/*
* Identifies potential spelling errors in the word
*/
public void spellCheck (String word) {
if (!root.isPresent(word)) {
System.out.println ("Spelling mistake " + word);
}
}
} // End Trie
Test client
