-4

While I am using below comparator to sort an object I am getting Comparison method violates its general contract issue in the comparator.

final Set<Span> set = new TreeSet<Span>(new Comparator<Span>() {

        public int compare(final Span firstSpan, final Span secSpan) {
            BigInteger s1X0 = firstSpan.getCoordinates().getX0();
            BigInteger s1X1 = firstSpan.getCoordinates().getX1();
            BigInteger s2X0 = secSpan.getCoordinates().getX0();
            BigInteger s2X1 = secSpan.getCoordinates().getX1();

            BigInteger s1Y0 = firstSpan.getCoordinates().getY0();
            final BigInteger s2Y0 = secSpan.getCoordinates().getY0();

            if(s1X0.intValue() == s2X0.intValue() && s1X1.intValue() == s2X1.intValue() && s1Y0.intValue() == s2Y0.intValue()){
                return 0;
            }
            if ((s1Y0.intValue() - s2Y0.intValue() <= 5) && (s1Y0.intValue() - s2Y0.intValue() >= -5)) {
                return (s1X0.intValue()>s2X0.intValue()) ? 1 : -1;
            } else {
                if ((s1X0.intValue() >= s2X0.intValue() && s1X0.intValue() <= s2X1.intValue())
                        || (s2X0.intValue() >= s1X0.intValue() && s2X0.intValue() <= s1X1.intValue())) {
                    return (s1Y0.intValue() > s2Y0.intValue()) ? 1 : -1;
                } else {
                    return s1X0.intValue() > s2X0.intValue() ? 1 : -1;
                }
            }

        }

    });
Stuart Marks
  • 127,867
  • 37
  • 205
  • 259
A. Gupta
  • 1
  • 3
  • 4
    Given that you're calling `intValue()` 24 times, why don't you just make `s1X0` etc `int` variables? That would make it easier to help you, and your code easier to read. – Jon Skeet Jun 14 '17 at 07:28
  • 3
    It would also help if you'd tell us what you're trying to achieve, and ideally provide a [mcve] demonstrating the problem - given concrete examples, it should be easy for us to show you the place where your comparison is inconsistent. – Jon Skeet Jun 14 '17 at 07:29
  • 3
    Do you understand what that error message means? Carefully read the API docs of [`java.util.Comparator`](http://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html), it explains the requirements for the implementation of the `compare` method. Your implementation violates these requirements, so you have to check your code and adjust it to make sure it complies. – Jesper Jun 14 '17 at 07:31
  • 3
    `return s1X0.intValue() > s2X0.intValue() ? 1 : -1;` doesn't look transitive to me (what happens if the values are equal?). – chrylis -cautiouslyoptimistic- Jun 14 '17 at 07:34
  • I guess that the error comes from the `return 0` condition. Given the rest of the method you should probably use `||` instead of `&&` in the `if` just above. – Olivier Grégoire Jun 14 '17 at 07:41
  • 3
    Where to start? Using `BigInteger` suggests that the values might exceed the `int` range, otherwise, why are you using `BigInteger`? So doing comparisons based on `int` values only is error prone. You are also using subtraction without checking for overflow. Besides that, can you explain the comparator’s logic in plain words? And then, recheck whether the code really follows that logic? – Holger Jun 14 '17 at 07:46

2 Answers2

5

A Comparator must impose a total ordering on the objects it compares. In particular this means that it must be transitive, i.e., if a is smaller than b, and b is smaller than c, then a must be smaller than c. Your Comparator does not have that property.

Consider the following example:

a.getX0() == 1    b.getX0() == 2    c.getX0() == 3
a.getX1() == 4    b.getX1() == 5    c.getX1() == 6
a.getY0() == 4    b.getY0() == 0    c.getY0() == -4

then it holds that a is smaller than b (the difference in y0 is smaller than 5), b is smaller than c (the difference is y0 is smaller than 5), but a is not smaller than c (the difference in y0 is larger than 5, so the y0 value is taken).

In what order should these three objects be sorted?

Additionally, your code has other problems. If you convert everything to an int, an overflow might occur (which could also cause the exception you mention). When the data are stored as BigInteger, you should also do the comparison using BigIntegers, using e.g. the methods BigInteger.subtract and BigInteger.compare.

Hoopje
  • 12,677
  • 8
  • 34
  • 50
1

By using BigInteger.intValue you just assumed that all your numbers will fit in simple integers.

Since BigInteger is a Comparable you should rely on BigInteger.compare instead of comparing int values.

B. Bri
  • 546
  • 2
  • 7
  • 23