Find the case where comparator might not work

Question

I want to sort the List of (List of Integers) so that the list that contains number 3 is put on top of the list ,leaving the existing order of remaining elements intact.

    final ArrayList<ArrayList<Integer>> arrayLists = Lists.newArrayList(
        Lists.newArrayList(1, 2),
        Lists.newArrayList(1, 2, 3),
        Lists.newArrayList(1, 2),
        Lists.newArrayList(1, 3),
        Lists.newArrayList(1, 4),
        Lists.newArrayList(1, 2, 3)
    );
    System.out.println(arrayLists);

which is

[[1, 2], [1, 2, 3], [1, 2], [1, 3], [1, 4], [1, 2, 3]]

Initial attempt is with below comparator

Comparator<List<Integer>> c = new Comparator<List<Integer>>() {
    @Override
    public int compare(final List<Integer> o1, final List<Integer> o2) {
        System.out.println("Compare " + o1 + "<=>" + o2);
        if (o1.contains(3))
            return -1;
        return 0;
    }
};

Collections.sort(arrayLists, c);
System.out.println(arrayLists);

returns

Compare [1, 2, 3]<=>[1, 2]
Compare [1, 2]<=>[1, 2, 3]
Compare [1, 2]<=>[1, 2]
Compare [1, 3]<=>[1, 2]
Compare [1, 3]<=>[1, 2, 3]
Compare [1, 4]<=>[1, 2]
Compare [1, 4]<=>[1, 2]
Compare [1, 2, 3]<=>[1, 2]
Compare [1, 2, 3]<=>[1, 2, 3]
Compare [1, 2, 3]<=>[1, 3]

[[1, 2, 3], [1, 3], [1, 2, 3], [1, 2], [1, 2], [1, 4]]

which is what is expected (All lists that contain 3 are at the top)

However looking deeper at javadoc for Comparator suggests that

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

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z

Which is not fully implemented by above comparator, which can easily asserted with test below .

    final ArrayList<Integer> x = Lists.newArrayList(1, 2, 3);
    final ArrayList<Integer> y = Lists.newArrayList(1, 2);
    System.out.println(c.compare(x,y));
    System.out.println(c.compare(y,x));


Compare [1, 2, 3]<=>[1, 2] => -1
Compare [1, 2]<=>[1, 2, 3] => 0 which is not -(-1)

Is there any way to actually prove that above comparator does not work with some particular example List (Where it doesn't put the list that contains 3 to the top)?

Answer 1

Is there any way to prove that above comparator does not work in some cases?

Yes. The most obvious reason is that it can return -1 but never a positive number. This clearly violates the first rule.

A comparator that does not break the rules is

Comparator<List<Integer>> c = new Comparator<List<Integer>>() {
    @Override
    public int compare(final List<Integer> o1, final List<Integer> o2) {
        return Integer.compare(o1.contains(3) ? 0 : 1, o2.contains(3) ? 0 : 1);
    }
};

In Java 8, you can simplify this to

Comparator<List<Integer>> c = Comparator.comparingInt(o -> o.contains(3) ? 0 : 1);

I recommend using the new methods Comparator.comparingX. In addition to reducing verbosity, it also makes it much easier to write correct compare methods.

This works, and the documentation of Collections.sort guarantees that

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

An alternative approach would be to iterate over the original list and form two separate lists, one containing lists containing 3, the other containing lists not containing 3, then use addAll at the end. This has better time complexity than the approach using sort (O(n) rather than O(n log n)).

Answer 2

There are some suggestions for improving the comparator or making the comparator valid according to the constraints that are mentioned in the documentation.

However the actual question was

Is there any way to actually prove that above comparator does not work with some particular example List (Where it doesn't put the list that contains 3 to the top)?

And the answer is: Yes, there is.

This may not be what your actual intention was behind this question. But a very pragmatic check could look like this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ComparatorTest
{
    public static void main(String[] args)
    {
        List<List<Integer>> arrayLists = new ArrayList<List<Integer>>(
            Arrays.asList(
            Arrays.asList(1, 2),
            Arrays.asList(1, 2, 3),
            Arrays.asList(1, 2),
            Arrays.asList(1, 3),
            Arrays.asList(1, 4),
            Arrays.asList(1, 2, 3)
        ));
        System.out.println(arrayLists);
        Comparator<List<Integer>> c = new Comparator<List<Integer>>() {
            @Override
            public int compare(final List<Integer> o1, final List<Integer> o2) {
                //System.out.println("Compare " + o1 + "<=>" + o2);
                if (o1.contains(3))
                    return -1;
                return 0;
            }
        };

        Collections.sort(arrayLists, c);
        System.out.println(arrayLists);        

        validate(arrayLists, c);;
    }

    private static <T> void validate(
        List<T> list, Comparator<? super T> comparator)
    {
        for (int i=0; i<list.size(); i++)
        {
            for (int j=0; j<list.size(); j++)
            {
                T x = list.get(i);
                T y = list.get(j);
                int xy = comparator.compare(x, y);
                int yx = comparator.compare(y, x);

                if (Math.signum(xy) != -Math.signum(yx))
                {
                   System.out.println(
                       "The implementor must ensure that " +
                       "sgn(compare(x, y)) == -sgn(compare(y, x)) " +
                       "for all x and y.");
                   System.out.println("This is not the case for x="+x+", y="+y);
                }
                for (int k=0; k<list.size(); k++)
                {
                    T z = list.get(k);
                    int yz = comparator.compare(y, z);
                    int xz = comparator.compare(x, z);
                    if (xy > 0 && yz > 0)
                    {
                        if (xz <= 0)
                        {
                            System.out.println(
                                "The implementor must ensure that " +
                                "the relation is transitive: " +
                                "((compare(x, y)>0) && (compare(y, z)>0)) " +
                                "implies compare(x, z)>0.");
                            System.out.println(
                                "This is not the case for " +
                                "x="+x+", y="+y+", z="+z);
                        }
                    }

                    if (xy == 0)
                    {
                        if (Math.signum(xz) != -Math.signum(yz))
                        {
                            System.out.println(
                                "Ihe implementor must ensure that " +
                                "compare(x, y)==0 implies that " +
                                "sgn(compare(x, z))==sgn(compare(y, z)) " +
                                "for all z");
                            System.out.println(
                                "This is not the case for " +
                                "x="+x+", y="+y+", z="+z);
                        }
                    }
                }
            }
        }
    }
}

The output of this program is

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.
This is not the case for x=[1, 2, 3], y=[1, 2, 3]
The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.
This is not the case for x=[1, 2, 3], y=[1, 3]
...
Ihe implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z
This is not the case for x=[1, 2], y=[1, 2, 3], z=[1, 2, 3]
Ihe implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z
This is not the case for x=[1, 2], y=[1, 2, 3], z=[1, 3]
...

listing all the violations of the contract for the given comparator and the given list.

Answer 3

The problem is you're not returning 1. You need to be accounting for all cases in your compare. So what you should have is

Comparator<List<Integer>> c = new Comparator<List<Integer>>() {
    @Override
    public int compare(final List<Integer> o1, final List<Integer> o2) {
        System.out.println("Compare " + o1 + "<=>" + o2);
        if (o1.contains(3) && !o2.contains(3)) {
            return -1;
        } else if (!o1.contains(3) && o2.contains(3)) {
            return 1;
        } else {
            return 0;
        }
    }
};

UPDATE

To prove that your compare doesn't work in some cases, let x be a List containing 3 and y be a List not containing 3. From your compare we have sgn(compare(x, y)) as negative and sgn(compare(y, x)) as zero, invalidating the first condition of the Comparator contract.

Furthermore, you can't have any sort of transitivity since your compare doesn't ever return a positive value. This invalids the other two conditions of the contract.

In general, you want to try to account for all cases where possible. This will ensure stable code.

Answer 4

If you want to preserve order try this initial data:

 final ArrayList<ArrayList<Integer>> arrayLists = Lists.newArrayList(
    Lists.newArrayList(3, 1, 2),        
    Lists.newArrayList(1, 2),
    Lists.newArrayList(1, 2, 3),
    Lists.newArrayList(1, 2),
    Lists.newArrayList(1, 3),
    Lists.newArrayList(1, 4),
    Lists.newArrayList(1, 2, 3)
);

And you can see that order is not preserved as final result is:

[[1, 2, 3], [1, 3], [1, 2, 3], [3, 1, 2], [1, 2], [1, 4]]

Your comparator always put lists containing the 3 value on top, but it doesn't ensure that order is preserved. To do so you must implement symmetric comparation as stated in documentation.