Why does this code throw exception - Comparison method violates its general contract

Question

I am using the following code that is throwing a IllegalArgumentException :

// Copyright (c) 2003-2014, Jodd Team (jodd.org). All Rights Reserved.

package jodd.util;

import java.util.Comparator;

/**
 * Compares two strings in natural, alphabetical, way.
 */
public class NaturalOrderComparator<T> implements Comparator<T> {

    protected final boolean ignoreCase;

    public NaturalOrderComparator() {
        ignoreCase = false;
    }

    public NaturalOrderComparator(boolean ignoreCase) {
        this.ignoreCase = ignoreCase;
    }

    /**
     * Compare digits at certain position in two strings.
     * The longest run of digits wins. That aside, the greatest
     * value wins.
     */
    protected int compareDigits(String str1, int ndx1, String str2, int ndx2) {
        int bias = 0;

        while (true) {
            char char1 = charAt(str1, ndx1);
            char char2 = charAt(str2, ndx2);

            boolean isDigitChar1 = CharUtil.isDigit(char1);
            boolean isDigitChar2 = CharUtil.isDigit(char2);

            if (!isDigitChar1 && !isDigitChar2) {
                return bias;
            }
            if (!isDigitChar1) {
                return -1;
            }
            if (!isDigitChar2) {
                return 1;
            }

            if (char1 < char2) {
                if (bias == 0) {
                    bias = -1;
                }
            } else if (char1 > char2) {
                if (bias == 0) {
                    bias = 1;
                }
            } else if (char1 == 0 && char2 == 0) {
                return bias;
            }

            ndx1++;
            ndx2++;
        }
    }

    public int compare(T o1, T o2) {
        String str1 = o1.toString();
        String str2 = o2.toString();

        int ndx1 = 0, ndx2 = 0;
        int zeroCount1, zeroCount2;
        char char1, char2;

        int result;

        while (true) {
            // only count the number of zeroes leading the last number compared
            zeroCount1 = zeroCount2 = 0;

            char1 = charAt(str1, ndx1);
            char2 = charAt(str2, ndx2);

            // skip over leading spaces or zeros in both strings

            while (Character.isSpaceChar(char1) || char1 == '0') {
                if (char1 == '0') {
                    zeroCount1++;
                } else {
                    zeroCount1 = 0; // counts only last 0 prefixes, space char interrupts the array of 0s
                }
                ndx1++;
                char1 = charAt(str1, ndx1);
            }

            while (Character.isSpaceChar(char2) || char2 == '0') {
                if (char2 == '0') {
                    zeroCount2++;
                } else {
                    zeroCount2 = 0;
                }
                ndx2++;
                char2 = charAt(str2, ndx2);
            }

            // process digits

            boolean isDigitChar1 = CharUtil.isDigit(char1);
            boolean isDigitChar2 = CharUtil.isDigit(char2);

            if (isDigitChar1 && isDigitChar2) {
                result = compareDigits(str1, ndx1, str2, ndx2);
                if (result != 0) {
                    // not equals, return
                    return result;
                }
                // equal numbers
                if (zeroCount1 != zeroCount2) {
                    return zeroCount1 - zeroCount2;
                }
            }

            if (char1 == 0 && char2 == 0) {
                // the end; the strings are the same, maybe compare ascii?
                return zeroCount1 - zeroCount2;
            }

            // check when one of the numbers is just zeros
            if (isDigitChar1 || isDigitChar2) {
                if (zeroCount1 != zeroCount2) {
                    return zeroCount2 - zeroCount1;
                }
            }

            // checks when both numbers are zero
            if (zeroCount1 != zeroCount2) {
                return zeroCount1 - zeroCount2;
            }

            // compare chars
            if (ignoreCase) {
                char1 = Character.toLowerCase(char1);
                char2 = Character.toLowerCase(char2);
            }
            if (char1 < char2) {
                return -1;
            }
            if (char1 > char2) {
                return 1;
            }

            ndx1++;
            ndx2++;
        }
    }

    /**
     * Safe charAt.
     */
    private static char charAt(String s, int i) {
        if (i >= s.length()) {
            return 0;
        }
        return s.charAt(i);
    }
}

throws the exception:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:747)
    at java.util.TimSort.mergeAt(TimSort.java:483)
    at java.util.TimSort.mergeCollapse(TimSort.java:410)
    at java.util.TimSort.sort(TimSort.java:214)
    at java.util.TimSort.sort(TimSort.java:173)
    at java.util.Arrays.sort(Arrays.java:659)
    at java.util.Collections.sort(Collections.java:217)

This is called by the following function:

@Override
    public int compare(final T o1, final T o2) {
        int result;
        final MyObject obj1 = (MyObject) o1;
        final MyObject obj2 = (MyObject) o2;

                   return     result = compareStringId(obj1.getStringId(),obj2.getStringId());           

    }

private int compareStringId(final String Id1, final String Id2) {
        return super.compare((T) Id1, (T) Id2);
    }

It work fine on our local machines, however it fails on production and we have no means to connect to that machine to figure out why. Could you please assist

Answer 1

The issue was with the incorrect implementation of a Comparator. According to Java documentation, a Comparator must be both reflexive and transitive. In this case, the transivity was not guaranteed. Prior Java 8 that was not a big issue, i.e. the sorting implementation (MergeSort) would not throw exception. Java8 changed default sorting implementation to TimSort that is much more sensitive to comparators with invalid contract, hence it might throw an exception.

However, this does not help you much in solving your issue. How about to check the latest version of the same class here. It has been upgraded to support the comparator contract, plus it works better on some edge cases, not to mention initial support for accents.