Bruce Zu Bruce Zu - 3 months ago 11
Java Question

how to write the equals() of Comparator

I am trying to implement the equals method of Comparator, but stuck in halfway.
Regarding to the description in equals() that "sgn(comp1.compare(o1,o2))==sgn(comp2.compare(o1, o2)) for every object reference o1 and o2." Should I take a case in this method? how can I know the every object reference o1 and o2 when I am writing the equals() .

Comparator c = new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}

@Override
public boolean equals(Object obj) {
Type genericType = obj.getClass().getGenericInterfaces()[0];
Type type = ((ParameterizedType) genericType).getActualTypeArguments()[0];
if (((Class<?>) type).getName().equals(Interval.class.getName())) {
// how to implement
// "sgn(comp1.compare(o1,o2))==sgn(comp2.compare(o1, o2))
// for every object reference o1 and o2."
return true;
}
return false;
}
};

Answer

Comparators can be considered equivalent if they sort elements the same way. This test could be used to optimize sorting, but in practice I'm not aware of core Java collections taking advantage of this hint.

Failing to recognize this equivalence might eliminate some theoretical opportunities for optimization, but it won't break anything. So, it is generally not necessary to override the equals() method.

As the documentation for Comparator.equals() says:

Note that it is always safe not to override Object.equals(Object).

The default, identity-based implementation of equals() works well if you can define your order as a class or instance member, rather than creating a new instance each time it's used. This way, two sorted collections that use the same comparator can be detected, because their comparators will be equal.

private static final Comparator<Interval> orderByStart = new Comparator<Interval>() {
  @Override
  public int compare(Interval o1, Interval o2) {
    return o1.start - o2.start;
  }    
};

I see this is a work around

No. It's the correct way to implement the Comparator.equals() method.

Let's take a closer look at the solution you are insisting upon:

Comparator<Interval> c = new Comparator<Interval>() {

  @Override
  public int compare(Interval o1, Interval o2) {
    return o1.start - o2.start;
  }

  @Override
  public boolean equals(Object obj) {
    if (!(obj instanceof Comparator<?>))
      return false;
    @SuppressWarnings("unchecked") /* We'll catch this below. */
    Comparator<Interval> that = (Comparator<Interval>) obj;
    return 
       IntStream.rangeClosed(Integer.MIN_VALUE, Integer.MAX_VALUE)
      .mapToObj(Interval::new)
      .allMatch(o1 -> {
         return
            IntStream.rangeClosed(Integer.MIN_VALUE, Integer.MAX_VALUE)
           .mapToObj(Interval::new)
           .allMatch(o2 -> {
              int sig = Integer.signum(compare(o1, o2));
              try {
                return Integer.signum(that.compare(o1, o2)) == sig;
              } catch (ClassCastException ex) {
                return false;
              }
            });
       });
  }

};

The equals() method of Comparator is meant as an optimization. If you can't test equality quickly and efficiently, don't bother trying—"it is always safe not to". The converse is not true: there is danger in implementing equals() incorrectly, as I've demonstrated here.

If you can't use a correct idiom, your program will look terrible and perform even worse.

Comments