0

When I write a RankedObject class which implements Comparable<RankedObject>:

public static class RankedObj implements Comparable<RankedObj>      {
    int i;
    public RankedObj(int i)     {
        this.i=i;
    }

    @Override
    public String toString() {
        return "RankedObj [i=" + i + "]";
    }


    @Override
    public int compareTo(RankedObj o) {
        if(this.i == 3)     {  // '3' will always be the smallest item
            return -1;
    }
    return this.i-o.i;
}

I want to make the list of RankedObject "in ascending order on the whole, at the same time, the number 3 to always be the smallest one". When testing, I found the order of the original list really affects the result, and the result is not correct in some cases. Namely:

//----CASE 1----
List<RankedObj> list = new ArrayList<>();
list.add(new RankedObj(11));
list.add(new RankedObj(1));
list.add(new RankedObj(12));
list.add(new RankedObj(3));
list.add(new RankedObj(8));
Collections.sort(list);
System.out.println(list);

//output (as I intend)
[RankedObj [i=3], RankedObj [i=1], RankedObj [i=8], RankedObj [i=11], RankedObj [i=12]]

//----CASE 2----
List<RankedObj> list = new ArrayList<>();
list.add(new RankedObj(11));
list.add(new RankedObj(12));
list.add(new RankedObj(3));
list.add(new RankedObj(8));
list.add(new RankedObj(1));
Collections.sort(list);
System.out.println(list);

//output (not what my Comparable intends)
[RankedObj [i=1], RankedObj [i=3], RankedObj [i=8], RankedObj [i=11], RankedObj [i=12]]

Could anyone tell my why? as well as how can I realize the purpose of making the list in ascending order on the whole while '3' being the smallest item? Thanks a lot!

P.S. According to my test using a Comparator in which the code is the same as the code in Comparable, the result is the same:

Collections.sort(list, new Comparator<RankedObj>() {
    @Override
    public int compare(RankedObj o1, RankedObj o2) {
        if(o1.i == 3)       {
            return -1;
    }
    return o1.i-o2.i;
    }
});
4

2 回答 2

3

Your comparison isn't symmetric.

Consider these two calls:

RankedObj x = new RankedObj(1);
RankedObj y = new RankedObj(3);
System.out.println(x.compareTo(y)); // -2
System.out.println(y.compareTo(x)); // -1

They should both give an answer of 0, or give answers with opposite signs. Instead, they'll both return a negative value - because in the first call, o1.i is 1 (not 3) so it will fall back to o1.i - o2.i - which is still negative.

Additionally, you have a problem that if you have a very strongly negative value, when you subtract a strongly positive value from it, the subtraction will overflow.

You need to fix it to be symmetric and to avoid overflow. This should do it:

@Override
public int compareTo(RankedObj o) {
    // Handle equality first
    if (this.i == o.i) {
        return 0;
    }
    // Handle the magic value correctly on *both* sides
    if(this.i == 3) {
        return -1;
    }
    if (o.i == 3) {
        return 1;
    }
    // Fall back to normal comparsions
    return Integer.compare(i, o.i);
}
于 2013-04-16T13:23:01.827 回答
2

Try:

@Override
public int compare(RankedObj o1, RankedObj o2) {
    if(o1.i == o2.i){       {
        return 0;
    } else if(o1.i == 3)       {
        return -1;
    } else if (o2.i == 3){
        return 1;
    }
return o1.i-o2.i;
}

The implemenation assumes you're only using small numbers which don't result in an overflow when subtracting one value from the other.

于 2013-04-16T13:24:06.630 回答