java - 扩展可比较的泛型

Question

我正在用 Java 开发一个基于模板的类，它实现了各种树结构（例如标准二叉树、红黑树或 B-Tree）。我的想法是让它像 Java Collections 中的各种列表一样完成。那是一个接口类，然后由指定的树扩展。但是，我遇到了一个奇怪的问题：

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

看起来Java认为对象是不同类型的......如何解决这个问题？

这是我的一段代码：

树.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 */
    }

}

编辑：感谢您的建议，我能够将错误数量减少到 5 个。它们是：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

现在，我的代码有它Node<T>并且Tree<T>缺少它。但是还有什么问题？

Answer 1

当您在 JDK 中复制功能时，您应该阅读代码以获得一些想法。

你的代码需要让你使用 Node 和 Tree 通用的一件事。

 public class BSTree<T extends Comparable<T>> extends Tree<T> {

和

protected Node<T> parent, left, right;

顺便说一句：当您可以使用原语时，您不应该使用包装器。

protected int nodesCount;

Answer 2

您在声明中缺少通用Tree参数BSTree：

public class BSTree<T ...> extends Tree<T>

这意味着add(T)in 方法BSTree不会按Tree原样覆盖 in 方法，因为它们没有相同的参数类型。

然而，由于T 一个类并不比一个更精确Object（我们只知道它实现了Comparable 接口），因此这两种方法都具有与 相同的擦除add(Object)，具有潜在不兼容的类型（在编译器的错误输出中标识为T#1和T#2）。

Answer 3

尝试：

public class BSTree<T extends Comparable<T>> extends Tree<T> {