I'm developing a template based classes in Java that implement various trees structure (such as standard binary tree, red-black tree or B-Tree). My idea is to have it done like various lists in Java Collections. That is one interface class which is then expanded by specified trees. However, I hit a wall with a strange problems:
BSTree.java:12: error: BSTree is not abstract and does not override abstract method search(Comparable) in Tree
public class BSTree<T extends Comparable<T>> extends Tree {
^
BSTree.java:20: error: name clash: add(T#1) in BSTree and add(T#2) in Tree have the same erasure, yet neither overrides the other
public void add(T key) throws NullPointerException {
^
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Comparable<T#2> declared in class Tree
BSTree.java:28: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
if (key.compareTo(ptr.key) == -1) {
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:42: error: name clash: remove(T#1) in BSTree and remove(T#2) in Tree have the same erasure, yet neither overrides the other
public void remove(T key) throws NullPointerException, TreeException {
^
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Comparable<T#2> declared in class Tree
BSTree.java:49: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
if (key.compareTo(ptr.key) == 0) {
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:81: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:89: error: name clash: search(T#1) in BSTree and search(T#2) in Tree have the same erasure, yet neither overrides the other
public Node<T> search(T key) throws NullPointerException, KeyNotStoredException {
^
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Comparable<T#2> declared in class Tree
BSTree.java:94: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
if (key.compareTo(ptr.key) == 0) return ptr;
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:95: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
It looks like Java thinks that the object are of different types... How to fix that?
Here's piece of my code:
Tree.java
class Node<T extends Comparable<T>> {
protected T key;
protected Node parent, left, right;
public Node(T key, Node parent) {
this.key = key;
this.parent = parent;
this.left = null;
this.right = null;
}
}
public abstract class Tree<T extends Comparable<T>> {
protected Node<T> root;
protected Integer nodesCount;
public abstract void add(T key) throws NullPointerException;
public abstract void remove(T key) throws NullPointerException, TreeException;
public abstract Node<T> search(T key) throws NullPointerException, KeyNotStoredException;
}
BSTree.java
public class BSTree<T extends Comparable<T>> extends Tree {
public BSTree() {
root = null;
nodesCount = new Integer(0);
}
@Override
public void add(T key) throws NullPointerException {
if (root == null) root = new Node<T>(key, null);
else {
boolean left = false;
Node ptr = root, parent = ptr.parent;
while (ptr != null) {
parent = ptr;
left = false;
if (key.compareTo(ptr.key) == -1) {
ptr = ptr.left;
left = true;
} else ptr = ptr.right;
}
if (left) parent.left = new Node<T>(key, parent);
else parent.right = new Node<T>(key, parent);
}
nodesCount++;
}
@Override
public void remove(T key) throws NullPointerException, TreeException {
/* implementation */
}
@Override
public Node<T> search(T key) throws NullPointerException, KeyNotStoredException {
/* implementation */
}
}
EDIT: Thanks to your pieces of advice I was able to reduce number of errors to 5. Here they are: javac -d ../bin *.java
BSTree.java:28: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
if (key.compareTo(ptr.key) == -1) {
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:49: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
if (key.compareTo(ptr.key) == 0) {
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:81: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:94: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
if (key.compareTo(ptr.key) == 0) return ptr;
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
BSTree.java:95: error: method compareTo in interface Comparable<T#2> cannot be applied to given types;
else if (key.compareTo(ptr.key) < 0) ptr = ptr.left;
^
required: T#1
found: Comparable
reason: actual argument Comparable cannot be converted to T#1 by method invocation conversion
where T#1,T#2 are type-variables:
T#1 extends Comparable<T#1> declared in class BSTree
T#2 extends Object declared in interface Comparable
Now, my code has Node<T> and Tree<T> where it lacked it. But what's still wrong?
When you duplicating functionality in the JDK, you should read the code to get some ideas.
One thing your code needs to make your use of Node and Tree generic.
public class BSTree<T extends Comparable<T>> extends Tree<T> {
and
protected Node<T> parent, left, right;
BTW: You shouldn't use a wrapper when you can use a primitive.
protected int nodesCount;