I am currently working on an English translation. If you like to help to proofread please contact me: ullenboom ät g m a i l dot c o m.

Java Videotraining Werbung

1. Datenstrukturen und Algorithmen

Datenstrukturen speichern in der Anwendung zentrale Informationen. Organisiert werden sie über Listen, Mengen, Queues und Assoziativspeicher. In Java werden die Schnittstellen und Klassen rund um Datenstrukturen Collection-API genannt. Da so viele Typen zur Auswahl stehen, ist es Gegenstand von diesem Kapitel, Ordnung in das Chaos zu bringen und durch die Aufgaben den Einsatz der entsprechenden Sammlungen zu verdeutlichen.

Voraussetzungen

  • Datenstrukturen Listen, Mengen, Assoziativspeicher abgrenzen können

  • Datentypen List, ArrayList und LinkedList kennen

  • Datentypen Set, HashSet und TreeSet kennen

  • Datentypen Map, HashMap und TreeMap kennen

  • Unterschied zwischen Queue und Deque kennen

  • Ordnung mit Comparator schaffen können

  • Iteratoren einsetzen und implementieren können

  • Datenstrukturen threadssicher verwenden können

  • Optional: Interesse an der Open-Source-Bibliothek Guava für weitere Datenstrukturen

Verwendete Datentypen in diesem Kapitel:

1.1. Die Typen der Collection-API

Die Liste der verwendeten Typen ist ja diesmal lang. Allerdings folgt das Design einem grundlegenden Prinzip, sodass es dann doch nicht so kompliziert ist:

  • Schnittstellen beschreiben die Funktionalität einer Datenstruktur, das »was wird geboten«.

  • Klassen nutzen verschiedene Strategien, um die Vorschriften aus den Schnittstellen umzusetzen; sie stehen für das »wie wird es implementiert«.

Als Entwickler müssen wir Schnittstellen und Implementierungen kennen, und zur Wiederholung schauen wir uns die zentralen Typen noch einmal an, die uns in diesem Kapitel öfter begegnen werden:

Collection Classes UML
Abbildung 1. UML-Diagramm ausgewählter Datenstrukturen und Typbeziehungen

Festzuhalten ist:

  • Iterable ist die allgemeinste Schnittstelle, die für das steht, was abgelaufen werden kann; Iterable liefert Iterator-Instanzen. Nicht nur Datenstrukturen sind Iterable.

  • Collection ist die oberste Schnittstelle, die wirklich für Datenstrukturen steht. Sie schreibt Methoden vor zum Hinzufügen von Elementen zur Sammlung oder zum Löschen.

  • Unter Collection stehen die eigentlichen Abstraktionen, ob es sich um eine Liste, Menge oder Queue handelt. Darunter finden sich die Implementierungen.

  • Einige Operationen befinden sich nicht bei den Datentypen selbst, sondern sind ausgelagert in eine Klasse Collections. Ähnliches gilt für Arrays, wo es auch eine Utility-Klasse Arrays gibt.

Wir wollen für die Klassen und Schnittstellen java.util.Set, java.util.List, java.util.Map, java.util.HashSet, java.util.TreeSet, java.util.Hashtable, java.util.HashMap und java.util.TreeMap einen Entscheidungsbaum aufbauen. Folgende Überlegungen müssen bei der Auswahl angestellt werden:

  • Zugriff über Schlüssel

  • Duplikate erlaubt

  • schneller Zugriff

  • sortiertes Iterieren

  • threadsicher

Sollte der Zugriff von einem Schlüssel auf einen Wert erfolgen, so ist das im Allgemeinen ein Assoziativspeicher, das heißt eine Implementierung der Schnittstelle Map. Implementierungen von Map sind HashMap, TreeMap und Hashtable. Allerdings sind auch Listen besondere Assoziativspeicher, wobei der Index eine ganze Zahl ist, der bei 0 beginnt und aufsteigend ist. Listen funktionieren immer dann ganz gut, wenn der Schlüssel eine kleine Ganzzahl ist und es wenig Leerräume gibt. Eine Assoziation von beliebigen Ganzzahlen auf Objekte lässt sich mit einer Liste nicht gut abbilden.

Duplikate sind in Listen erlaubt, allerdings nicht in Mengen und Assoziativspeichern. Es gibt durchaus Anforderungen, dass eine Menge vermerken soll, wie oft ein Element vorkommt, doch das muss selbst implementiert werden mit einem Assoziativspeicher, der das Element mit einem Zähler verbindet.

Einen schnellen Zugriff erlauben alle Datenstrukturen. Die Frage ist nur, wonach man fragt. Eine Liste kann nicht schnell die Frage beantworten, ob ein Element vorhanden ist oder nicht, denn die Liste muss dafür von vorne nach hinten durchlaufen werden. Bei einem Assoziativspeicher oder einer Menge ist diese Abfrage durch die interne Organisation der Daten sehr viel schneller. Dieser Existenztest lässt sich bei Datenstrukturen, die intern mit dem Hashing-Verfahren arbeiten, noch etwas schneller beantworten als bei Datenstrukturen, die Elemente sortiert halten.

Listen lassen sich sortieren, und das Ablaufen liefert die Elemente in der sortierten Reihenfolge. Ein TreeSet und eine TreeMap sind ebenfalls nach einem Kriterium sortiert. Die Datenstrukturen mit dem Hashing-Verfahren haben keine benutzerdefinierte Sortierung.

Datenstrukturen lassen sich in drei Gruppen einteilen: Datenstrukturen seit Java 1.0, Datenstrukturen seit Java 1.2 und Datenstrukturen seit Java 5. In den ersten Java-Versionen wurden die Datenstrukturen Vector, Hashtable, Dictionary und Stack eingeführt. Diese Datenstrukturen sind alle threadsicher, doch werden sie heute nicht mehr verwendet. In Java 1.2 wurde die Collection-API eingeführt, alle Datenstrukturen sind nicht threadsicher. Unter Java 5 ist das neue Paket java.util.concurrent eingeführt worden, alle Datenstrukturen dort sind sicher gegen nebenläufige Veränderungen.

1.2. Listen

Bei den Aufgaben wollen wir mit der einfachsten Datenstruktur einsteigen, den Listen. Listen sind Sequenzen von Informationen, bei der die Reihenfolge beim Anhängen neuer Elemente beibehalten wird und Elemente mehrfach vorkommen können. Auch null ist als Element erlaubt.

1.2.1. Singen und Kochen: Listen ablaufen und Eigenschaften prüfen ⭐

Captain CiaoCiao stellt eine neue Mannschaft zusammen. Alle in der Crew haben einen Namen und einen Beruf:

record CrewMember( String name, Profession profession ) {
  enum Profession { CAPTAIN, NAVIGATOR, CARPENTER, COOK, MUSICIAN, DOCTOR }
}

Bei jeder Crew achtet Captain CiaoCiao darauf, dass es genauso viele Köche wie Musiker gibt.

Aufgabe:

  • Schreibe eine Methode areSameNumberOfCooksAndMusicians(List<CrewMember>), die true zurückgibt, wenn es gleich viele Köche wie Musiker gibt, sonst false.

Beispiel:

CrewMember captain   = new CrewMember( "CiaoCiao", CrewMember.Profession.CAPTAIN );
CrewMember cook1     = new CrewMember( "Remy", CrewMember.Profession.COOK );
CrewMember cook2     = new CrewMember( "The Witch Cook", CrewMember.Profession.COOK );
CrewMember musician1 = new CrewMember( "Mahna Mahna", CrewMember.Profession.MUSICIAN );
CrewMember musician2 = new CrewMember( "Rowlf", CrewMember.Profession.MUSICIAN );

List<CrewMember> crew1 = List.of( cook1, musician1 );
System.out.println( areSameNumberOfCooksAndMusicians( crew1 ) ); // true

List<CrewMember> crew2 = List.of( cook1, musician1, musician2, captain );
System.out.println( areSameNumberOfCooksAndMusicians( crew2 ) ); // false

List<CrewMember> crew3 = List.of( cook1, musician1, musician2, captain, cook2  );
System.out.println( areSameNumberOfCooksAndMusicians( crew3 ) ); // true

Java 8 Backport

Die Aufgabe greift bei CrewMember auf ein Record zurück. Das kann problemlos durch eine Klasse mit den Objektvariablen String name, Profession profession und einem geschachtelten Typ Profession ausgedrückt werden.

1.2.2. Kommentare aus Listen filtern ⭐

Bonny Brain liest ein altes Logbuch von Captain Dipturus Dimwit, das wiederholt immer vier Einträge enthält:

  1. Magnetkompasskurs [1]

  2. Geschwindigkeit der Wasserströmung

  3. Wetter

  4. Kommentare und allgemeine Beobachtungen

Bonny Brain sucht nach einem bestimmten Eintrag in den Kommentaren, daher sollen aus einer Liste mit Zeichenfolgen der erste, zweite und dritte Eintrag gelöscht werden, dass nur noch der vierte Eintrag mit dem Kommentar übrigbleibt.

Aufgabe:

  • Realisiere eine Methode void reduceToComments(List<String> lines), die jeweils den ersten, zweiten und dritten Eintrag in der übergebenen Liste löscht und nur den vierten behält.

Beispiele:

  • "A1", "A2", "A3", "A4", "B1", "B2", "B3", "B4", "C1", "C2", "C3", "C4""A4", "B4", "C4"

  • leere Liste → nichts passiert

  • "A1" → Ausnahme Illegal size 1 of list, must be divisible by 4

1.2.3. Listen kürzen, denn Abschwung gibt es nicht ⭐

Für Captain CiaoCiao soll es immer nur bergauf gehen; wenn er Zahlenfolgen liest, sollen sie immer nur aufsteigen.

Aufgabe:

  • Schreibe eine Methode trimNonGrowingNumbers(List<Double> numbers), die die Liste abschneidet, wenn die nächste Zahl nicht mehr größer oder gleich der vorherigen ist.

  • Bedenke: Die übergebene Liste muss veränderbar sein, sodass Elemente gelöscht werden können.

Beispiele:

  • Wenn die Liste die Zahlen 1, 2, 3, 4, 5 enthält, bleibt die Liste so.

  • Enthält die Liste die Zahlen 1, 2, 3, 2, 1, wird die Sequenz gekürzt zu 1, 2, 3.

1.2.4. Essen mit Freunden: Elemente vergleichen, Gemeinsamkeiten finden ⭐

Bonny Brain plant auf dem Festland eine Party, und in einem großen Kreis sollen immer zwei Gäste nebeneinandersitzen, die mindestens eine Gemeinsamkeit haben. Gäste sind durch den folgenden Typ deklariert:

public record Guest(
    boolean likesToShoot,
    boolean likesToGamble,
    boolean likesBlackmail
) { }

Aufgabe:

  • Schreibe eine Methode int allGuestsHaveSimilarInterests(List<Guest> guests), die -1 liefert, wenn alle Gäste einen Nachbarn haben, der in mindestens einer Eigenschaft übereinstimmt. Andernfalls ist die Rückgabe >= 0 und der Index auf genau dem ersten Gast, der falsch sitzt, also mit keinem seiner Nachbarn etwas gemeinsam hat.

  • Der Typ Guest kann beliebig erweitert werden.

Java 8 Backport

Records sind neu in Java 16; in älteren Java-Versionen implementiere Guest als Klasse:

public class Guest {
  public boolean likesToShoot;
  public boolean likesToGamble;
  public boolean likesBlackmail;
}

1.2.5. Listen auf gleiche Reihenfolge der Elemente prüfen ⭐

Fat Donny Bone Spurs und Ally Al Lyons schmuggeln sich in die Selbsthilfegruppe der anonymen Freibeuter und sollen Captain CiaoCiao berichten, wer im Gesprächskreis rechts neben wem sitzt. Beide versuchen, sich zu erinnern. Sie fangen bei ihren Aufzählungen nicht zwangsläufig mit derselben Person an.

Aufgabe:

  • Schreibe eine Methode isSameCircle(List<String> names1, List<String> names2), die testet, ob die Namen in den beiden Listen in der gleichen Reihenfolge unmittelbar aufeinanderfolgen. Bedenke, dass die Personen im Kreis sitzen und die letzte Person in der Liste neben der ersten Person der Liste »sitzt«.

Beispiele:

  • Liste 1: Alexandre, Charles, Anne, Henry. Liste 2: Alexandre, Charles, Anne, Henry → stimmen überein

  • Liste 1: Anne, Henry, Alexandre, Charles, Liste 2: Alexandre, Charles, Anne, Henry → stimmen überein

  • Liste 1: Alexandre, Charles, Anne, Henry. Liste 2: Alexandre, Charles, Henry, Anne → stimmen nicht überein

  • Liste 1: Anne, Henry, Alexandre, Charles, Liste 2: Alexandre, William, Anne, Henry → stimmen nicht überein

1.2.6. Und jetzt das Wetter: Wiederholte Elemente finden ⭐

Napoleon Nase unterhält sich mit Bonny Brain über das Wetter: »Wir hatten die letzten Monate so viele Regentage hintereinander, das war schlecht für Kaperungen.« Bonny Brain antwortet: »So viele Regentage waren das nicht hintereinander!«. Wer hat recht?

Gegeben ist eine Liste von Wetterdaten:

Regen, Sonne, Regen, Regen, Hagel, Schnee, Sturm, Sonne, Sonne, Sonne, Regen, Regen, Sonne

In der Liste kommt Sonne dreimal hintereinander vor. Das wollen wir wissen. Zwar kommt Regen in der Liste insgesamt häufiger vor, doch das ist für die Lösung nicht relevant.

Aufgabe:

  • Lege eine neues Record WeatherOccurrence für Wetterinformationen an:

    record WeatherOccurrence( String weather, int occurrences, int startIndex ) { }
  • Implementiere eine Methode WeatherOccurrence longestSequenceOfSameWeather(List<String> weather), die verrät,

    • welches Wetter

    • wie oft am häufigsten direkt hintereinander in der Liste auftaucht und

    • wo die längste Liste anfängt.

      Kommt ein Wetter hintereinander gleich oft vor, kann die Methode frei entscheiden, was sie liefert. Elemente dürfen null sein.

Java 8 Backport

Records gibt es seit Java 16, in älteren Versionen nutzen wir eine Klasse: class WeatherOccurrence { String weather; int occurrences; int startIndex; }. Es ist dann sinnvoll, eine toString()-Methode zu schreiben.

1.2.7. Bon-Ausgaben erzeugen ⭐

Ein Kassenbon enthält Einträge und Informationen wie Anzahl, Produktname, Preis, Gesamtsumme.

Programmiere in dieser Aufgabe einen Kassenbon.

Aufgabe:

  • Lege eine neue Klasse Receipt für den Bon an.

  • Ein Bon besteht aus Einträgen vom Typ Item. Lege die Klasse Item als geschachtelten Typ in Receipt.

  • Jedes Item hat einen Namen und einen (brutto) Preis, der in Cent gespeichert ist.

  • Receipt soll toString() überschreiben und einen formatierten Bon liefern:

    • Gib alle Produkte und die Summe aus.

    • Einträge können auf dem Bon mehrmals vorkommen und sollen zusammengefasst werden. Es stehen zum Beispiel nicht Nüsse, Nüsse untereinander, sondern 2x Nüsse. Die Einträge müssen für die Gleichwertigkeit den gleichen Namen und Preis haben.

    • Verwende NumberFormat.getCurrencyInstance(Locale.GERMANY), um die Währung zu formatieren.

Beispiel:

  • Mit dem Aufbau

    Receipt receipt = new Receipt();
    receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
    receipt.addItem( new Receipt.Item( "Lightsaber", 19999 ) );
    receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
    receipt.addItem( new Receipt.Item( "Log book", 1000 ) );
    receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
    System.out.println( receipt );

    ist die Ausgabe:

    3x  Peanuts                 2,22 €    6,66 €
    1x  Lightsaber            199,99 €  199,99 €
    1x  Log book               10,00 €   10,00 €
    
    Sum: 216,65 €

1.2.8. Alles schmeckt besser mit Käse: In Listen Elemente einfügen ⭐

Captain CiaoCiao mag Gemüse, aber wenn, dann muss ordentlich Käse dazu.

Aufgabe:

  • Schreibe eine Methode insertCheeseAroundVegetable(List), die eine Liste von Rezeptzutaten bekommt und immer dann, wenn Gemüse in der Liste vorkommt, die Zutat »Käse« direkt davor oder dahinter ergänzt.

  • Die Liste muss veränderbar sein.

Beispiele:

  • Gnocchi, Zucchini, Paprika, Sahne, Brühe, Milch, Butter, Zwiebel, Tomate, Salz, Pfeffer → Gnocchi, Zucchini, Käse, Paprika, Käse, Sahne, Brühe, Milch, Butter, Zwiebel, Käse, Tomate, Käse, Salz, Pfeffer

  • Käse → Käse

Greife auf eine feste Menge von Gemüsesorten zurück.

1.2.9. Elemente mit dem Iterator suchen und Covid Cough finden ⭐⭐

Bonny Brain rennt zum Hafen und sucht Covid Cough, der in seinem Schiff Desinfektionsmittel bunkert. Jedes Schiff enthält eine Liste mit Passagiernamen. Schiffe sind durch folgende kleine Klasse deklariert:

class Ship {
  private List<String> persons = new ArrayList<>();
  void addName( String name ) { persons.add( name ); }
  boolean contains( String name ) { return persons.contains( name ); }
  @Override public String toString() {
    return "" + persons;
  }
}

Am Hafen liegen 100 Schiffe, die in einer LinkedList<Ship> gespeichert sind. Covid Cough versteckt sich in einem unbekannten Schiff, simulieren wir das:

final int NUMBER_OF_SHIPS = 100;

List<Ship> ships = new LinkedList<>();
for ( int i = 0; i < NUMBER_OF_SHIPS; i++ )
  ships.add( new Ship() );

ships.get( new Random().nextInt( ships.size() ) ).addName( "Covid Cough" );

Bonny Brain kommt an einem der vielen Zugänge zum Hafen an und rechts sowie links von ihr liegen Schiffe:

int index = new Random().nextInt( ships.size() );
ListIterator<Ship> iterator = ships.listIterator( index );

Der einzige Zugriff auf die Schiffe ist durch den ListIterator gegeben. Bedenke, dass man mit dem ListIterator nur nach vorne und zurück gehen kann, es gibt keinen wahlfreien Zugriff!

Aufgabe:

  • Besuche mit dem ListIterator die Schiffe, und finde Covid Cough.

  • Gibt es eine Strategie, wie wir die Person am schnellsten finden? Es ist bekannt, wie viele Schiffe es insgesamt gibt, nämlich 100. Da der Index bekannt ist, an der Bonny Brain den Hafen betritt, weiß man auch, wie viele Schiffe links und rechts vom Eingang liegen.

1.2.10. Elemente verschieben, Reise nach Jerusalem spielen ⭐

Bei einer Geburtstagsfeier spielen die Gäste Reise nach Jerusalem (engl. musical chairs). Die Personen sitzen auf Stühlen, und wenn die Musik anfängt zu spielen, stehen sie auf und laufen um die Stühle. Die Namen der Gäste befinden sich in einer Liste.

Aufgabe A:

  • Lege eine neue Klasse MusicalChairs an.

  • Lege einen Konstruktor MusicalChairs(String... names) an, der die Namen intern speichert.

  • Implementiere die Methode toString(), die die Namen kommasepariert liefert.

  • Schreibe eine Methode rotate(int distance), die die Namen in der Liste um die Position distance nach rechts verschiebt. Die rechts herausfallenden Elemente werden links wieder eingeschoben. Die Operation ist in place, die (interne) Liste selbst wird also verändert, und die Methode liefert keine Rückgabe.

Nutze für die Aufgabe eine passende Methode aus Collections.

Beispiel:

MusicalChairs musicalChairs =
    new MusicalChairs( "Laser", "Milka", "Popo", "Despot" );
musicalChairs.rotate( 2 );
System.out.println( musicalChairs ); // Popo, Despot, Laser, Milka

Aufgabe B:

  • Schreibe eine weitere Methode void rotateAndRemoveLast(int distance), die zunächst die Liste um distance Positionen nach rechts verschiebt und dann das letzte Element löscht.

  • Ergänze eine Methode String play(), die rotateAndRemoveLast(…​) in einer Schleife so oft aufruft, bis es nur noch ein Element in der Liste gibt; dann steht der Sieger fest, und er wird als String zurückgegeben. Die Distanz ist bei jedem Durchlauf zufällig.

Berücksichtige bei der Lösung den Fall, dass die Liste leer sein könnte.

1.2.11. Fragespiel mit Planeten programmieren ⭐⭐

Captain CiaoCiao nimmt neue Rekruten an, und um ihr Wissen zu testen, fragt er sie nach dem Durchmesser der Planeten des Sonnensystems. Er wünscht sich dafür eine interaktive Anwendung, bei der zufällig ein Planet ausgewählt wird, und die Rekruten müssen den Durchmesser kennen.

Die Planeten sind als Aufzählungstyp vordefiniert:

Listing 1. com/tutego/exercise/util/PlanetQuiz.java
enum Planet {

  JUPITER( "Jupiter", 139_822 ), SATURN( "Saturn", 116_464 ),
  URANUS( "Uranus", 50_724 ), NEPTUNE( "Neptune", 49_248 ),
  EARTH( "Earth", 12_756 ), VENUS( "Venus,", 12_104 ),
  MARS( "Mars", 6_780 ), MERCURY( "Mercury", 4_780 ),
  PLUTO( "Pluto", 2_400 );

  public final String name;
  public final int    diameter; // km

  Planet( String name, int diameter ) {
    this.name     = name;
    this.diameter = diameter;
  }
}

Aufgabe:

  • Programmiere eine Konsolenanwendung, die im ersten Schritt eine zufällige Reihenfolge aller Planeten aufbaut. Überlege, wie wir die Methode shuffle(…​) aus java.util.Collections dafür nutzen können.

  • Iteriere über diese zufällige Folge von Planeten, und erzeuge eine Konsolenausgabe, die nach dem Durchmesser dieser Planeten fragt. Als Auswahlmöglichkeit soll der Rekrut vier Durchmesser in Kilometer angezeigt bekommen, wobei ein Durchmesser der korrekte ist und drei Durchmesser von unterschiedlichen Planeten stammen.

  • Gibt der Rekrut den richtigen Durchmesser ein, erscheint auf dem Bildschirm eine Meldung; wenn der falsche Durchmesser eingegeben wurde, meldet die Konsolenausgabe den korrekten Durchmesser.

Beispiel:

What is the diameter of planet Uranus (in km)?
49248 km
50724 km
12756 km
139822 km
50724
Correct!

What is the diameter of planet Pluto (in km)?
12104 km
4780 km
2400 km
12756 km
11111
Wrong! The diameter of Pluto is 2400 km.

What is the diameter of planet Jupiter (in km)?
139822 km
6780 km
2400 km
49248 km
...

1.2.12. Implementierung der Klasse java.util.ArrayList verstehen ⭐⭐

Eine java.util.ArrayList ist eine wichtige Datenstruktur. Sie konkurriert direkt mit einem Array. Zwei Fragen kommen in den Sinn: Wie ist die ArrayList eigentlich implementiert, und wie groß könnte der Geschwindigkeitsunterschied sein?

  • Unter https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java kann man die Quellen der Implementierung einsehen. Schaffe dir einen Überblick.

  • Intern nutzt die Implementierung für die Daten das Array elementData. Wie gelingt die Implementierung von get(int) und set(…)? Wie sind die "Kosten"?

  • Wo wird das Array-Objekt elementData angelegt?

  • Eine ArrayList ist in der Regel immer ein bisschen größer als die Anzahl der aktuellen Elemente, als Art Puffer. Die Größe nennt man Kapazität. Wenn man ein ArrayList-Objekt mit dem Standard-Konstruktor aufbaut, für wie viele Elemente ist im Array Platz?

  • Wenn beim Einfügen das Array zu klein ist, vergrößert ensureCapacity(…​) das Array. Wie funktioniert die Methode? Welche Strategie steckt dahinter?

  • Baue eine ArrayList mit dem Standard-Konstruktor auf und füge 1.000 Elemente an. Wie viele Kopieroperationen sind nötig?

1.3. Mengen

Mengen enthalten ihre Elemente nur einmal. Sie können unsortiert oder sortiert sein. Java sieht für die Abstraktion die Schnittstelle Set vor, zwei wichtige Implementierungen sind HashSet und TreeSet.

Bei Mengen stellt sich eine ganze Reihe von Fragen:

  1. Ist die Menge leer?

  2. Welche Elemente befinden sich in der Menge?

  3. Ist ein gefragtes Element in der Menge, ja oder nein?

  4. Wenn zwei Mengen gegeben sind, enthalten sie beide die gleichen Elemente?

  5. Wie sieht eine neue Menge aus, wenn zwei Mengen vereinigt werden?

  6. Enthält die Menge eine andere Menge vollständig, ist also eine Menge eine Teilmenge einer anderen?

  7. Was ist bei zwei Mengen die Schnittmenge, also welches sind die Elemente, die in beiden Mengen vorkommen?

  8. Wie sieht die Differenzmenge aus, wenn man also Elemente aus einer Menge löscht, die in einer anderen Menge vorhanden sind?

Einige dieser Operationen lassen sich direkt über den Datentyp Set beantworten. So gibt es z. B. die Methoden isEmpty() oder contains(…​). Insbesondere die Mengenoperationen sind nicht sehr gut abgebildet, und Programmierer müssen für sie manchmal Umwege gehen. Für Teilmengen gibt es beispielsweise die Collections-Methode disjoint(Collection<?>, Collection<?>), doch sie liefert ein boolean, das besagt, ob die beiden Sammlungen kein gemeinsames Element haben.

Beantworten wir einige der Fragen durch Aufgaben.

1.3.1. Teilmengen bilden, Gemeinsamkeiten herausfinden ⭐

Die Tochter von Bonny Brain datet Cora Corona, und sie wollen herausfinden, ob sie zusammenpassen. So schreiben beide auf, was sie mögen. Das sieht so aus:

Set<String> me = new HashSet<>();
Collections.addAll( he, "Candy making", "Billiards", "Fishkeeping", "Eating", "Action figures", "Birdwatching", "Axe throwing" );
Set<String> she = new HashSet<>();
Collections.addAll( she, "Axe throwing", "Candy making", "Action figures", "Casemodding", "Skiing", "Satellite watching" );

Aufgabe:

  • Wie viel Prozent Übereinstimmung haben beide? Mit welchen Methoden können wir die Frage beantworten?

Schaue nach Methoden in Set, ob damit Teilmengen oder Schnittmengen gebildet werden können.

1.3.2. Doppelte Elemente aus Arrays entfernen ⭐

Aufgabe:

  • Lege eine statische Methode double[] unique(double... values) an, die ein Array mit allen Elementen des übergebenen Arrays in der gleichen Reihenfolge zurückgibt, allerdings keine doppelten Einträge.

  • Bei dem Argument null muss die Methode eine Ausnahme auslösen.

Beispiel:

Listing 2. com/tutego/exercise/util/UniqueArrayElements.java
System.out.println( Arrays.toString( unique() ) ); //                                    []
System.out.println( Arrays.toString( unique( 1, 2 ) ) ); //                      [1.0, 2.0]
System.out.println( Arrays.toString( unique( 1, 1 ) ) ); //                           [1.0]
System.out.println( Arrays.toString( unique( 1, 2, 1 ) ) ); //                   [1.0, 2.0]
System.out.println( Arrays.toString( unique( 1, 2, 1, Double.NaN ) ) ); //  [1.0, 2.0, NaN]
System.out.println( Arrays.toString( unique( 1, Double.NaN, Double.NaN ) ) ); // [1.0, NaN]
System.out.println( Arrays.toString( unique( -0, 0 ) ) ); //                [1.0, 2.0, NaN]

1.3.3. Alle in einem Wort enthaltenen Wörter ermitteln ⭐⭐

Captain CiaoCiao fängt eine geheime Nachricht ab, und der Text besteht aus Wörtern, die scheinbar zusammenhangslos sind. Nach etwas Grübeln fällt ihm auf, dass in den Wörtern andere Wörter stecken. In »Rhabarbermarmelade« findet er unter anderem »Rhabarber«, »marmelade«, »arme«, »arm«, »lade«, »hab«.

Ein Programm soll herausfinden, welche gültigen Wörter ein gegebenes Wort enthält. Um herauszufinden, was ein gültiges Wort ist, kann man auf eine Wortliste aus dem Internet zurückgreifen:

Aufgabe:

  • Schreibe ein Programm mit einer statischen Methode Collection<String> wordList(String string, Collection<String> words), die alle in string enthaltenen Teil-Strings generiert und genau die Wörter in einer Collection zurückliefert, die in dem Wörterbuch words gültige Wörter sind.

Beispiel für das englische Wörterbuch:

  • wordList( "wristwatches", words )[wrist, wristwatch, wristwatches, rist, ist, twa, twat, wat, watch, watches, tch, tche, che, hes]

  • bibliophobia[abib, bib, bibl, bibliophobia, pho, phobia, hob, obi, obia]

Eine Datei mit Wörtern lässt sich so in eine Datenstruktur überführen:

private static final String WORD_LIST_URL =
    "https://raw.githubusercontent.com/creativecouple/all-the-german-words/master/corpus/de.txt";
    // "https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt";

private static Collection<String> readWords() throws IOException {
  URL url = new URL( WORD_LIST_URL ); //    370.000 words
  Collection<String> words = new HashSet<>( 500_000 );
  try ( InputStream is = url.openStream() ) {
    new Scanner( is ).forEachRemaining( s -> words.add( s.toLowerCase() ) );
  }
  return words;
}

1.3.4. Fast Gleiches richtig sortieren ⭐⭐

Gegeben ist eine Sammlung von Strings, etwa so:

"-13.123", "0", "0", "10101010", "10101010.0", "0.0", "-0.0",

Aufgabe:

  • Diese Liste soll sortiert werden, dabei sind doppelte Elemente zu entfernen, wie etwa die zweite "0".

  • Zwar sind "0", "0.0", "-0.0" als numerische Werte gleich, aber sie sollen trotzdem als drei Einträge erhalten bleiben.

  • Die Zahlen können beliebig lang sein und beliebig viele Nachkommastellen haben.

Gäben wir die obere Liste nach der Sortierung aus, käme etwa Folgendes auf den Bildschirm:

[-13.123, -0.0, 0, 0.0, 10101010, 10101010.0]

1.3.5. Mit einem UniqueIterator doppelte Elemente ausschließen ⭐⭐

In anderen Datenstrukturen, zum Beispiel Listen, können Elemente mehrfach vorkommen. Schreibe einen UniqueIterator, der Elemente einer Collection nur einmal liefert.

Die generischen Typen werden wie folgt deklariert:

public class UniqueIterator<E> implements Iterator<E> {

  public UniqueIterator( Iterator<? extends E> iterator ) {
    // ...
  }

  // usw.
}

Am Konstruktor ist abzulesen, dass der neue Iterator einen existierenden Iterator als Parameter bekommt. Ein Aufruf könnte also so aussehen:

List<String> names = ...;
Iterator<String> UniqueIterator = new UniqueIterator( names.iterator( ) );

1.4. Assoziativspeicher

Assoziativspeicher verbinden Schlüssel mit Werten. In anderen Programmiersprachen werden sie auch Dictionary genannt. Java schreibt über die Schnittstelle Map die Operationen für alle Implementierungen vor. Zwei wichtige Implementierungen sind HashMap und TreeMap.

1.4.1. Zweidimensionale Arrays in Map konvertieren ⭐

Datentypen, die von Collection erben, sind relativ flexibel in der Annahme von Daten, so lassen sich zum Beispiel die Elemente einer List über addAll(Collection) in ein Set kopieren. Auch Arrays lassen sich mit Arrays.asList(…​) direkt als Collection nutzen.

Der Datentyp Map ist weniger flexibel, es lassen sich nicht einfach Arrays oder andere Collection-Sammlungen in eine Map überführen.

Aufgabe:

  • Schreibe eine Methode Map<String, String> convertToMap(String[][]), die ein zweidimensionales Array in eine java.util.Map konvertiert.

  • Der erste Eintrag im Array soll der Schlüssel, der zweite der Wert sein.

  • Die Schlüssel implementieren korrekt hashCode() und equals(…​).

  • Kommt später im Array der gleiche Schlüssel nochmals vor, überschreibt die Methode das frühere Pärchen.

  • Schlüssel und Werte dürfen nicht null sein und müssen zu einer Ausnahme führen.

Beispiel:

String[][] array = {
    { "red",   "#FF0000" },
    { "green", "#00FF00" },
    { "blue",  "#0000FF" }
};
Map<String, String> colorMap = convertToMap( array );
System.out.println( colorMap ); // {red=#FF0000, green=#00FF00, blue=#0000FF}

1.4.2. Text in Morsecode konvertieren und umgekehrt ⭐

Captain CiaoCiao muss zu einer entfernten Insel eine Nachricht über Morsecode verschicken. Ein Morse-Funkspruch besteht aus kurzen und langen Symbolen, die mit den Zeichen . und - angedeutet sind.

Kopiere die folgende Definition in eine neue Klasse Morse:

// A .-      N -.      0 -----
// B -...    O ---     1 .----
// C -.-.    P .--.    2 ..---
// D -..     Q --.-    3 ...--
// E .       R .-.     4 ....-
// F ..-.    S ...     5 .....
// G --.     T -       6 -....
// H ....    U ..-     7 --...
// I ..      V ...-    8 ---..
// J .---    W .--     9 ----.
// K -.-     X -..-
// L .-..    Y -.--
// M --      Z --..

Aufgabe:

  • Lege eine neue Klasse Morse an.

  • Schreibe zwei Methoden:

    • String encode(String string). Sie nimmt einen String an und konvertiert ihn in Morsecode. Jedes Zeichen der Zeichenfolge soll im entsprechenden Morsecode ausgegeben werden. Jeder Block soll dabei in der Ausgabe durch ein Leerzeichen getrennt sein. Nicht bekannte Zeichen werden übersprungen. Kleinbuchstaben sollen wie Großbuchstaben gewertet werden. Zwischen den Wörtern gibt es zwei Leerzeichen.

    • String decode(String string). Macht aus Morsecode wieder die Originalzeichenketten. Die zwei Leerzeichen für Worttrenner werden wieder zu einzelnen Leerzeichen.

1.4.3. Worthäufigkeit mit Assoziativspeicher merken ⭐⭐

Girly Gossip lauscht auf dem Deck einer Gruppe, damit sie Captain CiaoCiao später erzählen kann, was gerade diskutiert wird. Wichtig ist das, was als Wort oder Wortfügung oft genannt wird.

Aufgabe:

  • Schreibe eine Methode List<String> importantGossip(String... words), die aus einem Vararg von Zeichenfolgen genau die fünf Zeichenketten in einer Liste zurückliefert, die am häufigsten im übergebenen Array vorkommen.

Beispiel:

String[] words = {
    "Baby Shark", "Corona", "Baby Yoda", "Corona", "Baby Yoda", "Tiger King",
    "David Bowie", "Kylie Jenner", "Kardashian", "Love Island", "Bachelorette",
    "Baby Yoda", "Tiger King", "Billie Eilish", "Corona"
};
System.out.println( importantGossip( words ) );

gibt aus

[Baby Yoda, Corona, Tiger King, Baby Shark, Bachelorette]

Bedenke, dass es nicht um die einzelnen Wörter wie Baby oder Yoda geht, sondern immer um den gesamten String, also etwa Baby Yoda oder Baby Shark.

1.4.4. Farben einlesen und vorlesen lassen ⭐⭐

Bonny Brain bekommt ein neues Design für ihre Flaggen, doch die Designer sprechen nur Kauderwelsch:

Für den Hintergrund nehmen wir #89cff0 oder #bcd4e6 und für den Text vielleicht #fffaf0 oder #f8f8ff.

Sie findet heraus, dass eine Angabe wie #RRGGBB für den Rot-, Grün-, Blauanteil einer Farbe steht, hexadezimal kodiert. Zum Glück gibt es »Übersetzungstabellen« wie https://tutego.de/download/colors.csv, die Zeilen enthält wie

amber,"Amber",#ffbf00,255,191,0
aqua,"Aqua",#0ff,0,255,255
blush,"Blush",#de5d83,222,93,131
wine,"Wine",#722f37,114,47,55

Teilweise stehen in der Datei die Farbwerte nur mit drei Symbolen, etwa wie im Beispiel aqua mit 0ff. In dem Fall werden die einzelnen Farbangaben verdoppelt, also wird aus #RGB dann #RRGGBB.

Aufgabe:

  1. Lege für die Repräsentation von Farben eine neue Klasse Color an. Jede Farbe hat einen Namen (String name) und einen RGB-Wert (int rgb). Schreibe — oder generiere über die IDE — die Methode toString(). Ergänze weitere Methoden, falls das sinnvoll ist.

  2. Lege eine neue Klasse ColorNames an.

    • Gib der Klasse eine Objektvariable HashMap<Integer, Color> colorMap, damit sich ColorNames intern alle Color-Objekte in einer Map merken kann; die Schlüssel der Map sind die RGB-Werte als Ganzzahl, und der assoziierte Wert ist das entsprechende Color-Objekt.

    • Kopiere die Datei https://tutego.de/download/colors.csv lokal auf die Festplatte.

    • Lege einen Konstruktor an, der die Datei einliest. Wir können dafür den Scanner einsetzen, oder die Datei komplett mit Files.readAllLines(Paths.get("colors.csv")) einlesen, was eine List<String> liefert.

    • Zerlege jede Zeile der CSV-Quelle, extrahiere den Farbnamen (2. Spalte) und RGB-Wert (3. Spalte). Tipp: Der Farbwert lässt sich mit einer Java-Methode in eine Ganzzahl konvertieren: Integer.decode("#722f37") liefert 7483191. Bedenke, dass Farbangaben in der Form #RGB und #RRGBB auftreten können.

    • Übertrage den Farbnamen und Ganzzahlwert auf Color-Objekte, und setze sie in die Map.

    • Füge eine Methode decode(int rgb) ein, die für einen RGB-Wert das assoziierte Color-Objekt liefert.

Beispiel:

  • mapper.decode( 7483191 )Optional['Wine' is RGB #722F37]

  • mapper.decode( 7 )Optional.empty

1.4.5. Namen einlesen und Längen verwalten ⭐

Bonny Brain spielt gerne Namens-Kreuzworträtsel, wo jeder Eintrag ein Name ist. Oftmals fällt ihr kein Name mit einer gewissen Länge ein — eine Software soll helfen!

Aufgabe:

  1. Die Datei http://tutego.de/download/family-names.txt enthält Nachnamen. Speichere die Datei auf dem eigenen Dateisystem.

  2. Lies die Datei ein. Dafür können wir zum Beispiel die Klasse Scanner einsetzen oder die Files-Methode readAllLines(Path).

  3. Sortiere die Namen in ein TreeMap<Integer, List<String>> ein: Der Schlüssel ist die Länge des Namens, die Liste enthält alle Namen mit der gleichen Länge.

  4. Liste auf der Kommandozeile alle Namen aufsteigend der Länge nach auf.

  5. Frage von der Kommandozeile nach einer Länge und gibt alle Namen dieser Länge aus, solange die Länge nicht 0 oder negativ ist.

1.4.6. Fehlende Zeichen finden ⭐⭐

Captain CiaoCiao hat sich die Schriftrollen vom Toten Meer (Cumexhopp-Rollen) ergaunert und keiner konnte den Text bisher entschlüsseln. Er möchte es schaffen! Viele Zeichen sind jedoch unleserlich, während andere Zeichen gut lesbar sind. Auch ist gut erkenntlich, wie viele Zeichen das Wort hat.

Aufgabe:

  • Lege eine neue Klasse mit main(…​)-Methode an und kopiere die zwei Listen in das Programm:

    List<String> words = Arrays.asList( "house", "mouse", "horn", "cannon" );
    List<String> missingLettersWords = Arrays.asList( "_ouse", "ho__", "ca__on", "gun", "__e__", "_____" );
  • Ordne jedem Wort aus missingLettersWords alle möglichen Wörter aus dem Wörterbuch words zu, bei denen der Unterstrich unbekannte Zeichen symbolisiert.

  • Die Länge der vorgeschlagenen Wörter aus dem Wörterbuch muss gleich der Wortlänge des »unleserlichen« Worts sein.

  • Es muss mindestens ein Zeichen gegeben sein.

Beispiel:

  • Mögliche Bildschirmausgabe aus den gegebenen Listen:

    _ouse -> [mouse, house]
    ho__ -> [horn]
    ca__on -> [cannon]
    gun -> No results
    __e__ -> No results
    _____ -> No results

1.4.7. Anzahl Wege zum dreiköpfigen Affen berechnen ⭐⭐

Nach einer durchzechten Nacht in Manhattan vermisst Captain CiaoCiao seinen dreiköpfigen Affen. Er muss das Stofftier irgendwo auf dem Weg verloren haben! Aber wo könnte es sein? Seine Mannschaft muss alle Straßen vom Start zum Ziel ablaufen. Das Einzige, woran Captain CiaoCiao sich noch erinnern kann, ist dass er nicht über die Diagonale gekommen ist.

Catalan number 4x4 grid example
Abbildung 2. Mögliche Wege vom Start zum Ziel (Quelle: Wikipedia)

Das Bild zeigt 4 × 4 Straßenblöcke und es gibt 14 Möglichkeiten. Nach einiger Zeit des Suchens findet die Crew das Stofftier, Glück gehabt!

Captain CiaoCiao überlegt: Was wäre, wenn es 5 oder 10 Blöcke gäbe — wäre die Anzahl der Wege dann nicht viel zu groß zum Suchen?

Die Antwort auf die Frage liefert die Mathematik. Was hier gesucht wird, ist ein monotoner Pfad für ein Quadrat mit n × n Zellen. Die Anzahl möglicher Pfade liefert die Catalan-Zahl, die wie folgt berechnet wird:

Cn = (2n)! / (n+1)! n!

Aufgabe:

  • Setze die Formel durch eine Methode BigInteger catalan(BigInteger n) um. Greife intern auf eine eigene Methode BigInteger factorial(BigInteger n) zur Fakultätsberechnung zurück.

  • In der Formel müssen drei Fakultäten berechnet werden: n!, (n+1)! und (2n)!. Es ist (n+1)! nichts anderes als n! × (n+1) ist, also muss n! zweimal berechnet werden; auch entsteht auf dem Weg zur Berechnung von (2n)! das Zwischenergebnis (n+1)! Viele Multiplikationen müssen also doppelt gemacht werden, daher sollen die Produkte in einem Cache zwischengespeichert werden: greife dafür auf den Datentyp WeakHashMap zurück.

  • Vergleiche die Zeiten, wenn wir die catalan(…​)-Methode mit den gleichen Parametern zweimal aufrufen. Als Vorlage nutze folgenden Code:

    long start = System.nanoTime();
    BigInteger catalan1000 = catalan( BigInteger.valueOf( 1000 ) );
    long end = System.nanoTime();
    System.out.println( catalan1000 );
    System.out.println( TimeUnit.NANOSECONDS.toMillis( end - start ) );

1.4.8. Feiertage in einem sortierten Assoziativspeicher verwalten ⭐

In einer TreeMap sind die Elemente automatisch sortiert. TreeMap implementiert java.util.NavigableMap, was HashMap hingegen nicht tut. Die Ordnung bestimmt entweder ein externer Comparator, oder die Elemente haben eine natürliche Ordnung.

Der API-Dokumentation entnehmen wir, dass firstEntry() und lastEntry() das kleinste bzw. größte Element liefern. Der Rückgabetyp ist Map.Entry<K,V>.

Ist ein Schlüssel key gegeben, liefern folgende Methoden eine Rückgabe relativ zu diesem Schlüssel:

  • ceilingXXX(K key): Liefert ein Ergebnis, das größer oder gleich diesem Schlüssel ist.

  • floorXXX(K key): Liefert ein Ergebnis, das kleiner oder gleich dem gegebenen Schlüssel ist.

  • lowerXXX(K key): Liefert ein Ergebnis, das echt kleiner als der gegebene Schlüssel ist.

  • higherXXX(K key): Liefert ein Ergebnis, das echt größer als der gegebene Schlüssel ist.

Alle Methoden liefern null, wenn es keine Antwort auf die Frage gibt.

Für Teilmengen bieten sich die folgenden Methoden an:

  • SortedMap<K,V> subMap(K fromKey, K toKey)

  • NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

Im ersten Fall ist fromKey inklusiv und toKey exklusiv; das entspricht der üblichen Konvention von Java. Mit der zweiten Methode lässt sich präziser steuern, ob das Start- oder Endelement dazugehört.

Aufgabe:

  • Baue einen sortierten Assoziativspeicher auf:

    NavigableMap<LocalDate, String> dates = new TreeMap<>();
    dates.put( LocalDate.of(...), "..." );

    Die Typisierung <LocalDate, String> bedeutet, dass ein temporaler Typ LocalDate mit einem String assoziiert werden soll.

  • Die Klasse LocalDate implementiert Comparable, das heißt, die Elemente haben eine natürliche Ordnung.

  • Fülle die Datenstruktur mit einigen Paaren für reale oder fiktive Feiertage.

  • Beantworte mit den passenden Methoden von NavigableMap folgende Fragen:

    • Was ist laut Datenstruktur der früheste und letzte Feiertag?

    • Die Weihnachtsferien enden am 06.01. Was ist nach den Weihnachtsferien der erste Feiertag?

    • Welche Datumswerte liegen in den Weihnachtsferien vom 23.12. – 06.01. (Datumswerte inklusiv)?

    • Lösche die Weihnachtsferien aus der Datenstruktur.

1.4.9. Gemeinsamkeiten bestimmen: Partygedeck und Mitbringsel ⭐

Bonny Brain plant eine Party, und alle Familien bringen etwas mit:

Set<String> gombonoGifts = new HashSet<>();
Collections.addAll( gombonoGifts, "Vodka", "BBQ Grill", "kneading soap" );

Set<String> banannaGifts = new HashSet<>();
Collections.addAll( banannaGifts, "Vodka", "drinking helmet" );

Set<String> cilimbiGifts = new HashSet<>();
Collections.addAll( cilimbiGifts,
                    "drinking helmet", "Money box", "Vodka", "water pistol" );

List<Set<String>> families =
    Arrays.asList( gombonoGifts, banannaGifts, cilimbiGifts );

Da Bonny Brain eine perfekte Strategin ist, will sie wissen, ob Dinge mehrfach mitgebracht werden.

Aufgabe:

  • Schreibe eine Methode printMultipleGifts(List<Set<String>> families), die ausgibt, welche Dinge wie oft mitgebracht werden.

  • Was wurde mehr als einmal mitgebracht?

Beispiel:

  • Mögliche Ausgabe bei den oberen Belegungen:

    {drinking helmet=2, kneading soap=1, water pistol=1, Money box=1, BBQ Grill=1, Vodka=3}
    drinking helmet
    Vodka

1.5. Properties

Die Klasse Properties ist ein besonderer Assoziativspeicher, der nur Strings mit Strings assoziiert. Die Klasse repräsentiert nicht nur eine Datenstruktur, sondern kann auch Dateien lesen und schreiben, die sogenannten Property-Dateien. Das sind Textdateien, die in der Regel zur Konfiguration verwendet werden. Schlüssel-Wert-Paare sind in der Datei durch = getrennt. Auch lassen sich die Werte in einem XML-Format lesen und schreiben, doch das ist unüblich.

1.5.1. Komfortablen Properties-Dekorator entwickeln ⭐⭐

Die Klasse Properties enthält Schlüssel-Wert-Paare, wobei die Schlüssel immer nur Strings sind. Mögliche Konvertierungen müssen Entwickler selbst vornehmen, was lästig ist.

Aufgabe:

Schreibe eine Klasse PropertiesConfiguration, die ein Properties-Objekt dekoriert. Die allgemeinste Methode liefert ein Optional, das entweder gefüllt ist oder leer, wenn es den Schlüssel nicht gibt:

  • Optional<String> getString(String key)

Der Vorteil beim Optional ist, dass einfach Alternativen für Default-Werte bestimmt werden können: conf.getProperty("rank").orElse("Captain").

Weitere Methoden von PropertiesConfiguration sollen Konvertierungen durchführen:

  • Optional<Boolean> getBoolean(String key)

  • OptionalLong getLong(String key)

  • OptionalDouble getDouble(String key)

  • Optional<BigInteger> getBigInteger(String key)

Wenn es zu dem Schlüssel keinen assoziierten Wert gab, ist der Behälter leer. Wenn die Konvertierung zu einem Fehler misslingt, führt das ebenfalls zu einem leeren Behälter.

Beispiel für die API:

Properties root = new Properties();
root.setProperty( "likes-rum", "true" );
root.setProperty( "age", "55" );
root.setProperty( "income", "123456789012" );
root.setProperty( "hobbies", "drinking, gambling\\, games, swearing competitions" );
root.setProperty( "weakness_of_character", "" );
PropertiesConfiguration conf = new PropertiesConfiguration( root );
Optional<Boolean> maybeLikesRum = conf.getBoolean( "likes-rum" );
OptionalLong maybeAge = conf.getLong( "age" );
Optional<BigInteger> maybeIncome = conf.getBigInteger( "income" );

System.out.println( maybeLikesRum );       // Optional[true]
System.out.println( maybeAge );            // OptionalLong[55]
System.out.println( maybeIncome );         // Optional[123456789012]

Optionale Ergänzung: Listen erfragen

Fortgeschrittene Entwickler können folgende Methode implementieren:

  • List<String> getList(String key). Liefert eine Liste von kommaseparierten Strings. Das Komma selbst kann durch \, ausmaskiert werden.

Ein Beispiel:

List<String> hobbies = conf.getList( "hobbies" );
List<String> weaknessOfCharacter = conf.getList( "weakness_of_character" );

System.out.println( hobbies );             // [drinking, gambling, games, swearing competitions]
System.out.println( hobbies.size() );      // 3
System.out.println( weaknessOfCharacter ); // []

Optionale Ergänzung: Binäre Werte speichern

Eine java.util.HashMap kann beliebige Typen assoziieren, bei einer Properties können nur Strings mit Strings assoziiert werden. Sind andere Datentypen, wie byte-Arrays, zu speichern, müssen sie in einen String konvertiert werden. Ein byte[] kann auf unterschiedliche Weise in einen ASCII-String konvertiert werden, etwa über die BASE64-Kodierung; Java kann das über die Klasse Base64.

Da Properties eher gelesen als geschrieben werden, reichten uns bisher die getXXX(…​)-Methoden. Bei folgender Ergänzung sollen zwei neue Methoden geschrieben werden, eine zum Setzen und eine zum Abfragen:

  • void putBinary(String key, byte[] bytes)

  • Optional<byte[]> getBinary(String key)

Ein Anwendungsbeispiel:

conf.putBinary( "binary", new byte[]{ 0, 1, 127, (byte) 254, (byte) 255 } );
System.out.println( conf.getString( "binary" ) ); // Optional[AAF//v8=]
byte[] binary = conf.getBinary( "binary" ).get();
System.out.printf( "%d %d %d %d %d", binary[0], binary[1], binary[2], binary[3], binary[4] );

1.5.2. INI-Dateien einlesen und als Properties repräsentieren ⭐⭐

In der Windows-Welt gibt es INI-Dateien für Konfigurationen. Das Dateiformat ist sehr einfach:

  • Mit [Sektion] werden Bereiche gestartet

  • Schlüssel-Wert-Paare werden mit = getrennt, wie auch die Java-Properties.

  • Zeilenkommentare beginnen mit ; oder #.

  • Am Anfang können Schlüssel-Wert-Paare ohne vorherige Sektion erscheinen, das sind dann globale Properties.

Aufgabe:

  • Schreibe ein Programm, was Strings im INI-Format in ein Properties-Objekt überführt.

  • Die Sektionen werden zu Präfixen, die Schlüssel folgen mit . separiert.

Beispiel:

date=9.6.2020
[personal]
name=CiaoCiao
rank=Captain
# Some details
[professional.detail]
job=pirat
tough_cookie=

Aus dem gegebenen Beispiel soll ein Properties-Objekt mit folgenden Einträgen entstehen:

date=9.6.2020
personal.name=CiaoCiao
personal.rank=Captain
professional.detail.job=pirat
professional.detail.tough_cookie=

Melde Fehler, wenn es zu einem Schlüssel mehrere Assoziationen gibt. Melde auch einen Fehler, wenn es eine Zeile ohne = gibt. Schlüssel ohne Werte, wie in tough_cookie= sind in Ordnung.

link:solutions/src/main/java/com/tutego/exercise/util/IniParser.java[Lösung

1.6. Stapelspeicher (Stack) und Warteschlangen (Queue)

Eine allgemeine Liste erlaubt in Java den Zugriff auf die Elemente über einen Index, wir nennen so einen Zugriff auch wahlfreien Zugriff, weil wir die Wahl haben, an jeder Stelle ein Element zu erfragen. Es gibt Datenstrukturen, die deutlich eingeschränkter sind und z. B. nur Elemente am Anfang oder am Ende einfügen oder löschen können. Dazu zählen:

  • Stapelspeicher (Stacks)

  • Warteschlangen (Queues)

Bei einem Stapelspeicher kann man nur an einem Ende Elemente einfügen und muss an diesem Ende die Elemente wieder entnehmen. Das Prinzip wird auch LIFO genannt: Last In, First Out. Im Gegensatz dazu steht die Queue. Bei ihr wird zunächst das als Erstes ausgelesen, was auch als Erstes hinzugefügt wurde. Das Prinzip heißt FIFO: First In, First Out.

Reine Stacks und Queues gibt es in Java nicht, nur Schnittstellen, die von Listen implementiert werden.

1.6.1. UPN-Taschenrechner programmieren ⭐

Mathematische Ausdrücke schreiben wir in der Regel in der Infixnotation, bei der die Operatoren zwischen den Operanden stehen, etwa 47 + 11. Prinzipiell kann der Operator aber auch vor den Operanden stehen, wie + 47 11, oder dahinter, wie in 47 11 +.

Die Taschenrechner von Hewlett-Packard hatten in den 1980er-Jahren eine besondere Eingabe etabliert, die umgekehrte polnische Notation (UPN). Das ist eine Postfix-Notation, bei der die Operatoren hinter den Werten stehen. Der Vorteil für die Computer ist, dass der Vorrang — Punktrechnung geht vor Strichrechnung — von den Nutzern schon aufgelöst wurde, was die Programmlogik im Taschenrechner vereinfacht. Auch PostScript nutzt diese Darstellung, denn über einen Stack können mathematische Ausdrücke einfach ausgewertet werden.[2]

Wir wollen einen UPN-Rechner programmieren.

Aufgabe:

  1. Schreibe ein Programm, das als Erstes einen String wie etwa "12 34 23 + *" in Tokens zerlegt. Tipp: Zum Zerlegen lässt sich split(…​) von String oder ein Scanner nutzen.

  2. Nach dem Zerlegen soll das Ergebnis auswertet werden. Beginne mit einem festen String zum Testen.

  3. Lies von der Kommandozeile einen String ein, sodass wir einen echten UPN-Taschenrechner haben.

  4. Welche Fehler und Probleme müssen behandelt und abgefangen werden? Wie sollten wir Fehler behandeln?

1.6.2. Designfehler bei java.util.Stack erkennen ⭐⭐

Die Java-Bibliothek bietet zwar eine Klasse java.util.Stack, die wird in der Praxis allerdings nicht verwendet.

  1. Welche Methoden besitzt ein Stack? Gibt es Methoden, die für einen Stack unangebracht sind?

  2. Wenn man sich die Vererbungshierarchie der Klasse Stack ansieht, so fällt auf, dass sie von java.util.Vector abgeleitet wird. Bewerte die Implementierung aus der Sicht eines API-Designers. Ist das Design eher gut oder eher schlecht? Kann es vielleicht die First-In-First-Out-Semantik zerstören?

1.7. BitSet

Die Klasse BitSet ist eine platzsparende und performante Alternative zu boolean-Arrays. Nützlich ist die Datenstruktur dann, wenn man eine Abbildung einer Ganzzahl auf einen Wahrheitswert benötigt. Die Datenstruktur kann schnell beantworten, ob ein Index (eine positive Ganzzahl) mit true oder false assoziiert ist. Wenn die Anzahl der Bits zu groß wird, oder wenn es große Lücken gibt, ist https://github.com/brettwooldridge/SparseBitSet eine gute Alternative.

1.7.1. Finde doppelte Einträge, und löse das tierische Chaos ⭐

Captain CiaoCiao füttert vor dem Zubettgehen die Tiere seines Privatzoos. Doch da er vom Rum etwas angeschickert ist, vergisst er, das Tor zu schließen. Am nächsten Morgen bemerken Gabi Gräte und Fred Fritte, dass Tiere fehlen. Schnell laufen sie zu Captain CiaoCiao: »Einige Tiere sind entflohen!« — »Beim Klabautermann! Welche?«, fragt der Captain. Die beiden überlegen und zeichnen auf (Schreiben ist nicht ihre Stärke):

  • 🐩🐏🐴🦋🐙

  • 🐴🐏🐧🐸🦋🐌

Captain CiaoCiao stellt fest, dass beide ein schlechtes Gedächtnis haben, und will nur Tiere suchen lassen, die von beiden genannt werden.

Aufgabe:

  • Schreibe eine Methode String sameSymbols(String, String), die eine Zeichenfolge mit den gemeinsamen Symbolen zurückliefert. Auf die Reihenfolge kommt es nicht an, alle Unicode-Zeichen sind möglich.

  • Da wir über den String laufen müssen und dieser »höhere« Unicodezeichen enthält, die durch zwei char ausgerückt werden, soll die Lösung auf string.codePoints().forEach(consumer) zurückgreifen. Diese Anweisung läuft über alle Zeichen des Strings string und ruft den übergebenen IntConsumer für jedes Zeichen auf. Das ist eine Anwendung der Stream-API, die wir uns im folgenden Kapitel genauer anschauen werden.

Beispiele:

  • sameSymbols("🐩🐏🐴🦋🐙", "🐴🐏🐧🐸🦋🐌")"🐏🐴🦋"

  • sameSymbols("abcy", "bcd")"bc"

  • sameSymbols("abc", "def")""

Da das Ergebnis eilt, ist die Methode so zu implementieren, dass die Laufzeit linear mit der Länge der Zeichenfolgen ist, in Informatiksprech: O(N+M), wenn N und M die Längen der Zeichenfolgen sind. Es sind alle Unicode-Zeichen erlaubt.

1.8. Threadsichere Datenstrukturen

Für die bisherigen Aufgaben rund um die Datenstrukturen ArrayList, LinkedList, HashSet, TreeSet usw. haben wir nie mehr als den Main-Thread benötigt. Bei den folgenden Aufgaben kommen mehr Threads und nebenläufige Zugriffe ins Spiel, und dann müssen wir threadsichere Datenstrukturen verwenden. Für die Lösungen wollen wir auf die Datentypen aus dem Paket java.util.concurrent zurückgreifen, in der eine ganze Reihe von threadsichere Datenstrukturen deklariert werden, die auch bei einer beliebigen Anzahl paralleler Zugriffe korrekt arbeiten und eine sehr gute Performance aufweisen.

1.8.1. Unterschied zwischen HashMap, Synchronized-Wrapper, ConcurrentHashMap verstehen

Die Datenstrukturen aus der Collection-API sind nicht threadsicher. Im Paket java.util.concurrent gibt es dahingehend Datenstrukturen, auf die man mit vielen Threads zugreifen kann.

  • Lege eine HashMap an und schreibe mit vielen Threads nebenläufig in die Datenstruktur; sie wird kaputt gehen, wie kann man das sehen?

  • Nutze den Synchonized-Wrapper Collections.synchronizedMap() und versuche es erneut. Wie ist das Ergebnis?

  • Nutze eine ConcurrentHashMap. Was passiert hier, wenn man mit mehreren Threads darauf zurückgreift? Was hat sie für einen Vorteil gegenüber dem Synchronized-Wrapper?

  • Es gibt noch Hashtable, woher kommt die Klasse und nutzt man sie noch?

1.8.2. Schiff beladen ⭐⭐

Captain CiaoCiao und Crew macht sich bereit für das nächste große Abenteuer auf der Insel Gazorpazorp. 5 Mitarbeiter stellen Kisten und Fässer auf die Laderampe, und 10 Mitarbeiter verstauen die Waren im Schiff. Auf der Laderampe können höchstens 5 Objekte gleichzeitig stehen.

Aufgabe:

  • Erzeuge für die Rampe eine ArrayBlockingQueue<String> der Kapazität 5.

  • Erzeuge zwei verschiedene Runnable-Implementierungen Loader und Unloader, die einen Verweis auf die ArrayBlockingQueue bekommen.

    • Der Loader stellt Strings auf die Rampe (zufällige Strings aus einer Menge von Produktnamen).

    • Der Unloader soll Strings von der Rampe nehmen und auf dem Bildschirm ausgeben.

      Es brauchen Loader und Unloader für ihre Arbeit zufällig zwischen 1 und 2 Sekunden.

  • 5 Threads sollen Unloader und 10 Threads Loader sein.

Für das Hinzufügen und Herausnehmen gibt es unterschiedliche Methoden. Der Unterschied ist wichtig, sonst kann es zu Programmfehlern kommen:

Tabelle 1. BlockingQueue-Methoden zum Einfügen und Entnehmen von Elementen
OperationAusnahmenull-RückgabeBlockiert

Einfügen

add(e)

offer(e)

put(e)

Entnehmen

remove()

poll()

take()

Aus den Methodennamen kann man die Semantik nicht ableiten, den Unterschied muss man lernen. Für unsere Aufgabe kommt nur eine Spalte und diese Methoden in Frage.

1.8.3. Wichtige Nachrichten als Erstes bearbeiten ⭐⭐

Eine PriorityQueue hat eine interne Sortierung, sodass die Elemente mit einer höheren Priorität nach vorne wandern. Die Priorität ergibt sich entweder aus der natürlichen Ordnung der Elemente, die Comparable implementieren, oder einem externen Comparator. »Kleine« Elemente haben eine größere Priorität und wandern in der PriorityQueue nach vorne. Am Ende der Queue stehen die Elemente mit der niedrigsten Priorität. (Das ist so wie bei den Impfungen: Die Priorisierungsgruppe 1 bekommt den Stoff zuerst.)

Von verschiedenen Seiten bekommt Captain CiaoCiao Aufgaben zugeteilt. Die Wünsche von Bonny Brain gehen natürlich immer vor. Captain CiaoCiao erkennt sie daran, dass die Arbeitsaufträge von Bonny Brain das Kosewort »Kanönchen« enthalten.

Aufgabe:

  • Schreibe eine Klasse Message, die einen String für den Arbeitsauftrag und einen Zeitstempel vom Typ long speichert. Den Zeitstempel initialisiere mit System.nanoTime(). Implementiere/Generiere hashCode(), equals(Object) und toString().

  • Implementiere für Message einen Comparator, der eine Ordnung schafft, sodass Nachrichten mit dem Kosewort »kleiner« sind als Nachrichten ohne Kosewort, damit das später als höhere Priorität gewertet werden kann. Wenn beide Nachrichten ein Kosewort enthalten oder beide Nachrichten kein Kosewort enthalten, sind sie gleich »groß«.

  • Erweitere den Comparator um eine weitere Vergleichslogik, so dass der Zeitstempel berücksichtigt wird und eine frühere Nachricht auch früher bearbeitet wird.

  • Initialisiere die PriorityQueue mit Nachrichten, und beobachte, wie Nachrichten mit dem Kosewort in der Queue nach vorne wandern.

Beispiel:

Unter der Annahme, dass PriorityQueue<Message> tasks eine korrekt initialisierte Datenstruktur ist, wird es bei folgendem Programm zu der dargestellten Ausgabe kommen:

tasks.add( new Message( "Treasure Hunt" ) );
System.out.println( tasks );

tasks.add( new Message( "Kanönchen, Family Movie Night!" ) );
System.out.println( tasks );

tasks.add( new Message( "Build a pirate ship" ) );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

tasks.add( new Message( "Capture the Flag" ) );
System.out.println( tasks );

tasks.add( new Message( "Bury the treasure, Kanönchen" ) );
System.out.println( tasks );

tasks.add( new Message( "Kanönchen, make a treasure map" ) );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

Die Ausgabe ist:

['Treasure Hunt', 46400]
['Kanönchen, Family Movie Night!', 23700, 'Treasure Hunt', 46400]
['Kanönchen, Family Movie Night!', 23700, 'Treasure Hunt', 46400, 'Build a pirate ship', 70600]
'Kanönchen, Family Movie Night!', 23700
['Treasure Hunt', 46400, 'Build a pirate ship', 70600]
'Treasure Hunt', 46400
['Build a pirate ship', 70600]
['Build a pirate ship', 70600, 'Capture the Flag', 83200]
['Bury the treasure, Kanönchen', 10900, 'Capture the Flag', 83200, 'Build a pirate ship', 70600]
['Bury the treasure, Kanönchen', 10900, 'Kanönchen, make a treasure map',
71400, 'Build a pirate ship', 70600, 'Capture the Flag', 83200]
'Bury the treasure, Kanönchen', 10900
['Kanönchen, make a treasure map', 71400, 'Capture the Flag', 83200, 'Build a pirate ship', 70600]
'Kanönchen, make a treasure map', 71400
['Build a pirate ship', 70600, 'Capture the Flag', 83200]
'Build a pirate ship', 70600
['Capture the Flag', 83200]
'Capture the Flag', 83200
[]

1.8.4. Wenn verbraucht, dann neu ⭐⭐⭐

Der Ausdruck new BigInteger(1024, new SecureRandom()) erzeugt eine große Zufallszahl vom Typ BigInteger.

Aufgabe:

  • Schreibe eine eigene Klasse SecureRandomBigIntegerIterator, die Iterator implementiert und unendlich viele BigInteger liefern kann.

  • Immer dann, wenn die Zahl abgefragt und »verbraucht« wird, soll ein Hintergrund-Thread automatisch eine neue Zufallszahl berechnen.

1.9. Googles Java SE-Ergänzung Guava

Auch wenn die Java Standard Bibliothek die zentralen Datenstrukturen wie Listen, Mengen, Assoziativspeicher mitbringt, fehlt doch einiges. Es gibt z. B. keine bidirektionalen Maps, keine Tabellen, keine konfigurierbare Cache-Implementierung, es gibt keine Bags, so etwas wie Mengen, die allerdings einen Zähler verwalten für die Anzahl gleicher Elemente.

Zwei bekannten Erweiterungen der Standardbibliotheken sind:

Die folgenden Aufgaben lassen sich ganz gut mit den erweiterten Möglichkeiten von Guava nutzen.

Nimm zur Vorbereitung folgende Dependency in der Maven-POM mit auf:

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>30.1-jre</version>
</dependency>

1.9.1. Telefonnummern Wörtern zuweisen ⭐⭐

Bonny Brain findet ein altes Telefonbuch und dort sind die Nummern über Buchstaben kodiert, vermutlich, um sie sich leichter merken zu können. Sie möchte die Nummern in ihre Kontaktverwaltung übertragen und benötigt eine Umrechnung in die Ziffernfolge.

Die Zuordnung von Buchstaben zu den Ziffern sieht so aus:

NummerBuchstaben

0

-

1

-

2

A, B, C

3

D, E, F

4

G, H, I

5

J, K, L

6

M, N, O

7

P, Q, R, S

8

T, U, V

9

W, X, Y, Z

Aufgabe:

  • Schreibe eine Methode, die aus einem String mit Buchstaben die korrekte Nummernfolge macht.

  • Bonny Brain erkennt, dass das Umsetzen von Nummern in Buchstaben clever ist. Schreibe eine Methode, die aus einer Ziffernfolge alle denkbaren Symbolfolgen generiert. 0 soll dabei 0 bleiben und 1 ebenso 1.

Beispiel:

String number = "624";
List<String> words = numberToWords( number );
words.forEach( word -> System.out.println( word + " -> " + wordToNumber( word ) ) );

liefert die Ausgabe

NAG -> 624
NAH -> 624
NAI -> 624
NBG -> 624
NBH -> 624
NBI -> 624
NCG -> 624
NCH -> 624
NCI -> 624
MAG -> 624
MAH -> 624
MAI -> 624
MBG -> 624
MBH -> 624
MBI -> 624
MCG -> 624
MCH -> 624
MCI -> 624
OAG -> 624
OAH -> 624
OAI -> 624
OBG -> 624
OBH -> 624
OBI -> 624
OCG -> 624
OCH -> 624
OCI -> 624

1.9.2. Windgeschwindigkeit in Beaufortskala konvertieren ⭐

Captain CiaoCiao ist mit der Beaufortskala vertraut und sowieso mit jeder Arbeit von Sir Francis Beaufort, den er für die genauen Seekarten bewundert.

Der Urlaub auf einem echten Segelboot ist gar nicht mehr entspannend, als bei einem Unglück der Steuermann Suki Sushi von Bord gegangen ist; nun muss ein Leichtmatrose das Windmessgerät ablesen und Captain CiaoCiao die Windgeschwindigkeit übermitteln. Die Windgeschwindigkeit möchte Captain CiaoCiao aber gar nicht wissen, sondern nur die Beaufortskala.

Tabelle 2. Beaufortskala mit Windgeschwindigkeiten
BeaufortskalaWindgeschwindigkeitBezeichnung

0 Bft

0 km/h

Windstille

1 Bft

1 - 5 km/h

leichter Zug

2 Bft

6 - 11 km/h

leichte Brise

3 Bft

12 - 19 km/h

schwache Brise

4 Bft

20 - 28 km/h

mäßige Brise

5 Bft

29 - 38 km/h

frische Brise

6 Bft

39 - 49 km/h

starker Wind

7 Bft

50 - 61 km/h

steifer Wind

8 Bft

62 - 74 km/h

stürmischer Wind

9 Bft

75 - 88 km/h

Sturm

10 Bft

89 - 102 km/h

schwerer Sturm

11 Bft

103 - 117 km/h

orkanartiger Sturm

12 Bft

> 117 km/h

Orkan

Aufgabe:

  • Schreibe eine Methode, die die Windgeschwindigkeit in die Beaufortskala konvertiert.

1.9.3. Feststellen, ob jemand noch nicht überfallen wurde ⭐

Captain CiaoCiao hat seine Prinzipien: Hat er einen reichen Händler ausgeraubt, ist er anständig genug, ihn nicht wieder auszurauben. Deshalb schreibt er alle Namen seiner Opfer in eine Art Logbuch. Doch kodiert er die Namen, damit sich ein Händler nicht selbst verschonen kann. Außerdem muss das Logbuch kompakt sein, denn Captain CiaoCiao möchte immer eine ausgedruckte Version bei sich tragen.

Das Logbuch von Captain CiaoCiao soll eine spezielle Datenstruktur mit dem Namen Bloomfilter sein. Damit kann man effizient — und mit wenig Speicherverbrauch — überprüfen, ob ein Element nicht in einem Container enthalten ist, aber nur mit einer gewissen Wahrscheinlichkeit eine Antwort bekommen, ob ein Element enthalten ist. Für Captain CiaoCiao ist das in Ordnung, denn sein Logbuch hilft ihm festzustellen, ob ein Name definitiv nicht vorkommt und somit ein Kandidat für den nächsten Überfall ist.

Aufgabe:

  • Gegeben ist folgende Liste früherer Opfer:

    String[] names = { "Thomas Geldregen", "Rainer Reichtum", "Heinz Goldsocken",
                       "Gisela von Prunk", "Herbert Gönnemeyer", "Linda Edel", "Florian Silber" };
  • Nutze die Klasse BloomFilter von Guava und kopiere die Namen in diese Datenstruktur.

  • Erfrage von der Kommandozeile einen Namen und teste, ob dieser nicht in der Datenstruktur ist.

Das Guava-Team hat unter https://github.com/google/guava/wiki/HashingExplained#bloomfilter eine kurze (englische) Einführung geschrieben.


1. Magnetkompasskurs MgK, engl. Compass Course (CC), ist der Winkel zwischen dem Weg eines Schiffes und Kompass-Nord.
2. Linux-Benutzer haben in der Regel dc installiert und können mit der UPN ein wenig spielen, eine Kurzeinführung liefert https://de.wikipedia.org/wiki/Dc_(Unix).