prystupa

  Scenario: Matching incoming Buy market order against Sell market order when another - limit - Sell order present
    Given the following orders are submitted in this order:
      | Broker | Side | Qty | Price |
      | A      | Sell | 100 | MO    |
      | B      | Sell | 100 | 10.5  |
    Then market order book looks like:
      | Broker | Qty | Price | Price | Qty | Broker |
      |        |     |       | MO    | 100 | A      |
      |        |     |       | 10.5  | 100 | B      |
    When the following orders are submitted in this order:

prystupa

Feature: Computing strongly connected components of a graph using Tarjan's algorithm

  Scenario: Simple chain with no loops
    Given the following edges of a graph with "3" vertices:
      | Start | End |
      | 1     | 2   |
      | 2     | 3   |
    When I compute strongly connected components of this graph using Tarjan's algorithm
    Then there is a connected component of the graph:
      | Node | Successors |

prystupa

class StronglyConnectedComponentsAlgo {

  type GraphAdjList = Vector[Set[Int]]
  type SubGraphAdjList = Map[Int, Set[Int]]

  def compute(adjacencyList: GraphAdjList): Vector[SubGraphAdjList] = {

    def strongConnect(v: Int, state: State): State = {

      if (!state.visited(v).isDefined) {

prystupa

algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if

prystupa

class MatchingEngine(buy: OrderBook, sell: OrderBook, orderTypes: (Order => OrderType))
  extends mutable.Publisher[OrderBookEvent] {
  
  // Only the relevant modified code is shown
  // ...
  
  private def tryMatchWithTop(order: Order, top: Order): Option[Trade] = {
    def trade(price: Double) = {
      val (buy, sell) = if (order.side == Buy) (order, top) else (top, order)
      Some(Trade(buy.broker, sell.broker, price, math.min(buy.qty, sell.qty)))

prystupa

  Scenario: Matching incoming Buy limit order against a single outstanding Sell market order
    When the following orders are submitted in this order:
      | Broker | Side | Qty | Price |
      | A      | Sell | 100 | MO    |
      | B      | Buy  | 120 | 10.5  |
    Then the following trades are generated:
      | Buying broker | Selling broker | Qty | Price |
      | B             | A              | 100 | 10.5  |
    And market order book looks like:
      | Broker | Qty | Price | Price | Qty | Broker |

prystupa

class OrderBook(side: Side, orderTypes: (Order => OrderType)) {

  private var marketBook: List[Order] = Nil
  private var limitBook: List[(Double, List[Order])] = Nil
  private val priceOrdering = if (side == Sell) Ordering[Double] else Ordering[Double].reverse

  def bestLimit: Option[Double] = limitBook.headOption.map({
    case (limit, _) => limit
  })
  

prystupa

class OrderBookSteps extends ShouldMatchers {
 
  // only the new code is shown
  // ...
  
  @Then("^the best limit for \"([^\"]*)\" order book is \"([^\"]*)\"$")
  def the_best_limit_for_order_book_is(sideString: String, expectedBestLimit: String) {

    val (_, book) = getBook(sideString)
    val actual = book.bestLimit

prystupa

Feature: Maintaining best limit in the order book

  Scenario Outline: Various life cycles of the order book best limit
  # When are no orders in the book, the best limit is not defined
    Then the best limit for "<Side>" order book is "None"
  # If a market order enters the book, the best limit is still undefined
    When the following orders are added to the "<Side>" book:
      | Broker | Qty | Price |
      | A      | 100 | MO    |
    Then the "<Side>" order book looks like:

prystupa

  private def tryMatchWithTop(order: Order, top: Order): Option[Trade] = top match {

    case topLimit: LimitOrder => {
      if (orderTypes(order).crossesAt(topLimit.limit)) {
        val (buy, sell) = if (order.side == Buy) (order, topLimit) else (topLimit, order)
        Some(Trade(buy.broker, sell.broker, topLimit.limit, math.min(buy.qty, sell.qty)))
      }
      else None
    }
  }