Göm menyn

TDDC30 Programmering i Java, datastrukturer och algoritmer

Laboration 2 - Stormarknaden

Uppgiften

Den här laborationen går ut på att lära sig mekanismerna för de grundläggande länkade datastrukturerna Lista, Stack, och Kö(en. Queue) och att få prova på att skapa en egen iterator. Dessa klasser ska göras som generiska klasser. Dessutom ingår exceptions och paket.

Scenariot är en simulering av en stormarknad med kunder som kommer och handlar varor och går till kassan. För att hålla reda på kunderna används en lista, för en kunds varukorg används en stack, och för kunderna i en kassa används en kö, så klart!

Er uppgift är att implementera ett paket som heter myutil som innehåller de generiska klasserna MyList, MyStack och MyQueue. MyList ska också kunna returnera en instans av MyListIterator som implementerar interfacet Iterator för listan (detta interface finns definierat i paketet java.util). Era klasser ska följa specifikationen nedan.

Implementationen ska göras med hjälp av en länkad struktur med noder, för att ni ska få öva på detta. Ni ska alltså inte använda existerande datastrukturklasserna i klassbiblioteket (som exempelvis LinkedList, vilket man annars normalt skulle göra), utan göra er helt egna implementation av en länkad lista.

Det finns ett stormarknadssimuleringsprogram som använder klasserna MyList, MyStack och MyQueue. När era klasser är implementerade korrekt ska detta gå att köra och fungera på ett rimligt sätt. Utöver detta program kan det vara bra att göra separata testprogram för era klasser för att säkerställa att de fungerar. Dessutom är det bra att kunna testa varje klass för sig innan alla andra klasser är klara. Detta är obligatoriskt för att testa att MyListIterator verkligen fungerar korrekt. Ett exempel på ett testprogram för MyStack finns tillgängligt. Testklasserna ska inte ligga i paketet myutil, utan i ett annat, fristående paket.

Definition av klasser som ska implementeras

De klasser ni ska implementera (förutom testprogram) ska ligga i ett paket som heter myutil. Lägg paketet i samma Eclipse-projekt som stormarknadsklasserna. Tänk igenom hur synligheten av klasser och variabler bör se ut när de ligger i ett paket. Bör alla klasser vara synliga utanför paketet tex?

De klasser ni ska implementera ska fungera som respektive abstrakt datatyp är beskriven i kursboken (Goodrich & Tamassia: "Data structures and Algorithms in Java"). Enbart de metoder som finns i klassbeskrivningarna nedan behöver implementeras. De metoder som avviker från boken har en kommentar kring detta.

MyStack

 
MyStack<E>
(Vart ska detta stå egentligen? Varför?)
Metoder
 public void push(E element)
 
 public E pop()
    Kastar exception
    
 public boolean empty()
     Motsvarar bokens isEmpty
     
 public int size()

MyQueue

MyQueue<E>
Metoder
 public void enqueue(E element)
 
 public E dequeue()
     Kastar exception
     
 public boolean empty()
     Motsvarar bokens isEmpty
     
 public int size()

MyList

Ska vara en "singly linked list" 
MyList<E> implements Iterable<E>
Metoder
 public void add(E element)
    Ska lägga till ett nytt element i listan 
    
 public E getRandomElement()
    Ska returnera ett slumpmässigt element utan att ta bort det ur listan
    Kastar exception
    
 public boolean empty()
    Motsvarar bokens isEmpty
    
 public int size()
 
 public Iterator<E> iterator()
    Returnerar en instans av MyListIterator för den aktuella listan

MyListIterator

(För detaljer om hur de här funktionerna ska fungera, se specifikationen av interfacet i Javas API, länkat nedan:) 
MyListIterator<E> implements Iterator<E>
Metoder
 public boolean hasNext()
 
 public E next()
    Kastar exception
  
 public void remove()
    Kastar exception

E ovan är den generiska typen för datat som ska lagras i strukturerna.

I en del metoder kan det uppstå fel som ska leda till att ett Exception (undantag) kastas. Vilka metoder detta gäller ses ovan. Ett exempel är metoden pop(), vilken ska ge ett exception om den körs på en tom stack. De exceptions ni kastar kan antingen vara befintliga exceptionklasser, eller egna klasser. Exceptionklassen ska dock vara rimlig, det vill säga beskriva felet som uppstår på något sätt. Om ni gör någon egen exceptionklass ska den ärva från lämplig befintlig exceptionklass. Oavsett om ni ärver eller gör egna klasser måste era exceptionklasser vara av typen RuntimeException för att det ska fungera med kodskelettet. Använd gärna Javas API för att hitta lämpliga klasser. Tips: börja med att hitta RuntimeException och se i JavaDoc'en vilka klasser det finns som ärver av den.

Utöver detta kommer det att behövas en nodklass, konstruktorer för klasserna, och antagligen en del privata hjälpfunktioner.

Given kod

Testprogrammet finns här. Spara koden i filerna Supermarket.java, Customer.java och Checkout.java, i default package.

Skumma igenom den givna koden lite kort, och notera t.ex. hur det finns en delay i SuperMarket som justerar hur fort programmet kör, och hur slumpens används för att göra varje körning annorlunda från den föregående. Starta sedan simuleringen med klassen Supermarket där main-metoden finns.

Tips

Som ni märker påminner den här labben till viss del om listlabben i Adakursen (TDDD11). Uppbyggnaden av MyList kommer att vara i princip densamma som där, så om ni har glömt bort hur ni gjorde där gå gärna tillbaka och friska upp minnet! Adalabben var mer omfattande, och innehöll fler funktioner än den här, men själva uppbyggnaden av en nodstruktur är densamma. Ett par saker att tänka på:

  • I Ada användes pekare för nästa nod, i Java behövs inte det eftersom alla variabler (som är klasser) är referenser.
  • I Adalabben hade ni ingen listklass, utan fristående funktioner. Nu ska ni ha en listklass som innehåller 'pekaren' till det första elementet i listan och alla metoder som hör till listklassen.

Examination

Bifoga följande i ett mail till er labassistent:

  • Hela Eclipse-projektet samt källkoden enligt de generella instruktionerna. Alla klasser och publika metoder ska vara kommenterade med javadoc-kommenterar. Koden ska följa kodstandarden och vara enhetligt indenterad.
  • En kort redogörelse av följande frågor (cirka en halv A4-sida):
    • Vad är fördelarna med en iterator? (Jämfört med att direkt operera på noderna i listans datastruktur.)
    • Beskriv kortfattat hur er iterator fungerar. Hur är den implementerad internt? Vilka instansvariabler har den, och hur påverkas dessa av de olika metodanropen? Tycker ni att er implementation är bra?
  • En separat sida där ni anger ungefär hur mycket tid ni har använt för uppgiften (för er grupp), och några kortfattade reflektioner kring uppgiften. Det kan t.ex vara synpunkter på uppgiften och feedback till lärarna, vad som känns oklart, begrepp som är svåra, osv. (bedöms ej)

Checklista för inlämnat material:

  • Är alla delar inlämnade?
  • Följer koden kodkonventionerna(se "Kursmaterial")? Avvikelser ger rest.
  • Är koden enhetligt indenterad? Slarvig indentering ger omedelbart rest.
  • Är koden kommenterad enligt kodkonventionen?
  • Används en rimlig åtkomstnivå för klasser, variabler och metoder?
  • Uppfyller programmet kravspecifikationen?
  • Ligger era klasser i ett paket som heter myutil?
  • Är paketet välstrukturerat?
  • Är datastrukturerna implementerade med hjälp av en egen nod-klass?
  • Testar testprogrammet för MyListIterator att alla metoder för iteratorn fungerar korrekt?
  • Visar diskussionen på en god förståelse?

Skapad för kursen HKGBB7
Modifierad av Sara Stymne 2005, 2006, Johan Janzén 2011,2012, Jonas Lindgren 2013.

Sidansvarig: Jonas Lindgren
Senast uppdaterad: 2013-01-27