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 Javaprogram 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. Om aktiehandeln är stor är det viktigt att implementera dessa prioritetsköer effektivt. Du ska därför implementera dem med (binära) heapar.
En användare kan göra tre saker: köpa, sälja, samt ändra ett redan lagt bud. T ex skriver vi
Ada K 70
om Ada vill köpa aktien för 70 kr. På motsvarande sätt skriver vi
Bengt S 71
om Bengt vill sälja aktien för 71 kr,
Bengt NS 71 70
om Bengt ändrar sitt säljbud från 71 till 70 kr (NS = ny säljkurs), och
Ada NK 70 72
om Ada ändrar sitt köpbud från 70 till 72 kr (NK = ny köpkurs).
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:
Ada köper från Bengt för 70 kr
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 68
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, och givet att jämförelser tar konstant tid). 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.
Man kan 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. Man kan t ex 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).
Även om vi rekommenderar att ni implementerar en uppdaterbar heap, accepteras även den mindre effektiva metoden att leta upp elementet genom sökning. Denna sökning måste dock ha komplexiteten O(n) i värsta fall.
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:
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 72
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:
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 69
Det ska också gå att skriva java Lab2 < Budlista. Filens innehåll finns då i System.in.
Det finns ett testprogram som kan användas.