DD1346 Labb 6

Labb 6, Fler Designmönster

Målet med denna labb är att introducera fler designmönster, och få en känsla för dessa genom att tillämpa dem på några enklare programexempel.

För godkänt till betyg A på denna labb krävs att samtliga uppgifter skall vara utförda, samt att båda i labbgruppen kan svara på samtliga frågor.

A1. Composite

Rekommenderad läsning: Composite Pattern Iterator Pattern, Iterable, Iterator och The for Statement, Prototype, Prototype, Prototype.

Idén med mönstret Composite är att grupper av objekt ordnade hierarkiskt i en trädstruktur ska kunna behandlas på samma sätt som enstaka objekt. En operation på det sammansatta objektet ska utföras på objektets alla delar.

Ett sammansatt objekt (composite object) innehåller andra objekt som själva kan vara sammansatta eller enstaka. Ett typiskt exempel på Composite är en filkatalog där en katalog kan innehålla både filer och andra kataloger, som i sin tur kan innehålla både filer och andra kataloger o.s.v. i många nivåer. Filerna är löv i trädet. Ett annat exempel är en bild som byggs upp av grafiska primitiver (linjestycken, ovaler, rektanglar m.m) och sammansättningar av grafiska primitiver där en sammansättnng kan innehålla både andra sammansättningar och primitiva objekt.

I den här uppgiften skall vi implementera Composite som en resväska. Vi kan tänka oss att tröjor och byxor läggs direkt i resväskan, medan hårspännen och gummisnoddar stoppas i små askar eller påsar som kanske i sin tur läggs i en necessär eller större påse som läggs bredvid större plagg i väskan. Strumpor läggs i en påse som läggs i väskan.

Uppgift A1.1 Implementera de klasser som behövs för en resväska enligt mönstret Composite. Den klass som kallas Component i mönstrets vanliga beskrivning är en abstrakt klass från vilken klasserna för de enskilda prylarna och klassen eller klasserna för sammansättningarna ärver. Minst tre olika nivåer av sammansättningar ska kunna användas. T.ex. att hårspännen ligger i en påse som ligger i en necessär tillsammans med tvål och schampo och att necessären ligger i resväskan bredvid större klädesplagg. Uppgift A1.2 Ge klasserna ovan en toString()-metod som ska skriva ut en text som benämner föremålet, t.ex "en påse". Om föremålet är en behållare ska det anropa toString()-metoden i alla prylar som den innehåller, så att ett anrop av toString() skriver ut namnet på föremålet och allt som det innehåller. Ett anrop av resväskans toString()-metod skall skriva ut en lista på allt som finns i den, såväl behållare som prylar. Formatera utskriften så att den blir naturligt språk, t.ex "en påse, som innehåller en penna, en kamera och en ask som innehåller en sten".
Uppgift A1.3 Ge varje klass ovan en getWeight()-metod som returnerar föremålets vikt. En behållare har en vikt som består av dess egenvikt plus summan av vikten av alla föremål den innehåller.
Uppgift A1.4 Skriv ett körbart ramprogram som skapar en resväska fylld med minst 10 olika saker på minst 3 olika nivåer, och som skriver ut en lista på alla föremål samt deras sammanlagda vikt med hjälp av metoderna ovan. Mönstrets struktur ser till att hela innehållet gås igenom då en metod anropas för något objekt i strukturen.
Fråga A1.5 Måste behållare och icke-behållare vara av olika klasser? Varför?
Fråga A1.6 När man skriver ut listan ovan, blir listningen av typen bredden först eller djupet först?

Syftet med mönstret Iterator är att iterera eller "gå igenom" alla element ur en sammansatt struktur utan att man behöver befatta sig med den underliggande strukturen. Att använda en iterator på en lista är naturligt och implementationen av en listiterator är ofta enkel.

Även för mer komplicerade strukturer har man god nytta av iteratorer. Composite-sammansättningar och andra trädstrukturer kan mycket väl förses med iteratorer. Iteratorn "levererar" elementen i sekvens utan att man behöver veta hur strukturen är uppbyggd. "Man" är här den som använder iteratorn. Den som programmerar iteratorn måste förstås känna till strukturen.

Uppgift A1.7 Utöka er komponentklass så att den implementerar gränssnittet Iterable, och skapa två iteratorklasser som den kan returnera. En Iteratorklass skall gå igenom objekten i bredden-först-ordning, och den andra i djupet först-ordning. Iteratorklassen måste givetvis implementera Iterator-gränssnittet.
Visa att er Composite-struktur numera medgör åtkomst med en for each-loop (även känt som enhanced for statement).

Med mönstret Prototype skapar man först ett objekt som man kan ändra och justera till man är nöjd, och sedan skapar man nya objekt genom att kopiera prototypen. Vid behov kan man ytterligare modifiera sin prototyp när man vill skapa objekt med andra inställningar eller innehåll. När man klonar ett sammansatt objekt, likt er Composite, är det viktigt att man även gör kopior av innehållet, så att två olika resväskor inte innehåller samma necessär, t.ex.

Uppgift A1.8 Implementera Prototype-mönstret för er resväskeklass. Visa att nya resväskor som skapats är helt oberoende av prototypen och av varandra.

A2. Factory

Det finns flera designmönster som innehåller ordet Factory. Gemensamt för dem är att man inte skapar objekt på det vanliga sättet med new utan genom ett metodanrop. Metoderna ses som "fabriker" där objekt skapas och vanliga namn på metoderna är getInstance() eller create(). Typen för det skapade objektet bestäms i metoden utom räckhåll för klienten (användaren). Inuti metoderna används förstås new, men klienten har inte direkt tillgång till new. Vanliga skäl för den här tekniken är att användaren ska slippa bry sig om objektets typ eller att det säkrare blir rätt typ om metoden väljer och inte användaren eller att klassen själv skall ha full kontroll över vilka objekt som skapas.

I denna uppgift ska ni skapa en Human factory. Ni kan med fördel återanvända en del kod från lab 1, men det kommer att krävas en del mindre omskrivningar. Vi låter klassen Human vara en abstrakt klass, med två konkreta underklasser Fysiker och Datalog. De två konkreta klasserna har samma egenskaper som klassen Fysiker i lab 1, med undantaget att klassen Datalog skriver ut en annan text vid anrop av toString(), t.ex enligt mönstret "Anna, ålder 25 år, började data 2007".

Uppgift A2.1 Ge klassen Human en metod som heter Create och som levererar antingen ett objekt av klassen Fysiker eller Datalog beroende på parametrarna. Definiera Create enligt följande:

public static Human create(String name, String year, int age){ // skriv kod här }

Strängen year skall vara av typen "D04" eller "F09", och bokstaven skall alltså avgöra vilken typ av objekt som skapas.
Uppgift A2.2 Skriv ett testprogram som skapar objekt av Fysiker och Datalog med hjälp av metoden ovan. Se till att det inte går att skapa objekt av Fysiker och Datalog på annat sätt än genom metoden ovan. Det ska alltså inte gå att kompilera new Fysiker(...) eller new Datalog(...) i testprogrammet. Det får inte heller gå att instansiera objekt som ärver från Human eller dess subklasser, t.ex genom att skapa en anonym subklass till Human. När ni redovisar skall ni både visa att det fungerar att gära rätt (dvs att använda create) och att det inte fungerar om man försöker göra fel (t.ex anropa new direkt). Se också till att testprogrammet på något sätt bekräftar att objekt av rätt typ skapats, t.ex. genom anrop av toString() som skriver ut information om objekten.

A3. Builder

På ordinarie tenta våren 2012 ställdes en fråga om hur man kan hantera synbart motstridiga krav för effektiv instoppning och effektiv utplockning av element i en större datastruktur. Ett sätt att lösa detta är genom att använda mönstret Builder.
I den här labben ska ni skapa klassen BuilderList, som implementerar gränssnittet List, och som tillåter instoppning av element i listan med metoden add(int index, E e), samt utplockning av element från godtycklig position med metoden get(int index).
Som riktlinje borde er BuilderList vara jämförbar med en LinkedList vad gäller instoppningsprestanda, och med en ArrayList vad gäller utplockning av element, specifikt när man använder den enligt mönstret som beskrivs nedan.

Uppgift A3.1 Skriv klassen BuilderList, som använder sig av mönstret Builder.

Testscenariot som vi tänker oss är följande (skrivet i pseudokod):

start stopwatch

`For`	`i := 0 to N`
	`myList.add(a(), XX)`
`end`

`For`	`i := 0 to N`
	`myList.get(b())`
`end`

stop stopwatch

Här antas a() vara en lämplig (t.ex slumpmässig) funktion som väljer ett index. XX är ett element som ska lagras, t.ex en siffra. b() är en funktion som returnerar ett slumpmässigt tal mellan 0 och N. myList är ett listobjekt, av någon av typerna ArrayList, LinkedList eller BuilderList.

Uppgift A3.2 Skriv ett testprogram som demonstrerar er BuilderList enligt pseudokoden ovan, och visa dess prestanda i jämförelse med LinkedList och ArrayList. Visa ett scenario där er klass är minst 1000 gånger snabbare för att köra pseudokoden ovan (dvs en körning innehåller först N st insättningar och sedan N st utplockningar) än att använda endera av de två andra List-typerna. De enda metoder som bör anropas i någon lista är add och get. För vilka typer av a()-metoder får ni störst förbättring?

Sidansvarig: Christian Smith <ccs@kth.se>
Uppdaterad 2011-05-20