Lab 2: Aktiehandel

En användare kan göra tre saker: köpa, sälja, samt ändra ett redan lagt bud. Exempelvis skriver vi

om Ada vill köpa aktien för 70 kr. På motsvarande sätt skriver vi

om Bengt vill sälja aktien för 71 kr,

om Bengt ändrar sitt säljbud från 71 till 70 kr (NS = ny säljkurs), och

om Ada ändrar sitt köpbud från 70 till 72 kr (NK = ny köpkurs).

Ni får anta att indata är sådant att varje person har som mest ett enda bud i prioritetskön.

I det fall att ett bud accepteras ska ert program registrera köpet på kommandoraden. I ovanstående fall ändrade Bengt sitt säljbud till 70 kr vilket matchar Adas köpbud. Då ska programmet skriva:

Efter det att ditt program skrivit ut alla genomförda köp, ska det till slut skriva ut orderboken. Säljare och köpare ska listas i prioritetsordning enligt följande exempel:

I en binär heap har båda operationerna insättning och borttagning av högst prioriterat element värstafallskomplexiteten O(log n) (där n är köns storlek, jämförelser tar O(1) tid, och arrayen inte ändrar storlek). Att ändra en prioritet tar O(n) eftersom man i värsta fall måste söka genom hela heapen efter det element vars prioritet ska ändras.

Ni ska dock åstadkomma O(log n) även för ändringsoperationen genom att använda en uppdaterbar heap. I en uppdaterbar heap har men en hjälpdatastruktur som håller reda på var i heapen ett visst element är lagrat. Ni ska använda en hashtabell som lagrar elementens positioner i heapen. På det sättet kan man hitta ett givet element i heapen med komplexiteten O(1) (om man har en perfekt O(1) hashfunktion).

Ert huvudprogram ska heta Lab2.java. Det har en parameter Budlista som är en fil med en lista av bud enligt ovanstående format med ett bud per rad:

När ni skriver java Lab2 Budlista ska ert program skriva ut en lista av avslut följt av aktuell orderbok enligt följande format:

Det ska också gå att skriva:

Filens innehåll finns då i System.in.

Det finns ett flertal flaggor som kan användas. För att se dem, kör:

Ni kan t.ex hoppa över tidiga testfall med

Det går också att köra:

för parallell testning. Detta testar eventuellt snabbare genom att köra flera testfall parallellt. Detta använder metoden pureMain(String[]) som tar en array med alla kommandon och returnerar en sträng med all utdata istället för att skriva till System.out. Användning av System.out/System.err bör i detta undvikas helt eftersom det då blandas mellan olika test och kan vara missvisande.

Detta är ert huvudprogram som det har beskrivits ovan. Utgå ifrån Lab2.java. Förstå ungefär vad den existerande koden gör (och vad de bitar som saknar ska göra) innan ni fortsätter. Ni kan vänta med att fylla i de bitar som saknas tills ni har börjat på er prioritetskö. Ni får ändra på den existerande koden hur mycket ni vill.

Denna klass beskriver ett bud. Ni kan utgå ifrån Bid.java.

Se till så att inga instanser av klassen går att ändra (alla instansvariabler ska vara "final"). t.ex strängar går inte att ändra. se boken sidan 61. Implementera inte Comparable, använd separata komparatorer istället för att jämföra bud. Se nedan.

Dessa är till för att beskriva prioriteten av elementen i era två prioritetsköer. Ni behöver en för säljare och en för köpare.

compare är vanligtvis kompatibel (se compare) med equals, alltså att compare ger 0 om och endast om equals ger true.

Ni måste använda en ArrayList med generiska element. Använd alltså inte en array. Konstruktorerna måste ta en komparator som parameter. Komparatorn använder ni för att bestämma prioritetsordningen av elementen i heapen.

Ni bör läst igenom kapitel 21.2 innan ni implementerar er prioritetskö. Ni kan också läsa om heapar på wikipedia. Utgå gärna från koden i kursboken på sidan 812-818. Ni behöver inte skriva av koden, utan hittar den på Companion Website, men kom ihåg att ändra paketnamn, klassnamn, författare, osv..

Ni måste inte implementera något specifikt gränssnitt, men ni måste på valfritt sätt minst implementera:

…eftersom detta behövs i ert huvudprogram.

För att implementera en oeffektiv uppdatering så söker ni igenom hela heapen efter det element (använd equals eller comparatorn) vars prioritet ska ändras. Välj vad ni vill göra då ni inte hittar det. Om ni hittar det, så byt ut elementet mot det nya och jämför sedan med parent/left/right för att återställa heapegenskapen. Skapa 2 hjälpmetoder (t.ex percolateDown och percolateUp) som flyttar ett element neråt (eller uppåt) tills elementet är på en lämplig plats. percolateDown finns redan om ni utgår från koden i boken. Använd sedan dessa två metoder i koden för insättning, borttagning, och uppdatering.

En bra idé är att beskriva den klassinvariant som måste uppfyllas och testa att den håller i början och slutet av varje anrop till publika metoder (vilket är exakt då den måste hålla). Använd assertions för att testa klassinvarianten. För att assertions ska testas när ni kör er kod så måste ni ange flaggan -ea, annars testas de inte.

Exempel på hur ni kan testa er invariant:

invariantCheck beskriver den invariant som ni har för er prioritetskö.

I koden ovan kommer showHeap att anropas när invarianten inte håller. Ni bör implementera denna metod så att den visar hur er heap ser ut. Detta gör att ni kan lättare komma på vad som gick fel.

Skriv en fil med indata till ert program och se om det verkar fungera. Använd sedan testprogrammet för att se om ert program fungerar. Om testprogrammet ger indata som ert program ger fel utdata för, ger ett oväntat exception, eller då er klassinvariant inte håller, så måste ni analysera vad som gått fel.

Ni kan göra utskrifter för debugging var som helst i er kod, men använd då System.err (inte System.out). Testprogrammet skriver ut allt efter varje test. Hittar ni inte lätt ett fel som testprogrammet ger så spara den indata som testprogrammet antav i en fil och kör ert program själva med filen som argument. Använder ni eclipse så kan ni ange filens namn som argument, och använda debuggern som finns i eclipse för att stega igenom programmet.