Add additional rules to the compare method of a Comparator

Question

I currently have a code snippet which returns strings of a list in ascending order:

Collections.sort(myList, new Comparator<MyClass>() {
    @Override
    public int compare(MyClass o1, MyClass o2) {
        return o1.aString.compareTo(o2.aString);
    }
});

While it works, I would like to add some custom "rules" to the order to put certain strings to the front. For instance:

if(aString.equals("Hi")){
// put string first in the order
}

if(aString begins with a null character, e.g. " ") {
// put string after Hi, but before the other strings
}

// So the order could be: Hi, _string, a_string, b_string, c_string

Is it possible to customize the sorting of a list with a Comparator like this?

Answer 1

The answer from MC Emperor is quite nice (+1) in that it fulfills the OP's requirement of not using Java 8 APIs. It also uses a neat internal function technique (the getOrder method) of mapping conditions to small integer values in order to effect a first-level comparison.

Here's an alternative that uses Java 8 constructs. It assumes that MyClass has a getString method that does the obvious thing.

    Collections.sort(myList,
        Comparator.comparing((MyClass mc) -> ! mc.getString().equals("Hi"))
                  .thenComparing(mc -> ! mc.getString().startsWith(" "))
                  .thenComparing(MyClass::getString));

This is pretty opaque until you get used to this style. The key insight is that the "extractor" function that's supplied to Comparator.comparing and Comparator.thenComparing often simply extracts a field, but it can be a general mapping to any other value. If that value is Comparable then an additional Comparator for it needn't be provided. In this case the extractor function is a boolean expression. This gets boxed to a Boolean which as it turns out is Comparable. Since false orders before true we need to negate the boolean expression.

Also note that I had to provide an explicit type declaration for the lambda parameter, as type inference often doesn't work for chained comparator cases such as this one.

Answer 2

That's possible.

Using Java 8 features

You could pass a function to the Comparator.comparing method to define your rules. Note that we simply return integers, the lowest integer for the elements which should come first.

Comparator<MyClass> myRules = Comparator.comparing(t -> {
    if (t.aString.equals("Hi")) {
        return 0;
    }
    else if (t.aString.startsWith(" ")) {
        return 1;
    }
    else {
        return 2;
    }
});

If you want the remaining elements to be sorted alphabetically, you could use thenComparing(Comparator.naturalOrder()), if your class implements Comparable. Otherwise, you should extract the sort key first:

Collections.sort(myList, myRules.thenComparing(Comparator.comparing(t -> t.aString)));

Note that the actual specific numbers returned don't matter, what matters is that lower numbers come before higher numbers when sorting, so if one would always put the string "Hi" first, then the corresponding number should be the lowest returned (in my case 0).

Using Java <= 7 features (Android API level 21 compatible)

If Java 8 features are not available to you, then you could implement it like this:

Comparator<MyClass> myRules = new Comparator<MyClass>() {

    @Override
    public int compare(MyClass o1, MyClass o2) {
        int order = Integer.compare(getOrder(o1), getOrder(o2));
        return (order != 0 ? order : o1.aString.compareTo(o2.aString));
    }

    private int getOrder(MyClass m) {
        if (m.aString.equals("Hi")) {
            return 0;
        }
        else if (m.aString.startsWith(" ")) {
            return 1;
        }
        else {
            return 2;
        }
    }
};

And call it like this:

Collections.sort(list, myRules);

This works as follows: first, both received strings are mapped to your custom ruleset and subtracted from eachother. If the two differ, then the operation Integer.compare(getOrder(o1), getOrder(o2))¹ determines the comparison. Otherwise, if both are the same, then the lexiographic order is used for comparison.

Here is some code in action.

---

^{1 Always use Integer::compare rather than subtracting one from the other, because of the risk of erroneous results due to integer overflow. See here.}

Answer 3

Yes, that is possible, you have complete control over the compareTo() method. Two things:

1. Use String#equals instead of == to compare strings
2. Make sure you check both arguments to compareTo for your exceptional cases.

A concrete way of implementing something where some words are always first and some words are always last, with ordering defined among the exceptions:

Map<String, Integer> exceptionMap = new HashMap<>();
exceptionMap.put("lowest", -2);
exceptionMap.put("second_lowest", -1);
exceptionMap.put("second_highest", 1);
exceptionMap.put("highest", 2);

public int compareToWithExceptionMap(String s1, String s2) {
  int firstExceptional = exceptionMap.getOrDefault(s1, 0);
  int secondExceptional = exceptionMap.getOrDefault(s2, 0);

  if (firstExceptional == 0 && secondExceptional == 0) {
    return s1.compareTo(s2);
  }
  return firstExceptional - secondExceptional;
}