Why does this compareTo() method lead to a contract violation while sorting?

Question

I have a list of filenames and want to compare these in the following order:

• all names ending with ".rar" should come before files with ".r01", ".r02", ...
• all names ending with ".par2" should come after files with with any other suffix

So I am using the following compareTo method for one of my Java classes:

public class DownloadFile implements Comparable<DownloadFile>
{
    // custom code ...

    @Override
    public int compareTo(DownloadFile other)
    {
        if(other == null)
            throw new NullPointerException("Object other must not be null");

        // special cases -- .rar vs .par2 etc.
        String thisStr = filename.toLowerCase();
        String oStr = other.getFilename().toLowerCase();
        if(thisStr.endsWith(".rar") && oStr.matches(".*\\.r[0-9]{2,}$"))
            return -1;
        if(thisStr.matches(".*\\.r[0-9]{2,}$") && oStr.endsWith(".rar"))
            return 1;
        if(!thisStr.endsWith(".par2") && oStr.endsWith(".par2"))
            return -1;
        if(thisStr.endsWith(".par2") && !oStr.endsWith(".par2"))
            return 1;

        // normal comparison based on filename strings
        return thisStr.compareTo(oStr);
    }
}

However, on some data this leads to the following execption:

Exception in thread "Thread-12" java.lang.IllegalArgumentException: Comparison method violates its general contract!

I tried to understand what I am missing here, but I can't find the issue.
Can you spot where I am violating the contract?

PS: If I comment out the second two ifs, then the exeception is still thrown. So the problem lies with the first two ifs.

Answer 1

It is not transitive.
Linear ordering of elements is not possible.

Proof by counterexample.

Say you have got 3 DownloadFiles (c, b, a) with names in lowercase:

c.par2
b.notpar2
a.par2

To simplify I will use < for linear ordering and names in lowercase.

c.par2 < b.notpar2 and b.notpar2 < a.par2, but it is not true that c.par2 < a.par2.
This relation is not transitive.

In logic... it would be like:

cRb and bRa, but it is not true that cRa.

All you have to do is to answer how to order your files linearly...
I would go for something like this:

if(aMethodOnThis < aMethodOnOther) {
    return -1; //or 1
}
if(aCompletelyDifferentCriterium) {
    //...
}
return 0; //or return thisFileName.compareTo(otherFileName);

The return 0 at the end is quite important, because it returned for indistinguishable files.

In that case:

public class DownloadFile implements Comparable<DownloadFile>{

    String filename;

    DownloadFile(String filename) {
        this.filename = filename;
    }

    public String getFilename() {
        return this.filename;
    }

    @Override
    public String toString() {
        return this.getFilename();
    }

    @Override
    public int compareTo(DownloadFile downloadFile) {
        String thisStr = this.filename.toLowerCase();
        String oStr = downloadFile.getFilename().toLowerCase();
        if(thisStr.endsWith(".rar")) {
            if(!oStr.endsWith(".rar"))
                return -1;
        }
        if(oStr.endsWith(".rar")) {
            if(!thisStr.endsWith(".rar"))
                return 1;
        }
        if(thisStr.matches(".*\\.r[0-9]{2,}$")) {
            if(!oStr.matches(".*\\.r[0-9]{2,}$"))
                return -1;
        }
        if(oStr.matches(".*\\.r[0-9]{2,}$")) {
            if(!thisStr.matches(".*\\.r[0-9]{2,}$"))
                return 1;
        }
        if(thisStr.endsWith(".par2")) {
            if(!oStr.endsWith(".par2"))
                return -1;
        }
        if(oStr.endsWith(".par2")) {
            if(!thisStr.endsWith(".par2"))
                return 1;
        }
        return thisStr.compareTo(oStr);
    }

    public static void main(String[] args) {
        List<DownloadFile> fileList = new ArrayList<>();
        fileList.add(new DownloadFile("a.rar"));
        fileList.add(new DownloadFile("b.rar"));
        fileList.add(new DownloadFile("a.r01"));
        fileList.add(new DownloadFile("b.r01"));
        fileList.add(new DownloadFile("a.r10"));
        fileList.add(new DownloadFile("b.r10"));
        fileList.add(new DownloadFile("a.par2"));
        fileList.add(new DownloadFile("b.par2"));
        fileList.add(new DownloadFile("a.other"));
        fileList.add(new DownloadFile("b.other"));
        Collections.shuffle(fileList);
        Collections.sort(fileList);
        System.out.println(fileList);
    }
}

To make it shorter Predicate<String> from Java 8 comes in handy ;)

@Override
public int compareTo(DownloadFile downloadFile) {
    String thisStr = this.filename.toLowerCase();
    String oStr = downloadFile.getFilename().toLowerCase();
    List<Predicate<String>> conditionList = new ArrayList<>();
    conditionList.add(s -> s.endsWith(".rar"));
    conditionList.add(s -> s.matches(".*\\.r[0-9]{2,}$"));
    conditionList.add(s -> s.endsWith(".par2"));
    for(Predicate<String> condition : conditionList) {
        int orderForCondition =
                conditionHelper(thisStr, oStr, condition);
        if(orderForCondition != 0)
            return orderForCondition;
    }
    return thisStr.compareTo(oStr);
}

private int conditionHelper(String firstStr, String secondStr,
                            Predicate<String> condition) {
    if(condition.test(firstStr))
        if(!condition.test(secondStr))
            return -1;
    if(condition.test(secondStr))
        if(!condition.test(firstStr))
            return 1;
    return 0;
}