I found a java implementation of a trie and would like to have a similar one in J2ME. Here is the code.
Node class
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
class Node {
private final char ch;
/**
* Flag indicates that this node is the end of the string.
*/
private boolean end;
private LinkedList<Node> children;
public Node(char ch) {
this.ch = ch;
}
public void addChild(Node node) {
if (children == null) {
children = new LinkedList<Node>();
}
children.add(node);
}
public Node getNode(char ch) {
if (children == null) {
return null;
}
for (Node child : children) {
if (child.getChar() == ch) {
return child;
}
}
return null;
}
public char getChar() {
return ch;
}
public List<Node> getChildren() {
if (this.children == null) {
return Collections.emptyList();
}
return children;
}
public boolean isEnd() {
return end;
}
public void setEnd(boolean end) {
this.end = end;
}
}
TrieNode Class
import java.io.File;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class WordTree {
Node root = new Node(' ');
public WordTree() {
}
/**
* Searches for a strings that match the prefix.
*
* @param prefix - prefix
* @return - list of strings that match the prefix, or empty list of no matches are found.
*/
public List<String> getWordsForPrefix(String prefix) {
if (prefix.length() == 0) {
return Collections.emptyList();
}
Node node = getNodeForPrefix(root, prefix);
if (node == null) {
return Collections.emptyList();
}
List<LinkedList<Character>> chars = collectChars(node);
List<String> words = new ArrayList<String>(chars.size());
for (LinkedList<Character> charList : chars) {
words.add(combine(prefix.substring(0, prefix.length() - 1), charList));
}
return words;
}
private String combine(String prefix, List<Character> charList) {
StringBuilder sb = new StringBuilder(prefix);
for (Character character : charList) {
sb.append(character);
}
return sb.toString();
}
private Node getNodeForPrefix(Node node, String prefix) {
if (prefix.length() == 0) {
return node;
}
Node next = node.getNode(prefix.charAt(0));
if (next == null) {
return null;
}
return getNodeForPrefix(next, prefix.substring(1, prefix.length()));
}
private List<LinkedList<Character>> collectChars(Node node) {
List<LinkedList<Character>> chars = new ArrayList<LinkedList<Character>>();
if (node.getChildren().size() == 0) {
chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar())));
} else {
if (node.isEnd()) {
chars.add(new LinkedList<Character> (Collections.singletonList(node.getChar())));
}
List<Node> children = node.getChildren();
for (Node child : children) {
List<LinkedList<Character>> childList = collectChars(child);
for (LinkedList<Character> characters : childList) {
characters.push(node.getChar());
chars.add(characters);
}
}
}
return chars;
}
public void addWord(String word) {
addWord(root, word);
}
private void addWord(Node parent, String word) {
if (word.trim().length() == 0) {
return;
}
Node child = parent.getNode(word.charAt(0));
if (child == null) {
child = new Node(word.charAt(0));
parent.addChild(child);
}
if (word.length() == 1) {
child.setEnd(true);
} else {
addWord(child, word.substring(1, word.length()));
}
}
public void load() {
WordTree tree = new WordTree();
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(new File("C:/Users/Sironka/Documents/NetBeansProjects/Final Maa Adaptive System/dictionary/Maa Corpus.txt-02-ngrams-Freq.txt")));
String eachLine = null;
while ((eachLine = br.readLine()) != null) {
tree.addWord(eachLine);
}
} catch (Exception e) {
e.printStackTrace();
} finally {
if (br != null) {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
System.out.println(tree.getWordsForPrefix("ore"));
}
public static void main(String[] args) {
WordTree trieloader = new WordTree();
trieloader.load();
System.out.println("");
}
}
Here are the challenges:
1. Changing the for loop format
2. Classes like linkedList, Collections are not available in j2me
Request: 1. converting the above to j2me. (A similar j2me implementation will help).
Please assist me in this since i am completely stuck in my project. The trie will assist me in text prediction (t9).
