Why does my compare method violate its general contract?

Question

public static Comparator<Container> DEPARTURE = new Comparator<Container>() {
    @Override
    public int compare(Container container1, Container container2) {
        if (container1.departure.time.isBefore(container2.departure.time))
            return -1;
        else if (container1.departure.time.equals(container2.departure.time) && 
                 container1.departure.maxDuration == container2.departure.maxDuration && 
                 container1.departure.transportCompany.equals(container2.departure.transportCompany) && 
                 container1.departure.transportType == container2.departure.transportType)
            return 0;
        else
            return +1;
    }
};

the departure variable is just an instance of an object containing the following fields:

    public DateTime time;
    public int maxDuration;
    public TransportType transportType;
    public String transportCompany;

P.S. the time object is an instance of DateTime from the Joda-Time library and TransportType is an enumeration containing the constants Train, Seaship, Barge and Truck.

EDIT:

Ok, so, I edited my comparator to the following:

    public static Comparator<Container> DEPARTURE = new Comparator<Container>() {
        @Override
        public int compare(Container container1, Container container2) {
            if (container1.departure.time.isBefore(container2.departure.time))
                return -1;
            else if (container1.departure.time.isBefore(container2.departure.time))
                return +1;
            else {
                if (container1.departure.maxDuration == container2.departure.maxDuration && container1.departure.transportType == container2.departure.transportType && container1.departure.transportCompany.equals(container2.departure.transportCompany))
                    return 0;
                else
                    return +1;
            }
        }
    };

but this obviously violates the general contract. How do I make it so it sorts by time and then sort those objects that have equivalent times by their other attributes only caring if they're equal or not? Hope this makes sense ...

EDIT: SOLUTION

Thank you all for answering my question! After studying your comments I came up with the following solution that seems to work (not thoroughly tested though):

I actually moved the comparing part to departure his class because I also need to compare by arrival. I decided to simply sort by all attributes (consecutively time, maxDuration, transportCompany and transportType) and the solution I came up with is:

    public static Comparator<Container> ARRIVAL = new Comparator<Container>() {
        @Override
        public int compare(Container container1, Container container2) {
            return container1.arrival.compareTo(container2.arrival);
        }
    };

    public static Comparator<Container> DEPARTURE = new Comparator<Container>() {
        @Override
        public int compare(Container container1, Container container2) {
            return container1.departure.compareTo(container2.departure);
        }
    };

And then the compareTo method:

    @Override
    public int compareTo(LocationMovement lm) {
        if (this.time.isBefore(lm.time))
            return -1;
        else if (this.time.isAfter(lm.time))
            return +1;
        else {
            int c = this.maxDuration - lm.maxDuration;
            if (c != 0) return c;

            c = this.transportCompany.compareTo(lm.transportCompany);
            if (c != 0) return c;

            c = this.transportType.ordinal() - lm.transportType.ordinal();
            return c;
        }
    }

If container `c1` and container `c2` have the same `departure.time`, but differ in the other attributes, then both `compare(c1,c2)` and `compare(c2,c1)` will return `+1`. — tobias_k, Jan 07 '14 at 11:20
Sidenote: Having such a huge monstrous evaluation in the `else if` is just asking for trouble. — Ceiling Gecko, Jan 07 '14 at 11:22
Thank you guys for answering. Could you take a look at my edit, please? — Yaeger, Jan 07 '14 at 11:49
Your first two `if` checks check the same condition. Also, in your "equals"-case (the new `else`) you should also have a possibility to return `-1`, or you still have the same problem as in the first approach. — tobias_k, Jan 07 '14 at 12:06
In your solution, you can, of course, change that last `if (c != 0) return c; return 0;` to `return c;`. (You could just return the result of the ordinal comparison, but it's easier to debug if you put it in `c` first.) — T.J. Crowder, Jan 08 '14 at 09:53
@T.J.Crowder Oh yes, of course! Thank you, you were helpful! — Yaeger, Jan 08 '14 at 10:04

score 4 · Answer 1 · answered Jan 07 '14 at 11:21

4

The general contract is that

COMPARATOR.compare(a, b) = - COMPARATOR.compare(b, a)

In your case, the code which returns -1 one way could return 0 the other.

answered Jan 07 '14 at 11:21

Peter Lawrey

525,659
79
751
1,130

I can see how his original code would return **`1`** in one direction but `0` in the other, but not how it could return `-1` and `0`. Doesn't matter, of course, the problem is the same. – T.J. Crowder Jan 07 '14 at 12:08

score 1 · Accepted Answer · answered Jan 07 '14 at 12:15

In order to implement compare, all of the things you check must have the concept of being "lesser," "greater," or "equal" to one another, and then you must decide the order in which to check them, returning lesser/greater for the first of the items that isn't equal. That way, you satisfy the contract that compare(a, b) must be the converse of compare(b, a). If all of the parts of what you're comparing don't have the concept of "greater" or "lesser" (for instance, transport type), then either you can't implement compare or you must force an arbitrary (but reliable) greater/lesser interpretation on them.

Here's a conceptual example of doing that. In this case, the order I've chosen (arbitrarily) is: The time, the duration, the company, and the type. But a different order may be more reasonable. This is just an example. Also, you haven't said what the type of transportType is, so I've assumed it has a compareTo method; obviously it may not and you may have to adjust that.

public static Comparator<Container> DEPARTURE = new Comparator<Container>() {
    @Override
    public int compare(Container container1, Container container2) {
        int rv;

        // Times
        rv = container1.departure.time.compareTo(container2.departure.time);
        if (rv == 0) {
            // Duration
            if (container1.departure.maxDuration < container2.departure.maxDuration) {
                rv = -1;
            }
            else if (container1.departure.maxDuration > container2.departure.maxDuration) {
                rv = 1;
            }
            else {
                // Transport company
                rv = container1.departure.transportCompany.compareTo(container2.departure.transportCompany);
                if (rv == 0) {
                    // Transport type
                    rv = container1.departure.transportType.compareTo(container2.departure.transportType);
                }
            }
        }
        return rv;
    }
};

Thank you for answering, I have edited my question containing my solution. — Yaeger, Jan 08 '14 at 09:50

score 0 · Answer 3 · edited May 23 '17 at 12:28

Note that if two containers c1 and c2 have equal departure.time, but differ in the other attributes, then both compare(c1, c2) and compare(c2, c1) will return +1, i.e., c1>c2 and c2>c1.

Instead, you should either drop the other fields entirely, or compare them separately in nested or sequential if-elses in case the departure time is equal.

Take a look at this answer to a related question for a clean way to compare objects by multiple attributes.

Why does my compare method violate its general contract?

3 Answers3