public boolean endOfWord = false;

public String letters;

public TrieNode[] ptrs = new TrieNode[1];

public TrieNonLeaf() {

isLeaf = false;

}

public TrieNonLeaf(char ch) {

letters = new String();

letters += ch;

isLeaf = false;

}

public String suffix;

public TrieLeaf() {

isLeaf = true;

}

public TrieLeaf(String suffix) {

this.suffix = new String(suffix);

isLeaf = true;

}

private TrieNonLeaf root;

private 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 printTrie() {

printTrie(0,root,new String()); // assumption: the root is not null;

}

private void printTrie(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);

printTrie(depth+1,((TrieNonLeaf)p).ptrs[i],prefix);

}

else { // if leaf is null;

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));

}

}

}

private 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;

}

private 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);

}

private 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++;

}

}

}