edu.cuny.cat.market.matching
Class FourHeapShoutEngine

java.lang.Object
  edu.cuny.cat.market.AuctioneerPolicy
      edu.cuny.cat.market.matching.ShoutEngine
          edu.cuny.cat.market.matching.FourHeapShoutEngine

All Implemented Interfaces:

AuctionEventListener, edu.cuny.config.param.Parameterizable, edu.cuny.obj.Resetable, java.io.Serializable

Direct Known Subclasses:

GradMaxVolumeShoutEngine

public class FourHeapShoutEngine
extends ShoutEngine
implements 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 status is maintained in memory resident data structures and no crash recovery is provided.

Version:

$Revision: 1.16 $

Author:

Steve Phelps

See Also:

Serialized Form

Field Summary

protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	bIn Matched bids in ascending order
protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	bOut Unmatched bids in descending order
protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	sIn Matched asks in descending order
protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	sOut Unmatched asks in ascending order

Fields inherited from class edu.cuny.cat.market.matching.ShoutEngine

AscendingOrder, DescendingOrder

Fields inherited from class edu.cuny.cat.market.AuctioneerPolicy

auctioneer

Constructor Summary

FourHeapShoutEngine()

Method Summary

java.util.Iterator<Shout>	ascendingAskIterator()
java.util.Iterator<Shout>	askIterator()
java.util.Iterator<Shout>	bidIterator()
java.util.Iterator<Shout>	descendingBidIterator()
int	displaceHighestMatchedAsk(Shout ask)
int	displaceLowestMatchedBid(Shout bid)
protected int	displaceShout(Shout shout, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> from, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> 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.
org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	getMatchedAsks()
org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	getMatchedBids()
int	getMatchedVolume()
int	getNumOfMatchedAsks()
int	getNumOfMatchedBids()
int	getNumOfUnmatchedAsks()
int	getNumOfUnmatchedBids()
org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	getUnmatchedAsks()
org.apache.commons.collections15.buffer.PriorityBuffer<Shout>	getUnmatchedBids()
int	getUnmatchedDemand()
int	getUnmatchedSupply()
void	insertUnmatchedAsk(Shout ask) Insert an unmatched ask into the approriate heap.
void	insertUnmatchedBid(Shout bid) Insert an unmatched bid into the approriate heap.
java.util.Iterator<Shout>	matchedAskIterator()
java.util.Iterator<Shout>	matchedBidIterator()
java.util.List<Shout>	matchShouts() Return a list of matched bids and asks.
protected void	newAsk(Shout ask)
protected void	newBid(Shout bid)
void	newShout(Shout shout)
protected void	postRemovalProcessing() Sub-classes should override this method if they wish to check auction status integrity after shout removal.
protected void	preRemovalProcessing() Sub-classes should override this method if they wish to check auction status integrity before shout removal.
void	prettyPrint(java.lang.String title, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> shouts)
void	printState() Log the current status of the auction.
int	promoteHighestUnmatchedBid(Shout ask)
int	promoteLowestUnmatchedAsk(Shout bid)
int	promoteShout(Shout shout, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> from, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> to, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> matched)
protected void	reinsert(org.apache.commons.collections15.buffer.PriorityBuffer<Shout> 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() resets the state to be the same as the policy is created and initialized.
java.lang.String	toString()
protected static Shout	unifyShout(Shout shout, org.apache.commons.collections15.buffer.PriorityBuffer<Shout> 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 edu.cuny.cat.market.matching.ShoutEngine

getMatchedShouts

Methods inherited from class edu.cuny.cat.market.AuctioneerPolicy

eventOccurred, getAuctioneer, initialize, setAuctioneer, setup

Methods inherited from class java.lang.Object

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

Field Detail

bIn

protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout> bIn

Matched bids in ascending order

bOut

protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout> bOut

Unmatched bids in descending order

sIn

protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout> sIn

Matched asks in descending order

sOut

protected org.apache.commons.collections15.buffer.PriorityBuffer<Shout> sOut

Unmatched asks in ascending order

Constructor Detail

FourHeapShoutEngine

public FourHeapShoutEngine()

Method Detail

reset

public void reset()

Description copied from class: AuctioneerPolicy

resets the state to be the same as the policy is created and initialized.

Specified by:

reset in interface edu.cuny.obj.Resetable

Overrides:

reset in class AuctioneerPolicy

removeShout

public void removeShout(Shout shout)

Specified by:

removeShout in class ShoutEngine

removeAsk

protected void removeAsk(Shout shout)

removeBid

protected void removeBid(Shout shout)

toString

public java.lang.String toString()

Overrides:

toString in class AuctioneerPolicy

printState

public void printState()

Log the current status of the auction.

Specified by:

printState in class ShoutEngine

prettyPrint

public void prettyPrint(java.lang.String title,
                        org.apache.commons.collections15.buffer.PriorityBuffer<Shout> 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 class ShoutEngine

getLowestMatchedBid

public Shout getLowestMatchedBid()

Get the lowest matched bid

Specified by:

getLowestMatchedBid in class ShoutEngine

getLowestUnmatchedAsk

public Shout getLowestUnmatchedAsk()

Get the lowest unmatched ask.

Specified by:

getLowestUnmatchedAsk in class ShoutEngine

getHighestMatchedAsk

public Shout getHighestMatchedAsk()

Get the highest matched ask.

Specified by:

getHighestMatchedAsk in class ShoutEngine

unifyShout

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

Throws:

DuplicateShoutException

promoteShout

public int promoteShout(Shout shout,
                        org.apache.commons.collections15.buffer.PriorityBuffer<Shout> from,
                        org.apache.commons.collections15.buffer.PriorityBuffer<Shout> to,
                        org.apache.commons.collections15.buffer.PriorityBuffer<Shout> 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

newShout

public void newShout(Shout shout)
              throws DuplicateShoutException

Specified by:

newShout in class ShoutEngine

Throws:

DuplicateShoutException

newBid

protected void newBid(Shout bid)
               throws DuplicateShoutException

Throws:

DuplicateShoutException

newAsk

protected void newAsk(Shout ask)
               throws DuplicateShoutException

Throws:

DuplicateShoutException

askIterator

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

Specified by:

askIterator in class ShoutEngine

Returns:

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

ascendingAskIterator

public java.util.Iterator<Shout> ascendingAskIterator()

Specified by:

ascendingAskIterator in class ShoutEngine

Returns:

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

bidIterator

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

Specified by:

bidIterator in class ShoutEngine

Returns:

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

descendingBidIterator

public java.util.Iterator<Shout> descendingBidIterator()

Specified by:

descendingBidIterator in class ShoutEngine

Returns:

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

matchedAskIterator

public java.util.Iterator<Shout> matchedAskIterator()

Specified by:

matchedAskIterator in class ShoutEngine

Returns:

an iterator that non-destructively iterates over every matched ask in the auction in ascending order.

matchedBidIterator

public java.util.Iterator<Shout> matchedBidIterator()

Specified by:

matchedBidIterator in class ShoutEngine

Returns:

an iterator that non-destructively iterates over every matched bid in the auction in descending order.

matchShouts

public java.util.List<Shout> matchShouts()

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:

matchShouts in class ShoutEngine

preRemovalProcessing

protected void preRemovalProcessing()

Sub-classes should override this method if they wish to check auction status 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 status integrity after shout removal. This is useful for testing/debugging.

reinsert

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

getMatchedVolume

public int getMatchedVolume()

Specified by:

getMatchedVolume in class ShoutEngine

getUnmatchedSupply

public int getUnmatchedSupply()

Specified by:

getUnmatchedSupply in class ShoutEngine

getUnmatchedDemand

public int getUnmatchedDemand()

Specified by:

getUnmatchedDemand in class ShoutEngine

getNumOfUnmatchedBids

public int getNumOfUnmatchedBids()

Specified by:

getNumOfUnmatchedBids in class ShoutEngine

getNumOfMatchedBids

public int getNumOfMatchedBids()

Specified by:

getNumOfMatchedBids in class ShoutEngine

getNumOfUnmatchedAsks

public int getNumOfUnmatchedAsks()

Specified by:

getNumOfUnmatchedAsks in class ShoutEngine

getNumOfMatchedAsks

public int getNumOfMatchedAsks()

Specified by:

getNumOfMatchedAsks in class ShoutEngine

getMatchedBids

public org.apache.commons.collections15.buffer.PriorityBuffer<Shout> getMatchedBids()

Specified by:

getMatchedBids in class ShoutEngine

getUnmatchedBids

public org.apache.commons.collections15.buffer.PriorityBuffer<Shout> getUnmatchedBids()

Specified by:

getUnmatchedBids in class ShoutEngine

getMatchedAsks

public org.apache.commons.collections15.buffer.PriorityBuffer<Shout> getMatchedAsks()

Specified by:

getMatchedAsks in class ShoutEngine

getUnmatchedAsks

public org.apache.commons.collections15.buffer.PriorityBuffer<Shout> getUnmatchedAsks()

Specified by:

getUnmatchedAsks in class ShoutEngine