Kodprov 2017-12-18 – genomgång

Klassen LinkedSet skall vara en subtyp av Collection och Set. Eftersom inte Collection implementerar Set eller Set ärver av Collection är den enda möjligheten att möta subtypskravet att göra LinkedSet till en subklass av Collection och implementera interfacet Set.

public class LinkedSet extends Collection implements Set

Man måste förstå ordet subtyp här. I övrigt skall det vara uppenbart att man endast kan subklassa den enda och implementera den andra.

Både Set och Collection är parameteriserade över typparametern T och instruktionerna efterfrågar typsäkerhet – att det skall gå att skapa en mängd av element endast av en given typ. Lösningen är att parameteriser LinkedSet över T vilket kräver att man skickar vidare typparametern.

public class LinkedSet<A> extends Collection<A> implements Set<A>

Observera att man kan använda vilken bokstav man vill istället för A. Eftersom vi använt T redan i koden i LinkedSet är det rätt bokstav att använda för att undvika sök-och-ersätt.

Superklassen Collection har en konstruktor som kräver att en maxkapacitet anges. Då vi ärver av Collection måste vi se till att samtliga konstruktorer i LinkedSet anropar konstruktorn i Collection med maxkapaciteten. Så här kan vi t.ex. lösa det:

public LinkedSet(int maxCapacity) {
    super(maxCapacity);
}

Fälten first och last hade inga åtkomstmodifierare och testerna klagar om de inte är private. Lösning:

private Link first = new First(null);
private Link last = first;

När element skall läggas till skall vi kasta ett undantag om mängden är full. Exempelvis:

if (this.size() == this.maxCapacity()) throw new SetFullException();

Vidare skall vi se till att samma element bara förekommer i mängden en gång. Exempelvis:

if (this.contains(elem)) return false;

Att använda contains() kräver att man förstår att dess implementation av samma är det som efterfrågas i instruktionerna. De som har implementerat en egen sådan kontroll i add() måste använda equals() och inte ==.

Ytterligare en svårighet med denna uppgift är att förstå hur inlänkning går till i en lista med en tom första länk. Exempelvis:

this.last.next = new Link(elem);
this.last = this.last.next;

Observera att det inte finns några specialfall! Det finns alltid en länk vars next vi kan skriva. Vi får heller inte glömma bort att uppdatera this.last i samband med detta.

Implementation av iteraton kräver tre metoder. När man anropar next() skall man få ut nästa element (med start med det första, förstås – vid första anropet), och vid nästa anrop nästa element, etc. Metoden hasNext() returnerar true om nästa anrop till next() är valitt (dvs. vi passerar inte utanför listan). Till sist remove som tar bort ett element ur listan.

Här är en fungerande implementation av iteratorn.

private class SetIterator implements Iterator<T> {
    Link current;
    Link prev = null;
    public SetIterator(Link first) {
        this.current = first;
    }
    public T next() {
        this.prev = this.current;
        this.current = this.current.next;
        return this.current.element;
    }
    public boolean hasNext() {
        return this.current.next != null;
    }
    public void remove() {
        this.prev.next = this.current.next;
        this.current = this.prev.next;
    }
}

Att skriva en equals()-metod kräver att man minns problemet med overriding kontra overloading. Det är enkelt att förledas att tro att man kan skriva en equals()-metod på detta sätt:

public boolean equals(LinkedSet<T> o) {
    for (T elem : this) {
        if (o.contains(elem) == false) return false;
    }
    return this.size() == o.size();
}

Detta är korrekt, förutom att signaturen på metoden gör att vi inte override:ar Object:s equals()-metod. Denna skall nämligen ha följande signatur:

public boolean equals(Object o)

Som vi tog upp två gånger på föreläsningarna kan man använda sig av en kombination av båda implementationerna:

public boolean equals(Object o) {
    if (o instanceof LinkedSet<T>
        return this.equals((LinkedSet<T>) o);
    } else {
        return false;
    }
}

Obs: på grund av Javas type erasure är lösningen ovan inte typsäkerKompilatorn varnar men du får godkänt på kodprovet! eftersom typomvandling inte kan kontrollera elementtyperna. Detta kan man t.ex. lösa genom att implementera en egen contains som opererar på Object etc., eller helt enkelt ändra den existerande på detta vis:

public boolean contains(Object elem) {
    for (Object e : this) {
        if (e.equals(elem)) return true;
    }
    return false;
}

En avancerad variant är att använda wildcards, som vi gick igenom på föreläsningarna (här i kombination med contains()-metoden ovan).

public boolean equals(Object o) {
    if (o instanceof LinkedSet<?>
        for (Object obj : (LinkedSet<?>) o) {
            if (this.contains(obj) == false) return false;
        }
        return ((LinkedSet<?>) o).size() == this.size;
    } else {
        return false;
    }
}

En anledning till varför signaturen på equals() kräver att inparameterns typ är Object och inte något mer specifikt är för att ekvivalens är definierat för alla typer, dvs. det skall gå – dynamiskt – att jämföra två helt olika saker, och få ett svar på skalan sant/falskt. Denna kod visar varför detta är vettigt:

public void someFunction(Object probablyALinkedSet) {
    LinkedSet<T> set = new LinkedSet<T>(42);
    if (set.equal(probablyALinkedSet)) {
        ...
    }
}

/// In other method
someFunction(new LinkedSet<T>(42));

I koden ovan har vi tappat bort det faktum att probablyALinkedSet är ett LinkedSet statiskt. Om vi inte hade definierat equals() som en metod vars inparameter hade typen Object hade vi inte tillåtits testa dessa två tomma mängder för likhet.

Denna metod tillhandahåller tjänsten att kunna få ut innehållet i mängden som en array. Detta borde vara straightline-kod att skriva för alla, inte minst med tanke på att liknande metoder delats ut i koden redan som gör samma typ av iteration:

public Object[] asArray() {
    Object[] result = new Object[this.size()];
    int index = 0;
    for (T e : this) {
        result[index++] = e;
    }
    return result;
}

Klassen Collection tillhandahåller metoden newEmptycollection() som skapar en ny instans av klassen Collection att användas i t.ex. copy(). Men om vi använder copy() för att kopiera ett LinkedSet fungerar det inte om inte newEmptycollection() override:as i LinkedSet för att returerna ett LinkedSet:

public LinkedSet<T> newEmptyCollection(int maxCapacity) {
    return new LinkedSet<T>(maxCapacity);
}

Det går också bra att behålla returtypen om vi har löst subtypningsuppgiften korrekt:

public Collection<T> newEmptyCollection(int maxCapacity) {
    return new LinkedSet<T>(maxCapacity);
}

Ett problem med detta kodprov har varit att många har haft svårt att få sin kod att kompilera. Om man inte begriper t.ex. subtypningen eller den parametriska polymorfismen, måste man kämpa hårt och göra många manuella förändringar för att få sin klass att fungera. Förmodligen har en bov i kompileringsdramat varit konstruktorerna där Javas kompilator ger ett ganska svårtytt felmeddelande. Vad felmeddelande försöker säga är i stort sett: "hej, det där anropet till superklassens konstruktor som vi normalt kompilerar in automagiskt kan inte stoppas in automatiskt eftersom det inte finns någon parameterlös defaultkonstuktorn."

Att inte ens kunna kompilera måste ha varit djupt demoraliserande, och det är jag ledsen för! Glädjande är att många, trots detta problem, lyckats få så många saker rätt. Det är särskilt imponerande eftersom det inte ens funnits kompilatorhjälp att få! Bra kämpat där!

I framtiden skall jag undvika att dela ut kod som inte fungerar, tror jag. Det begränsar visserligen de möjliga uppgifterna en smula, men jag tror att det ändå är bäst så.

Av 70 som skrev har 32 blivit godkända, 16 är nära att bli godkända (18 poäng) och har därför fått rest och 22 är underkända. Vi förväntar oss därmed att knappt 48 av 70 blir godkända (65-69%).