På en aktiebörs handlar man med aktier i stora bolag. Man kan göra detta via internet om man har en banktjänst för aktiehandel. Man kan där ange om man vill köpa eller sälja ett visst aktieslag och ange det pris man är villig att betala.
Antag att du vill köpa aktier i Ericsson för 70 kr styck. Ditt bud kommer då att jämföras med säljkursen, dvs det lägsta pris någon säljare f n är villig att acceptera för sina Ericssonaktier. Om säljkursen är 70 kr eller lägre accepteras ditt bud och du får köpa aktierna för 70 kr. Man kallar en sådan genomförd affär ett "avslut". (Det är förstås oklokt att bjuda över lägsta säljkurs, men även sådana bud måste hanteras.) Om säljkursen är högre än 70 kr kommer ditt bud att läggas i Ericssons "orderbok" där alla ej genomförda bud registreras. Om det senare kommer in en ny säljare som är villig att sälja för 70 kr kommer ditt köp genomföras då i stället.
Er uppgift är att implementera ett program för aktiehandel enligt ovan. För enkelhets skull behöver ni bara kunna handla med ett aktieslag och alla bud avser bara en aktie i taget. Det finns däremot flera olika säljare och köpare. Buden ska anges i hela kronor. (Det är förstås enkelt att skriva ett mer generellt program som hanterar fler aktieslag och där godtyckligt antal aktier kan hanteras i en order.)
Orderboken består av två prioritetsköer: en för säljare och en för köpare. I prioritetskön för säljare innebär lägre pris högre prioritet. I prioritetskön för köpare innebär däremot högre pris högre prioritet.
En användare kan göra tre saker: köpa, sälja, samt ändra ett redan lagt bud. T ex skriver vi
Ada K 70om Ada vill köpa aktien för 70 kr. På motsvarande sätt skriver vi
Bengt S 71om Bengt vill sälja aktien för 71 kr,
Bengt NS 71 70om Bengt ändrar sitt säljbud från 71 till 70 kr (NS = ny säljkurs), och
Ada NK 70 72om Ada ändrar sitt köpbud från 70 till 72 kr (NK = ny köpkurs).
Om 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:
Ada köper från Bengt för 70 krOm säljbudet är lägre än köpbudet så sker köpet för det belopp som köpbudet anger.
Efter varje nytt bud som läggs till ska ett avslut ske om ett sådant är möjligt. Köpen ska alltså inte inträffa efter att alla bud registreras, utan i 'realtid'.
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:
Orderbok:
Säljare: Cecilia 70, Bengt 71, David 73, Erika 77
Köpare: Ada 69, Fredrik 68, Gustaf 68Ert huvudprogram ska heta Lab2.java. Det ska acceptera en parameter Budlista som är en fil med en lista av bud enligt ovanstående format med ett bud per rad:
Ada K 70
Bengt S 71
Cecilia S 70
Bengt NS 71 72
David K 72
Erik S 73
Frida S 71
Gustaf K 69
Hanna S 72När ni skriver java Lab2 Budlista ska ert program skriva ut en lista av avslut följt av aktuell orderbok enligt följande format:
Ada köper från Cecilia för 70 kr
David köper från Bengt för 72 kr
Orderbok:
Säljare: Frida 71, Hanna 72, Erik 73
Köpare: Gustaf 69Ni kan själva välja om ni vill tillåta flera bud per säljare eller köpare (t ex flera förekomster av Bengt S i budlistan). Att tillåta det är alltså en frivillig uppgift.
Ert program ska rapportera felaktiga ändringsorder genom utskrifter, t ex när en köpare eller säljare försöker ändra ett icke existerande bud. (För mer "oväntade" fel är det OK att kasta exceptions.)
Laborationen ska implementeras i Java.
För att undvika kompileringsvarningar om ni skapar arrayer med generisk typ (t.ex. E[] arr = (E[])Array.newInstance...) så kan ni använda @SuppressWarnings("unchecked") på de ställena.
Om aktiehandeln är stor är det viktigt att implementera prioritetsköerna effektivt. Ni ska därför implementera dem med binär heapar.
I binära heapar gäller att insättning och borttagning av det högst prioriterade elementet, har värstafallstidskomplexiteten O(log n) (där n är köns storlek, och givet att jämförelser tar konstant tid). Tidskomplexiteten för att ändra en prioritet är O(n), eftersom man i värsta fall måste söka genom hela heapen efter det element vars prioritet ska ändras.
Det går att implementera ändringsoperationen med tidskomplexiteten O(log n) genom att använda en hjälpdatastruktur som håller reda på var i heapen ett visst element är lagrat. Man kan t ex använda en hashmap som lagrar elementens positioner i heapen. På så sätt kan man hitta ett givet element i heapen med komplexiteten O(1), om man har en perfekt O(1) hashfunktion och jämförelser tar konstant tid. Vi rekommenderar att ni implementerar heapen på det här sättet, men den mindre effektiva metoden att leta upp elementet genom sökning accepteras också. Denna sökning måste dock ha komplexiteten O(n) i värsta fall (om vi antar att jämförelser tar konstant tid).
Er prioritetsköimplementation måste vara generisk. Den ska både kunna användas för köparkön och för säljarkön.
Prioritetsköns konstruktorer ska ta komparatorer som argument:
public PriorityQueue(..., Comparator<? super E> comp, ...) {
...
}Elementen i prioritetskön ska alltså vara av någon godtycklig typ E och via en Comparator så kan implementeringen utföra jämförelser mellan par av element.
Programmera modulärt. Stoppa inte in för mycket kod i en och samma metod/funktion.
Skriv själva några textfiler med budsekvenser för att testa att ert program fungerar. Gör tillräckligt många tester för att kontrollera att både säljbud, köpbud och ändringar fungerar. Under testningen kan det vara bra att skriva ut orderboken efter varje bud.
Det finns ett testprogram som bör användas. Detta testprogram körs automatiskt när ni skickar in labben så se till att ert program klarar det innan ni skickar in. Se nedan för mer information om detta.
Programkoden ska vara välstrukturerad och använda meningsfulla namn på variabler, metoder etc. Koden ska vara adekvat kommenterad. Förutom detta ska ni, i en separat textfil, förklara varför den asymptotiska komplexiteten hos era operationer är den avsedda:
Insättning av nytt bud: O(log n), där n är orderbokens storlek.
Genomförande av ett köp: O(log n).
Ändring av bud: O(n) (eller O(log n) för den mer effektiva implementationen).
Ni ska också ange vad den asymptotiska komplexiteten för att skriva ut prioritetsköerna är och motivera detta.
Notera att förklaring av komplexiteten innebär att ni hänvisar till olika delar av er egen kod, inte den allmänna algoritmen som ni utgick ifrån.
Om ni vill får ni utgå från följande kod: Lab2.java.
En kort beskrivning av hur man implementerar en binär heap i en array.
Kursboken har en implementation av binära heapar som ni får utgå från. Den kan dock inte kopieras rakt av: Weiss kräver att alla element ska implementera Comparable, men ni måste använda komparatorer.
En tidigare assistent på den här kursen har skrivit en text om komparatorer.
P g a begränsningar i Java går det inte att skapa en generisk array på följande sätt:
E[] arr = new E[8];Man kan istället skapa en array av typen Object och sedan "casta" om den till rätt typ:
E[] arr = (E[]) new Object[8];För att undvika detta problem kan man använda ArrayListor istället för arrayer. Då slipper man också tänka på att öka arrayens storlek när den blir full.
Ni ska skicka enbart skicka in lösa filer. Skicka enbart in er källkod (.java-filer), inte .class-filer. Huvudfilen ska heta Lab2.java. Förutom källkoden ska ni skicka ett textdokument med tidsanalyserna. Denna fil ska ha namnet dok.txt om ni skrivit på svenska och doc.txt om ni skrivit på engelska.
Fire har en ny funktion för att automatiskt testa inskickade labbar. Detta använder vi i labb 2. Det den automatiska testningen gör är att kompilera er källkod och köra samma program som ni har tillgång till (testprogram). Kör alltså testprogrammet själva innan ni skickar in för att försäkra er om att det kommer att klara testet. Om kompilering eller testprogrammet misslyckas får ni meddelande om detta och möjlighet att dra tillbaka er inlämning. Händer detta så gör det, fixa felet och skicka in igen. Labbrättaren kommer inte hantera en inlämning med misslyckad testning. Om ni behöver hjälp så gå till labbhandledning.
Notera att den automatiska testningen sker asynkront. Man behöver oftast ladda om sidan för att se testresultatet i fire.