cannot cast to java.lang.Comparable
25,501
Solution 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
}
}
Solution 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());
}
}
![pkenil96](https://i.stack.imgur.com/FAOaJ.jpg?s=256&g=1)
Author by
pkenil96
Updated on July 17, 2022Comments
-
pkenil96 almost 2 years
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)