På en aktiebörs handlar man med aktier i stora bolag. Man kan ange om man vill köpa eller sälja ett visst aktieslag och ange det pris man är villig att betala eller sälja för.
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, d.v.s. 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. Om säljbudet är lägre än köpbudet så sker alltså köpet för det belopp som köpbudet anger. (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.
Om ett köpbud läggs av en person som redan har ett bud i orderboken så ska det nya budet hädenefter gälla, och inte det gamla. Samma sak gäller för säljbud.
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.)
Laborationen består av två delar. Del A består av att implementera en prioritetskö m.h.a. en binär heap. Del B består av att implementera en klass som hanterar aktiehandel på det förenklade sätt som beskrivs ovan.
Implementera följande generiska gränssnitt för prioritetskö (filen PrioQueue.java
):
public interface PrioQueue<E> extends Iterable<E> {
void add(E e);
E peek();
E poll();
void remove(E e);
}
add(e)
lägger till e
i kön.peek()
returnerar elementet (eller ett av elementen) med högst prioritet. Elementet tas ej bort från kön. Om kön är tom returneras null
.poll()
returnerar och tar bort elementet med högst prioritet. Om kön är tom före anropet returneras null
.remove(e)
tar bort ett element som är lika med e
från kön, d.v.s. ett godtyckligt element f
i kön för vilket e.equals(f) == true
. Om inget sådant element finns ändras inte kön.PrioQueue
utökar Iterable
och därför måste även metoden iterator
implementeras. Iteratorn som returneras behöver inte genomlöpa köns element i någon särskild ordning.
Ni ska implementera gränssnittet med en generisk klass som heter BinHeap
. Denna ska implementera en binär heap. Klassen ska ha följande konstruktor:
public BinHeap(Comparator<? super E> comp) { ... }
Komparatorn som man anger när en kö skapas används för att avgöra prioritetsordningen. Ett mindre värde innebär högre prioritet, d.v.s. om för element e1
och e2
det gäller att comp.compare(e1, e2) < 0
så har e1
högre prioritet än e2
.
Tidskomplexiteten ska vara följande (n är antal element i kön):
add
: O(logn) amorteratpeek
: O(1)poll
: O(logn) amorteratremove
: O(n)iterator
: O(1)Det går alltså bra att remove
har linjär tidskomplexitet. Elementet som ska tas bort kan letas upp genom linjär sökning i arrayen som representerar heapen. Det går, genom att t.ex. använda en hjälpdatastruktur, få dess komplexitet till O(logn), men det behöver ni inte göra.
Den iteratorn ni returnerar i iterator
behöver inte implementera remove
. Ni kan skriva så här i iterator-klassen.
@Override
public void remove() {
throw new UnsupportedOperationException();
}
Iteratorn behöver heller ej hantera eventuella förändringar i kön som sker medan den stegar sig fram.
Er kod får (förutom java.lang
) använda java.util.Comparator
, java.util.Iterator
och java.util.ArrayList
. Använd gärna ArrayList
för representationen av heap istället för en rå array.
Testa er implementation genom att skriva en körbar klass där en instans skapas och några operationer utförs och kontrollera att resultaten av anropen till peek
och poll
är de förväntade. Kontrollera också, t.ex. i slutet på en sekvens av operationer, att iterator
returnerar en iterator som löper över de förväntade elementen. För ett konkret exempel för en annan klass, se labb-pm för labb 1.
Filen TestBinHeap.java
, som använder NaturalOrderComparator.java
, är ett program som automatiskt testar klassen BinHeap
. För att testa er klass kör ni programmet så här:
java TestBinHeap
Programmet kör tester i fem sekunder. Om en bugg hittas så visas den sekvens av operationer som exponerade buggen. Denna sekvens kan ni kopiera och köra som ett manuellt test. Det gör det enklare att avlusa programmet och komma underfund om vad som är fel.
Innan ni skickar in labben ska er klass klara testprogrammet, d.v.s. det ska köras i 5 sekunder, avsluta och säga att inga fel hittats.
Implementera en klass med namn StockTrade
(filen StockTrade.java
) som har följande konstruktor och metoder:
import java.util.Iterator;
public class StockTrade {
private PrioQueue<Bid> sellersQueue;
private PrioQueue<Bid> buyersQueue;
public StockTrade() { ... }
public Transaction placeSellBid(Bid bid) { ... }
public Transaction placeBuyBid(Bid bid) { ... }
public Iterator<Bid> sellBidsIterator() {
return sellersQueue.iterator();
}
public Iterator<Bid> buyBidsIterator() {
return buyersQueue.iterator();
}
}
Bid
(Bid.java
) är en klass som representerar ett bud. Den består av fälten String name
och int price
, d.v.s. säljarens/köparens namn och priset.
Transaction
(Transaction.java
) är en klass som representerar ett avslutat köp. Den består av fälten String sellerName
, String buyerName
och int price
, d.v.s. säljarens namn, köparens namn samt priset.
Orderboken ska representeras av två prioritetsköer med bud som element (PrioQueue<Bid>
), 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.
placeSellBid(bid)
ska lägga till bid
som ett säljbud i orderboken. Om samma person redan har ett säljbud i orderboken ska det nya budet ersätta det gamla. Om det nya budet gör att ett köp går att avsluta, d.v.s. det finns ett matchande köpbud, så ska dessa två bud tas bort från orderboken och köpet returneras. Annars ska null
returneras.placeBuyBid(bid)
ska lägga till bid
som ett köpbud i orderboken. Om samma person redan har ett köpbud i orderboken ska det nya budet ersätta det gamla. Om det nya budet gör att ett köp går att avsluta, d.v.s. det finns ett matchande säljbud, så ska dessa två bud tas bort från orderboken och köpet returneras. Annars ska null
returneras.Koden för sellBidsIterator
och buyBidsIterator
får inte ändras, utan måste vara som den anges ovan. Ni får lägga till instansvariabler och hjälpmetoder i klassen StockTrade
. Ni får använda hjälpklasser som ni skrivit själva. Er kod får (förutom java.lang
) använda java.util.Comparator
, java.util.Iterator
och java.util.HashMap
.
Det finns ett program (filen Run.java
) som kan användas för att testa er implementation av StockTrade
manuellt.
Här är ett exempel på hur det används.
java Run
Ada s 40
Bengt b 30
Stina s 25
Stina sells to Bengt at 30 SEK
David b 35
l
sellers:
Ada 40 SEK
buyers:
David 35 SEK
Ada s 32
Ada sells to David at 35 SEK
l
sellers:
buyers:
q
Ada s 40
betyder nytt säljbud på nivån 40 kr lagt av Ada.Bengt b 30
betyder nytt köpbud på nivån 30 kr lagt av Bengt.Stina sells to Bengt at 30 SEK
.l
visar orderboken. Notera att buden inte behöver vara listade i prioritetsordning (eller någon annan ordning).q
avslutar programmet.Gör körningar så att ni har täckt in alla möjliga situationer (t.ex. att ett bud ändras) och kontrollera så att resultaten är de förväntade.
Filen TestStockTrade.java
är ett program som automatiskt testar klassen StockTrade
. För att testa er klass kör ni programmet så här:
java TestStockTrade
Programmet kör cirka 200 tester. Om en bugg hittas så visas den sekvens av operationer som exponerade buggen. Denna sekvens kan ni kopiera och köra som ett manuellt test. Eller så kan ni skriva in motsvarande sekvens i programmet för manuell testning (Run
).
Innan ni skickar in labben ska er klass klara testprogrammet. Notera att eftersom antalet tester är begränsade så kan er kod innehålla buggar även om det passerar testet.
PrioQueue.java
TestBinHeap.java
NaturalOrderComparator.java
StockTrade.java
Bid.java
Transaction.java
Run.java
TestStockTrade.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.
Se till att ni noga följer de allmänna reglerna och riktlinjerna för laborationerna.
Innan ni skickar in ska ni se till att er kod klarar de automatiska tester som beskrivs ovan.
Skicka in följande filer:
BinHeap.java
StockTrade.java