Java Programming

Hello all,

I am fairly new to java and am trying to create a Patricia Trie of strings.
I have got some classes to make the tree and it's nodes but I get a compiler error trying to insert some nodes in the tree.
Here's my code so far.

// Patricia Tree Node class
package dictionary;

import java.util.ArrayList;
import java.util.List;

public class PatTreeNode<T> {

String key;
List<PatTreeNode<T>> children;
boolean real;
T value;

public PatTreeNode() {
key = "";
children = new ArrayList<PatTreeNode<T>>();
real = false;
}

public String getKey() {
return key;
}

public void setKey(String key) {
this.key = key;
}

public List<PatTreeNode<T>> getChildren() {
return children;
}

public void setChildren(List<PatTreeNode<T>> children) {
this.children = children;
}

public boolean isReal() {
return real;
}

public void setReal(boolean real) {
this.real = real;
}

public T getValue() {
return value;
}

public void setValue(T value) {
this.value = value;
}

}

// Implementing the Patricia Tree

package dictionary;

import java.util.ArrayList;
import java.util.Iterator;

public class PatTree<T> {

PatTreeNode<T> root;
long size;

public PatTree() {
root = new PatTreeNode<T>();
root.setKey("");
size = 0;
}

@SuppressWarnings("unchecked")

// insert new values in the tree
public void insert(String key, T value) throws DuplicateKeyException {
insert(key,root,value);
size++;
}

public void insert(String key, PatTreeNode<T> node, T value) throws DuplicateKeyException {
int i = 0;
int keylen = key.length();
int nodelen = node.getKey().length();

while (i < keylen && i < nodelen) {
if (key.charAt(i) != node.getKey().charAt(i)) {
break;
}
i++;
}

// we are at root node
if (node.getKey().equals("") == true || (i < keylen && i < nodelen)) {
boolean flag = false;
String newText = key.substring(i, keylen);
for (PatTreeNode<T> child : node.getChildren()) {
if (child.getKey().startsWith(newText.charAt(0) + "")) {
flag = true;
insert(newText, child, value);
break;
}
}

// add the node as the child of the current node

if (flag == true) {
PatTreeNode<T> n = new PatTreeNode<T>();
n.setKey(newText);
n.setReal(true);
n.setValue(value);

node.getChildren().add(n);
}
}

// we have data need to add as the child of current node
else if (i >= keylen && i < nodelen) {
PatTreeNode<T> n = new PatTreeNode<T>();
n.setKey(node.getKey().substring(i, nodelen));
n.setChildren(node.getChildren());
n.setReal(node.isReal());
n.setValue(node.getValue());

node.setKey(key);
node.setReal(true);
//node.setValue(value);

node.getChildren().add(n);
}

// there is an exact match. Just make the current node as data node
else if (i == keylen && i == nodelen) {
if (node.isReal() == true) {
throw new DuplicateKeyException("Duplicate Key");
}

node.setReal(true);
node.setValue(value);
}

// this node needs to be split
// insert as a prefix of the current node key
else if (i < keylen && i < nodelen) {
PatTreeNode<T> n1 = new PatTreeNode<T>();
n1.setKey(node.getKey().substring(i, nodelen));
n1.setReal(node.isReal());
n1.setValue(node.getValue());
n1.setChildren(node.getChildren());

PatTreeNode<T> n2 = new PatTreeNode<T>();
n2.setKey(key.substring(i, keylen));
n2.setReal(true);
n2.setValue(value);

node.setKey(key.substring(0, i));
node.setReal(false);
node.setChildren(new ArrayList<PatTreeNode<T>>());
node.getChildren().add(n1);
node.getChildren().add(n2);
}
}

// delete values from the tree
public boolean delete(String key) {
Visitor<T> visitor = new Visitor<T>() {
boolean delete = false;

public void visit(String key, PatTreeNode<T> parent, PatTreeNode<T> node) {
delete = node.isReal();

// if the node is real
if (delete) {
// if there are no children of the node, we need to delete the node
// from the list of it's parent
if (node.getChildren().size() == 0) {
Iterator<PatTreeNode<T>> it = parent.getChildren().iterator();
while (it.hasNext()) {
if (it.next().getKey().equals(node.getKey())) {
it.remove();
break;
}
}

// if parent is not real and has only one child
// they need to be merged
if (parent.getChildren().size() == 1 && parent.isReal() == false) {
mergeNodes(parent, parent.getChildren().get(0));
}
}
else if (node.getChildren().size() == 1) { //need to merge this only child with itself
mergeNodes(node, node.getChildren().get(0));
}

else { // mark the node as non-real
node.setReal(false);
}
}
}

// Merge a child with it's parent
private void mergeNodes(PatTreeNode<T> parent, PatTreeNode<T> child) {
parent.setKey(parent.getKey() + child.getKey());
parent.setReal(child.isReal());
parent.setValue(child.getValue());
parent.setChildren(child.getChildren());
}

public Object getResult() {
return Boolean.valueOf(delete);
}

};

visit(key, visitor);

if (((Boolean) visitor.getResult()).booleanValue()) {
size--;
}
return ((Boolean) visitor.getResult()).booleanValue();
}

public void visit (String key, Visitor<T> visitor) {
if (root != null) {
visit (key, visitor, null, root);
}
}

private void visit (String prefix, Visitor<T> visitor, PatTreeNode<T> parent, PatTreeNode<T> node) {
int i = 0;
int keylen = prefix.length();
int nodelen = node.getKey().length();

// match the prefix with the node
while (i < keylen && i < nodelen) {
if (prefix.charAt(i) != node.getKey().charAt(i)) {
break;
}
i++;
}

// match found when node key and prefix key match
if (i == keylen && i == nodelen) {
visitor.visit(prefix, parent, node);
}
else if (node.getKey().equals("") == true || (i < keylen && i >= nodelen)) {
String newText = prefix.substring(i, keylen);
for (PatTreeNode<T> child : node.getChildren()) {
if (child.getKey().startsWith(newText.charAt(0) + "")) {
visit(newText, visitor, node, child);
break;
}
}
}
}

// Display the Trie
public void display() {
display(0, root);
}

private void display(int level, PatTreeNode<T> node) {
for (int i = 0; i < level; i++) {
System.out.print(" ");
}
System.out.print("|");
for (int i = 0; i < level; i++) {
System.out.print("-");
}

if (node.isReal() == true) {
System.out.print(node.getKey() + "[" + node.getValue() + "]*");
}
else {
System.out.print(node.getKey());
}

for (PatTreeNode<T> child : node.getChildren()) {
display(level+1, child);
}
}

// main class
public static void main(String[] args) {
// new tree
PatTree<String> tree = new PatTree<String>();

//tree.display();

tree.insert("almanac", "1"); // GET AN ERROR HERE WHICH INVOKES THE DUPLICATEKEYEXCEPTION METHOD.

}

}// end of class PatTree


// Here's the DuplicateKeyException class
package dictionary;

public class DuplicateKeyException extends Exception {

private static final long serialVersionUID = 3421421743921421L;

public DuplicateKeyException(String msg) {
super (msg);
}

}

Any kind of help will be greatly appreciated.

Thanks.