Java: проблема с объединением дженериков, внутреннего класса и реализации

У меня проблема с объединением дженериков, implements и внутренних классов. Я создаю класс LinkedBinaryHeap, который содержит внутренний класс. Этот внутренний класс является общим HeapNode, который расширяет общий класс Node, который я создал; он просто добавляет переменную и методы для ключа/приоритета.

В LinkedBinaryHeap я создаю общий LinkedList для хранения HeapNode. Я предполагаю, что общие хранящиеся данные расширяют класс Comparable.

Вот схема того, что хранит что:

BinaryHeap->LinkedList(Nodes)->HeapNode(extends Node)->DATA,KEY

Моя проблема в том, что при объявлении LinkedList:

LinkedList<HeapNode> heap;

eclipse подчеркивает HeapNode и выдает ошибку:

Bound mismatch: The type LinkedBinaryHeap.HeapNode is not a 
valid substitute for the bounded parameter > 
of the type LinkedList

Я думаю, ошибка говорит мне, что HeapNode должен реализовать Comparable, однако мой класс Node реализует Comparable, так что об этом позаботились, верно?

Я пробовал разные вещи, но, похоже, ничего не работает, приведенный ниже код ближе всего к тому, что я нашел. Обратите внимание, что я пробовал оставить implements Comparable Node<T> вне внутреннего класса HeapNode, и это ничего не меняет.

Код:

LinkedBinaryHeap.java:

public class LinkedBinaryHeap<E extends Comparable<E>> {
    private LinkedList<HeapNode> heap;

    public LinkedBinaryHeap(){
        heap = new LinkedList<HeapNode>();
    }

    /* INNER CLASS DECLARATION. */
    private class HeapNode extends Node<E> implements Comparable<Node<E>>{
        int key;
        public HeapNode(int key, E data){
            super(data);
            this.key = key;
        }

        public int getKey(){
            return key;
        }

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

Узел.java:

public class Node<T extends Comparable<T>> implements Comparable<Node<T>>{
    protected T data;
    protected Node<T> next;
    protected Node<T> previous;

    public Node(T data){
        next = null;
        previous = null;
        this.data = data;
    }   

    /* Some other methods left out here. */

    public int compareTo(Node<T> node) {
        return data.compareTo(node.getData());
    }
}

Связанный список.java:

public class LinkedList<T extends Comparable<T>> implements Comparable<LinkedList<T>>{
    private Node<T> head;
    private Node<T> tail;
    private int size;

    public LinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    /* Other methods left out. */

    public int compareTo(LinkedList<T> list){
        // does stuff.
    }
}

person XdrummerXboy    schedule 22.02.2015    source источник
comment
Есть ли какая-то причина, по которой LinkedList и Node нужно реализовать Comparable? Это действительно очень неудобно, когда все так ограничено везде.   -  person Radiodef    schedule 22.02.2015


Ответы (2)


Согласно вашим определениям:

  1. HeapNode является подтипом Node<E>, но implements Comparable<Node<E>>
  2. LinkedList требует аргумента типа, чтобы T implements Comparable<T>
  3. то есть LinkedList<HeapNode> требует, чтобы HeapNode implements Comparable<HeapNode>
  4. чего нет (из (1) выше, это implements Comparable<Node<E>>)

Так что эти двое несовместимы.

Вам нужно в LinkedList выразить тип узла как параметр типа, ограниченный соответствующим образом, а также параметр типа компонента типа узла, также ограниченный соответствующим образом:

public class LinkedList<N extends Node<E>, 
                        E extends Comparable<E>> 
  implements Comparable<LinkedList<N, E>>{
  private N head;
  private N tail;
  private int size;
  ...

Теперь вашему LinkedBinaryHeap нужно настроить использование LinkedList:

public class LinkedBinaryHeap<E extends Comparable<E>> {
  private LinkedList<HeapNode, E> heap;

  public LinkedBinaryHeap(){
      heap = new LinkedList<HeapNode, E>();
  }

Теперь это должно скомпилироваться. Труднее сказать, достигает ли это ваших целей сравнения всего со всем остальным!

person Andy Brown    schedule 22.02.2015
comment
Благодарю вас! В итоге я отказался от реализации Comparable из Node и LinkedList, но мне все еще нужно было использовать его в HeapNode, чтобы иметь возможность хранить его в LinkedList (для сортировки). - person XdrummerXboy; 22.02.2015

LinkedList требует, чтобы T реализовал Comparable. HeapNode реализует Comparable<Node<E>>. HeapNode != Node, поэтому он не удовлетворяет привязке типа. Измените объявление LinkedList на T extends Comparable<? super T>. Это нормально с точки зрения типов: HeapNode объявляет, что может сравнивать себя с любым Node или подтипом Node. Конечно, это означает, что HeapNode должен переопределить compareTo, но вы как бы застряли там, поскольку Node уже реализует Comparable.

Изменить: как отмечают комментарии, этот ответ неверен, и его не стоит исправлять, потому что есть правильный ответ. Пусть это останется для потомков как урок в... чем-то. Как я не так хорошо разбираюсь в дженериках, как хотелось бы, может быть.

person Steve McKay    schedule 22.02.2015
comment
Это не сработает. Бьюсь об заклад, Node<T> head и tail теперь дают ошибку компилятора из-за несоответствия границ. - person Andy Brown; 22.02.2015
comment
@AndyBrown Ну, на самом деле это может сработать, им просто нужно будет изменить все объявления, чтобы они соответствовали. - person Radiodef; 22.02.2015
comment
@Radiodef. Это может работать, но не так, как написано, и я думаю, что потребуется больше, чем просто изменения в head и tail. (Возможно, мы жестоко соглашаемся друг с другом). - person Andy Brown; 22.02.2015