Sort a list with known values before unknown values

Question

I'm trying to sort a list with the following rules:

1. Known values should be ordered before unknown values.
2. Known values should be ordered by a separately defined key.
3. Unknown values should be ordered by their natural ordering.

I've got (1) and (2), just struggling with adding (3) in to the mix.

So far I have this:

List<String> values = Arrays.asList(
    "red", "orange", "yellow", "green", "blue", "indigo", "violet");

ImmutableMap<String, Integer> map = ImmutableMap.of("red", 1, "green", 2, "blue", 3);

Ordering<String> order = Ordering.natural()
    .nullsLast()
    .onResultOf(Functions.forMap(map, null));

Collections.sort(values, order);

System.out.println(values);

Which produces:

[red, green, blue, orange, yellow, indigo, violet]

But the last 4 are in their original order, whereas I'd like them sorted in their natural order:

[red, green, blue, indigo, orange, violet, yellow]

The only thing I can think of is writing my own custom function, which looks things up in the map and prepends the map result to the original value, using the map size if not found - e.g. it would return:

"1-red", "4-orange", "4-yellow", "2-green", "3-blue", "4-indigo", "4-violet"

But that only works if the mapped values are integers, and requires number formatting to order "02" before "10" etc.

Anyone have a better way of achieving this?

Answer 1

Here's the Guava version (when you're on Java 7 or lower):

Ordering<String> ordering = Ordering.natural().nullsLast()
        .onResultOf(Functions.forMap(map, null))
        .compound(Ordering.natural());

Here's the non-Guava version using pure Comparator (when on JDK 8+):

Comparator<String> comparator = Comparator
        .<String, Integer>comparing(map::get, Comparator.nullsLast(Comparator.naturalOrder()))
        .thenComparing(Comparator.naturalOrder());

PS. As you can see, the type inference in case of the Guava API is better (no need to specify explicit type parameters).

Answer 2

I THINK this solution should work for your problem. I do apologise for my use of ArrayLists- I couldn't find any documentation corresponding to an ImmutableMap in the Java 8 APIs. I've also assumed that natural order means ASCII order. Hope this helps :)

    //Values to be sorted
    ArrayList<Object> values = new ArrayList<>();

    values.add("red");
    values.add("orange");
    values.add("orange");
    values.add("yellow");
    values.add("green");
    values.add("blue");
    values.add("indigo");
    values.add("violet");
    values.add(1);    //I added 1 to verify output

    //List containing order of known values
    ArrayList<Object> knownOrder = new ArrayList<>();

    knownOrder.add("red");
    knownOrder.add(1);
    knownOrder.add("green");
    knownOrder.add("blue");
    knownOrder.add(3);

    ArrayList<Object> knownValues = new ArrayList<>();
    ArrayList<Object> unknownValues = new ArrayList<>();

    for (Object value: values) {
        if (knownOrder.contains(value)) {
            knownValues.add(value);
        }else {
            unknownValues.add(value);
        }
    }

    //Sort known values in required order
    Collections.sort(knownValues, (m1, m2)->knownOrder.indexOf(m1)-knownOrder.indexOf(m2));

    //Sort unknown values in natural order
    Collections.sort(unknownValues, (m1, m2)->m1.toString().charAt(0)-m2.toString().charAt(0));

    //Combine the known and unknown values into one ArrayList
    knownValues.addAll(unknownValues);

    System.out.println(knownValues);
    //Prints [red, 1, green, blue, indigo, orange, orange, violet, yellow]

I should also mention: This solution would not work for objects other than Strings and primitive Wrappers.