LinkedList Dojo mit Visual T# – Teil 3

Karate

Image courtesy of „luigi diamanti“ / FreeDigitalPhotos.net


Dies ist der dritte 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#.

Am Ende von Teil 2 habe ich ja bereits angekündigt, dass als Erstes ein Refactoring ansteht. Dabei werden wir nicht nur die LinkedList überarbeiten sondern auch die dazugehörigen Tests (ohne natürlich die Test-Funktionalitäten zu ändern).

Was riecht hier so streng?

Code Smell: Suchschleifen

Im Indexer haben wir zwei mal dieselbe Suchschleife, einmal im get- und einmal im set-Block. Diese Schleife extrahieren wir in eine eigene Methode, die wir dann aufrufen.

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
public T this[int index]
{
    get
    {
        if (index >= Count) throw new ArgumentOutOfRangeException();

        LinkedListElement temp = GetAt(index);

        return temp.Element;
    }
    set
    {
        if (index >= Count) throw new ArgumentOutOfRangeException();

        LinkedListElement temp = GetAt(index);

        temp.Element = value;
    }
}

private LinkedListElement GetAt(int index)
{
    LinkedListElement temp = first;

    for (int i = 0; i < index; i++)
    {
        temp = temp.Next;
    }
    return temp;
}

Wieder alle Tests ausführen und beruhigt sehen, dass immer noch alle Tests funktionieren.

Code Smell: Initialisierung in Tests

In jedem Test wird die Liste neu erzeugt. Dies kann in eine Methode ausgelagert werden, den sogenannten testcontext. Der Codeabschnitt vor dem runtest entspricht dabei dem TestInitialize- bzw. dem SetUp-Attribut, der Codeabschnitt nach dem runtest dem TestCleanup- bzw. dem TearDown-Attribut beim Microsoft Unit Test Tool bzw. bei NUnit.
Das sieht dann wie folgt aus (nur ein Test als Beispiel).

testclass LinkedListTest for LinkedList
{
    LinkedList sut;
       
    testcontext
    {
        test
        {
            sut = new LinkedList ();
            runtest;
        }
    }
       
    test Count get
    {
        runtest int count = sut.Count;

        assert count == 0;
    }
    (...)
}

Die beiden schlimmsten Code Smells sind behoben, aber die zwei Schleifen in Count und Add riechen auch noch ein wenig. Ich erlaube mir aber, die Nase noch ein bisschen zuzuklemmen und noch etwas Funktionalität hinzuzufügen.

Leeren Sie Ihren Kopf

Als erstes möchte ich die Liste leeren können, so dass ich wieder neue Elemente hinzufügen kann.

1
2
3
4
5
6
7
8
9
10
test Clear
{
    sut.Add(5);
    sut.Add(8);
    assert sut.Count == 2;
           
    runtest sut.Clear();

    assert sut.Count == 0;
}

Der assert-Ausdruck vor dem runtest ist eine kleine Zusatzsicherheit, dass die Liste auch Elemente enthält bevor wir sie löschen. Das ist erlaubt und auch vernünftig, da so auch wirklich das getestet wird, was man testen will. Der Test schlägt natürlich fehl, da Clear noch die Standard-Implementation enthält, die eine Exception wirft. Lassen wir den Test grün werden.

1
2
3
4
public void Clear()
{
    first = null;
}

Ganz nach dem Motto nach uns die Sintflut hängen wir einfach das erste Element der verketteten Liste ab und wir sind die Liste los. Der Garbage Collector kann sich dann um die Überreste kümmern.

Haben Sie ..?

Da dies so einfach war fügen wir noch eine Funktionalität mehr hinzu, die Methode Contains(). Wiederum zuerst den Test, der dann fehlschlägt:

1
2
3
4
5
6
7
8
9
test Contains(int)
{
    sut.Add(5);
    sut.Add(8);

    runtest bool res = sut.Contains(5);
           
    assert res;
}

Und die einfachste Implementation, die den Test erfüllt:

1
2
3
4
public bool Contains(T item)
{
    return true;
}

Ein zweiter Test soll den Fall abdecken, dass das Element nicht in der Liste vorhanden ist:

1
2
3
4
5
6
7
8
9
test Contains(int)
{
    sut.Add(5);
    sut.Add(8);

    runtest bool res = sut.Contains(6);
           
    assert res == false;
}

Natürlich kann die Überprüfung auch mit

assert !res;

erfolgen.

Hier die (nun sinnvolle) Implementierung, die den neuen Test erfüllt, ohne die anderen Tests fehlschlagen zu lassen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public bool Contains(T item)
{
    LinkedListElement temp = first;

    if (EqualityComparer.Default.Equals(temp.Element, item))
        return true;
    while (temp.Next != null)
    {
        temp = temp.Next;
        if (EqualityComparer.Default.Equals(temp.Element,item))
            return true;
    }

    return false;
}

Das Konstrukt in der if-Abfrage ist dem Umstand geschuldet, dass unsere LinkedList sowohl mit Value- als auch mit Reference-Typen funktionieren soll. Weiter Infos sind z.B. bei StackOverflow zu finden.

Bei der Implementation dieser Funktion habe ich gemerkt, dass noch nicht beide Randbedingungen überprüft werden. Also fügen wir noch einen zusätzlichen Test hinzu:

1
2
3
4
5
6
7
8
9
test Contains(int)
{
    sut.Add(5);
    sut.Add(8);

    runtest bool res = sut.Contains(8);
           
    assert res;
}

Dieser Test ist von Anfang an grün, wir haben unsere Implementation also richtig gemacht.

Wo finde ich ..?

Verwandt mit Contains() scheint IndexOf() zu sein. Nehmen wir uns diese Implementation auch noch gleich vor. Wie immer zuerst der Test. Wir übernehmen gleich die drei Tests von Contains() und passen sie an:

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
test IndexOf(int)
{
    sut.Add(5);
    sut.Add(8);

    runtest int pos = sut.IndexOf(5);
           
    assert pos == 0;
}
       
test IndexOf(int)
{
    sut.Add(5);
    sut.Add(8);

    runtest int pos = sut.IndexOf(6);
           
    assert pos == -1;
}
       
test IndexOf(int)
{
    sut.Add(5);
    sut.Add(8);

    runtest int pos = sut.IndexOf(8);
           
    assert pos == 1;
}

Natürlich schlagen alle drei Tests fehl. Nehmen wir nun auch den Code von Contains() und passen ihn für IndexOf() an:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int IndexOf(T item)
{
    int pos = 0;
    LinkedListElement temp = first;

    if (EqualityComparer.Default.Equals(temp.Element, item))
        return pos;
    while (temp.Next != null)
    {
        temp = temp.Next;
        pos++;
        if (EqualityComparer.Default.Equals(temp.Element, item))
            return pos;
    }

    return -1;
}

Mit minimalen Anpassungen sind wieder alle Tests grün. Aber wir haben wieder einen Code Smell, den wir auch gleich beheben:

1
2
3
4
public bool Contains(T item)
{
    return IndexOf(item) > -1;
}

Contains() überprüft nur noch, ob IndexOf() einen gültigen Index zurück gibt. Und dieses Refactoring hat nichts kaputt gemacht, es sind immer noch alle Tests grün.

Immer noch warten einige Methoden auf ihre Implementation. Diesen werden wir uns im vierten Teil annehmen.

3 Gedanken zu „LinkedList Dojo mit Visual T# – Teil 3

  1. Pingback: LinkedList Dojo mit Visual T# – Teil 2 « of bits and bytes

  2. Pingback: LinkedList Dojo mit Visual T# – Teil 4 « of bits and bytes

  3. Pingback: IList Dojo Retrospektive « of bits and bytes

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.