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örenklingar

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.)

Upplägg

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.

A. Binär heap

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);
}

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):

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.

Manuell testning

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.

Automatisk testning

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.

B. Klass för aktiehandel

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.

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.

Manuell testning

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

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.

Automatisk testning

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.

Givet material

Tips

Rapportering

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: