<![CDATA[/************************ Trie.java *******************************
*
*/
class TrieNode {
boolean isLeaf;
}
class TrieNonLeaf extends TrieNode {
boolean endOfWord = false;
String letters;
TrieNode[] ptrs = new TrieNode[1];
TrieNonLeaf() {
isLeaf = false;
}
TrieNonLeaf(char ch) {
letters = new String();
letters += ch;
isLeaf = false;
}
}
class TrieLeaf extends TrieNode {
String suffix;
TrieLeaf() {
isLeaf = true;
}
TrieLeaf(String suffix) {
this.suffix = new String(suffix);
isLeaf = true;
}
}
class Trie {
protected TrieNonLeaf root;
protected final int notFound = -1;
public Trie() {
}
public Trie(String word) {
root = new TrieNonLeaf(word.charAt(0)); // initialize the root
createLeaf(word.charAt(0),word.substring(1),root); // to avoid later
} // test;
public void sideView() {
sideView(0,root,new String()); // assumption: the root is not null;
}
protected void sideView(int depth, TrieNode p, String prefix) {
if (p.isLeaf) {
for (int j = 1; j <= depth; j++)
System.out.print(" ");
System.out.println(" >" + prefix + "|" + ((TrieLeaf)p).suffix);
}
else {
for (int i = ((TrieNonLeaf)p).letters.length()-1; i >= 0; i--) {
if (((TrieNonLeaf)p).ptrs[i] != null) {
// add the letter corresponding to position i to prefix;
prefix = prefix.substring(0,depth) +
((TrieNonLeaf)p).letters.charAt(i);
sideView(depth+1,((TrieNonLeaf)p).ptrs[i],prefix);
}
else { // if empty leaf;
for (int j = 1; j <= depth+1; j++)
System.out.print(" ");
System.out.println(">>" + prefix.substring(0,depth) +
((TrieNonLeaf)p).letters.charAt(i) + "|");
}
}
if (((TrieNonLeaf)p).endOfWord) {
for (int j = 1; j <= depth+1; j++)
System.out.print(" ");
System.out.println(">>" + prefix.substring(0,depth) + "||");
}
}
}
protected int position(TrieNonLeaf p, char ch) {
int i = 0;
for ( ; i < p.letters.length() && p.letters.charAt(i) != ch; i++);
if (i < p.letters.length())
return i;
else return notFound;
}
public boolean found(String word) {
TrieNode p = root;
int pos, i = 0;
while (true)
if (p.isLeaf) { // node p is a leaf
TrieLeaf lf = (TrieLeaf) p; // where the matching
if (word.substring(i).equals(lf.suffix)) // suffix of
return true; // word should be found;
else return false;
}
else if ((pos = position((TrieNonLeaf)p,word.charAt(i))) != notFound
&& i+1 == word.length()) // the end of word has to
if (((TrieNonLeaf)p).ptrs[pos] == null) // correspond
return true; // with an empty leaf
else if(!(((TrieNonLeaf)p).ptrs[pos]).isLeaf &&
((TrieNonLeaf)((TrieNonLeaf)p).ptrs[pos]).endOfWord)
return true; // or the endOfWord marker on;
else return false;
else if (pos != notFound && ((TrieNonLeaf)p).ptrs[pos] != null) {
p = ((TrieNonLeaf)p).ptrs[pos];// continue path,
i++; // if possible,
}
else return false; // otherwise failure;
}
protected void addCell(char ch, TrieNonLeaf p, int stop) {
int i;
int len = p.letters.length();
char[] s = new char[len+1];
TrieNode[] tmp = p.ptrs;
p.ptrs = new TrieNode[len+1];
for (i = 0; i < len+1; i++)
p.ptrs[i] = null;
if (stop < len) // if ch does not follow all letters in p,
for (i = len; i >= stop+1; i--) { // copy from tmp letters > ch;
p.ptrs[i] = tmp[i-1];
s[i] = p.letters.charAt(i-1);
}
s[stop] = ch;
for (i = stop-1; i >= 0; i--) { // and letters < ch;
p.ptrs[i] = tmp[i];
s[i] = p.letters.charAt(i);
}
p.letters = new String(s);
}
protected void createLeaf(char ch, String suffix, TrieNonLeaf p) {
int pos = position(p,ch);
TrieLeaf lf = null;
if (suffix != null && suffix.length() > 0) // don't create any leaf
lf = new TrieLeaf(suffix); // if there is no suffix;
if (pos == notFound) {
for (pos = 0; pos < p.letters.length() &&
p.letters.charAt(pos) < ch; pos++);
addCell(ch,p,pos);
}
p.ptrs[pos] = lf;
}
public void insert(String word) {
TrieNonLeaf p = root;
TrieLeaf lf;
int offset, pos, i = 0;
while (true) {
if (i == word.length()) { // if the end of word reached,
if (p.endOfWord)
System.out.println("duplicate entry1: " + word);
p.endOfWord = true; // set endOfWord to true;
return;
} // if position in p indicated
pos = position(p,word.charAt(i));
if (pos == notFound) { // by the first letter of word
createLeaf(word.charAt(i),word.substring(i+1),p);
// does not exist, create
return; // a leaf and store in it the
} // unprocessed suffix of word;
else if (pos != notFound && // empty leaf in position pos;
p.ptrs[pos] == null) {
if (i+1 == word.length()) {
System.out.println("duplicate entry2: " + word);
return;
}
p.ptrs[pos] = new TrieNonLeaf(word.charAt(i+1));
((TrieNonLeaf)(p.ptrs[pos])).endOfWord = true;
// check whether there is any suffix left:
String s = (word.length() > i+2) ? word.substring(i+2) : null;
createLeaf(word.charAt(i+1),s,(TrieNonLeaf)(p.ptrs[pos]));
return;
}
else if (pos != notFound && // if position pos is
p.ptrs[pos].isLeaf) { // occupied by a leaf,
lf = (TrieLeaf) p.ptrs[pos]; // hold this leaf;
if (lf.suffix.equals(word.substring(i+1))) {
System.out.println("duplicate entry3: " + word);
return;
}
offset = 0;
// create as many non-leaves as the length of identical
// prefix of word and the string in the leaf (for cell 'R',
// leaf "EP", and word "REAR", two such nodes are created);
do {
pos = position(p,word.charAt(i+offset));
// word = "ABC", leaf = "ABCDEF" => leaf = "DEF";
if (word.length() == i+offset+1) {
p.ptrs[pos] = new TrieNonLeaf(lf.suffix.charAt(offset));
p = (TrieNonLeaf) p.ptrs[pos];
p.endOfWord = true;
createLeaf(lf.suffix.charAt(offset),
lf.suffix.substring(offset+1),p);
return;
}
// word = "ABCDEF", leaf = "ABC" => leaf = "DEF";
else if (lf.suffix.length() == offset ) {
p.ptrs[pos] = new TrieNonLeaf(word.charAt(i+offset+1));
p = (TrieNonLeaf) p.ptrs[pos];
p.endOfWord = true;
createLeaf(word.charAt(i+offset+1),
word.substring(i+offset+2),p);
return;
}
p.ptrs[pos] = new TrieNonLeaf(word.charAt(i+offset+1));
p = (TrieNonLeaf) p.ptrs[pos];
offset++;
} while (word.charAt(i+offset) == lf.suffix.charAt(offset-1));
offset--;
// word = "ABCDEF", leaf = "ABCPQR" =>
// leaf('D') = "EF", leaf('P') = "QR";
// check whether there is any suffix left:
// word = "ABCD", leaf = "ABCPQR" =>
// leaf('D') = null, leaf('P') = "QR";
String s = null;
if (word.length() > i+offset+2)
s = word.substring(i+offset+2);
createLeaf(word.charAt(i+offset+1),s,p);
// check whether there is any suffix left:
// word = "ABCDEF", leaf = "ABCP" =>
// leaf('D') = "EF", leaf('P') = null;
if (lf.suffix.length() > offset+1)
s = lf.suffix.substring(offset+1);
else s = null;
createLeaf(lf.suffix.charAt(offset),s,p);
return;
}
else {
p = (TrieNonLeaf) p.ptrs[pos];
i++;
}
}
}
}
]]>