Consider I have a library call which accepts:

1. a list of items (of mixed/multiple types T1, T2, T3,..), and
2. a custom comparator C,

and, in addition to doing some work, sorts the list it accepts (first by type, and then using the custom comparator C).

Now, I need items of type T1 sorted by type and then using the custom order, while items of all other types (T2, T3,..) sorted by type only (i. e., once sorted by type, consequently sorted only with a no-op, order-preserving comparator).

In other words, I need smth like this (T1 is java.lang.Integer, T2 is java.lang.String):

import java.util.Comparator;
import java.util.List;

import static java.util.Arrays.asList;
import static java.util.Comparator.comparing;
import static java.util.Comparator.comparingInt;

class C {
    /**
     * The library call.
     */
    static <T> void processAndSort(final List<T> items,
                       final Comparator<? super T> secondaryComparator) {
        final Comparator<T> typeComparator = comparing(it -> it.getClass().getName());

        items.sort(typeComparator.thenComparing(secondaryComparator));

        // Do some extra work.
    }

    public static void main(final String ... args) {
        final List<?> items = asList(13, "Lorem",
                         8, "ipsum",
                         5, "dolor",
                         3, "sit",
                         2, "amet",
                         1, "consectetur",
                         1, "adipiscing");

        processAndSort(items, (final var left, final var right) -> {
            final Class<?> clazz = left.getClass();

            /*
             * Should be already sorted by type.
             */
            if (!clazz.equals(right.getClass())) {
                throw new IllegalStateException();
            }

            if (clazz.equals(Integer.class)) {
                /*
                 * Compare integers using a custom comparator.
                 */
                return comparingInt(Integer::intValue).compare((Integer) left, (Integer) right);
            }

            /*
             * For all other types, retain the original order.
             */
            return 0;
        });

        System.out.println(items);
    }
}

The above code, when run, will produce the following output:

[1, 1, 2, 3, 5, 8, 13, Lorem, ipsum, dolor, sit, amet, consectetur, adipiscing]

Now, provided that both Merge Sort and Timsort algorithms (used by the JDK to sort non-primitives) are stable, is it okay for my custom comparator to return 0 for the pairs where the order should be preserved?

Do any other alternatives exist?

CodePudding user response：

Yes, it is ok to use such a Comparator for sorting a List.

Collections.sort() (and List.sort() with very similar wording) only requires that

All elements in the list must be mutually comparable using the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the list).

and goes on

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

Neither does the contract for Comparator impose any further restrictions that would forbid such an implementation - it only cautions that such an order is not "consistent with equals" and therefore cannot be used with certain maps or sets.

CodePudding user response：

Yes, but.

Two important concerns:

1. Yes, comparators have the concept of 'on equal levels', meaning: objects that may not neccessarily be equal in the sense of 'same hashCode() and a.equals(b) is true' but for which the comparator indicates they are on the same level (compare(a, b) == 0). However, what that means is up to the thing that uses the comparator. For List.sort specifically, that merely means that everything that is 'at the same level' will be next to each other, and additionally that the ordering is stable, meaning, whatever ordering they had before you started sorting is the order they get afterwards. But that is just what List's sort does - for example a TreeSet states that you can only have 1 such element; if the comparator says that 2 items are on the same level, as far as TreeSet/TreeMap is concerned, they are equal, and therefore you can't have 2 items in one treeset for which compare(a, b) == 0, even if !a.equals(b). So, whilst the answer is 'yes' to this question, be aware that you can't universally use this 'comparator says they are on the same level'.

2. it's perfectly acceptable for a comparator to report compare(a, b) == 0 for non-equal a/b, but there are other rules that are not up for debate. ALL comparators must always adhere to these rules; failure to do this is a problem regardless of what you're using the comparator for:

• compare(a, a) == 0 must always hold.
• if compare(a, b) < 0, then compare(b, a) > 0 must always hold.
• if compare(a, b) < 0 and compare(b, c) < 0, then compare(a, c) < 0 must hold.

This comparator:

Comparator<Object> communism = (a, b) -> 0;

DOES adhere to all these rules, so, sure, you can do that.