CODEWITHSUNDEEP
javasortingcollections
Ôrel
Ôrel

Reputation: 7632

Comparator general contract violation

I have read all thread about transitive comparator, I don't get why this comparator function is violating a rule. If someone can clean my eyes, it is quite simple I think but I cannot get it

Stack is:

java.util.TimSort.mergeLo(TimSort.java:747)
java.util.TimSort.mergeAt(TimSort.java:483)
java.util.TimSort.mergeCollapse(TimSort.java:410)

my object (simplified)

public class SleepDetails  {
    private DateTime time;
    private SleepEnum type;
    [...]
}

public enum SleepEnum {
    DEEP(0), LIGHT(1), AWAKE(2), BEGIN(16), END(17);
    [...]
}

The comparator a static into a class

Comparator<SleepDetails> comparator = new Comparator<SleepDetails>(){
        public int compare(SleepDetails arg0, SleepDetails arg1) {
            int res = arg0.getTime().compareTo(arg1.getTime());
            if (res != 0)
                return res;
            if (arg0.getType() == arg1.getType())
                return 0;
            switch(arg0.getType()) {
              case BEGIN:
                return -1;
              case END:
                return 1;
              default:
                return 0;
            }
        }
    };

Mainly I want to sort the events by date, in case of two events with the same datetime put begin event first and end event as last.

I don't have the collection triggering the bug

Upvotes: 1

Views: 698

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

The problem is that your code does not distinguish enum values for the type other than BEGIN and END. In particular, it returns zero when the first type is neither BEGIN nor END, regardless of the second type.

However, this behavior is not symmetrical: if you swap the two items in a pair BEGIN and LIGHT, you would get -1 and 0, breaking the symmetry.

You can treat all types other than BEGIN and END as equal to each other, but then you need to use both sides when deciding the equality.

Upvotes: 1

Eran
Eran

Reputation: 393936

If you compare two SleepDetails instances having the same getTime(), and one of them has getType() BEGIN and the other AWAKE.

compare (one, two)

would give -1

while 

compare (two, one)

would give 0

This violates the contract :

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

You must also check arg1.getType() in your compare method (whenever arg0.getType() is neither BEGIN nor END).

    public int compare(SleepDetails arg0, SleepDetails arg1) {
        int res = arg0.getTime().compareTo(arg1.getTime());
        if (res != 0)
            return res;
        if (arg0.getType() == arg1.getType())
            return 0;
        switch(arg0.getType()) {
          case BEGIN:
            return -1;
          case END:
            return 1;
          default:
            switch(arg1.getType()) {
              case BEGIN:
                return 1;
              case END:
                return -1;
              default:
                return 0;
            }
        }
    }

Upvotes: 5

Related Questions