Archiv für den Monat: Dezember 2012

LinkedList Dojo mit Visual T# – Teil 2

Karate

Image courtesy of „luigi diamanti“ / FreeDigitalPhotos.net


Dies ist der zweite Teil von „LinkedList Dojo mit Visual T#“. In dieser Übungsaufgabe implementieren wir eine verknüpfte Liste nach dem Test-First Ansatz mit Hilfe von Visual T#.

Greifen Sie ruhig zu

Im ersten Teil haben wir die Funktion Add() und das Property Count implementiert. Nun wollen wir überprüfen, ob die Daten auch richtig abgelegt wurden. Dazu benötigen wir den Index-Operator (manchmal auch Indexer genannt) this[int index].

Als erstes wiederum ein Test, um eine erste Implementation zu erzwingen.

1
2
3
4
5
6
7
8
9
test this[int index] get
{
    LinkedList sut = new LinkedList ();
    sut.Add(5);

    runtest int value = sut[0];

    assert value == 5;
}

Und hier die zum Test passende Implementation.

1
2
3
4
5
6
7
8
9
10
11
public T this[int index]
{
    get
    {
        return first.Element;
    }
    set
    {
        throw new NotImplementedException();
    }
}

Schon beim Schreiben des Codes ist die nächste Frage aufgetaucht: Wie soll sich die Liste verhalten, wenn noch kein Element vorhanden ist oder wenn ein Index verwendet wird, der grösser ist als die Anzahl der Elemente in der Liste?
Die Dokumentation von IList<T> verrät es uns (im Bereich Exceptions):

ArgumentOutOfRangeException:
index is not a valid index in the IList<T>.

Dies hat zwei weitere Tests zur Folge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
test this[int index] get
{
    LinkedList sut = new LinkedList ();

    runtest int value = sut[0];

    assert thrown ArgumentOutOfRangeException;
}
       
test this[int index] get
{
    LinkedList sut = new LinkedList ();
    sut.Add(5);
    sut.Add(8);

    runtest int value = sut[2];

    assert thrown ArgumentOutOfRangeException;
}

Und dazu natürlich noch die passende Implementation, so dass die Tests auch wieder grün werden.

1
2
3
4
5
6
7
8
9
10
public T this[int index]
{
    get
    {
        if (index &gt;= Count) throw new ArgumentOutOfRangeException();
        return first.Element;
    }
    set
    (...)
}

Gezielter Zugriff

Natürlich funktioniert der Indexer bisher nur beim ersten Element richtig. Fügen wir also einen Test hinzu, um den wahlfreien Zugriff zu ermöglichen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
test this[int index] get
{
    int value1, value2;  
    LinkedList sut = new LinkedList ();
    for(int i = 0; i = Count) throw new ArgumentOutOfRangeException();

        LinkedListElement temp = first;

        for(int i = 0; i &lt; index; i++)
        {
            temp = temp.Next;
        }

        return temp.Element;
    }
    set
    (...)
}

Fehlt noch die Implementation des Setters, als erstes wieder der Test.

test this[int index] set
{
    int value1, value2;  
    LinkedList sut = new LinkedList ();
    for(int i = 0; i = Count) throw new ArgumentOutOfRangeException();

        LinkedListElement temp = first;

        for (int i = 0; i &lt; index; i++)
        {
            temp = temp.Next;
        }

        temp.Element = value;
    }
}

OK, bei der Implementation habe ich etwas geschummelt, ich habe das Test-First Prinzip missachtet und bereits die Überprüfung, ob der übergebene index gültig ist, eingebaut. Hier noch der Test, um die Überprüfung auch zu rechtfertigen.

 test this[int index] set
{
    LinkedList sut = new LinkedList ();
    sut.Add(5);
    sut.Add(8);
           
    runtest sut[2] = 3;

    assert thrown ArgumentOutOfRangeException;
}

Was mich aber mehr stört als die kleine Prinzip-Verletzung sind die Redundanzen im Code, am offensichtlichsten im zuletzt implementierten Indexer. Deshalb starten wir den dritten Teil mit einem Refactoring der bisher implementieren Funktionalitäten und Tests.

LinkedList Dojo mit Visual T# – Teil 1

Karate

Image courtesy of „luigi diamanti“ / FreeDigitalPhotos.net


In der Mai-Ausgabe der dotnetpro war die Dojo-Aufgabe (mehr Infos zu den Dojo-Aufgaben) eine verkettete Liste zu implementieren. Eine Aufgabe, bei der keine Ressourcenzugriffe (Datenbank, Filesystem …) und keine Abhängigkeiten das Testen erschweren. Also ein ideales Tummelfeld, um Unit Tests zu verwenden und dabei Visual T# einzusetzen (Einstieg in Visual T#). Dabei versuche ich nach dem Test-First Prinzip vorzugehen.

Aller Anfang ist leicht

Die Aufgabenstellung beschreibt die Anforderungen und die „Architektur“ der Liste schon relativ präzise, so dass ich mir erlaube gleich Visual Studio zu starten, ohne erst eine Skizze zu Papier zu bringen.

Die Visual Studio Solution enthält keine Überraschungen. Als erstes Project die Klassenbibliothek mit der zu erstellenden verketteten Liste (LinkedList) und als zweites das Visual T# Testprojekt.

Als erstes erfüllen wir die Anforderung, dass unsere LinkedList das Interface IList<T> implementiert. Die Methodenrümpfe erstellt uns Visual Studio auf Mausklick, so dass unser Projekt bereit für die ersten Test-Implementationen ist.

Erster Test

Als ersten Test erstellen wir die Überprüfung, dass eine leere Liste beim Abfragen der Anzahl der Elemente null zurück gibt.

1
2
3
4
5
6
7
8
9
10
11
testclass LinkedListTest for LinkedList< int >
{
    test Count get
    {
        LinkedList< int > sut = new LinkedList < int >();

        runtest int count = sut.Count;

        assert count == 0;
    }
}

Die einfachste Implementierung, die diesen Test erfüllt sieht so aus:

1
2
3
4
public int Count
{
    get { return 0; }
}

Noch nicht wirklich eine sinnvolle Implementierung aber aus dem Test-First Ansatz bzw. dem YAGNI-Prinzip richtig.

Ein Fuss vor den Andern

Für den nächsten Schritt müssen wir etwas mehr investieren. Wenn wir ein Element in der Liste haben möchten müssen wir zuerst das Element hinzufügen.

1
2
3
4
5
6
7
8
9
test Count get
{
    LinkedList< int > sut = new LinkedList < int >();
    sut.Add(5);
           
    runtest int count = sut.Count;

    assert count == 1;
}

Da wir noch keine Implementation für Add() haben wirft dieser Test eine NotImplementedException. Fügen wir also die Implementation hinzu und bauen auch das Property Count so um, dass der Test erfogreich ist. Dabei implementieren wir (vielleicht ein bisschen entgegen dem YAGNI- und KISS-Prinzip) auch gleich den internen Container, da dieser ja als Anforderung verlangt wird.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LinkedList< T > : IList< T >
{
    private class LinkedListElement
    {
        public T Element { get; set; }
        public LinkedListElement Next { get; set; }
    }

(...)

    public void Add(T item)
    {
        first = new LinkedListElement() { Element = item };
    }

    public int Count
    {
        get { if (first == null) return 0; return 1; }
    }

(...)

    private LinkedListElement first;
}

Dieser Code erfüllt die in den Tests definierten Anforderungen, aber da fehlt noch einiges. Machen wir also den nächsten Schritt, noch ein Element hinzufügen und die Anzahl überprüfen.

1
2
3
4
5
6
7
8
9
10
test Count get
{
    LinkedList< int > sut = new LinkedList < int >();
    sut.Add(5);
    sut.Add(8);
                       
    runtest int count = sut.Count;

    assert count == 2;
}

Kleine Anmerkung zu den Tests: Auch wenn es vielleicht den Anschein macht, ich habe keine Tests geändert sondern neue hinzugefügt. Bei T# dürfen mehrere Tests die selbe Signatur (in diesem Fall ‚test Count get‘) haben, das Testprojekt enthält jetzt also drei Tests.

Unbegrenztes Wachstum

Nun ist es Zeit, bei Add() und Count eine allgemeine Implementation einzufügen, die für beliebig viele (im Rahmen der Schnittstelle, Count ist z.B. vom Typ int) Elemente funktioniert.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public void Add(T item)
{
    if (first == null)
    {
        first = new LinkedListElement() { Element = item };
    }
    else
    {
        LinkedListElement temp = first;
        while(temp.Next != null)
        {
            temp = temp.Next;
        }
        temp.Next = new LinkedListElement { Element = item };
    }
}

public int Count
{
    get
    {
        if (first == null) return 0;

        int count = 1;
        LinkedListElement temp = first;
        while (temp.Next != null)
        {
            temp = temp.Next;
            count++;
        }
        return count;
    }
}

Vertrauen ist gut, Kontrolle ist besser

Mit einem weiteren Test überprüfen wir die allgemeine Gültigkeit der Implementation.

1
2
3
4
5
6
7
8
9
10
11
12
test Count get
{
    LinkedList< int > sut = new LinkedList < int >();
    for(int i = 0; i < 10; i++)
    {
        sut.Add(i);
    }
                 
    runtest int count = sut.Count;

    assert count == 10;
}

Somit haben wir einen Stand erreicht, bei dem wir die Liste befüllen können und die Werte scheinbar auch gespeichert werden. Um dies aber überprüfen zu können müssen wir eine Möglichkeit implementieren, auf die gespeicherten Werte wieder zugreifen zu können. Diese Funktionalität werden wir im zweiten Teil realisieren.