Java - Confused about Comparators and need to use one (I think). More info inside

Question

I created a class called Foo. Foo has three fields, which are all ints: x, y, and z. I want to make a PriorityQueue<Foo> which prioritizes the Foo objects differently in different situations. For instance, I might want to prioritize by x value, or maybe by y value, or maybe by z. But I won't know which value I want to prioritize by until runtime. I've heard you can use comparators to somehow impose an ordering on the fly, which I think would be perfect here.

I'm confused as to exactly how I would do this though. Could someone please show me an example if say I wanted to prioritize on x using a comparator (without having to override the compareTo function in my Foo class)?

Thank you very much.

This is a great way to start: http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue — Nicolas Modrzyk, Feb 13 '12 at 02:13
You don't have to override anything, but your Foo class will have to implement the [_Comparator_ interface](http://docs.oracle.com/javase/6/docs/api/). Just add the compare(a,b) method, and have it return an int less than zero if a < b, zero if a == b, and an int greater than zero if a > b. — Stevens Miller, Feb 13 '12 at 02:19

score 3 · Accepted Answer · edited Feb 13 '12 at 16:48

A comparator is a parameterized interface that allows you to define how two instances of the parameterized type can be compared. let's assume you have the following class

class Foo {
   int x;
   int y;
   int z;
}

Then to define a comparator that orders elements based on their x value then y then z we'd do the following

class XyzComparator implements Comparator<Foo> {
    @Override
    public int compare(Foo foo1, Foo foo2) {
          if(foo1.x != foo2.x) {
               return Integer.compare(foo1.x, foo2.x);
          }
          if(foo1.y != foo2.y) {
               return Integer.compare(foo1.y, foo2.y);
          }
          return Integer.compare(foo1.z, foo2.z);
    }
}

Similarly you can define comprators that compare elements based first on their y value then x the z...etc Finally at runtime you can instantiate a PriorityQueue with that comparator

PriorityQueue<Foo> queue;
if(x_then_y_then_z) {
    queue = new PriorityQueue<Foo>(10, new XyzComparator());
} else if (y_then_x_then_z) {
    queue = new PriorityQueue<Foo>(10, new ZxyComparator());
}

For more information take a look at the priority queue javadoc as well as the comparator javadoc

Edit: Please see @buritos comment regarding integer overflow.

that breaks comparator's contract. using subtraction in compare when dealing with numbers seems correct but what if foo1.y = -2147483648 and foo2.y = 1? obviously foo1.y is smaller than foo2.y but foo1.y-foo2.y = 2147483647 (because of silent int overflow) which is clearly not what you want as the result of your compare function. — buritos, Feb 13 '12 at 02:48
Very insightful. Thank you. I will update the code to reflect that. — 271828183, Feb 13 '12 at 02:57

score 1 · Answer 2 · answered Feb 13 '12 at 02:34

Comparator<Foo> comparator = new Comparator<Foo>() {
  @Override
  public int compare(Foo o1, Foo o2) {
    if (o1.x > o2.x)
      return 1;
    else if(o1.x < o2.x)
      return -1;
    else
      return 0;
  }
};

PriorityQueue<Foo> queue = new PriorityQueue<Foo>(10, comparator);

...

Java - Confused about Comparators and need to use one (I think). More info inside

2 Answers2