StringList:Javakurs

Übersicht

Zielsetzung

Eine Klasse, die eine Liste von Textzeilen verwaltet.

Die Umsetzung erfolgt mit einer doppelt verlinkten Liste:

_________________           _________________         _________________
| text: Zeile 1   |         | text: Zeile 2 |         | text: Zeile 3 |
| pred: <null>    | <-------|--: pred       | <-------|--: pred       |
| succ:         --|-------> | succ:       --|-------> | succ: <null>  |
|_________________|         |_______________|         |_______________|

Jedes Element hat einen Verweis auf das vorherige und das nachfolgende Element. Im ersten Element ist der Vorgänger null, im letzten Element der Nachfolger.

Die Klassen

class Element {
    String text = null;
    Element pred = null;
    Element succ = null;
}
/**
 * Implements a doubled linked list of strings.
 */
public class StringList {
    /**
     * @param args
     */
    public static void main(final String[] args) {
        final StringList list = new StringList();
        list.add("hello");
        list.add("all");
        list.add("worlds");
    }

    private Element first = null;
    private Element last = null;
    private int count = 0;
    /**
     * Adds a text to the end of the list.
     *
     * @param text
     *            text to append
     */
    public void add(final String text) {
        final Element element = new Element();
        element.text = text;
        if (this.last == null)
            this.last = this.first = element;
        else {
            element.pred = this.last;
            this.last.succ = element;
            this.last = element;
        }
        this.count++;
    }
    /**
     * Returns the text of the n-th element.
     *
     * @param index
     *            index of the wanted element
     * @return null: wrong index<br>
     *         otherwise: the text of the element with index <code>index</code>
     */
    public String get(final int index) {
        final Element element = getElement(index);
        final String rc = element == null ? null : element.text;
        return rc;
    }
    /**
     * @return the count
     */
    public int getCount() {
        return this.count;
    }
    /**
     * Gets the the n-th element of the list.
     *
     * @param index
     *            index of the wanted element
     * @return <code>null</code>: wrong index<br>
     *         otherwise: the text of the element with index <code>index</code>
     */
    Element getElement(final int index) {
        Element rc = null;
        if (index >= 0 && index < this.count) {
            rc = this.first;
            int ix = 0;
            while (rc != null && ix++ < index)
                rc = rc.succ;
        }
        return rc;
    }
    /**
     * @return the first
     */
    public Element getFirst() {
        return this.first;
    }
    /**
     * @return the last
     */
    public Element getLast() {
        return this.last;
    }
    /**
     * Searches for matching a regular expression
     *
     * @param start
     *            first index to search
     * @param regExpr
     *            the regular expression to search
     * @return -1: not found<br>
     *         otherwise: the lowest index of the element greater or equal
     *         <code>start</code> where the regular expression match
     */
    public int search(final int start, final String regExpr) {
        int rc = -1;
        Element element = getElement(start);
        if (element != null) {
            int index = start;
            final Pattern pattern = Pattern.compile(regExpr);
            do {
                if (pattern.matcher(element.text).find()) {
                    rc = index;
                    break;
                }
                index++;
                element = element.succ;
            } while (element != null);
        }
        return rc;
    }
}

Anmerkungen

Die Klasse Element wird nur innerhalb von StringList verwendet und kommt in keiner der public-Methoden als Ergebnis oder Parameter vor. Daher kann die Klasse in der gleichen Datei wie StringList verwendet definiert werden. Der Unterschied ist, dass StringList public ist, während Element nicht public ist.

Die Klassenvariablen von Element sind ohne Zugriffsprädikat. Daher kann von jeder Klasse innerhalb der Datei darauf zugegriffen werden.

Die Klassenvariablen first, last und count dürfen von anderen Klassen nur gelesen, nicht geändert werden. Daher sind sogenannte Getter-Funktionen zum Lesen der Variablen definiert. Der Name einer Getter-Funktion besteht aus dem Präfix "get" und dem Namen der Variablen (beginnend mit einem Großbuchstaben, also z.B. getCount().

Eclipse kann Getter- (und Setter-)Funktionen automatisch erstellen: entsprechende Variable(n) auswählen und im Menü "Source - Generate Getters and Setters" aufrufen.

Die Methode add() hängt eine neues Element ans Ende der bestehenden Liste.

Die Methode search() sucht das erste Element, das hinter einem gegebenen Index liegt und mit einem Suchmuster übereinstimmt. Als Suchmuster werden reguläre Ausdrücke verwendet.

JUnit Tests

Eine gängige Vorgehensweise beim Programmieren ist das "test driven development":

• Definiere vor der Implementierung Testfälle.
• Die Testfälle sollen alle oder wenigstens alle gängigen Möglichkeiten abdecken.
• Kommen bei Parametern Intervalle vor, so sind die 3 Möglichkeiten "vor der Grenze", "auf der Grenze" und "nach der Grenze" zu testen.

Java bietet unter anderem für solche Tests die "JUnit"s an:

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;

import org.junit.Test;

import de.hamatoma.jkurs.StringList;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
public class StringListTest {
    @Test
    public void testBasics() {
        final StringList list = new StringList();
        assertEquals(0, list.getCount());
        list.add("Hello");
        list.add("my");
        list.add("world");
        assertEquals(3, list.getCount());
        assertEquals("Hello", list.get(0));
        assertEquals("my", list.get(1));
        assertEquals("world", list.get(2));
        assertNull(list.get(-1));
        assertNull(list.get(3));
    }
    @Test
    public void testSearch() {
        final StringList list = new StringList();
        assertEquals(-1, list.search(0, "e"));
        list.add("Hello");
        list.add("my");
        list.add("world");
        assertEquals(0, list.search(0, "He"));
        assertEquals(-1, list.search(1, "He"));
        assertEquals(1, list.search(1, "y"));
        assertEquals(1, list.search(0, "y"));
        assertEquals(-1, list.search(2, "y"));
        assertEquals(2, list.search(0, "ld"));
        assertEquals(2, list.search(1, "ld"));
        assertEquals(2, list.search(2, "ld"));
        assertEquals(-1, list.search(3, "ld"));
    }
}

Anmerkungen

• Es gibt keine Methode main(): Die zu testenden Funktionen werden mit "@Test" gekennzeichnet. Der Aufruf der Testfunktionen erfolgt automatisch mit "Run as JUnit Test" bzw. "Debug as JUnit Test"
• Das Programm verwendet die zu testende Klasse und prüft danach, ob das Gewünschte passiert ist:
  • Es werden 3 Strings angehängt
  • Danach wird geprüft, ob die Anzahl 3 ist und ob die Werte wieder gelesen werden können.
• Auch werden die Fehlerzustände geprüft: Verwenden von undefinierten Indexwerten (z.B. -1).

Aufgaben

• Programmiere eine Methode insert(int index, String text), die ein Element beim angegebenen Index einfügt:

A ----- B ------ C
insert(1, "X")
A ----- X ------ B -------- C

• Erstelle eine Methode remove(int index), die ein Element an einer bestimmten Position entfernt.
• Optimiere die Methode get(): Wenn es günstiger ist, finde das Element von hinten (vom letzten Element aus).