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.

First of all, do you know one of the most probable cause of this error? http://stackoverflow.com/a/8327575/1743880 — Tunaki, Mar 04 '17 at 22:25
And all files with ".r02" endings have to come before those with ".par" at the end? — Grzegorz Górkiewicz, Mar 04 '17 at 23:09
@GrzegorzGórkiewicz You mean before those with ".par2" at the end? Yes, that is correct. — Matthias, Mar 04 '17 at 23:11
Furthermore, your comparator is not declared correctly. `compareTo` should take an argument of type `DownloadFile`. You should not use `instanceof`! (Even if it does make the `null` check redundant.) Throwing an exception for `null` seems harsh, but it's the author's (your) choice. Why didn't the compiler warn you that you weren't actually overriding `compareTo`? Did you declare the `Comparator` as a raw type? Don't. — Lew Bloch, Mar 04 '17 at 23:11
Why are you ignoring case in the comparison? That could cause different files to seem equal in name. — Lew Bloch, Mar 04 '17 at 23:12
@LewBloch When I use `DownloadFile` as argument type, **then** the compiler is warning me that I would not override the method. So why (how?) would I use `DownloadFile` as argument then? — Matthias, Mar 04 '17 at 23:14
You declared the type wrong. You only showed part of your code, and the error is in the part you didn't show. I ask again, did you declare the `Comparator` as a raw type? — Lew Bloch, Mar 04 '17 at 23:16
@LewBloch My class is implementing the `Comparable` interface, as shown in the updated code above. Does this answer your question? — Matthias, Mar 04 '17 at 23:19
Not directly, because you should have been able to say, "Why, yes, I did declare it as a raw type!" That is why your override is backwards. `Comparator` is a generic type, and should be used as `implements Comparator`. Do not use raw types. Do bother to look up what "raw type" means, especially if someone is asking you about it, which is a rather broad hint that it might just possibly be relevant to you. — Lew Bloch, Mar 04 '17 at 23:21
A small point: according to [the `Comparable` documentation](https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#compareTo-T-), the wrong type should throw `ClassCastException`, not `IllegalArgumentException`. — Chai T. Rex, Mar 04 '17 at 23:24
@LewBloch You're absolutely right, thanks for the feedback. I have changed the class to `public class DownloadFile implements Comparable` and the method to `public int compareTo(DownloadFile other)`. — Matthias, Mar 04 '17 at 23:27

Grzegorz Górkiewicz · Accepted Answer · 2017-03-05T00:12:30.613

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;
}

But the `if(aMethodOnThis < aMethodOnOther)` you recommend, am I not doing that with my `if` already? — Matthias, Mar 04 '17 at 23:02
Yes, you do it. But your conditions are not so different. In your case it boils down to the decision... you want files with `.par2` endings to come first before other files or not? I think two if conditions out of 4 at the end are redundant. — Grzegorz Górkiewicz, Mar 04 '17 at 23:04
I have added an explanation of the desired ordering logic to my original question. — Matthias, Mar 04 '17 at 23:09
I understand what you mean with "not transitive", but I don't understand **why** this is the case. Following your example my code would result in `b.notpar2 < a.par2` and `b.notpar2 < c.par2` and `a.par2 < c.par2` ... or wouldn't it? — Matthias, Mar 04 '17 at 23:23
@Matthias, it does not matter. If your code behaves like that it says nothing about its transitiveness. A relation R is transitive, iff for all elements from the given set: `aRb` and `bRc` implies `aRc`. In your example about `bRa` and `bRc`... transitiveness says nothing on the order of `a` and `c`. — Grzegorz Górkiewicz, Mar 04 '17 at 23:46

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

1 Answers1