Während die Java-Bibliothek mit Listen, Mengen, Assoziativspeichern einen guten Grundstock für die alltäglichen Aufgaben zur Datenverwaltung bietet, so gibt es dennoch Bedarf an weiteren Speicherstrukturen. Anstatt sie selbst zu definieren, ist es sinnvoll, in die Open-Source-Welt zu schauen. Besondern hervorzuheben ist Google Guava (http://code.google.com/p/guava-libraries/), welches eine Open-Source Bibliothek mit neuen Datenstrukturen, Utility-Methoden für die existierenden java.util-Datenstrukturen, sowie einigen anderen Utility-Klassen etwa für String-Behandlung oder zum Zerlegen von Zeichenketten ist. (Die Datenstrukturen von Guava stammen aus dem Projekt Google Collections Library, aber die Entwicklung geht bei Guava weiter.)

Für die folgenden Beispiele muss von der Webseite die Distribution guava-r06.zip heruntergeladen und das im Zip enthaltende Java-Archiv guava-r06.jar im Klassenpfad eingebunden werden.

1.1.1 Beispiel Multi-Set und Multi-Map

Da Java schon alles Grundlegende mitbringt stellt sich die Frage, was denn überhaupt fehlt. Dazu zwei Szenarios:

· Eine Textdatei soll analysiert werden. Am Ende soll feststehen, wie oft jedes Wort (unabhängig der Groß-/Kleinschreibung) in der Datei steht. Enthält die Datei etwa „In Ulm, um Ulm, um Ulm herum.“, so sollte herauskommen: „in“: 1, „ulm“: 3, „um“: 2, „herum“: 1. Im Grunde müsste es eine Menge geben, die Elemente mehrmals enthalten kann, eine sogenannte Multi-Menge (auch Multi-Set genannt). Eine Anfrage an die Multi-Menge gibt dann nicht nur ein Wahrheitswert für „enthält“ oder „enthält nicht“ zurück, sondern auch, wie oft ein Element in der Multi-Menge enthalten ist. Die Datenstruktur ist nicht Teil von Java, kann aber mit Standardmitteln für unseren Anwendungsfall mit einer Map<String, Integer> realisiert werden.

· Beispiel 2: Wieder soll eine Textdatei analysiert werden. Gespeichert werden soll für jedes Wort auch die Position, sodass sich später feststellen lässt, ob gewisse Wörter nicht vielleicht zu nah beieinander stehen, was schlechter Stil wäre. Bei der Zeichenfolge „In Ulm, um Ulm“ wäre das: „in“: 0, „ulm“: 3, 11, „um“: 8. Kämen nicht mehrere Positionen für das gleiche Wort in Frage – wie Um was ab Position 3 und 11 beginnt –, wäre eine Map perfekt. Nur gibt es in unserem Anwendungsfall zu einem Schlüssel gleich mehrere Werte. Gesucht ist eine so genannte Multi-Map. Die Java-Bibliothek enthält bisher keine Multi-Map, da damals die Sun-Entwickler argumentieren, eine solche Datenstruktur wird selten benötigt.[1] Für unseren Fall kann sie mit Map<String, List<Integer>> aber nachgebildet werden.

1.1.2 Datenstrukturen aus Guava

Guava bietet Entwicklern Klassen für Multi-Set, Mutli-Map und mehr. Dabei ist das Design vorbildlich und fügt sich perfekt in die Java-Standarddatenstrukturen ein. Das aus zwei Gründen:

· Schnittstellen deklarieren Operationen, die konkrete Klassen implementieren. So wie List eine Schnittstelle ist, die ArrayList implementiert, so wird Mulitmap etwa durch ArrayListMultimap implementiert.

· Die Datenstrukturen nutzen sehr präzise die Möglichkeiten von Java Generics. So wie Map<K,V> aus java.util, ist es die Multimap<K,V> aus Guava.

Schauen wir uns ein paar Schnittstellen und Implementierungen aus dem Paket com.google.common.collect an – die API-Dokumentation gibt es online unter http://guava-libraries.googlecode.com/svn/trunk/javadoc/index.html. (Die Schnittstelle sind jeweils mit ihren generischen Typvariablen genannt, die Implementierungen zur Abkürzung nicht.)

Bei den Klassen springen zwei Dinge ins Auge: Klassen, die mit Immutable und mit Forwarding beginnen.

· Immutable-Datenstrukturen kennen wir schon – das sind Datenstrukturen, die nur-lese-Zugriff erlauben, die aber nicht modifiziert werden können. Die Utility-Klasse Collections bietet uns ein Paar unmodifiableXXX()-Methoden, die einen nur-lese-Wrapper um die Basis-Typen Collection, List, Set, Map, SortedSet, SortedMap legen. Die ImmutableXXX-Klassen aus Guava sind die nicht veränderbaren Google-Datenstrukturen.

· Die abstrakten ForwardingXXX-Klassen arbeiten nach dem Dekorator-Pattern und leiten alle Operationen an eine andere Datenstruktur weiter. Es sind sehr spezielle Klassen und Guava nutzt sie intern – für Entwickler sind sie weniger relevant.

Im Grunde bleiben dann nur noch ein paar Datenstrukturen übrig, und das Implementierungsmuster ist wie bei den Java-Standardbibliotheken: Einige Datenstrukturen speichern die tatsächlichen Daten in Array-Listen, anderen in Hashing-Datenstrukturen, anderen wiederum in Mengen, die über Binärbäume sortiert sind.

Die Klassen ConcurrentHashMultiset (eine sichere nebenläufige Muliset-Implementierung) und EnumBiMap, EnumHashBiMap (Typen sind eingeschränkt auf Enums) sind Sonderfälle.

1.1.3 Utility-Klassen von Guava

Auf der einen Seite bietet Guava neue Datenstrukturen, auf der anderen Seite Utility-Klassen, die eine Ergänzung zu der einen Standardklasse Collections ist.

Weiterhin gibt es für die neuen Guava-Klassen die zwei Utility-Klassen Multimaps und Multisets.

1.1.4 Prädikate

Ein Prädikat ist ein Objekt, welches auf einem Argument eine Bedingung prüft und wahr oder falsch liefert. Guava gibt eine Prädikat-Schnittstelle Predicate<T> mit der Operation boolean apply(T input) vor. Ein Prädikat könnte etwa testen, ob eine Objektreferenz null ist, oder ein String eine Mindestlänge besitzt. Prädikate verändern die Argumente nie und dürfen sie nicht „zurechtbiegen“.

Mit eigenen Predicate-Objekten lässt sich auf diverse Methoden zurückgreifen, die Sammlungen filtern. Ein paar Beispielmethoden:

§ static <E> Collection<E> Collections2.filter( Collection<E> unfiltered, Predicate<? super E> predicate )
Liefert in der Rückgabe eine Collection, die alle Elemente von unfiltered enthält, die das Prädikat erfüllen.

§ static <E> Set<E> Sets.filter( Set<E> unfiltered, Predicate<? super E> predicate )
Liefert als Rückgabe eine Menge, bei der jedes Element das Prädikat erfüllt.

§ static <T> boolean Iterables.all( Iterable<T> iterable, Predicate<? super T> predicate )
Prüft, ob alle Elemente vom Iterable (eine List ist zum Beispiel Iterable, aber auch Set) das Prädikat erfüllen.

Zum Verknüpfen von Prädikaten bietet die Predicates-Klasse statische Kombinationsmethoden wie and(), compose(), or().

1.1.5 Transformationen

Oftmals müssen die Elemente in Datenstrukturen von einem Format in ein anderes gebracht werden. Zum Beispiel sollen bei String in einer Liste die Leerzeichen vorne und hinten abgeschnitten werden oder Farben sollen in Graustufen übersetzt werden.

Für Transformationen deklariert Guava die Schnittstelle Function<F,T> mit einer Operation T apply(F from). In den Guava-Utility-Klassen gibt es jeweils transform()-Methoden, die alle Elemente einer Datenstruktur durch eine Function leiten und auf der anderen Seite das Ergebnis in eine Datenstruktur setzen und diese zurückgeben. Ein paar Beispiele:

§ static <F,T> Collection<T> Collections2.transform( Collection<F> fromCollection, Function<? super F,T> function )

§ static <F,T> Iterable<T> Iterables.transform( Iterable<F> fromIterable, Function<? super F,? extends T> function )

§ static <F,T> Iterator<T> Iterators.transform( Iterator<F> fromIterator, Function<? super F,? extends T> function )

§ static <F,T> List<T> Lists.transform( List<F> fromList, Function<? super F,? extends T> function )

§ static <K,V1,V2> Map<K,V2> Maps.transformValues( Map<K,V1> fromMap, Function<? super V1,V2> function )

§ static <E> Collection<E> Collections2.filter( Collection<E> unfiltered, Predicate<? super E> predicate )

[1] http://java.sun.com/docs/books/tutorial/collections/interfaces/map.html