Sorting ArrayList: Comparison method violates its general contract

Question

I am trying to make a search auto-complete feature in an android app. There is list of business names and also a list business types that I am putting into one arraylist, scoring according to a fuzzy search algorithm, and then sorting the list based on the scores against the search term. I want business types that score the same as a business name to appear first. I wrap the instances of Business and BusinessType in this class as they are scored, add to list and then sort :

public class SearchMatch<T extends NameMatcher> implements Comparable<SearchMatch> {

    public T data;
    public int score;

    public SearchMatch(T data, int score) {
        this.data = data;
        this.score = score;
    }


    @Override
    public int compareTo(SearchMatch o) {
        if(this.score == o.score && this.data instanceof BusinessType 
            && o.data instanceof Business){
            return -1;
        }
        return o.score - this.score;
    }
}

... but this does not work. I get a "Comparison method violates its general contract." from Collections.sort - and nothing else in logcat.

I cant see what is wrong with it or how it violates transitivity (from other similar posts). The strange thing is if I return 1 instead of -1 I dont get the error but I get the wrong order of preference.

Thanks

Solved

public class SearchMatch<T extends NameMatcher> implements      Comparable<SearchMatch> {

public final T data;
public final int score;

public SearchMatch(final T data,final  int score) {
    this.data = data;
    this.score = score;
}


@Override
public int compareTo(SearchMatch o) {
    if(this.score == o.score && this.data instanceof BusinessType 
        && o.data instanceof Business){
        return -1;
    }

    if(this.score == o.score && this.data instanceof Business 
        && o.data instanceof BusinessType){
        return 1;
    }
    return o.score - this.score;
}
}

No if the name of a type of business scores the same as the name of an actual business i need it to placed before the business. — maturecheese, Dec 17 '16 at 01:23
Your solution could still break if `o.score - this.score` overflows. — Stephen C, Dec 17 '16 at 01:45

score 2 · Answer 1 · answered Dec 17 '16 at 01:26

You have violated the contract of comparator found in the comparator javadoc that states

sgn(compare(x, y)) == -sgn(compare(y, x))

Essentially you return -1 for both instances of x and y such that the if statement holds. This is a violation of the compartor contract. You should try returning 0 or throwing an exception if it should not occur.

Stephen C · Accepted Answer · 2016-12-17T01:35:09.340

2

Consider this:

Suppose you have an two objects b and bt that have the same score, one is a Business and the other is a BusinessType.

compareTo(bt, b) -> -1
compareTo(b, bt) -> 0   // Incorrect!  This should be >= 0.

Another potential problem is that o.score - this.score does not take account of integer overflow.

It is also possible that you are changing the values of score and/or data, or that the values are inconsistent due to incorrect synchronization. I recommend that you declare the two fields to be final. That will make the class immutable, and will also remove the need for synchronization (in this respect at least).

(Please refer to the other answers for the explanation of the "contract" that you are violating.)

edited Dec 17 '16 at 01:35

answered Dec 17 '16 at 01:29

Stephen C

698,415
94
811
1,216

I am using an executor with a single thread (i just cancel the scoring and sorting if there is a new key entered and start again), there can't be any synchonization problem. will make fields final. – maturecheese Dec 17 '16 at 01:39
@maturecheese - Still, if you make the fields final you remove the possibility that the problem is caused by mutation. Also, remember that other people with a similar problem to yours (and reading this Q&A) *could* be using the code in a multi-threaded context. *This answer is for them as well as you!* – Stephen C Dec 17 '16 at 01:43
Good point, thanks, and updated – maturecheese Dec 17 '16 at 01:46

score 0 · Answer 3 · answered Dec 17 '16 at 01:25

Here is the documentation for Comparable. It states the following:

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. (This implies that x.compareTo(y) must throw an exception if y.compareTo(x) throws an exception.)

The implementor must also ensure that the relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.

Your example does not seem to be satisfying these hence, the warning.

Sorting ArrayList: Comparison method violates its general contract

3 Answers3