Sorting list of files in android throwing 'Comparison method violates its general contract!'

Question

It's happening on my Android application & here is the stack trace:

Caused by 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.mergeForceCollapse(TimSort.java:422)
       at java.util.TimSort.sort(TimSort.java:219)
       at java.util.TimSort.sort(TimSort.java:169)
       at java.util.Arrays.sort(Arrays.java:2023)
       at java.util.Collections.sort(Collections.java:1883)

Here is my sort logic:

private static void sortFiles(List<File> listFiles, int sortDirection) {
    try {
      if (sortDirection == sortLatestFirst) {
        Collections.sort(listFiles, new LatestFirstComparator());
        ...

Here is the comparator:

class LatestFirstComparator implements Comparator<File> {
  @Override
  public int compare(File f1, File f2) {
    return Long.compare(f2.lastModified(), f1.lastModified());
  }
}

I've found related questions & other solutions, but none of them solves my problem. Moreover, this is not a consistent behavior, but happening only with some of the app users.

Answer 1

As said by others, the problem lies in the fact that the value of the last modified timestamp can change during the sort operation. In order to sort reliably, you have to cache the values for the duration of the sort operation:

private static void sortFiles(List<File> listFiles, int sortDirection) {
    if(listFiles.isEmpty()) return;
    Map<File,Long> cache = new HashMap<>();
    Comparator<File> byTime
        = Comparator.comparing(f -> cache.computeIfAbsent(f, File::lastModified));
    if(sortDirection == sortLatestFirst) byTime = byTime.reversed();
    listFiles.sort(byTime);
}

I assume that you use a notification mechanism for changes anyway, to decide when to reload the file list, so the sorting operation does not need to deal with it.

If you want to support an API level that doesn’t support Java 8 features, you have to use the more verbose variant

private static void sortFiles(List<File> listFiles, int sortDirection) {
    if(listFiles.isEmpty()) return;
    final Map<File,Long> cache = new HashMap<File,Long>();
    Comparator<File> byTime = new Comparator<File>() {
        @Override
        public int compare(File f1, File f2) {
            Long t1 = cache.get(f1), t2 = cache.get(f2);
            if(t1 == null) cache.put(f1, t1 = f1.lastModified());
            if(t2 == null) cache.put(f2, t2 = f2.lastModified());
            return t1.compareTo(t2);
        }
    };
    if(sortDirection == sortLatestFirst) byTime = Collections.reverseOrder(byTime);
    Collections.sort(listFiles, byTime);
}

Answer 2

EDIT: Following an advice from the comment by User Holger I'm expanding the answer by adding here important points from my previous comments. They are put in quotation blocks.

As I pointed out in comments, most probably some of the files being sorted are modified during the sorting. Then, what was initially an old file becomes a new file during sorting:

e.g. file A is detected as newer than B, and B newer than C, but then C is modified and appears newer than A

Thus the ordering relation 'is newer' appears non-transitive, which breaks the contract; hence the error.

If you need stable data, I suppose you could make your own objects with copies of necessary attributes; then the ordering will be well-defined, but... the final order may appear obsolete if files are modified during sorting. Anyway you can't avoid that in a multitasking environment; you'll never know when some other thread or process creates, modifies or deletes files until you re-scan the directory

IMHO you can only write your own sorting routine, which would handle such non-transitivity safely. For example it can reiterate when it detects the situation. But take care not to iterate too many times - if two or more files get updated constantly, the re-sorting routine could never finish its work!