Comparator breaching general contract

Question

The below code is a edited version of Dave Koelle's AlphanumComparator. The edit contains code which sorts empty strings to the end of the list, or bottom of the JTable in my case. The problem is a java.lang.IllegalArgumentException: Comparison method violates its general contract! occurs.

To fix my problem I looked into it and found reasons such as the comparator doesn't have a return 0; in the correct place. I also found a comment in the Java bug database which read

The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior

import java.util.Comparator;
import javax.swing.JTable;
import javax.swing.SortOrder;

public class AlphanumComparator implements Comparator<String> {
    JTable table;

    public AlphanumComparator(JTable table) {
        this.table = table;
    }

    private final boolean isDigit(char ch) {
        return ch >= 48 && ch <= 57;
    }

    private final String getChunk(String s, int slength, int marker) {
        StringBuilder chunk = new StringBuilder();
        char c = s.charAt(marker);
        chunk.append(c);
        marker++;
        if (isDigit(c)) {
            while (marker < slength) {
                c = s.charAt(marker);
                if (!isDigit(c))
                    break;
                chunk.append(c);
                marker++;
            }
        } else {
            while (marker < slength) {
                c = s.charAt(marker);
                if (isDigit(c))
                    break;
                chunk.append(c);
                marker++;
            }
        }
        return chunk.toString();
    }

    public int compare(String s1, String s2) {
        boolean swapInt = table.getRowSorter().getSortKeys().get(0).getSortOrder() == SortOrder.ASCENDING;

        int thisMarker = 0;
        int thatMarker = 0;
        int s1Length = s1.length();
        int s2Length = s2.length();

        if(s1Length != 0 && s2Length != 0) {
            while (thisMarker < s1Length && thatMarker < s2Length) {
                String thisChunk = getChunk(s1, s1Length, thisMarker);
                thisMarker += thisChunk.length();

                String thatChunk = getChunk(s2, s2Length, thatMarker);
                thatMarker += thatChunk.length();

                int result = 0;
                if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0))) {
                    int thisChunkLength = thisChunk.length();
                    result = thisChunkLength - thatChunk.length();
                    if (result == 0) {
                        for (int i = 0; i < thisChunkLength; i++) {
                            result = thisChunk.charAt(i) - thatChunk.charAt(i);
                            if (result != 0) {
                                return result;
                            }
                        }
                    }
                } else {
                    result = thisChunk.compareTo(thatChunk);
                }

                if (result != 0)
                    return result;
            }

            return s1Length - s2Length;
        } else {
            if(swapInt) {
                if(s1Length == 0) {
                    return 1;
                } else {
                    return -1;
                }
            } else {
                if(s1Length == 0) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }
    }
}

Would someone be able to help fix my problem and explain why this comparator is violating the Comparable contract

Exception stack trace if needed

Exception in thread "AWT-EventQueue-0" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeLo(ComparableTimSort.java:744)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:481)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1246)
    at javax.swing.DefaultRowSorter.sort(DefaultRowSorter.java:607)
    at javax.swing.DefaultRowSorter.setSortKeys(DefaultRowSorter.java:319)
    at javax.swing.DefaultRowSorter.toggleSortOrder(DefaultRowSorter.java:480)
    at javax.swing.plaf.basic.BasicTableHeaderUI$MouseInputHandler.mouseClicked(BasicTableHeaderUI.java:112)
    at java.awt.AWTEventMulticaster.mouseClicked(AWTEventMulticaster.java:270)
    at java.awt.Component.processMouseEvent(Component.java:6538)
    at javax.swing.JComponent.processMouseEvent(JComponent.java:3324)
    at java.awt.Component.processEvent(Component.java:6300)
    at java.awt.Container.processEvent(Container.java:2236)
    at java.awt.Component.dispatchEventImpl(Component.java:4891)
    at java.awt.Container.dispatchEventImpl(Container.java:2294)
    at java.awt.Component.dispatchEvent(Component.java:4713)
    at java.awt.LightweightDispatcher.retargetMouseEvent(Container.java:4888)
    at java.awt.LightweightDispatcher.processMouseEvent(Container.java:4534)
    at java.awt.LightweightDispatcher.dispatchEvent(Container.java:4466)
    at java.awt.Container.dispatchEventImpl(Container.java:2280)
    at java.awt.Window.dispatchEventImpl(Window.java:2750)
    at java.awt.Component.dispatchEvent(Component.java:4713)
    at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:758)
    at java.awt.EventQueue.access$500(EventQueue.java:97)
    at java.awt.EventQueue$3.run(EventQueue.java:709)
    at java.awt.EventQueue$3.run(EventQueue.java:703)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76)
    at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:86)
    at java.awt.EventQueue$4.run(EventQueue.java:731)
    at java.awt.EventQueue$4.run(EventQueue.java:729)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76)
    at java.awt.EventQueue.dispatchEvent(EventQueue.java:728)
    at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
    at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
    at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105)
    at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
    at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93)
    at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)

Answer 1

I think the problem is that your code never examines s2Length when s1Length is zero. You need to add another check to see if both strings are empty, like this:

if(swapInt) {
    if(s1Length == 0 && s2Length != 0) {
        return 1;
    } else if (s2Length == 0 && s1Length != 0) {
        return -1;
    } else {
        return 0;
    }
} else {
    if(s1Length == 0 && s2Length != 0) {
        return -1;
    } else if (s2Length == 0 && s1Length != 0) {
        return 1;
    } else {
        return 0;
    }
}

Your current implementation returns 1 or -1 even when the two strings are empty (meaning that they must compare as equal and return zero). New sorting algorithm detects this problem, and throws an exception.

Note:

You should be able to simplify this code further by making swapInt an int that is either 1 or -1, depending on the getSortOrder result:

if(s1Length == 0 && s2Length != 0) {
    return swapInt;
} else if (s2Length == 0 && s1Length != 0) {
    return -swapInt;
} else {
    return 0;
}

Answer 2

Your comparator does:

if (s1Length != 0 && s2Length != 0) {
    ...
} else {
    if (swapInt) {
        if(s1Length == 0) {
            return 1;
        } else {
            return -1;
        }
    } else {
        if(s1Length == 0) {
            return -1;
        } else {
            return 1;
        }
     }
}

So, if it doesn't enter the if block, it means that at least one string is empty. But both could be empty. But your comparator only returns -1 or 1 in that case. Which means that if A and B are both empty, and comparing A to B leads to -1, then comparing B to A will also lead to -1, and A is thus both smaller and greater than B at the same time.

Just start your else block with

if (s1Length == 0 && s2Length == 0) {
    return 0;
}