Implementing Java Comparator

Question

I am trying to write an algorithm which utilizes a min-priority queue, so I looked around on google and found the PriorityQueue. It seems that in order to use it, though, I am going to need to tell it how I want it to prioritize, and that the way to do this is with a comparator (I want to compare specific data fields of my "Node1" objects). More googling presented the idea of creating a new comparator which implements Comparator but overrides the compare method. What I am trying is this (and other variations of it as well):

import java.util.Comparator;

public class distComparator implements Comparator {

    @Override
    public int compare(Node1 x, Node1 y){
        if(x.dist<y.dist){
            return -1;
        }
        if(x.dist>y.dist){
            return 1;
        }
        return 0;
    }
}

The compiler protests on several grounds, one of which is that I haven't over-ridden the comparator class (which it says is abstract)

error: distComparator is not abstract and does not override abstract method compare(Object,Object) in Comparator

I have switched it to say "compare(object x, object y)", which takes care of that issue. At this point though the compiler complains that it can't find the "dist" variable in x or y--which makes sense, since they are part of my Node1 class, not the Object class.

So how is this supposed to work? It should have type Object, apparently, but then how do I direct it to the correct variable?

Solution 1

You need to implement Comparator<Node1>:

public class distComparator implements Comparator<Node1> {
                                                 ^^^^^^^

Without this, you are implementing Comparator<Object>, which isn't what you want (it can be made to work, but isn't worth the hassle).

The rest of the code in your question is fine, provided Node1 has an accessible member called dist.

Note that if you are using Java 7, the entire body of the method can be replaced with

return Integer.compare(x.dist, y.dist);

(replace Integer with Double etc, depending on the type of Node1.dist.)

Solution 2

As you can see here (the JSE Comparator JavaDoc page), the Comparator interface has a generic "parameter" describing the type for which this comparator is designed. The PriorityQueue is similar.

So, if you create a PriorityQueue<Node1>, you can create a Comparator<Node1> as follows:

public class distComparator implements Comparator<Node1> {    
    @Override
    public int compare(Node1 x, Node1 y){
        return x.dist - y.dist;
    }
}

Comments

[Polygnome]

You could also write return x.dist - y.dist

[NPE]

@Polygnome: Depending on the ranges involved this may or may not work for integers, but is a complete non-starter for floating-point values.

[Amr Lotfy]

use <> instead of []