Leysið dæmi 2.5.22 í bókinni.
Stock market trading. Investors place buy and sell orders for a particular stock on an electronic exchange, specifying a maximum buy or minimum sell price that they are willing to pay, and how many shares they wish to trade at that price. Develop a program that uses priority queues to match up buyers and sellers and test it through simulation. Maintain two priority queues, one for buyers and one for sellers, executing trades whenever a new order can be matched with an existing order or orders.
Skrifið gagnamót fyrir MatchingEngine sem býður upp á að bæta við kauptilboði (buy/bid order) og sölutilboði (sell/ask order). Látið hvert tilboð innihalda verð og auðkenni þess sem lagði inn tilboðið. Látið MatchingEngine taka inn viðmót (interface) fyrir callback þegar viðskipti eiga sér stað (trade execution), þ.e. þegar kauptilboð er parað við sölutilboð. Látið notanda MatchingEngine skilgreina execution callback sem prentar bara út executions með upplýsingum um verð og auðkenni beggja aðila.
Skrifið notkunarlýsingu fyrir öll föll sem þið skrifið í MatchingEngine. Skrifið fastayrðingu gagna fyrir útfærslu ykkar á MatchingEngine gagnamótinu.
Viðskipti eiga sér stað þegar hæsta kauptilboð er hærra en lægsta sölutilboð.
Efni til að koma ykkur af stað:
Fyrir þá sem leiðast þá eru hér nokkrar hugmyndir að auka viðbótum:
import java.util.Comparator;
public class MatchingEngine
{
private PriQueue<Order> bids;
private PriQueue<Order> asks;
private static class Order
{
String id;
int price;
public Order(String id, int price)
{
this.id = id;
this.price = price;
}
public String toString()
{
return id + ": " + price;
}
}
private static class AskComparator implements Comparator<Order>
{
public int compare(Order a, Order b)
{
if (a.price < b.price) return -1;
else if (a.price > b.price) return 1;
else return 0;
}
}
private static class BidComparator implements Comparator<Order>
{
public int compare(Order a, Order b)
{
if (a.price < b.price) return 1;
else if (a.price > b.price) return -1;
else return 0;
}
}
public MatchingEngine()
{
bids = new PriQueue<Order>(100, new BidComparator());
asks = new PriQueue<Order>(100, new AskComparator());
}
public void addAsk(String id, int price)
{
if (bids.Count() > 0)
{
Order bestBid = bids.peek();
if (bestBid.price > price)
{
System.out.printf("Trade: %s sells to %s at price %d\n", id, bestBid.id, price);
bids.deleteMin();
return;
}
}
asks.Put(new Order(id, price));
}
public void addBid(String id, int price)
{
if (asks.Count() > 0)
{
Order bestAsk = asks.peek();
if (bestAsk.price < price)
{
System.out.printf("Trade: %s sells to %s at price %d\n", bestAsk.id, id, bestAsk.price);
asks.deleteMin();
return;
}
}
bids.Put(new Order(id, price));
}
public void print()
{
Order bestBid = bids.peek();
Order bestAsk = asks.peek();
if (bestBid == null)
System.out.printf("Market: No bids -- Lowest ask %s @ %d\n", bestAsk.id, bestAsk.price);
else if (bestAsk == null)
System.out.printf("Market: Highest bid %s @ %d -- No asks\n", bestBid.id, bestBid.price);
else
System.out.printf("Market: Highest bid %s @ %d -- Lowest ask %s @ %d\n", bestBid.id, bestBid.price, bestAsk.id, bestAsk.price);
}
public static void main(String[] args)
{
MatchingEngine m = new MatchingEngine();
m.addAsk("A1", 150);
m.addBid("B1", 100);
m.addBid("B2", 200);
m.addBid("B3", 200);
m.addAsk("A2", 100);
}
}
import java.util.Comparator;
public class PriQueue<T>
{
// Gildin í forgangsbiðröðinni eru í f[0..n-1]
// í hrúgu með minnsta stak efst skv. cmp.
//
// Með öðrum orðum, þá gildir eftirfarandi
// röð um hrúguna:
// cmp.compare(f[i], f[2*i+1]) < 0
// cmp.compare(f[i], f[2*i+2]) < 0
private T[] f;
private int n;
private Comparator<T> cmp;
// Notkun: pq = new PriQueue(max, cmp);
// Fyrir: max > 0
// Eftir: pq er ný tóm forgangsbiðröð með pláss fyrir
// max gildi. Gildið sem er fremst skv. cmp hefur
// hæstan forgang.
@SuppressWarnings({"unchecked"})
public PriQueue(int max, Comparator<T> cmp)
{
this.n = 0;
this.f = (T[]) new Object[max];
this.cmp = cmp;
}
// Notkun: s = pq.deleteMin();
// Fyrir: pq er ekki tóm.
// Eftir: s er minnsta gildið sem var í pq.
// s hefur verið fjarlægt úr pq.
public T deleteMin()
{
T result = f[0];
f[0] = f[--n];
int i = 0;
while (true)
{
// f[0..n-1] er hrúga nema e.t.v.
// er f[i] of ofarlega.
// 0 <= i <= n
int b = 2*i+1;
if (b >= n) return result; // f[i] er barnlaust (lauf)
if (b+1 < n && cmp.compare(f[b+1], f[b]) < 0)
// Veljum hægra barnið ef það er minna en vinstra
b++;
if (cmp.compare(f[i], f[b]) >= 0)
// f[i] er á réttum stað
return result;
// f[b] < f[i], þ.e. foreldri er stærra
// en barn og þurfum því að víxla þeim.
swap(f, i, b);
i = b;
}
}
// Notkun: s = pq.peek();
// Fyrir: pq er ekki tóm.
// Eftir: s er minnsta gildið sem er í pq.
public T peek()
{
return f[0];
}
// Notkun: pq.Put(s);
// Fyrir: pq er ekki full.
// Eftir: s hefur verið bætt við pq.
public void Put(T s)
{
f[n++] = s;
int i = n-1;
while (i > 0)
{
// f[0..n-1] er í hrúgu nema e.t.v.
// er f[i] of neðarlega.
int parent = (i-1)/2;
if (cmp.compare(f[parent], f[i]) <= 0)
break;
// f[i] < f[parent], þ.e. barn er minna
// en foreldri og þurfum því að víxla þeim
swap(f, i, parent);
i = parent;
}
}
// Notkun: n = pq.Count();
// Eftir: n er fjöldi staka í pq.
public int Count()
{
return n;
}
// Notkun: b = pq.isFull();
// Eftir: b er satt þþaa. pq sé full.
public boolean isFull()
{
return n == f.length;
}
private static <T> void swap(T[] f, int a, int b)
{
T tmp = f[a];
f[a] = f[b];
f[b] = tmp;
}
}