Java 21 | Sequenced Collections

Sorted und Ordered Datenstrukturen

Im Bereich des Java Collections Frameworks versteht man unter sorted und ordered Datenstrukturen Folgendes:

• Sorted: Die Elemente der Collection sind sortiert bzw. können mithilfe eines Comparators benutzerdefiniert sortiert werden. Beispiel: List oder als konkrete Implementation ArrayList.

• Ordered: Dies ist auch bekannt unter dem Begriff «encounter order». Die Elemente der Collections sind nicht sortiert, haben aber (wenn man mit einem Iterator darüber iteriert) immer die gleiche Reihenfolge. Beispiel: SortedSet

Sorted und Ordered Collections haben gemeinsame Eigenschaften. Es ist bei diesen Collections genau definiert, was das erste bzw. letzte Element ist. Vor Java 21 hatte das Collections Framework aber keine Abstraktion dafür. Mit Java 21 und den Sequenced Collections ändert sich das nun.

Wir starten mit ein paar Daten, die wir in den folgenden Beispielen immer wieder verwenden wollen. Es handelt sich dabei um eine Collection von Integer-Werten. Wir können diese als List, SortedSet oder OrderedSet modellieren.

List INTEGERS = List.of(1, 2, 3, 4, 5); 

List integersAsList = new ArrayList(INTEGERS); 
SortedSet integersAsSortedSet = new TreeSet<>(INTEGERS); 
LinkedHashSet integersAsOrdereSet = new LinkedHashSet<>(INTEGERS);

Before Java 21

Um auf das erste Element einer Collection zuzugreifen, sind für jede Datenstruktur bzw. für konkrete Implementierung andere API-Methodenaufrufe nötig. Hier ein paar Beispiele: wir möchten auf das erste Element einer Collection von Integer-Werten zugreifen:

 // List
Integer firstInteger = integersAsList.get(0); 

// SortedSet 
firstInteger = integersAsSortedSet.first(); 

// OrderedSet 
firstInteger = integersAsOrderedSet.iterator().next();

Wenn man auf das letzte Element zugreifen möchte, wird es abenteuerlich bzw. es gibt gar keinen direkten API-Support dafür:

// List
Integer lastInteger = integersAsList.get(integersAsList.size() - 1);

// OrderedSet
lastInteger = integersAsSortedSet.last();

// SortedSet
// Kein API Support

Sequenced Collections

Die Sequenced Collections bieten nun ein gemeinsames API für den Zugriff auf das erste bzw. letzte Element einer Collection. Zusätzlich gibt es Methoden zum Hinzufügen und Löschen von Elementen am Anfang bzw. Ende von Collections. Und als Bonus gibt es eine Methode, die die Collection in umgekehrter Reihenfolge zurückliefert. Die Sequenced Collections sind neue Interfaces, die in das bestehende Collections Framework integriert wurden. Die uns schon bekannten Datenstrukturen wie Lists und Sets implementieren diese neuen Interfaces bereits.

Das zentrale Interface dazu ist SequencedCollection.

interface SequencedCollection extends Collection {
     SequencedCollection reversed(); 
     void addFirst(E);
     void addLast(E);
     E getFirst();
     E getLast();
     E removeFirst();
     E removeLast();
}

Mit Java 21 wurde das List Interface durch SequencedCollection erweitert. Damit sind alle Klassen, die das List-Interface implementieren, automatisch SequencedCollections.

public interface List extends SequencedCollection

So ist z.B. ArrayList neu eine SequencedCollection.

Für Sets gibt es das SequencedSet, welches fast identisch mit dem SequencedCollection-Interface ist. Einziger Unterschied ist, dass reversed() ein SequencedSet zurückgibt.

interface SequencedSet extends Set, SequencedCollection {
     SequencedSet reversed(); // covariant override
 }

Sorted Sets implementieren das Interface NavigableSet, das neu SortedSet erweitert. Ein Beispiel dazu ist die Klasse TreeSet.

public interface NavigableSet extends SortedSet

Ordered Sets implementieren direkt das Interface SequencedSet. Ein Beispiel dazu ist die Klasse LinkedHashSet.

Daneben gibt es noch Sets, die nicht sorted und nicht ordered sind (z.B. Klasse HashSet) und daher SequencedSet nicht erweitern bzw. implementieren.

Das obige Beispiel kann man nun mit den Sequenced Collections einfacher bzw. schöner schreiben, weil wir ein gemeinsames API für Lists und Sets haben. Wir schreiben uns eine Hilfsmethode, die das erste bzw. letzte Element einer Collection ausgibt. Diese Hilfsmethode verwenden wir dann für die verschiedenen List- und Set-Implementationen.

printFistLastElements(integersAsList);
printFistLastElements(integersAsSortedSet);
printFistLastElements(integersAsOrdereSet);

 void printFistLastElements(SequencedCollection values) {
    System.out.println(STR."fistLastElements for \{values.getClass().getName()}");
    T first = values.getFirst();
    T last = values.getLast();
    System.out.println(STR."input: \{values} first: \{first}, last: \{last}");
}

Wenn man den Code ausführt, erhält man folgende Ausgaben:

fistLastElements for java.util.ArrayList
input: [1, 2, 3, 4, 5] first: 1, last: 5

fistLastElements for java.util.TreeSet
input: [1, 2, 3, 4, 5] first: 1, last: 5

fistLastElements for java.util.LinkedHashSet
input: [1, 2, 3, 4, 5] first: 1, last: 5

Einen detaillierten Überblick über die Interface-Hierarchie gibt es direkt auf der JEP 431 Seite.

Alles in Reverse

Die SequencedCollection-Interfaces haben eine reversed()-Methode, die eine Collection in der umgekehrten Reihenfolge zurückgibt. Wir können uns wiederum eine kleine Hilfsmethode schreiben und die Daten aus dem vorigen Beispiel «umdrehen». Das funktioniert prima für Listen und Sorted/Ordered Sets.

printElementsInReverse(integersAsList);
printElementsInReverse(integersAsSortedSet);
printElementsInReverse(integersAsOrdereSet);

 void printElementsInReverse(SequencedCollection values) {
    System.out.println(STR."iterateInReverse for \{values.getClass().getName()}");
    System.out.println("input   : " + values);
    System.out.println("reversed: " + values.reversed());
}

Zu beachten ist, dass eine «reversed» Collection keine neue Collection ist, sondern nur eine View auf die bestehende Collection. D.h. wenn man die Input-Collection verändert, wird auch die «reversed»-Collection verändert. Hierzu wiederum ein Beispiel: wir starten mit einer Integer-Liste, erstellen mit reversed() eine View in umgekehrter Reihenfolge und geben den Inhalt der beiden Listen aus. Dann fügen wir am Anfang und am Ende der Input-Liste ein neues Element hinzu und geben wiederum beide Listen aus:

reversedIsAView(integersAsList, 0, 42);

 void reversedIsAView(SequencedCollection values, T smallValue, T bigValue) {
    System.out.println(STR."reversedIsAView for \{values.getClass().getName()}");

    SequencedCollection reversed = values.reversed();
    printCollections(values, reversed);

    System.out.println(STR."add first value \{smallValue} and last value \{bigValue}");
    try {
        values.addFirst(smallValue);
        values.addLast(bigValue);
        printCollections(values, reversed);
    } catch (UnsupportedOperationException e) {
        System.out.println(STR."addFirst()/addLast is not supported for \{values.getClass().getName()}");
    }
}

 void printCollections(SequencedCollection values, SequencedCollection reversed) {
    System.out.println("input   : " + values);
    System.out.println("reversed: " + reversed);
}

Wir erhalten folgende Ausgaben:

reversedIsAView for java.util.ArrayList

input   : [1, 2, 3, 4, 5]
reversed: [5, 4, 3, 2, 1]

add first value 0 and last value 42

input   : [0, 1, 2, 3, 4, 5, 42]
reversed: [42, 5, 4, 3, 2, 1, 0]

Man kann sehen, dass sich die Input- und «reversed»-Liste verändert haben. Noch zwei Punkte sind zu erwähnen:

Das Beispiel verwendet ArrayList. Es funktioniert aber genauso mit einem Sorted/Ordered Set.

• Wenn die Input-Collection immutable ist, wird beim Versuch Daten hinzuzufügen, eine UnsupportedOperationException geworfen.

Sequenced Maps

Neben SequencedCollection und SequencedSet gibt es noch das Interface SequencedMap. Es bietet die Funktionalität von SequencedCollection für Maps an. Dabei ist das Naming der Methoden etwas anders:

• firstEntry() / lastEntry() liefern das erste/letzte Key-Value Pair zurück
• pollFirstEntry() / pollLastEntry() löscht das erste/letzte Key-Value Pair und gibt es zurück
• putFirst() / putLast() fügt ein Key-Value Pair am Anfang/Ende ein
• reversed() gibt eine View auf die Map in umgekehrter Reihenfolge

In einem ersten Schritt erstellen wir zwei Sorted Maps: eine SortedMap und eine ConcurrentSkipListMap und befüllen diese mit Integer-Werten als Key und dem String «value_» + Key als Value:

private SortedMap sortedMap = createTreeMapWithIntegers();
private ConcurrentSkipListMap anotherSortedMap = createCSLMapWithIntegers();

private SortedMap createTreeMapWithIntegers() {
    SortedMap sortedMap = new TreeMap();
    for (int i = 0; i < 5; i++) {
        sortedMap.put(i, STR."value_\{i}");
    }
    return sortedMap;
}

private ConcurrentSkipListMap createCSLMapWithIntegers() {
    ConcurrentSkipListMap anotherSortedMap = new ConcurrentSkipListMap();
    for (int i = 0; i < 5; i++) {
        anotherSortedMap.put(i, STR."value_\{i}");
    }
    return anotherSortedMap;
}

Zum Zugriff auf das erste und letzte Element der Map, schreiben wir wiederum eine kleine Hilfsmethode, die dann von beiden Map-Implementationen verwendet werden kann.

printFistLastElements(sortedMap);
printFistLastElements(anotherSortedMap);

private void printFistLastElements(SequencedMap map) {
    System.out.println(STR."fistLastElements for \{map.getClass().getName()}");
    Map.Entry first = map.firstEntry();
    Map.Entry last = map.lastEntry();
    System.out.println(STR."FIRST: \{first.getKey()}|\{first.getValue()}");
    System.out.println(STR."LAST : \{last.getKey()}|\{last.getValue()}");
}

Dabei erhalten wir folgende Ausgabe:

fistLastElements for java.util.TreeMap
FIRST: 0|value_0
LAST : 4|value_4

fistLastElements for java.util.concurrent.ConcurrentSkipListMap
FIRST: 0|value_0
LAST : 4|value_4

Fazit

Die Sequenced Collections von Java 21 sind eine willkommene Erweiterung des bestehenden Collections Frameworks. Sie bieten ein gemeinsames API für Lists, Sets (und Maps) und wurden wunderschön ins bestehende Collections Framework integriert: Die vorhandenen Datenstrukturen implementieren (wo sinnvoll und möglich) die neuen Interfaces.

Links

• Michael Inden: Java 21 LTS Cool New Java Features