Java: Issue combining Generics, Inner class, and “implements”

I am having an issue combining generics, implements, and inner classes. I am creating a LinkedBinaryHeap class which contains an inner class. This inner class is the generic HeapNode which extends the generic Node class I created; it just adds a variable and methods for a key/priority.

In LinkedBinaryHeap I create a generic LinkedList to store HeapNodes. I am assuming the generic data being stored extends Comparable class.

Here is a layout of what stores what:

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

My issue is that when declaring the LinkedList:

LinkedList<HeapNode> heap;

eclipse underlines HeapNode and gives me the error:

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

I think the error is telling me that HeapNode must implement the Comparable, however my Node class implements Comparable, so that is taken care of, correct?

I have tried all sorts of different things, but nothing seems to work, the below code is the closest I came. Note that I have tried leaving implements Comparable Node<T> off the HeapNode inner class, and it changes nothing.

Code:

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

Node.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());
    }
}

LinkedList.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.
    }
}

Answer

As per your definitions:

  1. HeapNode is a subtype of Node<E> but implements Comparable<Node<E>>
  2. LinkedList requires a type argument such that T implements Comparable<T>
  3. i.e. a LinkedList<HeapNode> requires that HeapNode implements Comparable<HeapNode>
  4. which it does not (from (1), above, it implements Comparable<Node<E>>)

So the two are not compatible.

You need, in LinkedList, to express the node type as a type parameter, bounded appropriately, and the node type’s component type parameter as well, also bounded appropriately:

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

Now your LinkedBinaryHeap needs to adjust it’s use of LinkedList:

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

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

That should now compile. Whether it achieves your goals of comparing everything to everything else is harder to say!

Leave a Reply

Your email address will not be published. Required fields are marked *