cannot cast to java.lang.Comparable

Question

Although this question has already been asked but I have an implementation specific doubt.

I am trying to print the top view of the binary tree and following is the complete code for it:

import java.util.*;

class Node{
    int data;
    Node right;
    Node left;
    Node(int data){
        this.data = data;
    }
}

class Pair<F,S>{
    private F first;
    private S second;
    public Pair(F first, S second){
        this.first = first;
        this.second = second;
    }
    
    public F getFirst(){return first;}
    public S getSecond(){return second;}
}

class BinaryTreeTopView{

    public static void printTopView(Node root){

        if(root == null)
            return;

    Queue <Pair<Node,Integer>> q = new Queue<>();
    Map <Integer,Node> map = new HashMap<>();
    Pair<Node,Integer> p = new Pair<>(root, 0);
    q.add(p);
    
    /*
    I am storing nodes and the corresponding horizontal distances 
    in the form of a pair which then are being stored in the queue
    to ensure level order traversal
    */

    while(!q.isEmpty()){
        Pair<Node,Integer> temp = q.peek();
        q.remove();

        if(map.containsKey(temp.getSecond())==true){
            map.put(temp.getSecond(),temp.getFirst());
        } else {
            System.out.println(temp.getFirst().data);
            map.put(temp.getSecond(),temp.getFirst());                
        }

        if(temp.getFirst().left!=null){
            Pair<Node,Integer> left = new Pair<>(temp.getFirst().left, temp.getSecond()-1);
            q.add(left);
        }
        
        if(temp.getFirst().right!=null){
            Pair<Node,Integer> right = new Pair<> (temp.getFirst().right, temp.getSecond()+1);
            q.add(right);
        }
        
    }
}
public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.right = new Node(5);
    root.left.left = new Node(4);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.right.left.right = new Node(8);
    root.right.right.left = new Node(10);
    root.right.right.right = new Node(9);
    root.right.right.left.right = new Node(11);
    root.right.right.left.right.right = new Node(12);
    
    printTopView(root);
}
}

It compiles fine but an exception is being raised at the runtime. Now I have been getting the following exception and I am unable to figure out what the problem is:

Exception in thread "main" java.lang.ClassCastException: 
Pair cannot be cast to java.lang.Comparable at  java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:652)
at java.util.PriorityQueue.siftUp(PriorityQueue.java:647)
at java.util.PriorityQueue.offer(PriorityQueue.java:344)
at java.util.PriorityQueue.add(PriorityQueue.java:321)

Threesome

What is the complete stack trace? i.e. which line in your code does it correspond to? – Caphaitien

Also, I don't believe this is your real code, as new Queue<>() doesn't compile. – Caphaitien

@OliverCharlesworth..Oh i'm sorry...But it is my code....I actually posted the unedited code...Of course it won't compile...bt the one i actually comiled had PriorityQueue... So... Anyways thanx for pointing that out! – Threesome

Answer 1

It's because Pair isn't implementing Comparable. Either implement it:

public class Pair implements Comparable<Pair> {
    public int compareTo(Pair o) {
        // ...
    }
}

Or use Comparator in Your priority queue

Using Comparator ;

PriorityQueue<DummyObject> pq = new
             PriorityQueue<DummyObject>(5, new DummyObjectComparator());

Define your Comparator :

class DummyObjectComparator implements Comparator<DummyObject>{

      // Overriding compare()method of Comparator 

       public int compare(DummyObject s1, DummyObject s2) {
                   //some code
       }
 }

Escalator

Ok that worked! Thanx a lot for the answer! But i still am not clear about why do i need to implement comparable interface and override compareTo method! – Threesome

From error it seems you are using priority queue ,If you see this class use comparable or if comparator to compare between two element – Escalator

Yeah but what is the need of using a comparator when i am not using it....I all i am doing is storing my objects in a queue...?? – Threesome

Would you give example of "Or use Comparator in Your priority queue"? – Aristaeus

Answer 2

You're trying to add Pair instances to a PriorityQueue, so your Pair class must be Comparable. A reasonable implementation could be to force F and S to be Comparable on their own right, and then compare by the first element, and then the second one:

class Pair<F extends Comparable<F>, S extends Comparable<S>>
    implements Comparable<Pair<F, S>> {

    // All the code you already have is fine

    @Override
    public int compareTo(Pair<F, S> o) {
        int retVal = getFirst().compareTo(o.getFirst());
        if (retVal != 0) {
            return retVal;
        }
        return getSecond().compareTo(o.getSecond());
    }
}

Luellaluelle

Ok..but i still have got one dout..my method is not making any comparsions anywhere so why do i need to compare o.first and o.second – Threesome

The PriorityQueue sorts its elements by their natural order (i.e., it sorts them). In order to accomplish that, the elements must be comparable. – Luellaluelle

Answer 3

Your statement:

Queue <Pair<Node,Integer>> q = new Queue<>();

Doesn't compile because Queue is an interface and cannot be instantiated. I suspect that you've used a PriorityQueue instead.

Do you really need a priority queue, or would a simple LinkedList would suit your algoritm?

UPDATE:

BTW, with a LinkedList, the output is:

1 2 3 4 7 9

Electrodynamic