Java priority queues and comparable interface

Question

I've just been learning about priority queues and thought I'd try how it behaves with comparable interface.

Code Snippet:

import java.util.PriorityQueue;

class kinga implements Comparable<Double> {
    double time=909.909;
    double d;

    public kinga(double a) {  
        this.d=a;
    }

    public int compareTo(Double d) {
        return Double.compare(d, time);
    }

    public static void main(String arg[]) {
        PriorityQueue<kinga> r=new PriorityQueue<kinga>();

        r.add( new kinga(4545.45));
        r.add( new kinga(45.4));
        r.add( new kinga(1235.45));

        System.out.println(r.poll()+" "+r.poll()+" "+r.poll());
    }
}

It compiles but gives me Exception in thread "main" java.lang.ClassCastException: kinga cannot be cast to java.lang.Double.

What is wrong here. Can somebody tell me how comparable and priority queues work?

Solution 1

kinga should be comparable with kinga, not Double, so:

class kinga implements Comparable<kinga>

which means your compareTo method has to be changed to this:

public int compareTo(kinga o) {
    return Double.compare(o.d, d);
}

Solution 2

class kinga implements Comparable<Double>

That doesn't make sense. Although your class will compare fine with Double, Double is unaware of that, and won't compare fine with instances of kinga, which will break the Comparable contract. And since a kinga can't compare with another kinga, you can't use a PriorityQueue<kinga>.

It should be

class Kinga implements Comparable<Kinga>

(note the upper-case, to respect the Java naming conventions), which means: Kinga instances are comparable together.

The compareTo method should be

@Override
public int compareTo(Kinga other) {
    return Double.compare(this.d, other.d);
}

which means: I'm bigger than another Kinga if my d is bigger than the other Kinga's d.

Solution 3

PriorityQueue<kinga> will expect Comparable<kinga> in the add method. Passing a Comparable<Dobule> instead, is throwing ClassCastException

Comments

[Katona]

@JBNizet I am not sure, the original was Double.compare(d, time);, so I didn't change that

[JB Nizet]

But it doesn't make any sense.

[Katona]

by the way, PriorityQueue is possibly another example of sacrificing type safety for flexibility: if it had been declared as class PriorityQueue<E extends Comparable<E>>, then this error would have been caught at compile time, but then only elements with natural ordering could be put into the queue

[yshavit]

+1 To drive it home, consider Kinga k; Double d;. In this case,k.compareTo(d); works fine, but what about ’d.compareTo(k)`? The priority queue will call the latter sometimes, which is what causes the exception.

[committedandroider]

Can you guys take a look at my use of a PriorityQueue in this question? stackoverflow.com/questions/28800287/…

[committedandroider]

Can you take a look at my use of a PriorityQueue in this question? stackoverflow.com/questions/28800287/…