I have a list of points where each point is a tiny list of size 2. I want to sort the list of points in increasing order of x and if x values are equal, I break tie by sorting in decreasing order of y.

I wrote a custom comparator to sort the points like this:

Collections.sort(points, (a, b) -> {
    if (a.get(0) != b.get(0)) {
        return a.get(0) - b.get(0);
    } return b.get(1) - a.get(1); 
});

Here's the input before sorting:

(2, 1000)
(9, -1000)
(3, 15)
(9, -15)
(5, 12)
(12, -12)
(5, 10)
(10001, -10)
(19, 8)
(10001, -8)

Here's the result produced after sorting with the above comparator:

(2, 1000)
(3, 15)
(5, 12)
(5, 10)
(9, -15)
(9, -1000)
(12, -12)
(19, 8)
(10001, -10)
(10001, -8)

Observations:-

1. The input is sorted in ascending order on x.
2. (5, 12) was correctly put before (5, 10).
3. (9, -15) was correctly put before (9, -1000).
4. However, (10001, -10) was put before (10001, -8). Even though -8 is larger than -10.

Feel like I am missing something trivial. I experimented with a few other ways of writing the comparator like using Integer.compare(a, b) or just a.compareTo(t), but got the same result.

Finally, I changed the representation of point from List<Integer> to int[] and wrote the same comparator again. See results below:

Collections.sort(points, (a, b) -> {
    if (a[0] != b[0])
        return a[0] - b[0];
    return b[1] - a[1];
});

Input before sorting:

(2, 1000)
(9, -1000)
(3, 15)
(9, -150
(5, 12)
(12, -12)
(5, 10)
(10001, -10)
(19, 8)
(10001, -8)

After sorting:

(2, 1000)
(3, 15)
(5, 12)
(5, 10)
(9, -15)
(9, -1000)
(12, -12)
(19, 8)
(10001, -8)
(10001, -10)

So list of arrays is getting sorted correctly as (10001, -8) was correctly put before (10001, -10).

I am not able to understand why changing the representation of point resolved the issue and hence this question. I can give more details on how I am creating the List of points if required.

CodePudding user response：

I am missing something trivial

Method equals() should be used for object comparison. Double equals == checks whether two references point to the same object in memory.

Change the condition inside the comparator to !a.get(0).equals(b.get(0)).

So list of arrays is getting sorted correctly as (10001, -8) was correctly put before (10001, -10).

The reason for such behavior is that JVM cashes all the instances of Integer (as well as Byte, Short and Long) in the range [-128; 127]. I.e. these instances are reused, the result of autoboxing of let's say int with a value of 12 will be always the same object.

Because small values in your example like 3, 5, 12 will be represented by a single object, they were compared with == without issues. But the result for of comparison with == for two Integer instances with a value of 10001 will be false because in this case there will be two distinct objects in the heap.

The approach of cashing frequently used objects is called the Flyweight design pattern. It's very rarely used in Java because this pattern can bring benefits when tons of identical objects are being created and destroyed. Only in such a case cashing these objects will pay off with significant performance improvement. As far as I know, it's used in game development.

And as Code-Apprentice has pointed out in his answer, Point must an object, not a list. Use the power of objects and don't overuse collections. It brings many advantages: class provides you a structure, it's easier to organize your code when you are thinking in terms of objects, behavior declared inside a class is reusable. Point could be able for instance to whether are they aligned horizontally or vertically. And you can implement Comparable interface in this class so that points will be able to compare themselves without a Comparator.

CodePudding user response：

@Alexander Ivanchenko explains very well why you are seeing the behavior you do. One solution to the problem is to use Integer.compareTo():

Collections.sort(points, (a, b) -> {
    int xCompare = a[0].compareTo(b[0];
    if (xCompare != 0) {
        return xCompare;
    }
    retirm a[1].compareTo(b[1];
});

Beyond this, I suggest creating a Point class:

class Point {
    public int x;
    public int y;
}

Here I use public fields to follow the struct pattern. If you want to add getters and setters and other behavior, feel free to do so. Using a class to represent the structure of your data makes the code more understandable and easier to maintain. In fact, you can easily implement Comparable on a Point.