List Sorting puzzle

Question

Assuming I have

final Iterable<String> unsorted = asList("FOO", "BAR", "PREFA", "ZOO", "PREFZ", "PREFOO");

What can I do to transform this unsorted list into this:

[PREFZ, PREFA, BAR, FOO, PREFOO, ZOO]

(a list which begin with known values that must appears first (here "PREFA" and "PREFZ") and the rest is alphabetically sorted)

I think there are some usefull classes in guava that can make the job (Ordering, Predicates...), but I have not yet found a solution...

Answer 1

Note: This is not the most efficient solution. It is just a simple, straightforward solution that gets the job done.

I would first use Collections.sort(list) to sort the list.

Then, I would remove the known items, and add them to the front.

String special = "PREFA";
if (list.remove(special)
    list.add(0, special);

Or, if you have a list of array of these values you need in the front you could do:

String[] knownValues = {};
for (String s: knownValues) {
    if (list.remove(s))
        list.add(0, s);
}

Answer 2

I would also use Collections.sort(list) but I think I would use a Comparator and within the comparator you could define your own rules, e.g.

class MyComparator implements Comparator<String> {

    public int compare(String o1, String o2) {
        // Now you can define the behaviour for your sorting.
        // For example your special cases should always come first, 
        // but if it is not a special case then just use the normal string comparison.

        if (o1.equals(SPECIAL_CASE)) {
            // Do something special
        }
        // etc.
        return o1.compareTo(o2);
    }

}

Then sort by doing:

Collections.sort(list, new MyComparator());

Answer 3

I would keep separate lists.

One for known values and unknown values. And sort them separately, when you need them in a one list you can just concatenate them.

knownUnsorted.addAll(unsorted.size - 1, unknonwUnsorted);

Answer 4

I suggest filling List with your values and using Collections.sort(...).

Something like

Collections.sort(myList, new FunkyComparator());

using this:

class FunkyComparator implements Comparator {

    private static Map<String,Integer> orderedExceptions =
        new HashMap<String,Integer>(){{ 
            put("PREFZ", Integer.valueOf(1));
            put("PREFA", Integer.valueOf(2));
        }};

    public int compare(Object o1, Object o2) {
        String s1 = (String) o1;
        String s2 = (String) o2;
        Integer i1 = orderedExceptions.get(s1);
        Integer i2 = orderedExceptions.get(s2);

        if (i1 != null && i2 != null) {
            return i1 - i2;
        }
        if (i1 != null) {
            return -1;
        }
        if (i2 != null) {
            return +1;
        }
        return s1.compareTo(s2);
    }
}

Answer 5

Since I'm a fan of the guava lib, I wanted to find a solution using it. I don't know if it's efficient, neither if you find it as simple as others solution, but it's here:

final Iterable<String> all = asList("FOO", "BAR", "PREFA", "ZOO", "PREFOO", "PREFZ");
final List<String> mustAppearFirst = asList("PREFZ", "PREFA");
final Iterable<String> sorted = 
      concat(
            Ordering.explicit(mustAppearFirst).sortedCopy(filter(all, in(mustAppearFirst))),
            Ordering.<String>natural().sortedCopy(filter(all, not(in(mustAppearFirst)))));

Answer 6

You specifically mentioned guava; along with Sylvain M's answer, here's another way (more as an academic exercise and demonstration of guava's flexibility than anything else)

// List is not efficient here; for large problems, something like SkipList 
// is more suitable
private static final List<String> KNOWN_INDEXES = asList("PREFZ", "PREFA");

private static final Function<Object, Integer> POSITION_IN_KNOWN_INDEXES 
    = new Function<Object, Integer>() {
  public Integer apply(Object in) {
     int index = KNOWN_INDEXES.indexOf(in);
     return index == -1 ? null : index;
  }     
};


...


List<String> values = asList("FOO", "BAR", "PREFA", "ZOO", "PREFZ", "PREFOO");

Collections.sort(values,
  Ordering.natural().nullsLast().onResultOf(POSITION_IN_KNOWN_INDEXES).compound(Ordering.natural())
);

So, in other words, sort on natural order of the Integer returned by List.indexOf(), then break ties with natural order of the object itself.

Messy, perhaps, but fun.