Kodproven

Tips: fundera på hur Sentinel skall fungera när listan är tom.

Skriv också klart create() i klassen LinkFactory (som finns i kodfilen Sentinel.java) så att listor skapas korrekt. Du kan titta på hur create() används i List. (Vi har lagt skapandet av Sentinel-objekt här för att du bara skall behöva skriva kod i en enda fil.)

Kompilera allt med make. Testa din lösning med make test.

Observera att testerna i makefilen är till för att hjälpa dig att hitta fel i din kod och att programmet passerar testerna inte nödvändigtvis betyder att programmet är korrekt eller att du är godkänd.

Lösningsförslag

Vi arbetade hårt med att göra uppgiften tydlig så att det inte främst förmågan att läsa instruktioner prövades. Jag har fått kommentarer att den var för enkel, allt den var för svår, att den var omöjlig att förstå. På förmiddagsprovet hade uppgift 2 rubriken "Replace Conditionals with Polymorphism". Den rubriken tog vi bort till eftermiddagen då vi (Tobias och Elias) i efterhand tänkte att den rubriken var vilseledande eventuellt till att tänka bara på polymorfismen och inte allt det andra.

Uppgiften prövar ett antal saker. Man måste förstå subklassning och overriding av metoder och konstruktorer, man måste förstå polymorfism och dynamisk bindning, man måste kunna läsa den utdelade Javakoden. Vill man kunna testa en endast delvist löst uppgift måste man förstå t.ex. att kommentera ut saker i den utdelade koden, eller hur man skriver egna små tester, etc.

Vi valde att ge ett tips om att rita istället för att ge ut något i stil med denna bild:

    Lista av längden 0:
    List --> Sentinel

    Lista av längden två:
    List --> Link --> Link --> Sentinel
  

Utifrån några vanliga fel kunde vi ha varit ännu mer tydliga och ritat ut denna:

    Lista av längden 0:
    List --> Sentinel
               |
               |
               V
               null

    lista av längden två:
    List --> Link --> Link --> Sentinel
               |        |        |
               |        |        |
               V        V        V
               elem     elem     null
  

För att sentinel-objektet skall komma sist i listan måste LinkFactory.create() returnera en Sentinel. Efftersom returtypen är Link måste Sentinel ärva av Link. Orden subklass och arv förekommer inte i texten, utan det var meningen att detta skulle listas ut.

Så här skulle alltså create() se ut:

class LinkFactory {
    public static <T> Link<T> create() {
        return new Sentinel<T>();
    }
}

Det går även bra att ändra returtypen till Sentinel<T>.

Lösning på prov 1

public class Sentinel<T> extends Link<T> {
    public Sentinel() {
        super(null, null);
    }

    boolean contains(T element) {
        return false;
    }

    int size() {
        return 0;
    }

    Link<T> append(T element) {
        return new Link<T>(element, this);
    }
}

Lösning på prov 2

public class Sentinel<T> extends Link<T> {
    public Sentinel() {
        super(null, null);
    }

    int occurrences(T element) {
        return 0;
    }

    int size() {
        return 0;
    }

    Link<T> remove(T element) {
        return this;
    }
}

I något enstaka fall har jag sett koden för append() i remove() vilket skulle kunna göra mig misstänksam, iallafall om lösningen i övrigt är "perfekt".

Vanliga fel

Sentinel äver inte av Link

Flera har inte etablerat en arvsrelation mellan Sentinel och Link. Detta medför att create() inte kompilerar och att programmet inte går att testa, oavsett om koden i Sentinel är rätt i övrigt.

I något enstaka fall har en arvsrelation mellan Sentinel<T> och Link etablerats. Likaså mellan Sentinel och Link<T>. Det senare kompilerar inte. Det förra etablerar inte rätt subtypsrelation mellan Sentinel<T> och Link<T>!

Stafvel ==> ingen overriding

Ett stort antal har stavat fel till occurrences() på eftermiddagsprovet. Detta har lett till att programmet kraschar med ett NullPointerException i Link.occurrences(). Första provet jag rättade som gjorde detta fel gav mig några minuters huvudbry innan jag såg varför lösningen inte fungerade.

Detta hade kunnat avhjälpas med hjälp av skriva @Override-annoteringar på alla metoder som skulle göra override. En kompilator/IDE som prövar detta skulle då ha fångat stavfelet.

Missa att anropa superklassens konstruktor

Detta verkar ha varit ett väldigt vanligt fall, men det är svårt att avgöra hur vanligt eftersom jag bara har en version av koden. Klassen Link har en konstruktor som tar två argument, och om man subklassar Link i Sentinel måste den senares konstruktor anropa superklassens konstruktor (som vanligt). Detta är alltid fallet i Java, men om det finns en konstruktor som inte tar några argument, så stoppas det anropet in automagiskt.

Det vill säga, om Link hade sett ut så här:

public class Link<T> {
    public Link() {
        this(null, null);
    }

    public Link(T element, Link next) {
        this.value = element;
        this.next = next;
    }

    ...
}

Hade man inte behövt ha en konstruktor alls i Sentinel! Det måste man nu, och här är min lösning:

public class Sentinel<T> extends Link<T> {
    public Sentinel() {
        super(null, null);
    }
    ...
}

Nu till det som verkar ha varit kodprovets största miss, nämligen Javakompilatorns felmeddelande när man glömmer superanropet:

Sentinel.java:7: error: constructor Link in class Link cannot be applied to given types;
public class Sentinel extends Link {
       ^
  required: T#1,Link
  found: no arguments
  reason: actual and formal argument lists differ in length
  where T#1,T#2 are type-variables:
    T#1 extends Object declared in class Sentinel
    T#2 extends Object declared in class Link
Note: List.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

Detta felmeddelande är inte särskilt lättläst så det är inte enkelt att se att det är konstruktorerna som det är fel på... Illa! Om man kompilerar med -Xlint som föreslås ovan får man exakt samma meddelande en gång till. Hjälpsamt! (Alltså inte.)

Med facit i hand borde jag ha skrivit ett tips om detta i kodprovet, men eftersom det här felet inte uppkom när kodprovet provades ut så var det ingenting som jag tänkte på. Det är extremt synd om någon skulle ha kastat in handsken på grund av detta! Om det är någon tröst så tar jag det med mig till framtida kodprov.

Jag har fått ett par kommentarer i den inlämnade koden om just detta problem av typen "Det här problemet kan jag inte lösa utan Google!". Å ena sidan kan jag tycka att man skall kunna göra det, men å andra sidan kanske inte under en kodprovssituation.

En massa tomma fält i Sentinel, trots arv...

Flera har, trots att Sentinel ärver av Link, deklarerat attribut Link next och T element i Sentinel. Dessa har med något undantag antingen inte använts, och/eller alltid innehållit null.

Jag har svårt att förstå varför man skulle skriva sådan kod. Jag skulle kunna tänka mig att man gör detta för att bli av med ovan nämnda svårtolkade kompileringsfel, men det är en vild gissning. Om inte speglar det nog att man hade svårt att förstå uppgiften, eller vad en sentinel var.

Det förekommer också många konstruktorer som tar två argument som skickas vidare till superklassens konstruktor men som alltid är null.

Observera att detta är ingenting som man får fel för på kodprovet, men jag har försökt att anmärka på alla lösningar som gör detta.

Sentinel-objektet försvinner vid append/remove

En lösning av remove() som gör return null; eller en lösning av append() som gör return new Link(element, null) tappar sentinel-objektet ur listan. Detta leder inte omedelbart till en krasch, men om man t.ex. gör remove() följt av size() så får man ett NullPointerException när man kommer till slutet av listan.

Hur jag har rättat Java-delen

Två saker har påverkat rättningen av Java-delen av kodprovet denna gång:

1. Uppgiften var uppenbarligen svår, framförallt med avseende på super-anropet, där Javakompilatorn är närmast fientlig.
2. En av ThinLink-servrarna gick ned under eftermiddagens kodprov och skapade strul för många. Det är inte optimala förhållanden för att skriva ett kodprov.

Jag har tagit båda dessa saker under beaktande i min rättning, och det leder till en stor mängd rester (50% blev godkända, 25% rest). Jag föredrar att inte se det som att "jag har varit snäll", utan snarare som kodprovet består av tre delar: Tobias gör provet, studenter skriver provet, Tobias rättar provet; och alla dessa tre delar måste funka tillsammans. Syftet med kodprovet, som jag har sagt 1000 gånger under kursen, är att se till att någon som normalt bara skulle sitta brevid och se på när någon annan kodar faktiskt sätter sig ned och kodar själv. All betygssättning sker ju via redovisningar av mål.

Som jag skrev ovan är det många saker som uppgiften prövar: subklassning, subtypning, overriding, konstruktorer, att kunna läsa den utdelade Java-koden så att man t.ex. förstår hur occurrences() eller size() skall implementeras. Om koden visar att man har förstått lejonparten av detta har man fått rest, oavsett om koden kompilerar eller ej.

En student har gjort en lösning med hjälp av interface som visar på förståelse för det grundläggande problemet. Trots att lösningen inte är komplett har denna student också fått rest, med villkor att lösningen vid resttillfället fortsätter med interfacelösningen.

När jag rättar har jag ingen aning om vems prov jag rättar (det får ni ta mitt ord på, eller inte). Det gör att jag varken kan eller vill tolka någon lösning utifrån min kännedom om den som skrivit den (jag vet ju att X kan detta..., etc.). Det betyder att vissa rester mest blir en formsak, men det skall vara lika för alla. Alla ni som har mailat mig rätt lösning senare under dagen -- tack! Tyvärr måste ni fortfarande komma och göra resten eller skriva om kodprovet, beroende på hur det gick.

Med något enstaka undantag har endast körande felfria lösningar blivit godkända. Det betyder att följande lösning har givit rest, trots att den är super(null,null) från att bli godkänd. Vid resten så vill jag veta varför man måste anropa superklassens konstruktor och vad tanken är bakom detta, etc.

public class Sentinel<T> extends Link<T> {
    public Sentinel() {
        ///
    }

    int occurrences(T element) {
        return 0;
    }

    int size() {
        return 0;
    }

    Link<T> remove(T element) {
        return this;
    }
}

På samma sätt har följande lösning, som inte passerar testerna lett till rest. I nedanstående fall vill jag bl.a. veta vid resttillfället att man förstår varför detta inte fungerar, och hur programmet beter sig under körning.

public class Sentinel<T> extends Link<T> {
    public Sentinel() {
      super(null, null);
    }

    int occurences(T element) { // Stavfel
        return 0;
    }

    int size() {
        return 0;
    }

    Link<T> remove(T element) {
        return this;
    }
}

Om du vill diskutera detta finns det en bra tråd i Piazza här, eller skicka mig ett mail eller fånga mig AFK på Pollax.