CODEWITHSUNDEEP
javalistjava-8comparator
errantlinguist
errantlinguist

Reputation: 3828

Java 8: Idiomatically creating a Comparator for ordering objects based on their index in a List

What is the most idiomatic way of creating a Comparator<T> instance in Java 8 which defines an ordering of objects based on their relative index in a given List but nevertheless defines an object not present in that list as being "after" those which are in the list? — if I simply use List.indexOf(Object), objects not in the list will always be before those in the list due the fact that -1 is returned for all objects not in the list, which is less than any "true" index:

    final List<String> ordering = Arrays.asList("foo", "bar");
    final Comparator<String> orderingComparator = Comparator.comparingInt(ordering::indexOf);
    final String str1 = "foo";
    final String str2 = "baz";
    final String msg;
    final int cmp = orderingComparator.compare(str1, str2);
    if (cmp < 0) {
        msg = String.format("Element \"%s\" is ordered before \"%s\".", str1, str2);
    } else if (cmp > 0) {
        msg = String.format("Element \"%s\" is ordered after \"%s\".", str1, str2);
    } else {
        msg = String.format("Element \"%s\" is equal to \"%s\".", str1, str2);
    }
    System.out.println(msg);

This prints

Element "foo" is ordered after "baz".

whereas my desired behavior would print

Element "foo" is ordered before "baz".

Upvotes: 2

Views: 2785

Answers (3)

Stuart Marks
Stuart Marks

Reputation: 132460

+1 to Bubletan for mentioning Integer.compareUnsigned. As noted there, the overload of Comparator.comparing that takes a "downstream" Comparator consumes only reference types, which incurs boxing overhead. The alternative of using comparingInt avoids that overhead, but it means you have to do a tiny bit of arithmetic to get the effect of unsigned comparison. An alternative is to write out a lambda for a Comparator, which isn't too bad. Here it is, wrapped in a Comparator-returning function:

static <T> Comparator<T> comparingByIndex(List<? extends T> ordering) {
    return (t1, t2) -> Integer.compareUnsigned(ordering.indexOf(t1),
                                               ordering.indexOf(t2));
}

Since Collections.sort and Stream.sorted provide stable sorting, the elements not present in the ordering list will end up at the end, in the same order in which they occurred in the input. This might not be what you want. If you want them sorted by some other order, then a variation would be to provide a secondary Comparator that's called when neither element is present:

static <T> Comparator<T> comparingByIndex(List<? extends T> ordering,
                                          Comparator<? super T> cmp) {
    return (t1, t2) -> {
        int c1 = ordering.indexOf(t1);
        int c2 = ordering.indexOf(t2);
        if (c1 == -1 && c2 == -1) {
            return cmp.compare(t1, t2);
        } else {
            return Integer.compareUnsigned(c1, c2);
        }
    };
}

If you're sorting a stream, these variations let you do things like the following:

    .sorted(comparingByIndex(ordering))

    .sorted(comparingByIndex(ordering, someSpecializedComparator))

    .sorted(comparingByIndex(ordering, Comparator.reverseOrder()))

Upvotes: 3

Bubletan
Bubletan

Reputation: 3863

You could threat the result of indexOf as an unsigned integer. Then -1 would be the maximum value and be placed after the others.

This is probably the most readable way to do this (every index gets boxed though):

Comparator.comparing(ordering::indexOf, Integer::compareUnsigned)

Here is a faster alternative that avoids boxing:

Comparator.comparingInt(s -> ordering.indexOf(s) + Integer.MIN_VALUE)

Upvotes: 9

Anonymous
Anonymous

Reputation: 86323

I can only think of

    final Comparator<String> orderingComparator 
            = Comparator.comparingInt(s -> ordering.indexOf(s) == -1 ? ordering.size() : ordering.indexOf(s));

Now your code prints:

Element "foo" is ordered before "baz".

In this form it is inefficient in that it calls indexOf() twice. If you’re concerned, I leave it to you to rewrite it to avoid that.

PS I changed comparing() to comparingInt().

Upvotes: 4

Related Questions