“Any sufficiently advanced bug is indistinguishable from a feature.”
Rich Kulawiec
Kaum ein Bereich in der Software Entwicklung gebiert so furchtbare Töchter wie die Sortierung. Obwohl die Java Standard Bibliothek viele wunderbare Klassen bereitstellt, finden sich immer wieder Programmierer, die ihre eigenen Holzwege schaffen.
Die berühmtesten Vertreter sind die Behandlung von Nullwerten, Konfigurierbare Attributsortierer und die Sortierung mit Richtungsschalter.
Grundlagen
Das Herzstück jeder Sortierung sind die beiden Interfaces Comparable und Comparator. Das Interface Comparable wird von Klassen implementiert, deren Instanzen eine natürliche Ordnung untereinander kennen. Klassische Beispiele dafür sind die numerischen Klassen wie Integer und Double und Zeitwerte wie LocalDate.
public class Person implements Comparable<Person> {
private final LocalDate birthDay;
public int compareTo(Person o) {
return birthDay.compareTo(o.birthDay);
}
}
Im obigen Beispiel ist die Klasse Person sortierbar nach ihrem Geburtsdatum. Die Methode compareTo liefert einen negativen Wert, wenn die aktuelle Instanz innerhalb der Ordnung kleiner ist als die Vergleichsinstanz. Ist sie größer, dann liefert die Methode einen positiven Wert und bei Gleichheit den Wert 0. Die Klasse Person delegiert in diesem Fall einfach an die Klasse LocalDate, die auch das Interface Comparable implementiert.
Die Klasse Person soll aber auch nach Vorname und Nachname sortierbar sein. Für Klassen, bei den mehrere Sortierungen denkbar sind oder für die keine natürliche Ordnung mit Comparable festgelegt wurde, existiert das Interface Comparator.
private static Comparator<Person> byFirstname() {
return Comparator<Person>() {
public int compare(Person o1, Person o2) {
return o1.getFirstname().compareTo(o2.getFirstName());
}
}
}
Die hier dargestellte Implementierung sortiert Instanzen der Klasse Person nach deren Vornamen. Im folgenden Beispiel werden alle Personen im Stream nach ihrem Vornamen sortiert und in einer Liste gesammelt.
ancestors.stream().sorted(byFirstname()).toList();
Da Comparator ein Functional Interface ist, kann dies alles auch ein wenig kürzer geschrieben werden. Die Definition des Comparator als Methode.
private static Comparator<Person> byFirstname() {
return (p1, p2) -> p1.getFirstname().compareTo(p2.getFirstname());
}
Die Java Standard Bibliothek stellt hierfür die Methode Comparator.comparing bereit. Die Methode ist eine hilfreiche Verallgemeinerung für den Vergleich auf ein spezielles Attribut.
ancestors.stream().sorted(Comparator.comparing(Person::getFirstname).toList();
Comparator Anti-Pattern
Behandlung von Nullwerten
Listen die Sortiert werden sollen enthalten hin und wieder Lücken. Ein Comparator, der darauf nicht achtet, erzeugt schnell eine NullPointerException. Aus diesem Grund findet sich in vielen projektspezifischen Corporator Implementierungen eine null Prüfung.
private static Comparator<Person> byBirth() {
return Comparator<Person>() {
public int compare(Person o1, Person o2) {
if (o1 == null || o2 == null) {
return 0;
}
return o1.getDeath().compareTo(o2.getDeath());
}
}
}
Auf dem ersten Blick scheint dieser Source Code hinreichend zu sein, weil beide Vergleichswerte auf null geprüft werden. Leider hält sich dieser Comparator nicht an den Class Contract. Damit der Sortieralgorithmus die Instanzen an die richtige Stelle schiebt, muss die Ordnung der Instanzen konsistent sein. Dieser Comparator meldet aber immer Gleichheit bei dem Vergleich mit null, egal ob der Wert link oder rechts steht. Korrekt wäre z.B. die folgende Behandlung.
private static Comparator<Person> persons() {
return Comparator<Person>() {
public int compare(Person o1, Person o2) {
if (o1 == null || o2 == null) {
return o1 == o2 ? 0 : o1 == null ? -1 : 1;
}
return o1.compareTo(o2);
}
}
}
Auf diese Weise werden zuerst die Fälle mit null behandelt und danach die eigentliche Vergleichsoperation durchgeführt. Im Beitrag zum Guard Decorator wurde schon die Trennung von Parameterprüfungen und eigentlicher Verarbeitung angesprochen. Dies bietet sich auch an dieser Stelle an. Das Comparator Interface stellt die beiden nullsLeft und nullsRight Methoden für diese Aufgabe zur Verfügung.
ancestors.stream().sorted(Comparator.nullsLeft(comparing(Person::getFirstname()).toList());
Mit der Verwendung von nullsLeft werden alle null Werte in der Liste nach Links sortiert und alle anderen Werte nach ihrem Vornamen sortiert. Mit nullsRight landen die null Werte auf der anderen Seite.
Konfigurierbare Attributsortierer
Wenn es schnell gehen soll, man gerne alles in einer Klasse haben möchte oder alles immer konfigurierbar sein soll, dann werden konfigurierbare Attributsortierer erfunden. Die Person Klasse besitzt eine ganze Reihe von Attributen nach denen eine Liste von Personen sortiert werden könnte.
Manchmal müssen auch die Personen zuerst nach Nachname und dann zusätzlich nach Vornamen sortiert werden. Manchmal soll aufsteigend und manchmal absteigend sortiert werden. Außerdem müssen die Attribute auf null geprüft werden und eine Reihe weiterer Bedingungen geprüft werden.
Solche eierlegenden Wollmilchsäue unter den Klassen, können immer durch das Decorator Pattern ersetzt werden. Die Klasse Comparator bietet dafür eine fülle interessanter Hilfsmethoden.
Ich erspare mir ein negativ Beispiel für eine Klasse, die eine Liste von Personen nach ihrem Nachnamen und dann ihren Vornamen sortiert, und zeige die elegante Lösung am bisher verwendeten Beispiel.
ancestors.stream().sorted(comparing(Person::getLastname()).thenComparing(Person::getFirstname()).toList());
Die thenComparing Methode verknüpft die beiden Comparator Instanzen so, dass der Vornamenvergleich nur stattfindet, wenn die Nachnamen identisch sind.
Auf diese Weise lassen sich beliebige Comparator Instanzen sehr flexibel miteinander kombinieren.
Sortierung mit Richtungsschalter
Eine eigenartige Erweiterung des Comparator findet immer wieder den Weg ins Leben zurück. Egal wie oft man Implementierung dieser Comparator entfernt, sie kehren immer wieder zurück. Gemeint ist der Comparator der in beide Richtungen sortieren kann und dazu meist mit einem boolean Flag ausgerüstet ist.
private static Comparator<Person> byFirstname(boolean sortDirection) {
return Comparator<Person>() {
public int compare(Person o1, Person o2) {
boolean result = o1.getFirstname().compareTo(o2.getFirstName());
return sortDirection ? result : -result;
}
}
}
Das obige Beispiel ist ein relativ harmloser Vertreter dieser Gattung, da hier tatsächlich die grundlegende Eigenschaft der compare Methode ausgenutzt wurde. Soll in die andere Richtung sortiert werden, dann muss nur das Vorzeichen der Funkton geändert werden. Das konnte aber, seit der Einführung der Collections in Java 1.2, schon durch einen negierenden Decorator erfolgen.
Comparator<Person> upComparator = byFirstName(); Comparator<Person> downComparator = reversed(upComparator);
Der upComparator kann für das aufsteigende Sortieren verwendet und seine negation downComparator als absteigende Sortierung. Die Methode reverse ist die Negation oder Parametervertauschung in Form eines Comparator.
private static <T> Comparator<T> reversed(Comparator<T> comparator) {
return (c1, c2) -> comparator.compare(c2,c1);
}
Da dies eine sehr nützliche Funktionalität für die Sortierung ist, steht sie seit Java 8 im Comparator Interface zu Verfügung;
Comparator<Person> upComparator = byFirstName(); Comparator<Person> downComparator = upComparator.reversed();
Nützliche Helfer
Die Java Standard API beinhaltet eine ganze Reihe nützlicher Funktionen zur Erzeugung eigenen Comparator, von denen einige hier schon vorgestellt wurden. Auch im Projekt Stream Collector Utilities sind ein einige weitere zu finden.
safeComparing
Das Sortieren nach einem Attribut mit der comparing Methode kann zu einer NullPointerException führen.
persons.stream().sorted(comparing(Person::getDeath)).toList();
Hier wäre eine null-Behandlung wie bei nullsLeft oder nullsRight wünschenswert. Dies bietet die Comparators.saveComparing Methode.
persons.stream().sorted(Comparators.safeComparing(Person::getDeath)).toList();
Alternativ steht noch ein Variante zur Verfügung um einen Comparator für das Attribut anzugeben.
persons.stream().sorted(Comparators.safeComparing(Person::getName, myNameComparator)).toList();
Die Implementierung ist in wenigen Zeilen zusammengefasst und beruht auf der Standard comparing Methode.
public static <T, U extends Comparable<? super U>> Comparator<T> safeComparing(
Function<? super T, ? extends U> keyExtractor) {
return safeComparing(keyExtractor, naturalOrder());
}
Die erste vorgestellte Methode ist nur ein Spezialfall der zweiten Methode. Dafür wird diese mit der sehr nützlichen Comparator.naturalOrder Methode parametrisiert. Diese Standardmethode verwendet einen Comparator, der Comparable Instanzen mit ihrer compareTo Methode vergleicht.
public static <T, U extends Comparable<? super U>> Comparator<T> safeComparing(
Function<? super T, ? extends U> keyExtractor, Comparator<? super U> comparator) {
return comparing(keyExtractor, nullAwareLeft(comparator));
}
Die zweite Variante der safeComparing Methode dekoriert den übergebenen Comparartor mit einem weiteren Comparator nullAwareLeft, der eine null-Behandlung durchführt. An dieser Stelle könnte auch die nullsLeft Methode verwendet werden, aber ich verwende hier eine eigene Implementierung.
safeComparing mit Default-Wert
Manchmal ist es nicht erwünscht, dass die mit null belegten Attribute ans Ende , bzw. den Anfang sortiert werden.
cars.stream().sorted(Comparators.safeComparing(Cars::getColor)).collect(toList());
Im obigen Beispiel werden alle Car Instanzen ihrer Farbe nach sortiert. Leider hat die Instanz Tin Lizzy aus historischen Gründen keine Farbe gespeichert und wird nun ganz vorne in die Liste einsortiert.
“You can have it in any color you want, as long as it is black.”
Henry Ford
Selbstverständlich soll dieser Wagen unter Schwarz einsortiert werden, daher wird eine weitere Variante von safeComparing verwendet.
cars.stream().sorted(Comparators.safeComparing(Cars::getColor, "black")).collect(toList());
Dieser Variante von safeComparing dekoriert nicht den Comparator, sondern den die übergebene keyExtractor Funktion.
public static <T, U extends Comparable<? super U>> Comparator<T> safeComparing(
Function<? super T, ? extends U> keyExtractor, U defaultCompareValue) {
return comparing(safeKeyExtractor(requireNonNull(keyExtractor), requireNonNull(defaultCompareValue)));
}
private static <T, U extends Comparable<? super U>> Function<? super T, ? extends U> safeKeyExtractor(
Function<? super T, ? extends U> keyExtractor, U defaultKey) {
return keyExtractor.andThen(x -> x != null ? x : defaultKey);
}
Durch die Methode safeKeyExtractor wird dem keyExtractor eine weitere Function angehängt, um einen übergebenen null Wert durch den Defaultwert zu ersetzen.
nullAwareLeft und nullAwareRight
Die beiden Methoden sind Alternativen zu nullsLeft und nullsRight aus der Java Standard Bibliothek. Sie werden hier aufgeführt und von den safeComparing Methoden verwendet, weil mir ihre Implementierung gefällt.
public static <T> Comparator<T> nullAwareLeft(Comparator<? super T> comparator) {
return nullAware(comparator, -1, 1);
}
public static <T> Comparator<T> nullAwareRight(Comparator<? super T> comparator) {
return nullAware(comparator, 1, -1);
}
private static <T> Comparator<T> nullAware(Comparator<? super T> comparator, int left, int right) {
return (c1, c2) -> {
int i1 = c1 == null ? left : 0;
int i2 = c2 == null ? right : 0;
return i1 == i2 ? comparator.compare(c1, c2) : i1 + i2;
};
}
Die beiden Methode delegieren die Arbeit an die Methode nullAware, die als Parameter den dekorierten Comparator und die Resultate für die Prüfung der null Werte. Wie nicht anders zu erwarten sind die Werte bei den Methoden vertauscht.
Die nullAware Methode bestimmt zuerst einen Zwischenwert für die beiden Vergleichsparameter. Dabei wird dieser Zwischenwert 0 wenn der Vergleichsparameter gesetzt ist und er wird auf den Resultatwert für den Vergleichsparameter gesetzt, wenn dieser null ist.
In der letzten Zeilen findet also ein Vergleich statt, wenn beide Zwischenwerte gleich sind. Dies kann nur geschehen, wenn beide Vergleichsparameter ungleich null sind und folglich die Zwischenwerte 0 sind. Im anderen Fall werden nur die beiden Zwischenwerte addiert um das Ergebnis des null Vergleichs zu erhalten.
- Wenn beide Vergleichswerte
nullsind, dann gelten beide als gleich und das Ergebnis ist 0. Denn c1 = null \land c2 = null \implies i1 = -1 \land i2 = 1 \implies -1 + 1 = 0\\ - Wenn nur der linke Vergleichswert
nullist, dann ist er kleiner und das Ergebnis is -1. Denn c1 = null \land c2 \neq null \implies i1 = -1 \land i2 = 0 \implies -1 + 0 = -1\\ - Wenn nur der rechte Vergleichswert
nullist, dann ist er kleiner und das Ergebnis ist 1. Denn c1 \neq null \land c2 = null \implies i1 = 0 \land i2 = 1 \implies 0 + 1 = 1\\
Fazit
Die Sortierung in der Java Standard Bibliothek bietet einen reichhaltigen Fundus an Lösungen für den alltäglichen Gebrauch. Solange man sich den dort vorgestellten Design-Pattern nicht verschließt, können eigene Anwendungen elegant und kompakt implementiert werden.