net.sourceforge.jasa.market
Class FourHeapOrderBook

java.lang.Object
  net.sourceforge.jasa.market.FourHeapOrderBook

All Implemented Interfaces:

java.io.Serializable, OrderBook

public class FourHeapOrderBook
extends java.lang.Object
implements OrderBook, java.io.Serializable

This class provides market order-matching services using the 4-Heap algorithm. See:

"Flexible Double Auctions for Electronic Commerce: Theory and Implementation" by Wurman, Walsh and Wellman 1998.

See Also:

Serialized Form

Field Summary

protected java.util.PriorityQueue<Order>	bIn Matched bids in ascending order
protected java.util.PriorityQueue<Order>	bOut Unmatched bids in descending order
protected static AscendingOrderComparator	greaterThan
protected static DescendingOrderComparator	lessThan
protected java.util.PriorityQueue<Order>	sIn Matched asks in descending order
protected java.util.PriorityQueue<Order>	sOut Unmatched asks in ascending order

Constructor Summary

FourHeapOrderBook()

Method Summary

void	add(Order shout)
protected void	addAsk(Order ask)
protected void	addBid(Order bid)
java.util.Iterator<Order>	askIterator() Return an iterator that non-destructively iterates over every ask in the market (both matched and unmatched).
java.util.Iterator<Order>	bidIterator() Return an iterator that non-destructively iterates over every bid in the market (both matched and unmatched).
protected void	checkBalanced(Order s1, Order s2, java.lang.String condition)
void	checkIntegrity()
int	displaceHighestMatchedAsk(Order ask)
int	displaceLowestMatchedBid(Order bid)
protected int	displaceShout(Order shout, java.util.PriorityQueue<Order> from, java.util.PriorityQueue<Order> to)
int	getDepth()
Order	getHighestMatchedAsk() Get the highest matched ask.
Order	getHighestUnmatchedBid() Get the highest unmatched bid.
Order	getLowestMatchedBid() Get the lowest matched bid
Order	getLowestUnmatchedAsk() Get the lowest unmatched ask.
java.util.List<Order>	getUnmatchedAsks()
java.util.List<Order>	getUnmatchedBids()
protected void	initialise()
void	insertUnmatchedAsk(Order ask) Insert an unmatched ask into the appropriate heap.
void	insertUnmatchedBid(Order bid) Insert an unmatched bid into the appropriate heap.
boolean	isEmpty()
java.util.List<Order>	matchOrders() Return a list of matched bids and asks.
void	prettyPrint(java.lang.String title, java.util.PriorityQueue shouts)
void	printState() Log the current state of the market.
int	promoteHighestUnmatchedBid(Order ask)
int	promoteLowestUnmatchedAsk(Order bid)
int	promoteShout(Order shout, java.util.PriorityQueue<Order> from, java.util.PriorityQueue<Order> to, java.util.PriorityQueue<Order> matched)
protected void	reinsert(java.util.PriorityQueue<Order> heap, int quantity) Remove, possibly several, shouts from heap such that quantity(heap) is reduced by the supplied quantity and reinsert the shouts using the standard insertion logic.
void	remove(Order shout)
protected void	removeAsk(Order shout)
protected void	removeBid(Order shout)
void	reset()
int	size() Compute the total number of orders in the book.
java.lang.String	toString()
protected static Order	unifyShout(Order shout, java.util.PriorityQueue<Order> heap) Unify the shout at the top of the heap with the supplied shout, so that quantity(shout) = quantity(top(heap)).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

bIn

protected java.util.PriorityQueue<Order> bIn

Matched bids in ascending order

bOut

protected java.util.PriorityQueue<Order> bOut

Unmatched bids in descending order

sIn

protected java.util.PriorityQueue<Order> sIn

Matched asks in descending order

sOut

protected java.util.PriorityQueue<Order> sOut

Unmatched asks in ascending order

greaterThan

protected static AscendingOrderComparator greaterThan

lessThan

protected static DescendingOrderComparator lessThan

Constructor Detail

FourHeapOrderBook

public FourHeapOrderBook()

Method Detail

remove

public void remove(Order shout)

Specified by:

remove in interface OrderBook

removeAsk

protected void removeAsk(Order shout)

removeBid

protected void removeBid(Order shout)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

printState

public void printState()

Log the current state of the market.

Specified by:

printState in interface OrderBook

prettyPrint

public void prettyPrint(java.lang.String title,
                        java.util.PriorityQueue shouts)

insertUnmatchedAsk

public void insertUnmatchedAsk(Order ask)
                        throws DuplicateShoutException

Insert an unmatched ask into the appropriate heap.

Throws:

DuplicateShoutException

insertUnmatchedBid

public void insertUnmatchedBid(Order bid)
                        throws DuplicateShoutException

Insert an unmatched bid into the appropriate heap.

Throws:

DuplicateShoutException

getHighestUnmatchedBid

public Order getHighestUnmatchedBid()

Get the highest unmatched bid.

Specified by:

getHighestUnmatchedBid in interface OrderBook

getLowestMatchedBid

public Order getLowestMatchedBid()

Get the lowest matched bid

Specified by:

getLowestMatchedBid in interface OrderBook

getLowestUnmatchedAsk

public Order getLowestUnmatchedAsk()

Get the lowest unmatched ask.

Specified by:

getLowestUnmatchedAsk in interface OrderBook

getHighestMatchedAsk

public Order getHighestMatchedAsk()

Get the highest matched ask.

Specified by:

getHighestMatchedAsk in interface OrderBook

unifyShout

protected static Order unifyShout(Order shout,
                                  java.util.PriorityQueue<Order> heap)

Unify the shout at the top of the heap with the supplied shout, so that quantity(shout) = quantity(top(heap)). This is achieved by splitting the supplied shout or the shout at the top of the heap.

Parameters:

shout - The shout.

heap - The heap.

Returns:

A reference to the, possibly modified, shout.

displaceShout

protected int displaceShout(Order shout,
                            java.util.PriorityQueue<Order> from,
                            java.util.PriorityQueue<Order> to)
                     throws DuplicateShoutException

Throws:

DuplicateShoutException

promoteShout

public int promoteShout(Order shout,
                        java.util.PriorityQueue<Order> from,
                        java.util.PriorityQueue<Order> to,
                        java.util.PriorityQueue<Order> matched)
                 throws DuplicateShoutException

Throws:

DuplicateShoutException

displaceHighestMatchedAsk

public int displaceHighestMatchedAsk(Order ask)
                              throws DuplicateShoutException

Throws:

DuplicateShoutException

displaceLowestMatchedBid

public int displaceLowestMatchedBid(Order bid)
                             throws DuplicateShoutException

Throws:

DuplicateShoutException

promoteHighestUnmatchedBid

public int promoteHighestUnmatchedBid(Order ask)
                               throws DuplicateShoutException

Throws:

DuplicateShoutException

promoteLowestUnmatchedAsk

public int promoteLowestUnmatchedAsk(Order bid)
                              throws DuplicateShoutException

Throws:

DuplicateShoutException

add

public void add(Order shout)
         throws DuplicateShoutException

Specified by:

add in interface OrderBook

Throws:

DuplicateShoutException

addBid

protected void addBid(Order bid)
               throws DuplicateShoutException

Throws:

DuplicateShoutException

addAsk

protected void addAsk(Order ask)
               throws DuplicateShoutException

Throws:

DuplicateShoutException

askIterator

public java.util.Iterator<Order> askIterator()

Description copied from interface: OrderBook

Return an iterator that non-destructively iterates over every ask in the market (both matched and unmatched).

Specified by:

askIterator in interface OrderBook

bidIterator

public java.util.Iterator<Order> bidIterator()

Description copied from interface: OrderBook

Return an iterator that non-destructively iterates over every bid in the market (both matched and unmatched).

Specified by:

bidIterator in interface OrderBook

matchOrders

public java.util.List<Order> matchOrders()

Return a list of matched bids and asks. The list is of the form

( b0, a0, b1, a1 .. bn, an )

where bi is the ith bid and a0 is the ith ask. A typical auctioneer would clear by matching bi with ai for all i at some price.

Specified by:

matchOrders in interface OrderBook

initialise

protected void initialise()

reset

public void reset()

reinsert

protected void reinsert(java.util.PriorityQueue<Order> heap,
                        int quantity)

Remove, possibly several, shouts from heap such that quantity(heap) is reduced by the supplied quantity and reinsert the shouts using the standard insertion logic. quantity(heap) is defined as the total quantity of every shout in the heap.

Parameters:

heap - The heap to remove shouts from.

quantity - The total quantity to remove.

size

public int size()

Compute the total number of orders in the book.

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface OrderBook

getDepth

public int getDepth()

Specified by:

getDepth in interface OrderBook

getUnmatchedBids

public java.util.List<Order> getUnmatchedBids()

Specified by:

getUnmatchedBids in interface OrderBook

getUnmatchedAsks

public java.util.List<Order> getUnmatchedAsks()

Specified by:

getUnmatchedAsks in interface OrderBook

checkIntegrity

public void checkIntegrity()

checkBalanced

protected void checkBalanced(Order s1,
                             Order s2,
                             java.lang.String condition)