Why does my compare methd throw IllegalArgumentExc

I am having this problem for some time, have searched lots of StackOverflow questions but couldn't solve my problem.

I also asked a similar question before and got the suggestion to use,

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

It didn't solve my problem. I never got this exception on any of my test devices, but some of my users have been reporting it regularly. I am really clueless how to solve it.

The Exception

This is the exception that I am getting,

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:743)
at java.util.TimSort.mergeAt(TimSort.java:479)
at java.util.TimSort.mergeCollapse(TimSort.java:404)
at java.util.TimSort.sort(TimSort.java:210)
at java.util.TimSort.sort(TimSort.java:169)
at java.util.Arrays.sort(Arrays.java:2023)
at java.util.Collections.sort(Collections.java:1883)

or sometimes this,

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:864)
at java.util.TimSort.mergeAt(TimSort.java:481)
at java.util.TimSort.mergeCollapse(TimSort.java:406)
at java.util.TimSort.sort(TimSort.java:210)
at java.util.TimSort.sort(TimSort.java:169)
at java.util.Arrays.sort(Arrays.java:2010)
at java.util.Collections.sort(Collections.java:1883)

What I Have Done

enum FileItemComparator implements Comparator<FileItem> {

    //Using ENUM
    NAME_SORT {
        public int compare(FileItem o1, FileItem o2) {

            int result = 0;
            if (o1 != null && o2 != null) {

                String n1 = o1.getFileName();
                String n2 = o2.getFileName();

                if (n1 != null && n2 != null)
                    result = n1.compareTo(n2);
            }

            return result;
        }
    },
    DATE_SORT {
        public int compare(FileItem o1, FileItem o2) {

            int result = 0;
            if (o1 != null && o2 != null) {

                String d1 = o1.getFileDate();
                String d2 = o2.getFileDate();

                if (d1 != null && d2 != null) {

                    Long l1 = Long.valueOf(d1);
                    Long l2 = Long.valueOf(d2);

                    if (l1 != null && l2 != null) {
                        result = l1.compareTo(l2);
                    }
                }

            }

            return result;
        }
    },
    SIZE_SORT {
        public int compare(FileItem o1, FileItem o2) {

            int result = 0;
            if (o1 != null && o2 != null) {

                File f1 = o1.getItem();
                File f2 = o2.getItem();

                if (f1 != null && f2 != null) {

                    result = Long.valueOf(f1.length()).compareTo(Long.valueOf(f2.length()));
                }
            }

            return result;
        }
    };

    public static Comparator<FileItem> descending(final Comparator<FileItem> other) {

        return new Comparator<FileItem>() {
            public int compare(FileItem o1, FileItem o2) {
                return -1 * other.compare(o1, o2);
            }
        };
    }

    public static Comparator<FileItem> getComparator(final FileItemComparator... multipleOptions) {
        return new Comparator<FileItem>() {
            public int compare(FileItem o1, FileItem o2) {
                for (FileItemComparator option : multipleOptions) {
                    int result = option.compare(o1, o2);
                    if (result != 0) {
                        return result;
                    }
                }
                return 0;
            }
        };
    }
}

This is how I am sorting,

Collections.sort(dirs, FileItemComparator.getComparator(FileItemComparator.NAME_SORT));

The Problem

I am sure there is something wrong in the compare method with transitive dependencies. I have tried a lot and can't seem to fix it. Actually, I never got this problem in any of my test devices, but my users are reporting it constantly.

I hope anyone here will be able to catch the problem and help me solve it once and for all.

Updated Code (Thanks to @Eran)

I thought it would be best to help others by posting the complete updated code. It will help a lot of people facing the same problem.

enum FileItemComparator implements Comparator<FileItem> {

    //Using ENUM
    NAME_SORT {
        public int compare(FileItem o1, FileItem o2) {

            if (o1 == null) {
                if (o2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null in the end
                }
            } else if (o2 == null) {
                return -1;
            }

            String n1 = o1.getFileName();
            String n2 = o2.getFileName();

            if (n1 == null) {
                if (n2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null names after non null names
                }
            } else if (n2 == null) {
                return -1;
            }
            return n1.compareTo(n2);
        }
    },
    DATE_SORT {
        public int compare(FileItem o1, FileItem o2) {

            if (o1 == null) {
                if (o2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null in the end
                }
            } else if (o2 == null) {
                return -1;
            }

            String d1 = o1.getFileDate();
            String d2 = o2.getFileDate();

            if (d1 == null) {
                if (d2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null names after non null names
                }
            } else if (d2 == null) {
                return -1;
            }

            Long l1 = Long.valueOf(d1);
            Long l2 = Long.valueOf(d2);

            if (l1 == null) {
                if (l2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null names after non null names
                }
            } else if (l2 == null) {
                return -1;
            }

            return l1.compareTo(l2);
        }
    },
    SIZE_SORT {
        public int compare(FileItem o1, FileItem o2) {

            if (o1 == null) {
                if (o2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null in the end
                }
            } else if (o2 == null) {
                return -1;
            }

            File f1 = o1.getItem();
            File f2 = o2.getItem();

            if (f1 == null) {
                if (f2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null in the end
                }
            } else if (f2 == null) {
                return -1;
            }

            Long l1 = Long.valueOf(f1.length());
            Long l2 = Long.valueOf(f2.length());

            if (l1 == null) {
                if (l2 == null) {
                    return 0;
                } else {
                    return 1; // this will put null names after non null names
                }
            } else if (l2 == null) {
                return -1;
            }

            return l1.compareTo(l2);
        }
    };

    public static Comparator<FileItem> descending(final Comparator<FileItem> other) {

        return new Comparator<FileItem>() {
            public int compare(FileItem o1, FileItem o2) {
                return -1 * other.compare(o1, o2);
            }
        };
    }

    public static Comparator<FileItem> getComparator(final FileItemComparator... multipleOptions) {
        return new Comparator<FileItem>() {
            public int compare(FileItem o1, FileItem o2) {
                for (FileItemComparator option : multipleOptions) {
                    int result = option.compare(o1, o2);
                    if (result != 0) {
                        return result;
                    }
                }
                return 0;
            }
        };
    }
}

回答1:

Let's look at your first compare method :

    public int compare(FileItem o1, FileItem o2) {

        int result = 0;
        if (o1 != null && o2 != null) {

            String n1 = o1.getFileName();
            String n2 = o2.getFileName();

            if (n1 != null && n2 != null)
                result = n1.compareTo(n2);
        }

        return result;
    }

Suppose you are comparing two FileItems (let's call them o1 and o2), one with a file name and the other without (i.e. null file name). Your method will return 0.

Now if you compare o2 with another FileItem (o3) for which the file name is not null, you return 0 again.

But if you compare o1 to o3, since both of them have non null file name, the comparison returns -1 or 1 (assuming the file names are different).

Therefore your comparison is inconsistent since it's not transitive.

If one element lacks a property required for the comparison and the other doesn't, you shouldn't return 0. You should decide whether to return 1 or -1 (depending whether, for example, the FileItems with null names should be ordered before or after the FileItems with non null names).

For example :

public int compare(FileItem o1, FileItem o2) 
{
    if (o1 == null) {
        if (o2 == null) {
            return 0;
        } else {
            return 1; // this will put null in the end
        }
    } else if (o2 == null) {
        return -1;
    }
    String n1 = o1.getFileName();
    String n2 = o2.getFileName();
    if (n1 == null) {
        if (n2 == null) {
            return 0;
        } else {
            return 1; // this will put null names after non null names 
        }
    } else if (n2 == null) {
        return -1;
    }
    return n1.compareTo(n2);
}

回答2:

This is a common mistake with comparators - you are not handling null consistently. The usual pattern would look like this:

public int compare(FileItem o1, FileItem o2) {
    // null == null
    if (o1 == null && o2 == null) {
        return 0;
    }
    // null < not null
    if (o1 == null || o2 == null) {
        return -1;
    }
    // Neither can be null now so this is safe.
    String n1 = o1.getFileName();
    String n2 = o2.getFileName();
    // Same logic again.
    if (n1 == null && n2 == null) {
        return 0;
    }
    if (n1 == null || n2 == null) {
        return -1;
    }
    return n1.compareTo(n2);
}

Added

Note that this implementation also a common mistake as I am allowing compare(null,not_null) to equal compare(not_null,null) which also violates the contract - please use @Eran's solution or something like this.

public int compare(FileItem o1, FileItem o2) {
    // null == null
    if (o1 == null && o2 == null) {
        return 0;
    }
    // null != not null
    if (o1 == null || o2 == null) {
        // Swap these around if you want 'null' at the other end.
        return o1 == null ? -1: 1;
    }
    // Neither can be null now so this is safe.
    String n1 = o1.getFileName();
    String n2 = o2.getFileName();
    // Same logic again.
    if (n1 == null && n2 == null) {
        return 0;
    }
    if (n1 == null || n2 == null) {
        // Swap these around if you want 'null' at the other end.
        return n1 == null ? -1: 1;
    }
    return n1.compareTo(n2);
}