IDA - Institutionen för datavetenskap

Laboration 4a

Denna laboration är uppdelad i två delar - del A och del B. Innan ni börjar med del B så ska ni redovisa del A för en assistent för att säkerställa att er lösning innehåller allt den behöver.

Vad är abstrakta datatyper?

Hittills har ni arbetat med väldigt vanligt förekommande datatyper som strängar och tal men det är inte alltid tal och strängar räcker för att beskriva ett problem på ett bra sätt. Abstrakta datatyper (ADT) är ett sätt att beskriva sådan data som annars inte kan beskrivas med de datatyper som redan finns i språket. Man kan tänka sig att en ADT använder de datatyper och behållare vi redan känner till för att "föreställa" någonting annat, något som gör att vi kan modellera verkliga ting i våra program. I denna laboration kommer vi att skapa en ADT som representerar en kortlek med helt vanliga spelkort.

Ett spelkort har till exempel två attribut som krävs för att representera kortet (färg/suit och valör/value). När man hanterar ett sådant spelkort kan man låta en sammansatt datatyp såsom lista, dictionary eller en tupel representera kortet.

Vanligen använder man en abstrakt datatyp genom funktioner som används för att skapa, modifiera, extrahera data ur och visa datatypen. Finns dessa fyra funktioner är det möjligt att arbeta med er datatyp och utöka den allt eftersom ert program kräver det. Det är också bra att ha funktioner som kan verifiera att datan i er nya datatyp är korrekt, men det är inget krav för att kunna arbeta med datatypen.

Den kortleks-ADT som ni skapar i del A av denna laboration kommer ni sedan att använda i del B för att implementera en enklare krypteringsalgoritm, och kommer att kräva ett antal funktioner som kan verka på er ADT. Ni kan tänka på det som att ni fyller rollen av två olika programmerare. Dels har ni ADT-programmeraren i del A, som skapar en ADT som representerar en kortlek, samt funktioner som man kan använda med kortleken (t.ex. blanda kortleken, titta på ett kort, dra ett kort, sätta tillbaka ett kort, m.m.). Sedan kommer denna ADT att användas av problemlösnings-programmeraren i del B för att implementera en algoritm.

När ni i del B agerar som problemlösare så tar ni hjälp av ADT-funktionerna för er kortlek från del A för att lösa uppgifter. I denna roll får du aldrig (och ska inte behöva) veta exakt hur den abstrakta datatypen för kortleken är implementerad "bakom kulisserna". Föreställ dig att den enda information du har i denna roll är en lista av ADT-funktioner du kan använda, samt vad dessa returnerar och tar in för argument. För lite överkurs kan ni titta på PEP257, ett styrdokument som beskriver hur funktionskommentarer implementeras i Python, och på så vis kan ge information från ADT-programmeraren till problemlösaren.

Den viktiga insikten i denna laboration är dels hur en ADT kan modelleras på ett enkelt sätt, men även hur ni kan använda en redan definierad ADT som någon annan skapat.

Del A

Till att börja med kommer ni först att skapa en ADT som representerar en kortlek, samt skapa ett antal funktioner som beskrivs i detalj nedan. Dessa funktioner ska vara allmänna, ni ska inte skapa funktioner som är specifika för hur algoritmen senare ska implementeras. Var försiktiga så att ni inte hakar upp er allt för mycket på att skapa funktioner som "löser för mycket" av algoritmens steg. Tänk att man ska lika gärna kunna använda er ADT för att implementera ett enklare kortspel som exempelvis poker med samma ADT, så era funktioner bör vara generella nog för annat bruk. Dessutom så är det viktigt att ni, genom implementationen av era funktioner "döljer" hur ni implementerar hela leken med kort samt individuella kort.

En kortlek består normalt sett av 52 spelkort och två jokrar. För enkelhets skull kommer ni bara att använda er av en halv kortlek (två färger, tänk hjärter och spader) och två stycken jokrar. Varje kort i kortleken tilldelas ett värde, från 1 (för ess) till 13 (för kung) för vardera färg. De två jokrar som leken ska innehålla har ingen färg, men ni bör kunna särskilja mellan jokrarna, t.ex. genom att kalla dem joker A och B. Observera att ni senare ska hantera kortleken som om den bestod av kort, så ni får INTE representera ett kort med enbart ett tal.

För del B kommer ni att behöva implementera ett antal funktioner för er kortlek. Dessa funktioner ni kommer att behöva implementera är:

• En funktion som skapar och returnerar en kortlek med 26 kort och två jokrar.
• En funktion som returnerar hur många kort det finns i er kortlek.
• En funktion som tar emot en kortlek, och blandar den.
• En funktion som tar emot en kortlek och returnerar en identisk kopia (inklusive ordningen de är blandade i).
• En funktion som tar emot ett kort returnerar vilken färg och vilken valör ett det har (t.ex. hjärter ess, spader 5, spader kung).
• En funktion som returnerar vilket kort som ligger på en specifik plats i leken.
• En funktion som returnerar vilken plats i kortleken ett specifikt kort ligger på.
• En funktion som tar bort ett kort från en specifik plats i leken och returnerar kortet som tagits bort.
• En funktion som tar emot ett kort, en kortlek och ett index, och lägger in kortet på detta index (med andra ord, inversen av funktionen som tar bort ett kort).
• En funktion som delar kortleken i två delar, där första delen är från första kortet till och med den plats i kortleken som anges, och andra delen är resten av korten. Säg att vi skickar in plats 10 till funktionen, och att kortleken representeras av en lista. Då får vi tillbaka korten från index 0 till och med index 10 i en del, och korten på index 11 till slutet av kortleken i den andra. Skickar vi t.ex. in sista indexet (27) ska första delen innehålla alla kort, och andra delen vara helt tom.
• En funktion som tar emot två stycken kortlekar från funktionen innan och sätter ihop dem till en kortlek igen, och returnerar den sammanfogade kortleken.

Om ni känner att ni behöver fler funktioner för att lösa uppgiften är det självklart okej att lägga till dessa, men det är viktigt att ni tänker på att dessa ska vara generella. Den som använder er ADT inte ska behöva veta om vad det är för datatyper som kortleken byggs upp av för att använda er ADT, och det är viktigt att era funktioner inte "tar över" en del av algoritmen. Det finns lite mer information under När blir en ADT-funktion för specifik? och ni uppmanas att diskutera hur ni tänker med en assistent om ni vill lägga till fler funktioner.

Krav Innan du Fortsätter

Utöver att din kod fungerar enligt beskrivningarna ovan så behöver den uppfylla kraven nedan.

• Din kod skall följa principerna för god inkapsling av dina abstrakta datatyper. Detta innebär att dina abstrakta datatyper har alla funktioner som krävs för att hantera datan. Detta innebär också att dessa funktioner är det ENDA sättet som ni interagerar och behöver interagera med datan.
• Dina funktioner skall ha tydliga namn och skall lösa det delproblem som namnet indikerar
• Ni behöver förstå hur inkapslingen i ert program fungerar och varför den är viktig.
• Klasser är något som ligger utanför målen för denna kurs. Lösningen på detta problem ska inte innehålla någon klass (vet du inte vad en klass är för tillfället är det helt okej). Dessa erbjuder vissa features och säkerhet som det är meningen att ni skall lösa uppgiften utan. Klasser kommer ni arbeta med i TDP004.

När ni är klara med del A ska ni redovisa den för en assistent innan ni går vidare till del B.