uk.ac.liv.auction.core
Class FourHeapShoutEngine

java.lang.Object
  uk.ac.liv.auction.core.FourHeapShoutEngine

All Implemented Interfaces:

Resetable, java.io.Serializable, ShoutEngine

public class FourHeapShoutEngine

extends java.lang.Object

implements ShoutEngine, java.io.Serializable

This class provides auction shout management services using the 4-Heap algorithm. See:

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

All state is maintained in memory resident data structures and no crash recovery is provided.

Version:

$Revision: 1.29 $

Author:

Steve Phelps

See Also:

Serialized Form

Field Summary

protected org.apache.commons.collections.buffer.PriorityBuffer	bIn Matched bids in ascending order
protected org.apache.commons.collections.buffer.PriorityBuffer	bOut Unmatched bids in descending order
protected static AscendingShoutComparator	greaterThan
protected static DescendingShoutComparator	lessThan
protected org.apache.commons.collections.buffer.PriorityBuffer	sIn Matched asks in descending order
protected org.apache.commons.collections.buffer.PriorityBuffer	sOut Unmatched asks in ascending order

Constructor Summary

FourHeapShoutEngine()

Method Summary

java.util.Iterator	askIterator() Return an iterator that non-destructively iterates over every ask in the auction (both matched and unmatched).
java.util.Iterator	bidIterator() Return an iterator that non-destructively iterates over every bid in the auction (both matched and unmatched).
int	displaceHighestMatchedAsk(Shout ask)
int	displaceLowestMatchedBid(Shout bid)
protected int	displaceShout(Shout shout, org.apache.commons.collections.buffer.PriorityBuffer from, org.apache.commons.collections.buffer.PriorityBuffer to)
Shout	getHighestMatchedAsk() Get the highest matched ask.
Shout	getHighestUnmatchedBid() Get the highest unmatched bid.
Shout	getLowestMatchedBid() Get the lowest matched bid
Shout	getLowestUnmatchedAsk() Get the lowest unmatched ask.
java.util.List	getMatchedShouts() Return a list of matched bids and asks.
protected void	initialise()
void	insertUnmatchedAsk(Shout ask) Insert an unmatched ask into the approriate heap.
void	insertUnmatchedBid(Shout bid) Insert an unmatched bid into the approriate heap.
void	newAsk(Shout ask)
void	newBid(Shout bid)
protected void	postRemovalProcessing() Sub-classes should override this method if they wish to check auction state integrity after shout removal.
protected void	preRemovalProcessing() Sub-classes should override this method if they wish to check auction state integrity before shout removal.
void	prettyPrint(java.lang.String title, org.apache.commons.collections.buffer.PriorityBuffer shouts)
void	printState() Log the current state of the auction.
int	promoteHighestUnmatchedBid(Shout ask)
int	promoteLowestUnmatchedAsk(Shout bid)
int	promoteShout(Shout shout, org.apache.commons.collections.buffer.PriorityBuffer from, org.apache.commons.collections.buffer.PriorityBuffer to, org.apache.commons.collections.buffer.PriorityBuffer matched)
protected void	reinsert(org.apache.commons.collections.buffer.PriorityBuffer 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.
protected void	removeAsk(Shout shout)
protected void	removeBid(Shout shout)
void	removeShout(Shout shout)
void	reset() Reinitialise our state to the original settings.
java.lang.String	toString()
protected static Shout	unifyShout(Shout shout, org.apache.commons.collections.buffer.PriorityBuffer 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 org.apache.commons.collections.buffer.PriorityBuffer bIn

Matched bids in ascending order

bOut

protected org.apache.commons.collections.buffer.PriorityBuffer bOut

Unmatched bids in descending order

sIn

protected org.apache.commons.collections.buffer.PriorityBuffer sIn

Matched asks in descending order

sOut

protected org.apache.commons.collections.buffer.PriorityBuffer sOut

Unmatched asks in ascending order

greaterThan

protected static AscendingShoutComparator greaterThan

lessThan

protected static DescendingShoutComparator lessThan

Constructor Detail

FourHeapShoutEngine

public FourHeapShoutEngine()

Method Detail

removeShout

public void removeShout(Shout shout)

Specified by:

removeShout in interface ShoutEngine

removeAsk

protected void removeAsk(Shout shout)

removeBid

protected void removeBid(Shout shout)

toString

public java.lang.String toString()

printState

public void printState()

Log the current state of the auction.

Specified by:

printState in interface ShoutEngine

prettyPrint

public void prettyPrint(java.lang.String title,
                        org.apache.commons.collections.buffer.PriorityBuffer shouts)

insertUnmatchedAsk

public void insertUnmatchedAsk(Shout ask)
                        throws DuplicateShoutException

Insert an unmatched ask into the approriate heap.

Throws:

DuplicateShoutException

insertUnmatchedBid

public void insertUnmatchedBid(Shout bid)
                        throws DuplicateShoutException

Insert an unmatched bid into the approriate heap.

Throws:

DuplicateShoutException

getHighestUnmatchedBid

public Shout getHighestUnmatchedBid()

Get the highest unmatched bid.

Specified by:

getHighestUnmatchedBid in interface ShoutEngine

getLowestMatchedBid

public Shout getLowestMatchedBid()

Get the lowest matched bid

Specified by:

getLowestMatchedBid in interface ShoutEngine

getLowestUnmatchedAsk

public Shout getLowestUnmatchedAsk()

Get the lowest unmatched ask.

Specified by:

getLowestUnmatchedAsk in interface ShoutEngine

getHighestMatchedAsk

public Shout getHighestMatchedAsk()

Get the highest matched ask.

Specified by:

getHighestMatchedAsk in interface ShoutEngine

unifyShout

protected static Shout unifyShout(Shout shout,
                                  org.apache.commons.collections.buffer.PriorityBuffer 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(Shout shout,
                            org.apache.commons.collections.buffer.PriorityBuffer from,
                            org.apache.commons.collections.buffer.PriorityBuffer to)
                     throws DuplicateShoutException

Throws:

DuplicateShoutException

promoteShout

public int promoteShout(Shout shout,
                        org.apache.commons.collections.buffer.PriorityBuffer from,
                        org.apache.commons.collections.buffer.PriorityBuffer to,
                        org.apache.commons.collections.buffer.PriorityBuffer matched)
                 throws DuplicateShoutException

Throws:

DuplicateShoutException

displaceHighestMatchedAsk

public int displaceHighestMatchedAsk(Shout ask)
                              throws DuplicateShoutException

Throws:

DuplicateShoutException

displaceLowestMatchedBid

public int displaceLowestMatchedBid(Shout bid)
                             throws DuplicateShoutException

Throws:

DuplicateShoutException

promoteHighestUnmatchedBid

public int promoteHighestUnmatchedBid(Shout ask)
                               throws DuplicateShoutException

Throws:

DuplicateShoutException

promoteLowestUnmatchedAsk

public int promoteLowestUnmatchedAsk(Shout bid)
                              throws DuplicateShoutException

Throws:

DuplicateShoutException

newBid

public void newBid(Shout bid)
            throws DuplicateShoutException

Specified by:

newBid in interface ShoutEngine

Throws:

DuplicateShoutException

newAsk

public void newAsk(Shout ask)
            throws DuplicateShoutException

Specified by:

newAsk in interface ShoutEngine

Throws:

DuplicateShoutException

askIterator

public java.util.Iterator askIterator()

Description copied from interface: ShoutEngine

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

Specified by:

askIterator in interface ShoutEngine

bidIterator

public java.util.Iterator bidIterator()

Description copied from interface: ShoutEngine

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

Specified by:

bidIterator in interface ShoutEngine

getMatchedShouts

public java.util.List getMatchedShouts()

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:

getMatchedShouts in interface ShoutEngine

initialise

protected void initialise()

reset

public void reset()

Description copied from interface: Resetable

Reinitialise our state to the original settings.

Specified by:

reset in interface Resetable

preRemovalProcessing

protected void preRemovalProcessing()

Sub-classes should override this method if they wish to check auction state integrity before shout removal. This is useful for testing/debugging.

postRemovalProcessing

protected void postRemovalProcessing()

Sub-classes should override this method if they wish to check auction state integrity after shout removal. This is useful for testing/debugging.

reinsert

protected void reinsert(org.apache.commons.collections.buffer.PriorityBuffer 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.