1. Arrays

Arrays sind wichtige Datenstrukturen, die auch indirekt in Java auftauchen, etwa bei der erweiterten for-Schleife oder variablen Argumentlisten. Dieses Kapitel enthält Aufgaben zum Aufbau von Arrays, zum Ablaufen von Arrays und Fragen nach Algorithmen, etwa zur Suche von Elementen in einem Array.

Voraussetzungen

  • Arrays anlegen, abfragen, füllen können

  • Arrays mit erweiterter for-Schleife ablaufen können

  • ein- und mehrdimensionale Arrays nutzen können

  • variable Argumentlisten aufbauen können

  • Utility-Methoden der Klasse Arrays kennen

Verwendete Datentypen in diesem Kapitel:

1.1. Alles hat einen Typ

Bevor wir uns den Zugriff auf die Elemente anschauen, wollen wir uns mit den Typen näher beschäftigen. Es ist wichtig den Unterschied zwischen Objekttyp und Referenztyp zu kennen.

1.1.1. Quiz: Array-Typen ⭐

Arrays sind in Java kovariant, das bedeutet zum Beispiel, dass String[] ein Untertyp von Object[] ist. Das klingt ein bisschen akademisch, ist es vermutlich auch, daher soll die folgende Aufgabe das Verständnis für die Kovarianz von Arrays schärfen.

Überlege, ob alle Anweisungen compilieren bzw. zur Laufzeit funktionieren:

/* 1 */ String[] strings1 = new String[ 100 ];
/* 2 */ Object[] a1 = (String[]) strings1;
/* 3 */ Object[] a2 = strings1;
/* 4 */ Object[] strings2 = new String[]{ "1", "2", "3" };
/* 5 */ String[] a3 = (String[]) strings2;
/* 6 */ String[] strings3 = { "1", "2", "3" };
/* 7 */ Object[] a4 = strings3;
/* 8 */ Object[] strings4 = { "1", "2", "3" };
/* 9 */ String[] a5 = (String[]) strings4;

/* A */ int[] ints1 = new int[ 100 ];
/* B */ Object[] a6 = (int[]) ints1;
/* C */ Object[] ints2 = new int[ 100 ];
/* D */ int[] a7 = (int[]) ints2;

1.2. Eindimensionale Arrays

Ein Array ist eine Sammlung gleichartiger Elemente. Eindimensionale Arrays enthalten direkt die Elemente und keine weiteren Unter-Arrays.

1.2.1. Arrays ablaufen und Windgeschwindigkeit, Windrichtung ausgeben ⭐

Captain CiaoCiao segelt über das Meer, der Wind bläst von allen Seiten. Er muss die Windgeschwindigkeit und Windrichtung immer im Blick haben.

Aufgabe:

  1. Deklariere zwei Arrays int[] windSpeed und int[] windDirection.

  2. Initialisiere beide Arrays je mit drei ganzzahligen Zufallszahlen (prinzipiell sollte die Anzahl beliebig sein), wobei die Windstärke zwischen 0 und (kleiner) 200 km/h und die Windrichtung zwischen 0 und (kleiner) 360 Grad liegen kann.

  3. Laufe mit einer Schleife über das Array und gib alle Pärchen kommasepariert aus.

Beispiel:

  • Enthält z. B. das Array windSpeed die Werte {82, 70, 12} und das Array windDirection die Werte {12, 266, 92}, soll die Ausgabe auf dem Bildschirm sein:

    Wind speed 82 km/h and wind direction 12°, Wind speed 70 km/h and wind direction 266°, Wind speed 12 km/h and wind direction 92°

Hinweis: Bedenke, dass die Segmente mit einem Komma getrennt werden und am Ende kein Komma steht.

1.2.2. Konstante Umsatzsteigerung feststellen ⭐

Am Ende eines Monats bekommt Captain CiaoCiao die Umsätze gemeldet, die er und seine Crew — sagen wir mal — erwirtschaftet haben. In der monatlichen Liste ist vermerkt, wie der Gewinn an einem Tag ausfiel. Sie hat dieses Format:

//                Tag    1,    2,   3,    4,    5 ... bis maximal 31
int[] dailyGains  = { 1000, 2000, 500, 9000, 9010 };

Captain CiaoCiao ist mit den Zahlen zufrieden, und er möchte eine Belohnung zahlen, wenn Gewinne über 5 % gestiegen sind. Von 1000 auf 2000 ist ein satter Sprung um 100 %, von 500 auf 9000 ebenso, doch definitiv nicht von 2000 auf 500 und auch nicht von 9000 auf 9010.

Aufgabe:

  • Schreibe eine Methode int count5PercentJumps(int[]), die die Anzahl der Umsatzsprünge liefert. Ein Umsatzsprung ist dann gegeben, wenn der Umsatz 5 % über dem des Vortags lag.

  • Das übergebene Array darf nicht null sein, andernfalls folgt eine Ausnahme.

1.2.3. Aufeinanderfolgende Strings suchen und feststellen, ob Salty Snook kommt ⭐

Bonny Brain beobachtet die Flaggen der vorbeiziehenden Schiffe, denn sie wartet auf Salty Snook. Sie schaut sich jede Flagge an und weiß, dass Salty Snook nie alleine kommt, sondern sich in einem Konvoi von vier Schiffen bewegt. Die Flaggen selbst kennt sie nicht, nur weiß sie, dass alle die gleiche Aufschrift haben.

Aufgabe:

  • Schreibe eine neue Methode isProbablyApproaching(String[] signs), die dann true zurückliefert, wenn es im Array vier gleiche Kürzel hintereinander gibt. Bedenke, dass man Strings mit equals(…​) vergleicht.

  • Das übergebene Array darf nicht null sein, und kein Element im Array darf null sein.

Beispiel:

String[] signs1 = { "F", "DO", "MOS", "MOS", "MOS", "MOS", "WES" };
isProbablyApproaching( signs1 );  // true

String[] signs2 = { "F", "DO", "MOS", "MOS", "WES", "MOS", "MOS" };
isProbablyApproaching( signs2 );  // false

1.2.4. Array umdrehen ⭐

Charlie Creevey macht für Captain CiaoCiao die Finanzen. Doch statt die Einnahmen aufsteigend zu sortieren, hat er sie absteigend sortiert. Daher muss die Liste umgedreht werden.

Ein Array umzudrehen bedeutet, dass das erste Element mit dem letzten Element vertauscht wird, das zweite mit dem zweitletzten usw.

Aufgabe:

  • Schreibe eine neue statische Methode reverse(…​), die ein gegebenes Array umdreht:

    public static void reverse( double[] numbers ) {
      // TODO
    }
  • Die Operation soll in place sein, also das übergebene Array ändern. Wir wollen kein neues Array anlegen.

  • Die Übergabe null führt zu einer Ausnahme.

Beispiel:

  • { } → { }

  • { 1 } → { 1 }

  • { 1, 2 } → { 2, 1 }

  • { 1, 2, 3 } → { 3, 2, 1 }

Die Darstellung in den geschweiften Klammen ist nur symbolisch.

1.2.5. Das nächste Kino finden ⭐⭐

Die Klasse java.awt.Point repräsentiert Punkte mit x/y-Koordinaten. Diese lassen sich gut für Positionen einsetzen.

Im Kino läuft die Neuverfilmung »Unter der Flagge der Freibeuter« an, die Captain CiaoCiao unbedingt sehen muss. Doch wo befindet sich das nächste Kino?

Aufgabe:

  • Gegeben ist eine Menge von Point-Objekten in einem Array points für die Kinopositionen.

    Point[] points = { new Point(10, 20), new Point(12, 2), new Point(44, 4) };
  • Schreibe eine Methode double minDistance(Point[] points, int size), die den Abstand des Punktes zurückliefert, der die geringste Distanz zum Nullpunkt besitzt. Mit size können wir bestimmen, wie viele Elemente des Arrays betrachtet werden sollen, damit das Array auch prinzipiell größer sein kann.

  • null als Übergabe ist nicht erlaubt, auch dürfen die Punkte nicht null sein; es muss eine Ausnahme ausgelöst werden.

  • Was müssen wir ändern, wenn der Rückgabetyp Point ist, also der Punkt selbst mit dem kleinsten Abstand zurückgegeben werden soll?

Studiere die Javadoc zu java.awt.Point, um herauszufinden, ob der Punkt selbst Abstände zu anderen Koordinaten berechnen kann.

1.2.6. Süßigkeitenladen überfallen und fair aufteilen ⭐⭐

Captain CiaoCiao überfällt mit seinen Kindern Junior und Jackie einen Süßigkeitenladen. Die Süßigkeiten stehen in einem langen Regal, und jedes Produkt hat ein Gewicht. Die Daten liegen als Array vor:

int[] values = { 10, 20, 30, 40, 40, 50 };

Junior und Jackie stellen sich links und rechts an entgegengesetzten Enden des Regals auf, und da Captain CiaoCiao beide Kinder gleich lieb hat, sollen sie am Ende auch gleich viel mit nach Hause nehmen. Captain CiaoCiao zeigt im Regal auf eine Süßigkeit, sodass alle Produkte links davon zu Junior gehen und alle Produkte rechts von der Position (inklusive dem gezeigten) für Jackie sind.

Der Captain weiß zwar, was im Regal steht, aber nicht, ab welcher Position links und rechts die gleiche Summe entsteht. Abweichungen von 10 % sind für die Kinder in Ordnung. Für den Unterschied wollen wir auf folgende Formel für die relative Differenz zurückgreifen:

private static int relativeDifference( int a, int b ) {
  if ( a == b ) return 0;
  int absoluteDifference = Math.abs( a - b );
  return (int) (100. * absoluteDifference / Math.max( a, b ));
}

Aufgabe:

  • Schreibe eine Methode int findSplitPoint(int[]), die den Index im Array findet, bei dem links und rechts fair geteilt werden kann. Irgendeine Lösung reicht, es sind nicht alle Lösungen nötig.

  • Falls es keine faire Teilung gibt, soll eine Methode -1 liefern.

Beispiele:

  • 10 + 20 + 30 + 40 ≈ 40 + 50, denn 100 ≈ 90, und der Index für die Rückgabe ist 4

  • 10 20 30 40 40 100 führt zu -1, denn es gibt keine gültige Partitionierung

1.3. Erweiterte for-Schleife

Sollen Arrays ab dem ersten Element abgelaufen werden, so lässt sich dafür gut eine erweiterte for-Schleife mit unsichtbarem Schleifenzähler nutzen. Das spart Code ein.

1.3.1. Berge zeichnen ⭐⭐

Für die nächste Schatzsuche müssen Bonny Brain und die Crew über Berge und Hügel gehen. Sie bekommt vorher die Höhenmeter mitgeteilt und möchte sich vorher einen Eindruck vom Profil machen.

Aufgabe:

  • Schreibe ein Programm mit einer Methode printMountain(int[] altitudes), die ein Array mit Höhenmetern in eine ASCII-Darstellung umsetzt.

  • Die Höhe soll darstellt werden über ein Multiplikationszeichen * in genau dieser Höhe von einer Grundlinie. Die Höhen können beliebig sein, aber nicht negativ.

Beispiel:

  • Das Array { 0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 3, 2, 2, 1, 0 } soll darstellt werden als:

    5          *
    4         * *
    3      ***   *
    2    **       **
    1  **           *
    0 *              *

    Die erste Spalte dient der Verdeutlichung und muss nicht umgesetzt werden.

Optionale Erweiterung:

  • Deute statt mit * mit den Symbolen /, \, - und ^ an, ob wir aufsteigen, absteigen, auf einem Plateau sind oder an der Spitze stehen.

    5          ^
    4         / \
    3      --/   \
    2    -/       -\
    1  -/           \
    0 /              \

1.4. Zwei- und mehrdimensionale Arrays

Ein Array kann in Java Verweise auf andere Arrays enthalten, und so definiert man in Java mehrdimensionale Arrays. In Java gibt es keine echten zweidimensionalen Arrays; zweidimensionale Arrays sind nichts anderes als Arrays, die Unter-Arrays referenzieren, und die Unter-Arrays könnten unterschiedlich lang sein.

1.4.1. Mini-Sudoku auf gültige Lösung prüfen ⭐⭐

Da Überfälle ziemlich anstrengend sind, braucht Bonny Brain einen Ausgleich und beschäftigt sich mit Sudoku. Ein Sudoku-Spiel besteht aus 81 Feldern in einem 9-×-9-Gitter. Das Gitter lässt sich in neun Blöcke zerlegen, jeder Block ist ein zweidimensionales Array der Größe 3 × 3. In jedem dieser Blöcke muss jede Zahl von 1 bis 9 genau einmal vorkommen — keine darf fehlen.

Aufgabe:

  • Schreibe ein Programm, das ein zweidimensionales Array mit neun Elementen daraufhin testet, ob alle Zahlen von 1 bis 9 vorkommen.

  • Fehlende Elemente sollen gemeldet werden.

Beispiel:

  • Das folgende Array ist eine gültige Sudoku-Belegung:

    int[][] array = {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    };
  • Das folgende Array ist keine gültige Sudoku-Belegung:

    int[][] array = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 8 } };

    Der Fehler könnte etwa gemeldet werden mit: Missing 9.

1.4.2. Bild vergrößern ⭐⭐

Bilder werden im Speicher oft als Tripel von Rot-Grün-Blau-Werten gespeichert, wobei die einzelnen Werte sich zwischen 0 und 255 bewegen können. Da es bei Graustufenbildern keine Farben gibt, ist statt drei Werten nur ein Wert nötig.

Aufgabe:

  • Gegeben ist ein zweidimensionales Ganzzahl-Array mit Werten von 0 bis 255; das Array stellt gedanklich ein Graustufenbild dar.

  • Schreibe eine Methode int[][] magnify(int[][] array, int factor), die ein neues Array zurückgibt und das Bild um den gegebenen Faktor skaliert. Aus einem Bild der Größe 2 × 3 und dem Faktor 2 wird also ein Bild der Größe 4 × 6. Bildpunkte werden einfach verdoppelt, eine Interpolation der Werte ist nicht gewünscht.

Beispiel:

  • Nehmen wir folgendes Array an:

    { {1, 2, 3},
      {4, 5, 6} }

    Dann folgt nach einer Verdoppelung:

    { {1, 1, 2, 2, 3, 3},
      {1, 1, 2, 2, 3, 3},
      {4, 4, 5, 5, 6, 6},
      {4, 4, 5, 5, 6, 6} }

1.5. Variable Argumentlisten

Java erlaubt Methoden, der man eine beliebige Anzahl Argumente übergeben kann. Sie nennen sich Vararg-Methoden. Ein Vararg-Parameter darf nur zum Schluss einer Parameterliste stehen und ist ein Array. Beim Aufruf mit variablen Argumenten erzeugt der Compiler automatisch ein neues anonymes Array und übergibt es an die Methode.

1.5.1. SVG-Polygone mit variabler Koordinatenanzahl erzeugen ⭐

Bonny Brain möchte für ihren nächsten Arbeitsort eine Karte zeichnen, und die soll gedruckt und auf jeder Auflösung immer gut aussehen, weil es auf jedes Detail ankommt. Die beste Technologie dafür ist SVG.

In SVG gibt es verschiedene Primitive, etwa für Linien, Kreise oder Rechtecke. Auch für Linienzüge gibt es ein XML-Element. Ein Beispiel:

<polygon points="200,10 250,190 160,210" />

Aufgabe:

  • Deklariere eine Java-Methode printSvgPolygon(…​), der wir beliebig viele Koordinaten-Paare übergeben können. Welche Fehler könnte es bei der Übergabe geben?

  • Die Methode soll zu den übergebenen Paaren eine passende SVG-Ausgabe auf dem Bildschirm ausgeben.

Beispiel:

  • In printSvgPolygon( 200, 10, 250, 190, 160, 210 ) ist 200,10 ein Koordinatenpaar, 250,190 ebenso, genauso wie 160, 210. Die Bildschirmausgabe soll sein: <polygon points="200,10 250,190 160,210" />.

Optional: Studiere das Beispiel unter https://www.w3schools.com/graphics/tryit.asp?filename=trysvg_polygon. Kopiere das selbstgenerierte SVG in die Weboberfläche.

1.5.2. Auf Zustimmung prüfen ⭐

Captain CiaoCiao holt sich von seinen Crewmitgliedern eine Rückmeldung über einen Auftrag. Sämtliche Mitglieder können Ja oder Nein stimmen.

Aufgabe:

  • Gesucht ist eine Vararg-Methode allTrue(…​), der man eine beliebige Anzahl von boolean-Werten übergeben kann, aber mindestens ein Argument übergeben muss.

  • Sind alle Argumente true, ist auch die Rückgabe true; ist einer der boolean-Werte false, soll die Methode false zurückgeben.

  • Da ein Vararg intern ein Array darstellt, kann null übergeben werden — das muss zu einer Ausnahme führen.

Beispiel:

  • allTrue(true, true, true) liefert true.

  • allTrue(true) liefert true.

  • allTrue(true, false) liefert false.

  • allTrue(true, null) liefert eine Ausnahme.

  • allTrue() lässt sich nicht compilieren und muss einen Compilerfehler geben.

1.5.3. Hilfe, Tetraphobie! Alle Vieren nach hinten setzen ⭐⭐

Bonny Brain trifft befreundete Freibeuter in Hongkong und stellt fest, dass viele an Tetraphobie leiden und abergläubische Angst vor der Zahl 4 haben. Die Buchhalterin muss nun alle Zahlen mit einer 4 nach hinten setzen.

Aufgabe:

  • Schreibe eine Methode fourLast(int... numbers), die alle Zahlen, die eine 4 enthalten, hinter die Zahlen stellt, die keine 4 haben. Die Reihenfolge der Zahlen ohne 4 darf sich nicht ändern, die Zahlen mit einer 4 können irgendwo am Ende stehen.

  • fourLast(…​) soll das übergebene Array als Rückgabe haben.

  • null in der Übergabe muss zu einer Ausnahme führen.

Beispiel:

  • int[] numbers = {1, 44, 2, 4, 43}; fourLast(numbers); verändert das Array numbers so, dass 1 und 2 im Array vor 44, 4 und 43 stehen. Die 2 darf später nicht vor der 1 stehen.

  • fourLast( 4, 4, 44, 1234 ) liefert das vom Compiler automatisch generierte Array mit den Einträgen zum Beispiel in der Reihenfolge 4, 4, 44, 1234 zurück.

1.6. Die Utility-Klasse Arrays

Arrays »können« in Java nicht viel, interessante Methoden sind in Klassen ausgelagert, etwa java.util.Arrays. Eine Methode zum Kopieren von Arrays befindet sich in der Klasse System.

1.6.1. Quiz: Arrays kopieren ⭐

Wofür stehen diese unsinnigen Variablennamen und was ist der Effekt der folgenden Zeilen?

int[] hooey = { 1, 2, 3, 4 };
int[] shuck = new int[ hooey.length - 1 ];
int bushwa = 2;
int kelter = 0;
int piddle = 0;
System.arraycopy( hooey, kelter, shuck, piddle, bushwa );
System.arraycopy( hooey, bushwa + 1, shuck, bushwa, hooey.length - bushwa - 1 );
System.out.println( Arrays.toString( shuck ) );

1.6.2. Quiz: Arrays vergleichen ⭐

Wie sind die Ausgaben?

Object[] array1 = { "Anne Bonny", "Fortune", "Sir Francis Drake", new int[]{ 1, 2, 3 } };
Object[] array2 = { "Anne Bonny", "Fortune", "Sir Francis Drake", new int[]{ 1, 2, 3 } };
System.out.println( array1 == array2 );
System.out.println( array1.equals( array2 ) );
System.out.println( Arrays.equals( array1, array2 ) );
System.out.println( Arrays.deepEquals( array1, array2 ) );

1.7. Lösungsvorschläge

1.7.1. Quiz: Array-Typen

Interessant sind weniger die Variablendeklarationen und Zuweisungen von strings1 bis strings4 und int1 und int2; die Syntax ist uns bekannt: Ein Array wird entweder mit einer festen Größe oder mit Elementen vorinitialisiert.

Interessant sind die folgenden Typumwandlungen, die explizit oder implizit durchgeführt werden. Wir müssen dabei unterscheiden zwischen Typumwandlungen, die für den Compiler in Ordnung sind, und Typumwandlungen, die erst zur Laufzeit zu Schwierigkeiten führen. Das ist eine wichtige Unterscheidung, die auch in den Begriffen Objekttyp und Referenztyp deutlich wird. Für den Compiler gibt es Referenzvariablen und einen Referenztyp, der Compiler weiß nicht, was zur Laufzeit vor sich geht. Die Laufzeitumgebung wiederum weiß im Grunde nicht, unter welchem Variablentyp eine Variable deklariert wurde, sie weiß allerdings, was für ein Objekt sie gerade vor sich hat: Wir sprechen daher von dem Objekttyp.

Die erste Anweisung ist die ehrlichste. Für den Compiler ist es ein String-Array und für die Laufzeitumgebung ebenfalls.

Die Typumwandlungen in der zweiten Zeile ist irrelevant, weil String[] ein Untertyp von Object[] ist. Das ist sehr wichtig, denn genau das ist kovariant: Ein String-Array ist ein Untertyp eines Object-Arrays, auch ein Point[] ist ein besonderes Object[]. Das ist auch in der dritten Zeile ersichtlich, wo die explizite Typumwandlung fehlt, weil sie implizit ist.

In der vierten Anweisung wissen Laufzeitumgebung und Compiler Unterschiedliches. Für die Laufzeitumgebung steht weiterhin ein String-Array im Speicher, aber der Compiler kennt das String-Array nur als Object-Array. Diese Schreibweise ist prinzipiell gültig, und auch hier findet wieder eine implizite Typumwandlung statt.

In der fünften Anweisung werten wir das Object-Array zu einem String-Array auf. Das funktioniert zur Compilezeit und auch zur Laufzeit.

In der sechsten Anweisung wird wieder direkt ein String-Array aufgebaut und als String-Array vermerkt. Das ist die übliche Schreibweise. In der siebten Anweisung finden wir eine implizite Typanpassung vom String-Array zum Object-Array. Diese Anweisung ist in Ordnung.

Die achte und neunte Anweisung ist heimtückisch: Der Compiler baut bei der Zuweisung kein String-Array auf, sondern ein Object-Array und legt in dieses Object-Array String-Referenzen. Es gibt folglich kein String-Array, sondern nur ein Object-Array, das Strings referenziert. In der neunten Zeile vertraut der Compiler unserer Entscheidung, das Object-Array auf ein String-Array anzupassen. Der Compiler schluckt das, und es gibt keinen Compilerfehler. Ein Problem tritt aber zur Laufzeit auf. Da die Laufzeitumgebung natürlich weiß, dass in der Variablen strings4 nur ein Object-Array steht und kein besseres String-Array, folgt die Ausnahme java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.String;.

Die letzten vier Beispiele sind für den Compiler einfacher als falsch zu identifizieren. Während die Deklaration von ints1 noch korrekt ist, werden B und C und D zu einem Compilerfehler führen. Ein int-Array lässt sich nicht in ein Object-Array konvertieren, weder explizit wie in Zeile B noch implizit wie in Zeile C. Es gibt hier keine Typanpassung, so wie Object o = 1 auch falsch ist. Da wir schon Zeile C nicht compilieren können, führt auch Zeile D zu einem Compilerfehler: Es gibt keine Typanpassung von einem Object-Array in ein int-Array.

1.7.2. Arrays ablaufen und Windgeschwindigkeit, Windrichtung ausgeben

Listing 1. com/tutego/exercise/array/Windy.java
final int MAX_WIND_SPEED = 200;
final int MAX_DEGREE     = 360;

final int LENGTH = 5;
int[] windSpeed     = new int[ LENGTH ];
int[] windDirection = new int[ LENGTH ];

for ( int i = 0; i < LENGTH; i++ ) {
  windSpeed[ i ]     = (int) (Math.random() * MAX_WIND_SPEED);
  windDirection[ i ] = (int) (Math.random() * MAX_DEGREE);
}

for ( int i = 0; i < LENGTH; i++ ) {
  System.out.printf( "Wind speed %d km/h and wind direction %d°",
                     windSpeed[ i ], windDirection[ i ] );
  if ( i != LENGTH - 1 )
    System.out.print( ", " );
}

Die Lösung besteht aus vier Schritten. Zunächst wollen wir drei Konstanten definieren: für die maximale Windgeschwindigkeit und Windstärke sowie für die Anzahl der Elemente. LENGTH initialisieren wir mit 5, damit wir später beim Aufbau der Arrays windSpeed und windDirection nicht wieder das Literal 5 als magische Zahl in den Code schreiben müssen; wir können später einfach die Variable ändern, wenn wir größere Arrays wünschen.

Im zweiten Schritt laufen wir mit einer Schleifenvariablen von 0 bis zum letzten Element des Arrays. Das Array ist fünf Elemente groß, also dürfen wir von 0 bis 4 laufen. Im Rumpf der Schleife bilden wir zwei Zufallszahlen und initialisieren die Array-Elemente. Die Berechnung einer ganzzahligen Zufallszahl von 0 bis 200 sieht so aus: Mit Math.random() bekommen wir eine Zufallszahl als Fließkommazahl zwischen 0 und echt kleiner als 1. Die Multiplikation mit 200 liefert eine Zufallszahl zwischen 0 und echt kleiner als 200. Konvertiert (int) den Ausdruck in eine Ganzzahl, werden alle Nachkommastellen abgeschnitten, also liegt das Ergebnis als ganze Zahl zwischen 0 und 199 vor. Üblicherweise sind bei Bereichsangaben der Start inklusive und das Ende exklusive.

Die beiden Arrays sind nun initialisiert, und wir können die Paare ausgeben. Mit einer Schleife laufen wir das Array ab; wir greifen an der gleichen Position i auf die Arrays windSpeed und windDirection zurück. Bei der Ausgabe unterstützen uns printf(…​) und der Formatspezifizierer %d für Dezimalzahlen. In den Format-String setzen wir aber kein Komma, denn am Ende der Kette darf kein Komma stehen. Dass nur am Ende ein Komma steht, kann unterschiedlich gelöst werden. Die Herangehensweise hier fragt den Schleifenzähler ab, ob er für das letzte Element steht. Wenn i ungleich dem letzten Element ist, dann wird ein Separator gesetzt, andernfalls nicht.

1.7.3. Konstante Umsatzsteigerung feststellen

Listing 2. com/tutego/exercise/array/BigProfits.java
private static int count5PercentJumps( int[] dailyGains ) {

  if ( dailyGains.length < 2 )
    return 0;

  final double MIN_PERCENT = 5;

  int result = 0;

  // Index variable i starting at 1, second element
  for ( int i = 1; i < dailyGains.length; i++ ) {
    double yesterday = dailyGains[ i - 1 ];
    double today     = dailyGains[ i ];

    double percent = today / yesterday * 100 - 100;

    if ( percent >= MIN_PERCENT )
      result++;
  }

  return result;
}

Der Methode count5PercentJumps(…​) wird ein Array übergeben, das im besten Fall eine Reihe von Ganzzahlen enthält. Es kann passieren, dass null übergeben wird, was keine gültige Eingabe für das Programm sein soll. Greifen wir auf length zurück, gibt es im Fall von null eine NullPointerException — das ist so gewollt.

Existiert das Array-Objekt, aber enthält es kein oder nur ein Element, betrachten wir das als Fehler und geben 0 zurück.

Kommen wir weiter, wissen wir, dass mindestens zwei Elemente im Array stehen. Wir laufen mit einer for-Schleife über das Array, wobei wir mit dem Index i bei 1 beginnen und immer zwei Elemente gleichzeitig erfragen: das aktuelle Element an der Position i und das Element an der Position vorher, an der Position i - 1. Diese Elemente stehen für today und yesterday. Prinzipiell hätten wir auch bei 0 beginnen und bis < dailyGains.length - 1 laufen können.

Haben wir den Betrag für den heutigen und gestrigen Tag ausgelesen, müssen wir die relative prozentuale Steigerung berechnen. Das machen wir mit einer einfachen Formel. Wir achten allerdings darauf, dass die Division nicht auf Ganzzahlen durchgeführt wird, sondern auf Fließkommazahlen. Werden nämlich zwei Ganzzahlen dividiert, ist das Ergebnis wieder eine ganze Zahl. Wenn wir vorher die Zahlen aus dem Array herausnehmen und in ein double konvertieren, haben wir später durch die Division von zwei Fließkommazahlen ein genaueres Verhältnis. Damit vermeiden wir Probleme bei der Rundung, denn falls wir irgendwann einmal die Konstante verändern wollen, z. B. auf einen viel kleineren Wert, könnte es sein, dass kleine Sprünge nicht korrekt erkannt werden. Sonderfall: Tage, an denen kein Umsatz generiert wurde, funktionieren, weil die Steigerung am Folgetag Double.Infinity ist und »Unendlich« größer als MIN_PERCENT ist.

Nach der Berechnung der relativen Steigung prüfen wir, ob wir über unsere Konstante von 5 % kommen, und erhöhen die Variable result, in der wir uns alle Erhöhungen merken. Am Ende der Schleife geben wir result zurück und melden damit, wie viele Erhöhungen wir insgesamt gefunden haben.

1.7.4. Aufeinanderfolgende Strings suchen und feststellen, ob Salty Snook kommt

Listing 3. com/tutego/exercise/array/SaltySnook.java
public static boolean isProbablyApproaching( String[] signs ) {

  final int MIN_OCCURRENCES = 4;

  if ( signs.length < MIN_OCCURRENCES )
    return false;

  for ( int i = 0, count = 1; i < signs.length - 1; i++ ) {
    String currentSign = Objects.requireNonNull( signs[ i ] );
    String nextSign    = Objects.requireNonNull( signs[ i + 1 ] );
    if ( currentSign.equals( nextSign ) ) {
      count++;
      if ( count == MIN_OCCURRENCES )
        return true;
    }
    else // ! currentSign.equals( nextSign )
      count = 1;
  }
  return false;
}

Die Anzahl der gewünschten Schiffe merken wir uns in einer Konstanten MIN_OCCURRENCES, sodass wir die Anzahl später leicht ändern können.

Als Erstes prüfen wir, ob das Array mindestens MIN_OCCURRENCES viele Elemente hat. Wenn nicht, liefert die Methode dem Aufrufer false zurück. Wurde null übergeben, folgt eine NullPointerException durch den Zugriff auf das Attribut length, was den fehlerhaften Parameter deutlich meldet.

Wenn wir aus der Methode nicht aussteigen, gibt es mindestens vier Elemente. Beim Vergleich von nachfolgenden Elementen im Array gibt es in der Regel zwei Ansätze:

  • einen Index von 0 bis zum vorletzten Element generieren und dann Zugriff auf zwei Elemente über den Index und Index + 1

  • einen Index von 1 bis zum letzten Element generieren und dann Zugriff auf zwei Elemente über den Index - 1 und Index

Diese Lösung verwendet die erste Variante.

Die for-Schleife deklariert zwei lokale Variablen: i für den Index, und in der Variablen count merken wir uns die Anzahl der nacheinander gleichwertigen Strings; da ein String mindestens einmal vorkommt, wird die Variable mit 1 initialisiert.

Wir beginnen in der Schleife beim Index 0 und speichern das Element in einer Zwischenvariablen currentSign. An der Stelle 1 haben wir zum Start das zweite Element, und auch diese Belegung wird gesichert in einer sprechenden Variablen nextSign. Objects.requireNonNull(…​) wird an dieser Stelle eine Ausnahme auslösen, wenn eines der Array-Elemente null ist.

Strings haben eine equals(…​)-Methode, die zur Bestimmung der Gleichwertigkeit herangezogen wird. Es gibt zwei Ausgänge für den Vergleich:

  1. Wenn wir zwei gleiche aufeinanderfolgende Zeichenfolgen gefunden haben, setzen wir den Zähler counter hoch und testen, ob er gleich MIN_OCCURRENCES ist. In dem Fall liegen vier gleichwertige Zeichenfolgen hintereinander, und wir können mit return true aus der Methode aussteigen.

  2. Sind currentSign und nextSign nicht gleichwertig, müssen wir den Zähler auf 1 zurücksetzen.

Wurde am Ende der Schleife keine Zeichenfolge erkannt, die viermal hintereinander vorkommt, wird die Methode mit return false verlassen.

Der ganze if-else-Block lässt sich kürzen, wenn man bereit ist, immer zu testen, auch wenn der Zähler zurückgesetzt wurde:

count = currentSign.equals( nextSign ) ? count + 1 : 1;
if ( count == MIN_OCCURRENCES ) return true;

1.7.5. Array umdrehen

Listing 4. com/tutego/exercise/array/ArrayReverser.java
public static void reverse( double[] numbers ) {
  final int middle = numbers.length / 2;

  for ( int left = 0; left < middle; left++ ) {
    int right = numbers.length - left - 1;
    swap( numbers, left, right );
  }
}

private static void swap( double[] numbers, int i, int j ) {
  double swap  = numbers[ i ];
  numbers[ i ] = numbers[ j ];
  numbers[ j ] = swap;
}

Die reverse(…​)-Methode bekommt als Parameter ein Array. Wir bekommen folglich ein Verweis auf ein Objekt von einer anderen Stelle übergeben. Änderungen finden also auf keiner Kopie statt, sondern wir operieren auf genau dem Array, das der Aufrufer übergeben hat. Da Arrays Objekte sind, die über Referenzen angesprochen werden, ist es möglich, dass der Aufrufer null übergeben hat. In dem Fall führt das kommende numbers.length zu einer NullPointerException, und das ist in Ordnung.

Der Algorithmus selbst ist nicht schwierig. Wir müssen das erste mit dem letzten Element vertauschen, dann das zweite mit dem zweitletzten und so weiter. Das Vertauschen der Elemente lagern wir in eine eigene Methode swap(…​) aus.

Damit wir uns in reverse(…​) nicht selbst die Elemente überschreiben, dürfen wir nur bis zur Hälfte laufen. Die Variable middle steht für die Hälfte. Zwar wird die Variable nur ein einziges Mal in der Schleife genutzt, doch eine Variable dieser Art hilft, die Bedeutung dieses Ausdrucks genauer zu dokumentieren. Unsere Schleife beginnt mit dem Schleifenzähler left bei 0 und läuft bis zur Mitte. Die Variable right läuft in die entgegengesetzte Richtung.

1.7.6. Das nächste Kino finden

Listing 5. com/tutego/exercise/array/MinDistance.java
static double minDistance( Point[] points, int size ) {

  if ( points.length == 0 || size > points.length )
    throw new IllegalArgumentException(
        "Array is either empty or size out of bounds" );

  double minDistance = points[ 0 ].distance( 0, 0 );

  // Index variable i starting at 1, second element
  for ( int i = 1; i < size; i++ ) {
    double distance = points[ i ].distance( 0, 0 );
    if ( distance < minDistance )
      minDistance = distance;
  }

  return minDistance;
}

Als Erstes prüfen wir in der Methode, ob die Parameter points und size korrekt sind. Wir erwarten mindestens ein Element, und die Anzahl der zu betrachtenden Elemente darf nicht größer sein als die Anzahl der Elemente im Array. War die Übergabe null, folgt automatisch durch den Zugriff auf length eine NullPointerException.

Bei der Frage nach dem größten oder kleinsten Element einer Liste sehen die Algorithmen immer gleich aus. Wir beginnen mit einem Kandidaten und schauen dann, ob dieser Kandidat korrigiert werden muss. Unser Kandidat ist minDistance. Wir initialisieren ihn mit dem Abstand des ersten Punktes zum Nullpunkt. Den Abstand zum Nullpunkt müssen wir nicht selbst ausrechnen, hier hilft uns praktischerweise die Point-Methode distance(x,y). Wie übergeben die Koordinaten 0, 0, relativ zu denen der Punkt seinen Abstand berechnen soll.

Damit alle Punkte betrachtet werden, laufen wir durch das Array und nutzen size als Längenbeschränkung. Vom neuen Punkt berechnen wir ebenfalls den Abstand zum Nullpunkt, und falls wir einen Punkt gefunden haben, der näher am Nullpunkt liegt, müssen wir unsere Wahl korrigieren.

Am Ende der Methode geben wir die minimale Distanz zum Nullpunkt zurück. Falls die Methode jetzt nun nicht die Distanz selbst, sondern einen Point zurückgeben soll, schreiben wir die Methode so um, dass wir uns neben double minDistance zusätzlich Point nearest merken; würden wir auf minDistance verzichten, müsste jedes Mal die Distanz neu berechnet werden, was unnötig Performance kostet.

Listing 6. com/tutego/exercise/array/MinDistance.java
static Point minDistance2( Point[] points, int size ) {
  Point  nearest = points[ 0 ];
  double minDistance = nearest.distance( 0, 0 );

  for ( int i = 1; i < size; i++ ) {
    double distance = points[ i ].distance( 0, 0 );
    if ( distance < minDistance ) {
      minDistance = distance;
      nearest = points[ i ];
    }
  }
  return nearest;
}

1.7.7. Süßigkeitenladen überfallen und fair aufteilen

Listing 7. com/tutego/exercise/array/FairSharing.java
public static int findSplitPoint( int[] values ) {

  if ( values.length < 2 )
    return -1;

  int sumLeft = values[ 0 ];

  int sumRight = 0;
  for ( int i = 1; i < values.length; i++ )
    sumRight += values[ i ];

  for ( int splitIndex = 1; splitIndex < values.length; splitIndex++ ) {
    int relativeDifference = relativeDifference( sumLeft, sumRight );

    Logger.getLogger( "MuggingFairly" )
          .info( "splitIndex=" + splitIndex
                     + ", sum left/right=" + sumLeft + "/" + sumRight
                     + ", difference=" + relativeDifference );

    if ( relativeDifference <= 10 )
      return splitIndex;

    int element = values[ splitIndex ];
    sumLeft  += element;
    sumRight -= element;
  }
  return -1;
}

// https://en.wikipedia.org/wiki/Relative_change_and_difference
private static int relativeDifference( int a, int b ) {
  if ( a == b ) return 0;
  int absoluteDifference = Math.abs( a - b );
  return (int) (100. * absoluteDifference / Math.max( a, b ));
}

Den Algorithmus für die Lösung können wir gut iterativ oder rekursiv umsetzen. Die Entscheidung ist hier auf die gut verständliche iterative Variante gefallen.

Beginnen wir mit einer einfachen Überlegung, wie wir das Problem lösen können. Wir könnten

  1. einen Index nehmen, der das Array in zwei Hälften teilt,

  2. die Summe vom rechten und linken Teil berechnen,

  3. vergleichen und, wenn die beiden Seiten in etwa gleich sind, das Programm mit einem Ergebnis beenden.

Der Index wandert von vorne nach hinten, und die Summen werden immer neu berechnet. Dieser Algorithmus ist einfach, wir müssen allerdings mehrfach über das Array gehen, sodass letztendlich die Laufzeit quadratisch ist. Das geht besser.

Wenn wir das Array in zwei Teile zerlegen und der Cursor um eine Position nach rechts wandert, verändert sich die Summe nach einem ganz einfachen Muster: Das, was links zur Summe hinzukommt, wird rechts abgezogen. Das ist die Kernidee der Lösung.

Am Anfang der Methode prüfen wir, ob ein oder kein Element übergeben wurde. Dann kann es auch keine faire Teilung geben, und wir liefern -1 zurück. Falls die null-Referenz übergeben wird, knallt das Programm mit einer NullPointerException, was eine gute Reaktion ist.

Im nächsten Schritt deklarieren wir zwei Variablen, die die Summen der linken und rechten Hälfte speichern. Die linke Summe besteht am Anfang nur aus dem ersten Element des Arrays, die rechte Summe bildet sich vom zweiten (Index 1) bis zum letzten Element.

Diese beiden Variablen, sumLeft und sumRight, werden wir im Folgenden anpassen. Die Schleife läuft vom ersten bis zum letzten Element. Da wir schon vor dem Schleifendurchlauf die linke und rechte Summe komplett gebildet haben, können wir jetzt schon die relative Differenz berechnen, und wenn sie <= 10 ist, dann haben wir tatsächlich schon ein Ergebnis. Falls der Abstand der Werte größer war, wird zum linken Teil das Element addiert und vom rechten Element abgezogen. Zum Schluss geht es weiter in die Schleife, und falls die relative Differenz irgendwann einmal kleiner gleich 10 wird, springen wir mit dem splitIndex raus, andernfalls wird die Methode mit -1 beendet.

1.7.8. Berge zeichnen

Listing 8. com/tutego/exercise/array/MountainVisualizer.java
private static String mountainChar() { return "*"; }

public static void printMountain( int[] altitudes ) {

  int maxAltitude = altitudes[ 0 ];

  for ( int currentAltitude : altitudes )
    if ( currentAltitude > maxAltitude )
      maxAltitude = currentAltitude;

  // include height 0, so it’s >= 0
  for ( int height = maxAltitude; height >= 0; height-- ) {
    System.out.print( height + " " );
    for ( int altitude : altitudes )
      System.out.print( altitude == height ? mountainChar() : ' ' );
    System.out.println();
  }
}

Die Methode printMountain(int[] altitudes) nimm ein ganzes Array von Höheninformationen an, und für die grafische Darstellung müssen wir im ersten Schritt den höchsten Wert finden. Das ist die Aufgabe der ersten Schleife, die aber erst dann laufen darf, wenn das Array überhaupt Einträge hat. maxAltitude speichert das Maximum.

Im nächsten Schritt sind Zeilen zu zeichnen. Jede Zeile steht für eine Höhe. Das Schreiben aller Zeilen übernimmt eine for-Schleife mit einem Schleifenzähler height. Da es mit der maximalen Höhe beginnt, beginnt die Schleife mit maxAltitude und geht hinunter auf 0. Die Aufgabenstellung besagt, dass es nicht unter den Nullpunkt geht, das heißt, wir müssen keine zweite Suche für die kleinste Zahl ergänzen.

Im Rumpf der height-Schleife geben wir zunächst die Höhe aus gefolgt von einem Leerzeichen. (Wir schreiben height + " " und nicht height + ' ', warum?) Eine innere for-Schleife kümmert sich um die Zeile. Sie läuft wiederholt über die Höheninformationen altitudes, die der Methode übergeben wurden. Für jedes Element in altitudes fragen wir ab, ob es der Höhe height entspricht, und wenn ja, zeichnen wir das Symbol über mountainChar(), andernfalls ein Leerzeichen. Am Ende der Zeile wird eine Leerzeile geschrieben.

Das Zeichnen des Bergsymbols übernimmt die Methode mountainChar(); sie liefert ein * zurück. Wir hätten das Zeichen direkt zeichnen oder über eine Konstante referenzieren können, doch die Methode ist eine Vorbereitung für die nächste Aufgabe …​

Optionale Erweiterung

Im ersten Lösungsvorschlag gibt die Methode mountainChar() immer * zurück; wenn die Methode andere Symbole zurückgeben soll, braucht sie etwas mehr Kontext, denn sie muss zurück und nach vorne schauen können. Erweitern wir daher die Signatur: mountainChar(int[] altitudes, int index). Die Methode bekommt Zugriff auf das Array und auf die aktuelle Position. Der Aufruf sieht so aus:

Listing 9. com/tutego/exercise/array/MoreMountainVisualizer.java
for ( int height = maxAltitude; height >= 0; height-- ) {
  System.out.print( height + " " );
  for ( int x = 0; x < altitudes.length; x++ )
    System.out.print( altitudes[ x ] == height ?
                      mountainChar( altitudes, x ) : ' ' );
  System.out.println();
}

So kann mountainChar(…​) selbst entscheiden, was das richtige Symbol ist.

Listing 10. com/tutego/exercise/array/MoreMountainVisualizer.java
private static char mountainChar( int[] altitudes, int index ) {
  int previous = index == 0 ? 0 : altitudes[ index - 1 ];
  int current  = altitudes[ index ];
  int next     = index < altitudes.length - 1 ? altitudes[ index + 1 ] : -1;

  if ( previous < current && current > next )
    return '^';
  if ( current < next )
    return '/';
  if ( current > next )
    return '\\';
  // current == next )
  return '-';
}

Im ersten Schritt werden die Variablen previous, current und next mit den Höhen aus dem Array initialisiert; so lässt sich auf die Höhe des aktuellen Elements schauen, aber auch auf die des Vorgängers und Nachfolgers. Vor dem ersten Element des Arrays soll die Höhe 0 sein, genauso wie nach dem letzten Element.

Abhängig von den Beziehungen kann eine Wahl für das Zeichen auf der Höhe current getroffen werden:

  • Sind previous und next kleiner als current, so haben wir eine Spitze und zeichnen ein ^.

  • Sind wir niedriger als der rechte Nachbar, geht es bergauf, und wir zeichnen /.

  • Sind wir höher als der rechte Nachbar, geht es bergab, das Symbol ist \.

  • Andernfalls ist der rechte Nachbar auf der gleichen Höhe wie wir selbst, und das wird angedeutet durch -.

1.7.9. Mini-Sudoku auf gültige Lösung prüfen

Listing 11. com/tutego/exercise/array/Sudoku3x3Checker.java
final int DIMENSION = 3;
for ( int i = 1; i <= DIMENSION * DIMENSION; i++ ) {
  boolean found = false;
  matrixLoop:
  for ( int row = 0; row < DIMENSION; row++ ) {
    for ( int column = 0; column < DIMENSION; column++ ) {
      int element = array[ row ][ column ];
      if ( element == i ) {
        found = true;
        break matrixLoop;
      }
    }
  }
  if ( ! found )
    System.out.printf( "Missing %d%n", i );
}

Das Array für die Aufgabe deklarieren wir vorweg mit Elementen, ebenso legen wir eine Variable DIMENSION an, für die Ausmaße des Arrays. Wir gehen davon aus, dass das 3-×-3-Array genau neun Elemente besitzt.

Zwei verschiedene Lösungen wollen wir uns anschauen. Ist zu testen, ob die Zahlen 1 bis 9 in dem zweidimensionalen Array vorkommen, kann eine Schleife die Werte von 1 bis 9 produzieren, und dann lässt sich prüfen, ob jede dieser Zahlen in dem zweidimensionalen Array vorkommt. Dazu legen wir eine boolean-Variable found an, die wir am Anfang mit false initialisieren und immer dann, wenn im Array das Element vorkommt, auf true gesetzt wird; in dem Fall können wir auch die Schleifen abbrechen. Prinzipiell könnten wir natürlich weitersuchen, aber das ist unnötig. Für den Abbruch der Schleife müssen wir auf eine besondere Konstruktion in Java zurückgreifen, die Sprungmarken. Wenn wir in der Fallunterscheidung einfach nur break nutzen, beendet das die innerste Schleife, allerdings nicht die äußere Schleife. Mit einer Sprungmarke können wir auch die äußere Schleife mit break verlassen. Am Ende der Schleifen fragen wir das Flag found ab, und wenn das Flag weiterhin false ist, weil es in der Fallunterscheidung nicht auf true gesetzt wurde, fehlt die Zahl. Wir geben sie aus.

Der Nachteil der Lösung ist die relativ hohe Laufzeit, außerdem macht ein break mit Label den Code unleserlich und schwerer verständlich. Wir müssen neunmal das 3 × 3 große Array ablaufen. Das geht besser. Allerdings müssen wir uns merken, ob wir eine Zahl schon einmal gesehen haben oder nicht.

Listing 12. com/tutego/exercise/array/Sudoku3x3Checker.java
boolean[] numberExisted = new boolean[ DIMENSION * DIMENSION ];

for ( int row = 0; row < DIMENSION; row++ ) {
  for ( int column = 0; column < DIMENSION; column++ ) {
    int element = array[ row ][ column ];
    if ( element >= 1 && element <= 9 )
      numberExisted[ element - 1 ] = true;
  }
}

for ( int i = 0; i < numberExisted.length; i++ ) {
  boolean found = numberExisted[ i ];
  if ( ! found )
    System.out.printf( "Missing %d%n", i + 1 );
}

Die zweite Lösung deklariert ein boolean-Array numberExisted als Speicher. Das Praktische bei den Zahlen ist, dass sie zwischen 1 und 9 liegen, also können wir das problemlos auf den Index 0 bis 8 abbilden. Wenn wir aus dem Array eine Zahl holen und daraus einen Index für das Array berechnen, müssen wir uns davor schützen, eine ArrayIndexOutOfBoundsException zu bekommen. Daher prüfen wir vorher, ob die Zahl element im richtigen Bereich ist. Wenn, dann setzen wir auf der Position element - 1 den Wert true.

Nach dem einmaligen Durchlauf untersuchen wir das Array, und falls wir eine Position finden, die nie beschrieben wurde, wissen wir, dass die Zahl fehlt. Ob eine Stelle im Array mehrfach belegt wurde, spielt dabei keine Rolle.

1.7.10. Bild vergrößern

Listing 13. com/tutego/exercise/array/ArrayMagnifier.java
public static int[][] magnify( int[][] array, int factor ) {
  int width = array[ 0 ].length;
  int height = array.length;
  int[][] result = new int[ height * factor ][ width * factor ];

  for ( int row = 0; row < result.length; row++ ) {
    int[] cols = result[ row ];
    for ( int col = 0; col < cols.length; col++ )
      cols[ col ] = array[ row / factor ][ col / factor ];
  }
  return result;
}

private static void printValues( int[][] array ) {
  for ( int[] rows : array ) {
    for ( int col = 0; col < rows.length; col++ )
      System.out.printf( "%03d%s",
                         rows[ col ], col == rows.length - 1 ? "" : ", " );
    System.out.println();
  }
}

private static void fillWithRandomValues( int[][] array ) {
  for ( int row = 0; row < array.length; row++ ) {
    int[] cols = array[ row ];
    for ( int col = 0; col < cols.length; col++ ) {
      array[ row ][ col ] = ThreadLocalRandom.current().nextInt( 256 );
    }
  }
}

public static void main( String[] args ) {
  int[][] testArray = new int[ 2 ][ 5 ];
  fillWithRandomValues( testArray );
  printValues( testArray );
  int[][] result = magnify( testArray, 2 );
  printValues( result );
}

Der zentralen magnify(…​)-Methode haben wir noch ein paar weitere Methoden beiseitegestellt, die ein Array mit Zufallszahlen anlegen und die Informationen in einer Matrix ausgeben.

Um die Übersicht zu erhöhen, werden zum Start der Methode zwei neue Variablen deklariert, die für die Breite und Höhe des zweidimensionalen Arrays stehen. Die nächste Aufgabe besteht darin, ein neues zweidimensionales Array aufzubauen, das in der Höhe und Breite um den factor größer ist als das alte Array.

Die Hauptaufgabe übernehmen die zwei ineinandergeschachtelten Schleifen. In der ersten äußeren Schleife laufen wir mit row über alle neuen Zeilen. Da zweidimensionale Arrays nichts anderes sind als Arrays in Arrays, hält das äußere Array ganz viele Verweise auf die inneren Arrays, die Zeilen. Die Hilfsvariable cols steht genau für die Spalten so eine Zeile. Den inneren Schleifenzähler col lassen wir dann von 0 bis zur Breite dieser Zeile laufen.

Der interessante Teil ist in der inneren Schleife. Wir haben die Variablen row und col in den Wertebereichen des neuen vergrößerten zweidimensionalen Arrays. Es gilt, die Position result[row][col] zu initialisieren. Dazu holen wir uns die Werte aus dem alten kleinen array. Die Position rechnen wir runter mit row / factor für die Zeile und col / factor für die Spalte. Zur Erinnerung: row geht von 0 bis height * factor und col bis width * factor. Bei den Divisionen row / factor und col / factor werden Ganzahlen dividiert, und das Ergebnis ist wieder eine Ganzzahl; das hat zur Folge, dass mehrmals dieselbe Zahl aus dem kleinen Ursprungs-Array herausgeholt wird.

1.7.11. SVG-Polygone mit variabler Koordinatenanzahl erzeugen

Listing 14. com/tutego/exercise/array/SvgVarargPolygon.java
/**
 * Prints an SVG polygon. Example output:
 * <pre>
 *  <polygon points="200,10 250,190 160,210 " />
 * </pre>
 * @param points of the SVG polygon.
 */
public static void printSvgPolygon( int... points ) {

  if ( points.length % 2 == 1 )
    throw new IllegalArgumentException(
        "Array has an odd number of arguments: " + points.length );

  System.out.print( "<polygon points=\"" );

  for ( int i = 0; i < points.length; i += 2 )
    System.out.printf( "%d,%d ", points[ i ], points[ i + 1 ] );

  System.out.println( "\" />" );
}

Zwei Fehler können auftreten:

  1. Bei einem Vararg baut der Compiler selbst ein Array aus den übergebenen Argumenten auf, doch auch wir können einen Verweis auf ein Array übergeben. Da Referenzen null sein können, könnte es einen Aufruf von printSvgPolygon(null) geben. Die Übergabe wird durch null.length automatisch zu einer NullPointerException führen.

  2. Beim Aufruf von printSvgPolygon() baut der Compiler ein leeres Array auf; dieses enthält keine Elemente, was prinzipiell für unsere Methode in Ordnung ist. Aber es gibt eine andere Anforderung an die Länge: Die Methode selbst erwartet immer Pärchen von x- und y-Koordinaten. Es wäre ein Fehler, wenn nur eine Koordinate übergeben würde und nicht zwei. Leider kann der Compiler so etwas nicht testen, man kann an die Anzahl der Varargs keine Wünsche stellen wie: »höchstens 102 Elemente«, »die Anzahl der Elemente muss durch 10 teilbar sein« etc. Es bleibt uns nichts anderes übrig, als den Test zur Laufzeit durchzuführen. Wir können den Fehler leicht erkennen, indem wir prüfen, ob die Anzahl der Elemente in dem Array gerade oder ungerade ist. Ist die Anzahl gerade, wurden immer Paare übergeben, für x und y. Ist die Anzahl ungerade, so fehlt eine Koordinate. Wir bestrafen fehlerhafte Aufrufe mit einer IllegalArgumentException.Es wäre noch zu überlegen, aus beiden Prüfungen zwei Fallunterscheidungen zu machen, um dann im Fall der ungeraden Übergabe die Anzahl Elemente mit in die Ausnahmemeldung zu setzen.

Das Generieren der Ausgabe besteht aus drei Teilen:

  1. Im ersten Teil, dem Prolog, setzen wir das Start-Tag für das Polygon.

  2. Im zweiten Teil läuft eine Schleife über alle Elemente des Arrays und greift sich immer zwei Elemente heraus, die mit Komma getrennt auf die Konsole kommen — hinter dem Paar steht ein Leerzeichen. Da wir immer zwei Elemente gleichzeitig aus dem Array nehmen, wird im Fortschaltausdruck der for-Schleife der Index um 2 erhöht. Da die Anzahl der Elemente im Array gerade ist, wird es keine ArrayIndexOutOfBoundsExcepion geben können.

  3. Die Methode endet mit dem Epilog, dem Schließen des Tags.

1.7.12. Auf Zustimmung prüfen

Listing 15. com/tutego/exercise/array/AllTrue.java
private static boolean allTrue( boolean first, boolean... remaining ) {

  for ( boolean b : remaining )
    if ( b == false )
      return false;

  return first;
}

Bei variablen Argumentlisten ist es nicht möglich, eine Mindestanzahl von Argumenten zu erwarten. Die Lösung für das Problem besteht darin, eine Mindestanzahl von festen Parametern einzuführen und dann zum Schluss ein Vararg für den Rest einzusetzen.

Die Methode hat zwei Pfade, die zu einer Rückgabe true oder false führen:

  1. Als erstes gehen wir das Array ab. Ist einer der Wahrheitswerte im Array false, können wir die Methode direkt mit return false beenden. Wenn das Array leer ist, passiert nichts. Es gibt Autoren, die boolean-Werte nicht mit == false testen, sondern den Ausdruck negieren, aber ich meine, dass sich if ( b == false ) besser lesen lässt als if ( ! b ); es kommt auch auf den Variablennamen an. Es kann sein, dass als Argument null übergeben wurde, dann wird die erweiterte for-Schleife eine NullPointerException erzeugen, das ist gewollt.

  2. Kommt es zu keinem Abbruch der Schleife, müssen alle Elemente in dem Array true gewesen sein, und der erste Parameter first entscheidet über das Ergebnis.

1.7.13. Hilfe, Tetraphobie! Alle Vieren nach hinten setzen

Listing 16. com/tutego/exercise/array/Tetraphobia.java
private static boolean containsFour( int number ) {
  return String.valueOf( number ).contains( "4" );
}

public static int[] fourLast( int... numbers ) {

  if ( numbers.length < 2 )
    return numbers;

  for ( int startIndex = 0; startIndex < numbers.length; startIndex++ ) {
    if ( ! containsFour( numbers[ startIndex ] ) )
      continue;

    // from right to left search the first number without a 4
    for ( int endIndex = numbers.length - 1;
          endIndex > startIndex; endIndex-- ) {
      if ( containsFour( numbers[ endIndex ] ) )
        continue;
      // swap number[i] (with 4) and number[j] no 4
      int swap = numbers[ startIndex ];
      numbers[ startIndex ] = numbers[ endIndex ];
      numbers[ endIndex ]   = swap;
    }
  }
  return numbers;
}

Für unsere Lösung schreiben wir neben der gewünschten Methode fourLast(…​) eine zusätzliche private Methode boolean containsFour(int), die die Frage beantwortet, ob die übergebene Zahl eine 4 enthält. In der Implementierung machen wir es uns einfach und konvertieren die Zahl in einen String, und contains(String) prüft, ob der String "4" in der String-Repräsentation liegt. Die Prüfung hätten wir natürlich auch numerisch durchführen können, doch das wäre viel komplizierter gewesen. Wir müssten diese Zahl immer durch 10 teilen und uns dann den Rest anschauen und testen, ob er 4 ist. Da ist mehr Code als nur dieser eine Einzeiler nötig.

Die Methode fourLast(…​) bekommt ein Array übergeben, das wieder null sein kann und in so einem Fall durch numbers.length zu einer NullPointerException führt. Auch könnte das Array nur ein Element beinhalten; in dem Fall geben wir direkt das übergebene Array an den Aufrufer zurück.

Der Algorithmus ist einfach implementiert: Wir laufen mit einer Schleife von links nach rechts, und wenn wir etwas mit einer 4 finden, laufen wir mit einer zweiten Schleife von rechts nach links und suchen den ersten freien Platz ohne 4. Dann vertauschen wir die Inhalte des Arrays.

Der Lösungsvorschlag ist nicht ganz optimal und sollte von den Lesern verbessert werden.

  1. Das Erste, was verbessert werden sollte, ist die Schleife mit startIndex, die immer bis numbers.length läuft. Das ist unnötig, denn sollte die innere Schleife eine Zahl mit einer 4 finden, dann wird diese Zahl nach hinten gehen, und wir können von der Länge eins abziehen, denn das letzte Element müssen wir ja nicht mehr betrachten.

  2. Zweitens ist die innere Schleife nicht optimal, denn sie beginnt immer von rechts nach links, die erste Zahl ohne 4 zu suchen. Allerdings wächst der Block mit den Vieren nur nach links, sodass wir uns in einer zweiten Variablen merken könnten, wo wir unsere letzte 4 untergebracht haben. Läuft die innere Schleife erneut, könnten wir bei dieser Position weitermachen und müssen nicht erst von rechts wieder zu dieser Position finden.

  3. Drittens können wir die beiden Verbesserungen kombinieren. Für den Fall, dass in der inneren Schleife keine Vertauschung stattfindet, wären wir fertig.

1.7.14. Quiz: Arrays kopieren

Mit der Methode arraycopy(…​) lassen sich Bereiche in einem Array verschieben oder Teile eines Arrays in ein anderes Array kopieren. Betrachten wir aus der Javadoc die Parametervariablen von arraycopy(…​), die selbsterklärend sind:

static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

In unserem Fall wird nicht in einem Array etwas verschoben, sondern es werden zweimal Teile eines Arrays in ein neues Array kopiert. hooey ist die Quelle und shuck das Ziel. Setzen wir die Konstanten ein und benennen hooey und shuck um, folgt:

int[] src = { 1, 2, 3, 4 };
int[] dest = new int[ 3 ];
System.arraycopy( src, 0, dest, 0, 2 );
System.arraycopy( src, 3, dest, 2, 1 );

Es entsteht [1, 2, 4], also ein neues Array, in dem das Element 3 an Index 2 (bushwa) fehlt. Die erste Kopieroperation überträgt von der Quelle ab der ersten Stelle 0 in das neue Array ab der Stelle 0, insgesamt 2 Elemente. Die zweite Kopieroperation kopiert ab der Stelle 3 (überspringt also Stelle 2) alles bis zum Ende auf das Ziel-Array ab der Position 2. Die Anzahl der kopierten Elemente ist eins.

Bei den unsinnigen Variablennamen sollte auch klar geworden sein, dass sauberer Code — hier Variablenbezeichner — menschliche Verarbeitungszeit einspart und Fehler reduziert.

1.7.15. Quiz: Arrays vergleichen

Der Operator == prüft, ob die Objekte, auf die die beiden Referenzvariablen verweisen, identisch sind. Das tun die beiden Variablen array1 und array2 nicht, denn es sind im Speicher zwei völlig getrennt stehende Objekte. Daher wird die Ausgabe auch false sein.

Arrays sind Objekte, und als Objekte haben sie alle Methoden, die auch der Basistyp java.lang.Object bietet. Allerdings können wir mit keiner dieser Methoden irgendetwas anfangen, was wir schnell merken, wenn wir die toString()-Methode auf einem Array-Objekt aufrufen. Die equals(…​)-Methode eines Arrays stammt aus Object, und dort steht ein Identitätsvergleich, der, wie im ersten Punkt erklärt, zur Ausgabe false führt.

Um Arrays zu vergleichen sind wir bei der Klasse java.util.Arrays und der Methode equals(…​) ganz richtig. Prinzipiell können wir mit dieser Methode Arrays vergleichen, allerdings haben unsere beiden Arrays eine kleine Besonderheit: Sie enthalten Strings und ein inneres Array mit Ganzzahlen. Wenn dieses unterreferenzierte Array nicht vorhanden wäre, würde tatsächlich bei dieser Ausgabe true erscheinen. Allerdings arbeitet Array.equals(…​) flach, das heißt, das referenzierte innere Array müsste identisch sein, da aber auch dieses Ganzzahl-Array jeweils ein neues Array ist, sind die beiden Referenzen auf das Ganzzahl-Array nicht gleich und somit liefert Array.equals(…​) auf unserem Array false.

Nur bei der Methode Array.deepEquals(…​) wird true auf dem Bildschirm erscheinen. deepEquals(…​) verfolgt auch die referenzierten Unter-Arrays und schaut, ob die Werte gleichwertig sind. Auf die Identität der Unter-Arrays kommt es bei deepEquals(…​) nicht an. Die beiden Ganzzahl-Arrays sind gleichwertig, und daher ist auch die Rückgabe von deepEquals(…​) true.