Writing a proper implementation of compareTo

Question

private static class CharacterIndex implements Comparable<CharacterIndex> {
    private final char c;
    private final int index;

    public CharacterIndex(char c, int index) {
        this.c = c;
        this.index = index;
    }
}

Now I want to override the compareTo method for this class such that if I have the following List of CharacterIndex's objects [('y', 1), ('x', 2), ('b', 3), ('a', 3)] then after sorting, the objects should be like [('b', 3), ('a', 3), ('x', 2), ('y', 1)].

Sorting Strategy:

Objects for which the index is different can be shuffled (and should be in sorted order based only on the character's value). Objects that have same index should maintain their relative order after sorting.

One more example:

For [('y', 1), ('w', 2), ('x', 3)] the sorted list should be [(w, 2), (x, 3), (y, 1)] and not [(x, 3), (w, 2), (y, 1)].

My attempt:

@Override
public int compareTo(CharacterIndex ci) {
    if (this.index == ci.index)
        return -1; // don't swap if the index is same
    return Character.compare(this.c, ci.c);
}

But this approach gives me an exception:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1312)
    at java.util.Arrays.sort(Arrays.java:1506)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:141)

I saw this. But I couldn't clearly understand why am I getting this exception.

Is there a better way to sort the List<CharacterIndex> with the above given strategy?

Answer 1

Putting @RealSkeptic's comments into answer:

The java-docs of Comparable says that:

This interface imposes a total ordering on the objects of each class that implements it.

Total-ordering should follow the following properties:

• Reflexivity
• Antisymmetry
• Transitivity
• Comparability

To see more on what totally ordered sets are see this link.

My sorting strategy is not transitive.

Suppose my initial list is [(d,2), (y,1), (b,1)]

• (y,1) < (b,1) as for same index, I don't want to shuffle the order.
• (b,1) < (d,2) as for different index, I can shuffle order and then I need to compare the character only.

By transitivity, (y,1) < (d, 2). Which is not true.

So this is not a totally ordered comparison. And hence it breaks the rule provided by Comparable interface.

So we can't have a correct implementation of compareTo (which abide by the contract of Comparable interface) for this sorting strategy.

What you learned?

Your sorting strategy should always define total ordering on the objects of class that implements Comparable

Answer 2

It's because you have o1.compareTo(o2) == -1 && o2.compareTo(o1) == -1 if o1.index == o2.index. The contract for compareTo method is that those two must be of different signs: o1.compareTo(o2) and o2.compareTo(o1).

In other words this means both that o1 is less than o2 and o2 is less than o1, which is impossible.

Possible solution:

@Override
public int compareTo(CharacterIndex ci) {
    return Character.compare(this.c, ci.c);
}

Here we are comparing by character it carries. As @RealSkeptic noticed, there is no way to take index into account as the relation is no longer transitive.