_lob.pyx

#!/usr/bin/env python

"""
Limit order book simulation for Indian security exchange.
"""

# Copyright (c) 2012-2014, Lev Givon
# All rights reserved.
# Distributed under the terms of the BSD license:
# http://www.opensource.org/licenses/bsd-license

import rbtree
import copy
import csv
import datetime
import gzip
import logging
import numpy as np
import odict
import os
import pandas
import sys
import time

col_names = \
  ['record_indicator',
   'segment',
   'order_number',
   'trans_date',
   'trans_time',
   'buy_sell_indicator',
   'activity_type',
   'symbol',
   'instrument',
   'expiry_date',
   'strike_price',
   'option_type',
   'volume_disclosed',
   'volume_original',
   'limit_price',
   'trigger_price',
   'mkt_flag',
   'on_stop_flag',
   'io_flag',
   'spread_comb_type',
   'algo_ind',
   'client_id_flag']

# Some aliases for bids and asks:
BID = BUY = 'B'
ASK = SELL = 'S'

class LimitOrderBook(object):
    """
    Limit order book for Indian exchange.

    Parameters
    ----------
    show_output : bool
        Display last event and book state after recording every event.
    sparse_events : bool
        If set to True, only events in which the price or total volume
        of the best bid or ask changes.
    events_log_file : str
        File in which to log events. If set to None, no events are logged.
    stats_log_file : bool
        File in which to log running stats. If set to None, no running stats are logged.
    daily_stats_file : bool
        File in which to log accumulated daily stats. If set to None, no daily stats are logged.

    Notes
    -----
    If the file names specified for storing events or stats end with the string '.gz', the log is automatically
    compressed.
    
    """
    
    def __init__(self, show_output=True, sparse_events=True, events_log_file='events.log.gz',
                 stats_log_file='stats.log.gz', daily_stats_log_file='daily_stats.log.gz'):
        self.logger = logging.getLogger('lob')

        self._show_output = show_output
        
        # The order data in the book is stored in two dictionaries of ordered
        # dicts; the keys of each dictionary correspond to the price levels of
        # each ordered dict. The ordered dicts are used as
        # queues; adding a new entry with a key corresponding to the order
        # number is equivalent to pushing it into the queue, and the ordered
        # dict permits one to "pop" its first entry:
        self._book_data = {}
        self._book_data[BID] = {}
        self._book_data[ASK] = {}

        # Use Cython-based rbtrees classes to keep track of the best bid and
        # ask without having to compute the maximum/minimum prices of the buy
        # and sell portions of the book:
        # XXX Theoretically, the bintrees package could also be used for this
        # purpose; however, it causes Python to eventually segfault when used
        # in this LOB implementation. Saving only the prices in one of
        # the bintrees classes also doesn't appear to prevent this problem from
        # occurring.
        self._book_prices = {}
        self._book_prices[BID] = rbtree.rbtree()
        self._book_prices[ASK] = rbtree.rbtree()

        # This dictionary maps price levels to dictionaries that contain several
        # running stats for each level
        self._init_price_level_stats = {
            'volume_original_total': 0,
            'volume_disclosed_total': 0}        
        self._price_level_stats = {}
        self._price_level_stats[BID] = {}
        self._price_level_stats[ASK] = {}

        # Needed to determine when the best bid or ask prices or volumes change:
        self._init_last_book_best_values = \
            {'best_bid_price': 0.0,
             'best_bid_volume_original': 0,
             'best_ask_price': 0.0,
             'best_ask_volume_original': 0}
        self._last_book_best_values = \
            copy.copy(self._init_last_book_best_values)
        
        # This dictionary maps the IDs of orders that are in the book to their
        # price level:
        self._book_orders_to_price = {}
                
        # Generated events counter:
        self._event_counter = 1

        # Whether to only log events associated with changes in the price or
        # quantity of the best bid or ask:
        self._sparse_events = sparse_events
        
        # Counter for original events, i.e., those that are not generated by the
        # LOB:
        self._original_event_counter = 1
        
        # Events are written to this file:
        self._events_log_file = events_log_file
        if events_log_file:
            if os.path.splitext(events_log_file)[1] == '.gz':
                self._events_log_fh = gzip.open(events_log_file, 'w')
            else:
                self._events_log_fh = open(events_log_file, 'w')
            self._events_log_writer = csv.writer(self._events_log_fh)

        # Stats are written to this file:
        self._stats_log_file = stats_log_file
        if stats_log_file:
            if os.path.splitext(stats_log_file)[1] == '.gz':
                self._stats_log_fh = gzip.open(stats_log_file, 'w')                
            else:
                self._stats_log_fh = open(stats_log_file, 'w')
            self._stats_log_writer = csv.writer(self._stats_log_fh)

        # Daily stats are written to this file:
        self._daily_stats_log_file = daily_stats_log_file
        if daily_stats_log_file:
            if os.path.splitext(daily_stats_log_file)[1] == '.gz':
                self._daily_stats_log_fh = gzip.open(daily_stats_log_file, 'w')
            else:
                self._daily_stats_log_fh = open(daily_stats_log_file, 'w')
            self._daily_stats_log_writer = csv.writer(self._daily_stats_log_fh)

        # Values with which to initialize daily stats:
        self._init_daily_stats = {
            'num_orders': 0,
            'num_trades': 0,
            'trade_volume_total': 0.0,
            'trade_price_mean': 0.0,
            'trade_price_std': 0.0,
            'mean_order_interarrival_time': 0.0}

        # Daily stats are accumulated in this dictionary:
        self._curr_daily_stats = copy.copy(self._init_daily_stats)
        self._last_order_time = 0.0

        # Current day:
        self.day = None

        # Expiration date of securities; we use this to only consider securities
        # with a single expiration date (which is arbitrarily set to that of the
        # first order considered):
        self.expiry_date = ''
        
        # Order interarrival times are stored in this dictionary:
        self._order_interarrival_time = {}
        self._curr_order_interarrival_time = None

    def __del__(self):

        # Close all file handles before the object instance is cleaned up:
        try:
            self._events_log_fh.close()            
        except:
            pass
        try:
            self._stats_log_fh.close()
        except:
            pass
        try:
            self._daily_stats_log_fh.close()
        except:
            pass
        
    def clear_book(self):
        """
        Clear all outstanding limit orders from the book
        
        """

        self.logger.info('clearing outstanding limit orders')
        for d in self._book_data.keys():
            self._book_data[d].clear()
            self._book_prices[d].clear()
            self._price_level_stats[d].clear()
            self.day = None
        self._book_orders_to_price.clear()

    def process(self, df):
        """
        Process order data

        Parameters
        ----------
        df : pandas.DataFrame
            Each row of this DataFrame instance contains a single order.
            
        """
                
        for row in df.iterrows():
            order = row[1].to_dict()
            self.logger.info('processing order: %i (%s, %s)' % (order['order_number'],
                                                                order['trans_date'],
                                                                order['trans_time']))

            trans_date = datetime.datetime.strptime(order['trans_date'], '%m/%d/%Y')
            if self.day != trans_date.day:

                # Save the daily stats:
                if self._daily_stats_log_file and self.day is not None:
                   self.record_daily_stats(self.day)
                   
                # Reset the limit order book and trade volume variables when a new
                # day of orders begins:
                self.logger.info('new day - book reset')
                self.clear_book()
                self.day = trans_date.day
                self.logger.info('setting day: %s' % self.day)
                
                # Initialize last order time to the time of the first
                # order of the day:
                self._last_order_time = \
                  datetime.datetime.strptime(order['trans_date']+' '+\
                                             order['trans_time'],
                                             '%m/%d/%Y %H:%M:%S.%f')        
        
                # Reset variables used for accumulating daily stats:
                self._curr_daily_stats = \
                    copy.copy(self._init_daily_stats)

                # Reset variables used for saving last best book values:
                self._last_book_best_values = \
                    copy.copy(self._init_last_book_best_values)
                    
            # Restrict all orders processed to a single expiry date because
            # futures orders with different expiry dates are effectively
            # distinct securities insofar as the LOB is concerned:
            if not self.expiry_date:
                self.logger.info('setting expiry date: %s' % self.expiry_date)
                self.expiry_date = order['expiry_date']                
            else:
                if self.expiry_date != order['expiry_date']:
                    self.logger.info('skipping order %s with expiry date %s' % \
                                     (order['order_number'], order['expiry_date']))
                    continue
                    
            if order['activity_type'] == 1:
                self.add(order, 'Y')
            elif order['activity_type'] == 3:
                self.cancel(order)
            elif order['activity_type'] == 4:
                # XXX It seems that a few market orders are listed as modify orders;
                # temporarily treat them as add operations XXX                  
                if order['mkt_flag'] == 'Y':
                    self.add(order, 'Y')
                else:    
                    self.modify(order)
            else:
                raise ValueError('unrecognized activity type %i' % \
                                 order['activity_type'])                

    def create_level(self, indicator, price):
        """
        Create a new empty price level queue.

        Parameters
        ----------
        indicator : str
            Indicate whether to create a new buy ('B') or sell ('S') price
            level.
        price : float
            Price associated with new level.

        Returns
        -------
        od : odict
            New price level queue.
        
        """

        od = odict.odict()
        self._book_data[indicator][price] = od
        self._book_prices[indicator][price] = True        
        self._price_level_stats[indicator][price] = \
            copy.copy(self._init_price_level_stats)
        self.logger.info('created new price level: %s, %f' % (indicator, price))
        return od
    
    def delete_level(self, indicator, price):
        """
        Delete an existing price level.

        Parameters
        ----------
        indicator : str
            Indicate whether to delete a buy ('B') or sell ('S') price level.
        price : float
            Price associated with level.

        """
        
        self._book_data[indicator].pop(price)
        del self._book_prices[indicator][price]
        self._price_level_stats[indicator].pop(price)
        self.logger.info('deleted price level: %s, %f' % (indicator, price))

    def add_order(self, order):
        """
        Add an order to the book.

        Parameters
        ----------
        order : dict
            Order data.
            
        """

        order_number = order['order_number']
        indicator = order['buy_sell_indicator']
        price = order['limit_price']
        od = self.price_level(indicator, price)

        # Create a new price level queue if none exists for the order's
        # limit price:
        if od is None:
            self.logger.info('no matching price level found')
            od = self.create_level(indicator, price)
        
        od[order_number] = order
        self._book_orders_to_price[order_number] = od
        
        # Update price level stats:
        self._price_level_stats[indicator][price]['volume_original_total'] += \
            order['volume_original']
        self._price_level_stats[indicator][price]['volume_disclosed_total'] += \
            order['volume_disclosed']
            
        self.logger.info('added order: %s, %s, %s' % \
                            (order_number, indicator, price))    
            
    def delete_order(self, order):
        """
        Delete an order from the book.

        Parameters
        ----------
        order : dict
            Order data.

        Notes
        -----
        If the price level queue containing the specified order is empty after
        the order is deleted, it is removed from the limit order book.
        
        """

        order_number = order['order_number']
        try:            
            od = self._book_orders_to_price.pop(order_number)
        except:
            self.logger.info('order not found: %s' % order_number)
        else:
            order = od.pop(order_number)
            indicator = order['buy_sell_indicator']
            price = order['limit_price']

            # Update price level stats:
            self._price_level_stats[indicator][price]['volume_original_total'] -= \
                order['volume_original']
            self._price_level_stats[indicator][price]['volume_disclosed_total'] -= \
                order['volume_disclosed']

            self.logger.info('deleted order: %s, %s, %s' % \
                             (order_number, indicator, price))    
            
            # If the price level queue contains no other orders, remove it:
            if not od:
                self.delete_level(indicator, price)
            
    def best_bid_price(self):
        """
        Return the best bid price defined in the book.

        Returns
        -------
        order : dict
            Limit order with best (highest) bid price.

        Notes
        -----
        Assumes that there are no empty price levels in the book.
        
        """

        try:
            best_price = self._book_prices[BID].max()
        except:
            return None
        else:
            return best_price
        
    def best_bid_data(self):
        """
        Return data associated with the best bid

        Returns
        -------
        best_bid_price : float
            Bid price.
        volume_original_total : int
            Total original volume.
        volume_disclosed_total : int
            Total disclosed volume.
       
        """
        
        best_bid_price = self.best_bid_price()
        if best_bid_price is not None:
            volume_original_total = \
                self._price_level_stats[BID][best_bid_price]['volume_original_total']
            volume_disclosed_total = \
                self._price_level_stats[BID][best_bid_price]['volume_disclosed_total']
        else:
            volume_original_total = volume_disclosed_total = 0
        return best_bid_price, volume_original_total, volume_disclosed_total
    
    def best_ask_price(self):
        """
        Return the best ask price defined in the book.

        Returns
        -------
        order : dict
            Limit order with best (lowest) ask price.

        Notes
        -----
        Assumes that there are no empty price levels in the book.
        
        """

        try:
            best_price = self._book_prices[ASK].min()
        except:
            return None
        else:
            return best_price

    def best_ask_data(self):
        """
        Return data associated with the best ask.

        Returns
        -------
        ask_price : float
            Ask price.
        volume_original_total : int
            Total original volume.
        volume_disclosed_total : int
            Total disclosed volume.
       
        """
        
        best_ask_price = self.best_ask_price()
        if best_ask_price is not None:
            volume_original_total = \
                self._price_level_stats[ASK][best_ask_price]['volume_original_total']
            volume_disclosed_total = \
                self._price_level_stats[ASK][best_ask_price]['volume_disclosed_total']
        else:
            volume_original_total = volume_disclosed_total = 0
        return best_ask_price, volume_original_total, volume_disclosed_total
        
    def price_level(self, indicator, price):
        """
        Find a specified price level in the limit order book.
        
        Parameters
        ----------
        indicator : str
            Indicate whether to find a buy ('B') or sell ('S') price level.
        price : float
            Price associated with level.
        
        Returns
        -------
        od : odict.odict
            Ordered dict with matching price level.

        """

        # Validate buy/sell indicator:
        try:
            book = self._book_data[indicator]
        except KeyError:
            raise ValueError('invalid buy/sell indicator')

        # Look for price level queue:
        try:
            od = book[price]
        except KeyError:
            #self.logger.info('price level not found: %s, %f' % (indicator, price))
            return None
        else:
            #self.logger.info('price level found: %s, %f' % (indicator, price))
            return od

    def record_event(self, **event):
        """
        This routine saves the specified event information.

        Parameters
        ----------
        event : dict
            Event data.
            
        """

        # Each entry contains:
        # time, date, order number,
        # indicator (B or S), market order status (Y or N),
        # io status (Y or N), action (add, modify, cancel, trade), 
        # whether an order is original (Y) or generated by the LOB (N),
        # price associated with event
        # original volume associated with event, disclosed 
        # volume associated with event,
        # best bid, best bid original volume,
        # best ask, best ask original volume,

        # Accumulate stats for arriving original orders (i.e., NOT orders
        # that are generated in response to modify requests):
        if event['is_original'] == 'Y':
            self._original_event_counter += 1
            self._curr_daily_stats['num_orders'] += 1

            # Compute time since last order arrival:
            date_time = datetime.datetime.strptime(event['date']+' '+\
                                                   event['time'],
                                                   '%m/%d/%Y %H:%M:%S.%f')
            curr_interarrival_time = \
                (date_time-self._last_order_time).total_seconds()
            self._last_order_time = date_time
            if self._curr_daily_stats['num_orders'] == 1:
                self._curr_daily_stats['mean_order_interarrival_time'] = \
                    curr_interarrival_time
            else:
                N = float(self._curr_daily_stats['num_orders'])
                N_prev = N-1
                self._curr_daily_stats['mean_order_interarrival_time'] = \
                    self._curr_daily_stats['mean_order_interarrival_time']*(N_prev/N)+\
                    curr_interarrival_time/N
                    
        # Accumulate stats for generated trades:
        if event['action'] == 'trade':

            # Number of trades:
            self._curr_daily_stats['num_trades'] += 1

            # Total trade volume:
            self._curr_daily_stats['trade_volume_total'] += \
                event['volume_original']

            # Average trade price:
            if self._curr_daily_stats['num_trades'] == 1:                
                self._curr_daily_stats['trade_price_mean'] = \
                    event['price']
            else:
                N = float(self._curr_daily_stats['num_trades'])
                N_prev = N-1
                self._curr_daily_stats['trade_price_mean'] = \
                    (self._curr_daily_stats['trade_price_mean']*N_prev+\
                    event['price'])/N
                self._curr_daily_stats['trade_price_std'] = \
                  np.sqrt((self._curr_daily_stats['trade_price_std']**2*N_prev+\
                          (event['price']-self._curr_daily_stats['trade_price_mean'])**2)/N)

        if self._show_output:
            print '----------------------------------------'

            # Print last event:
            print self.event_to_row(event)
            
            # Print queue states:
            print 'sell queue:'
            self.print_book(SELL)
            print 'buy queue:'
            self.print_book(BUY)

        if self._events_log_file:

            # If sparse event logging is requested, check whether the event
            # action is a trade (which always occurs after some other action and
            # therefore never is associated with a change in the best bid or ask
            # values) or whether the best bid and ask prices or volume
            # have changed since the last event before recording the event:            
            # XXX Don't pay attention to the disclosed volume:
            if self._sparse_events:
                best_keys = ['best_bid_price', 'best_ask_price',
                            'best_bid_volume_original',
                            'best_ask_volume_original']
                if event['action'] == 'trade' or \
                    any([event[k] != self._last_book_best_values[k] for k in best_keys]):                
                    row = self.event_to_row(event)
                    self._events_log_writer.writerow(row)

                    # Update the last best values:
                    for k in best_keys:
                        self._last_book_best_values[k] = event[k]
            else:
                row = self.event_to_row(event)
                self._events_log_writer.writerow(row)
                
    def record_stats(self, t, d):
        """
        Record running stats.

        Parameters
        ----------
        t : str
            Time.
        d : str
            Date.
            
        """
        
        if self._stats_log_file:
            row = [t, d,
                   self._curr_daily_stats['num_orders'],
                   self._curr_daily_stats['num_trades'],
                   self._curr_daily_stats['trade_volume_total'],
                   self._curr_daily_stats['trade_price_mean'],
                   self._curr_daily_stats['trade_price_std'],
                   self._curr_daily_stats['mean_order_interarrival_time']]
            self._stats_log_writer.writerow(row)

    def record_daily_stats(self, d):
        """
        Record daily stats.

        Parameters
        ----------
        d : str
            Date.
                    
        """

        if self._daily_stats_log_file:
            row = [d,
                   self._curr_daily_stats['num_orders'],
                   self._curr_daily_stats['num_trades'],
                   self._curr_daily_stats['trade_volume_total'],
                   self._curr_daily_stats['trade_price_mean'],
                   self._curr_daily_stats['trade_price_std'],
                   self._curr_daily_stats['mean_order_interarrival_time']]
            self._daily_stats_log_writer.writerow(row)
            
    def add(self, new_order, is_original):
        """
        Add the specified order to the LOB.
        
        Parameters
        ----------
        new_order : dict
            Order to add.
        is_original : char
            'Y' if the order is original (i.e., not generated by the LOB in
            response to certain modification requests), 'N' otherwise.
            
        Notes
        -----        
        New orders are implicitly appended onto the end of each ordered dict.
        One can obtain the oldest order by popping the first entry in the dict.
        
        """

        best_bid_price, best_bid_volume_original, best_bid_volume_disclosed = \
          self.best_bid_data()
        best_ask_price, best_ask_volume_original, best_ask_volume_disclosed = \
          self.best_ask_data()
        event = \
          dict(time=new_order['trans_time'],
               date=new_order['trans_date'],
               order_number=new_order['order_number'],
               indicator=new_order['buy_sell_indicator'],
               mkt_flag=new_order['mkt_flag'],
               io_flag=new_order['io_flag'],
               action='add',
               is_original=is_original,               
               price=new_order['limit_price'],               
               volume_original=new_order['volume_original'],
               volume_disclosed=new_order['volume_disclosed'],
               best_bid_price=best_bid_price,
               best_bid_volume_original=best_bid_volume_original,
               best_ask_price=best_ask_price,
               best_ask_volume_original=best_ask_volume_original)

        # Retrieve data regarding the order to be added:
        new_indicator = new_order['buy_sell_indicator']
        volume_original = new_order['volume_original']
        volume_disclosed = new_order['volume_disclosed']

        self.logger.info('attempting add of order: %s, %s, %s, %f, %d, %d' % \
                         (new_order['order_number'], new_indicator, new_order['mkt_flag'],
                         new_order['limit_price'], volume_original,
                         volume_disclosed))
        
        # If the buy/sell order is a market order, check whether there is a
        # corresponding limit order in the book at the best ask/bid price:
        if new_order['mkt_flag'] == 'Y':
            while volume_original > 0:

                # Find the queue corresponding to the best bid/ask
                # price as appropriate; if no such queue exists
                # (because the buy/sell sections of the book don't
                # contain at least one buy/sell limit order), then
                # stop trying to match orders and discard the market order:
                if new_indicator == BUY:
                    buy_order = new_order
                    best_price = self.best_ask_price()
                    if best_price is None:
                        self.logger.info('no sell limit orders in book yet '
                                         '- stopping processing of market buy order')
                        break
                    od = self.price_level(ASK, best_price) 
                elif new_indicator == SELL:
                    sell_order = new_order
                    best_price = self.best_bid_price()
                    if best_price is None:
                        self.logger.info('no buy limit orders in book yet '
                                         '- stopping processing of market sell order')
                        break
                    od = self.price_level(BID, best_price)
                else:
                    RuntimeError('invalid buy/sell indicator')

                # If there is still residual volume but the best price is no
                # longer compatible with that of the arriving order, stop
                # trying to match orders:
                if new_indicator == BUY and best_price > new_order['limit_price']:
                    self.logger.info('best ask exceeds specified buy price')
                    break
                if new_indicator == SELL and best_price < new_order['limit_price']:
                    self.logger.info('best bid is below specified sell price')
                    break

                # Orders in the book that have explicitly disclosed (i.e.,
                # non-zero) volumes are assumed to actually be completely
                # hidden; therefore, they must be processed AFTER
                # orders with 0 disclosed volume. We therefore 
                # need to reorder the orders in the identified price level to
                # list all orders with 0 disclosed volumes before the others:
                order_number_list = []
                for order_number in od.keys():
                    if od[order_number]['volume_disclosed'] == 0:
                        order_number_list.append(order_number)
                for order_number in od.keys():
                    if od[order_number]['volume_disclosed'] > 0:
                        order_number_list.append(order_number)
                        
                # Move through the limit orders in the price level queue from
                # oldest to newest:
                for order_number in order_number_list:
                    curr_order = od[order_number]
                    if curr_order['buy_sell_indicator'] == BUY:
                        buy_order = curr_order
                    elif curr_order['buy_sell_indicator'] == SELL:
                        sell_order = curr_order
                    else:
                        RuntimeError('invalid buy/sell indicator')

                    # If a bid/ask limit order in the book has the same volume as
                    # that requested in the sell/buy market order, record a
                    # transaction and remove the limit order from the queue:
                    if curr_order['volume_original'] == volume_original:
                        self.logger.info('current limit order original volume '
                                         'vs. arriving market order original volume: '
                                         '%s = %s' % \
                                         (curr_order['volume_original'],
                                          volume_original))

                        # Record the add event:
                        self.record_event(**event)

                        # Record the trade event:
                        event['action'] = 'trade'
                        event['price'] = best_price
                        event['volume_original'] = volume_original
                        event['volume_disclosed'] = volume_disclosed
                        self.record_event(**event)

                        # Record running stats:
                        self.record_stats(event['time'], event['date'])
                        
                        self.delete_order(curr_order) 
                        volume_original = 0.0                 
                        break

                    # If a bid/ask limit order in the book has a greater volume
                    # than that requested in the sell/buy market order, record a
                    # transaction and decrement its volume accordingly:
                    elif curr_order['volume_original'] > volume_original:
                        self.logger.info('current limit order original volume '
                                         'vs. arriving market order original volume: '
                                         '%s > %s' % \
                                         (curr_order['volume_original'],
                                          volume_original))   

                        # Record the add event:
                        self.record_event(**event)

                        # Record the trade event:
                        event['action'] = 'trade'
                        event['price'] = best_price
                        event['volume_original'] = volume_original
                        event['volume_disclosed'] = volume_disclosed
                        self.record_event(**event)

                        # Record running stats:
                        self.record_stats(event['time'], event['date'])
                        
                        if new_order['io_flag'] == 'N':
                            self.logger.info('Non-IOC order - residual volume preserved')
                            curr_order['volume_original'] -= volume_original
                            self._price_level_stats[curr_order['buy_sell_indicator']][curr_order['limit_price']]['volume_original_total'] \
                                -= volume_original
                        else:
                            self.logger.info('IOC order - residual volume discarded')
                        volume_original = 0.0
                        break

                    # If the bid/ask limit order in the book has a volume that is
                    # below the requested sell/buy market order volume, continue
                    # removing orders from the queue until the entire requested
                    # volume has been satisfied:
                    elif curr_order['volume_original'] < volume_original:
                        self.logger.info('current limit order original volume '
                                         'vs. arriving market order original volume: '
                                         '%s < %s' % \
                                         (curr_order['volume_original'],
                                          volume_original))                  
                        trade = dict(trade_price=best_price,
                                     trade_quantity=curr_order['volume_original'],
                                     buy_order_number=buy_order['order_number'],
                                     sell_order_number=sell_order['order_number'])

                        # Record the add event:
                        self.record_event(**event)

                        # Record the trade event:
                        event['action'] = 'trade'
                        event['price'] = best_price
                        event['volume_original'] = curr_order['volume_original']
                        event['volume_disclosed'] = curr_order['volume_disclosed']
                        self.record_event(**event)

                        # Record running stats:
                        self.record_stats(event['time'], event['date'])
                        
                        volume_original -= curr_order['volume_original']
                        self.delete_order(curr_order)
                    else:

                        # This should never be reached:
                        pass

        elif new_order['mkt_flag'] == 'N':

            # Check whether the limit order is marketable:
            price = new_order['limit_price']
            marketable = True
            best_ask_price = self.best_ask_price()
            best_bid_price = self.best_bid_price()
            if new_indicator == BUY and best_ask_price is not None \
                   and price >= best_ask_price:
                self.logger.info('buy order is marketable')
                best_price = best_ask_price;
            elif new_indicator == SELL and best_bid_price is not None \
                   and price <= best_bid_price:
                self.logger.info('sell order is marketable')
                best_price = best_bid_price;
            else:
                marketable = False

            # If the limit order is not marketable, add it to the appropriate
            # price level queue in the limit order book:
            if not marketable:
                self.logger.info('order is not marketable')
                self.record_event(**event)
                self.add_order(new_order)
                
            # Try to match marketable orders with orders that are already in the
            # book:
            else:

                # If the requested volume in the order isn't completely
                # satisfied at the best price, recompute the best price and
                # try to satisfy the remainder:
                while volume_original > 0.0:

                    # Find the queue corresponding to the best bid/ask
                    # price as appropriate; if no such queue exists
                    # (because the buy/sell sections of the book don't
                    # contain at least one buy/sell limit order), then
                    # stop trying to match orders and save the limit order:                    
                    if new_indicator == BUY:
                        buy_order = new_order                    
                        best_price = self.best_ask_price()
                        if best_price is None:
                            self.logger.info('no sell limit orders in book yet '
                                             '- stopping processing of limit buy order')
                            self.add_order(new_order)
                            break
                        od = self.price_level(ASK, best_price)
                    elif new_indicator == SELL:
                        sell_order = new_order
                        best_price = self.best_bid_price()
                        if best_price is None:
                            self.logger.info('no buy limit orders in book yet '
                                             '- stopping processing of limit sell order')
                            self.add_order(new_order)
                        od = self.price_level(BID, best_price)
                    else:
                        RuntimeError('invalid buy/sell indicator')

                    # If there is still residual volume but the best price is no
                    # longer compatible with that of the arriving order, stop
                    # trying to match orders and save the residue as a new limit
                    # order:
                    if new_indicator == BUY and best_price > new_order['limit_price']:
                        self.logger.info('best ask exceeds specified buy price')
                        if new_order['io_flag'] == 'N':
                            new_order['volume_original'] = volume_original
                            self.add(new_order, 'N')
                        break
                    if new_indicator == SELL and best_price < new_order['limit_price']:
                        self.logger.info('best bid is below specified sell price')
                        if new_order['io_flag'] == 'N':
                            new_order['volume_original'] = volume_original
                            self.add(new_order, 'N')
                        break

                    # Orders in the book that have explicitly disclosed (i.e.,
                    # non-zero) volumes are assumed to actually be completely
                    # hidden; therefore, they must be processed AFTER
                    # orders with 0 disclosed volume. We therefore 
                    # need to reorder the orders in the identified price level to
                    # list all orders with 0 disclosed volumes before the others:
                    order_number_list = []
                    if od is not None:
                        for order_number in od.keys():
                            if od[order_number]['volume_disclosed'] == 0:
                                order_number_list.append(order_number)
                        for order_number in od.keys():
                            if od[order_number]['volume_disclosed'] > 0:
                                order_number_list.append(order_number)
                    
                    # Move through the limit orders in the price level queue from
                    # oldest to newest:
                    for order_number in order_number_list: 
                        curr_order = od[order_number]
                        if new_indicator == BUY:
                            sell_order = curr_order
                        elif new_indicator == SELL:
                            buy_order = curr_order
                        else:
                            RuntimeError('invalid buy/sell indicator')

                        # If a bid/ask limit order in the book has the same volume
                        # as that requested in the sell/buy limit order, record a
                        # transaction and remove the limit order from the queue:
                        if curr_order['volume_original'] == volume_original:
                            self.logger.info('current limit order original volume '
                                             'vs. arriving limit order original volume: '
                                             '%s = %s' % \
                                             (curr_order['volume_original'],
                                              volume_original))

                            # Record the add event:
                            self.record_event(**event)

                            # Record the trade event:
                            event['action'] = 'trade'
                            event['price'] = best_price
                            event['volume_original'] = volume_original
                            event['volume_disclosed'] = volume_disclosed
                            self.record_event(**event)

                            self.delete_order(curr_order)
                            volume_original = 0.0
                            break
                        
                        # If a bid/ask limit order in the book has a greater volume
                        # than that requested in the sell/buy limit order, record a
                        # transaction and decrement its volume accordingly:
                        elif curr_order['volume_original'] > volume_original:
                            self.logger.info('current limit order original volume '
                                             'vs. arriving limit order original volume: '
                                             '%s > %s' % \
                                             (curr_order['volume_original'],
                                              volume_original))

                            # Record the add event:
                            self.record_event(**event)

                            # Record the trade event:
                            event['action'] = 'trade'
                            event['price'] = best_price
                            event['volume_original'] = volume_original
                            event['volume_disclosed'] = volume_disclosed
                            self.record_event(**event)

                            # Record running stats:
                            self.record_stats(event['time'], event['date'])
                            
                            if new_order['io_flag'] == 'N':
                                self.logger.info('Non-IOC order - residual volume preserved')  
                                curr_order['volume_original'] -= volume_original
                                self._price_level_stats[curr_order['buy_sell_indicator']][curr_order['limit_price']]['volume_original_total'] \
                                  -= volume_original
    
                            else:
                                self.logger.info('IOC order - residual volume discarded')
                            volume_original = 0.0
                            break

                        # If the bid/ask limit order in the book has a volume
                        # that is below the requested sell/buy market order
                        # volume, continue removing orders from the queue until
                        # the entire requested volume has been satisfied:
                        elif curr_order['volume_original'] < volume_original:
                            self.logger.info('current limit order original volume '
                                             'vs. arriving limit order original volume: '
                                             '%s < %s' % \
                                             (curr_order['volume_original'],
                                              volume_original))

                            # Record the add event:
                            self.record_event(**event)

                            # Record the trade event:
                            event['action'] = 'trade'
                            event['price'] = best_price
                            event['volume_original'] = curr_order['volume_original']
                            event['volume_disclosed'] = curr_order['volume_disclosed']
                            self.record_event(**event)

                            # Record running stats:
                            self.record_stats(event['time'], event['date'])
                            
                            volume_original -= curr_order['volume_original']
                            self.delete_order(curr_order) 
                        else:

                            # This should never be reached:
                            pass                                            
        else:
            raise RuntimeError('invalid market order flag')
        
    def modify(self, new_order):
        """
        Modify the order with matching order number in the LOB.
        """

        best_bid_price, best_bid_volume_original, best_bid_volume_disclosed = \
          self.best_bid_data()
        best_ask_price, best_ask_volume_original, best_ask_volume_disclosed = \
          self.best_ask_data()
        event = \
          dict(time=new_order['trans_time'],
               date=new_order['trans_date'],
               order_number=new_order['order_number'],
               indicator=new_order['buy_sell_indicator'],
               mkt_flag=new_order['mkt_flag'],
               io_flag=new_order['io_flag'],
               is_original='Y',
               action='modify',               
               price=new_order['limit_price'],               
               volume_original=new_order['volume_original'],
               volume_disclosed=new_order['volume_disclosed'],
               best_bid_price=best_bid_price,
               best_bid_volume_original=best_bid_volume_original,
               best_ask_price=best_ask_price,
               best_ask_volume_original=best_ask_volume_original)

        self.logger.info('attempting modify of order: %s, %s' % \
                         (new_order['order_number'],
                          new_order['buy_sell_indicator']))
        
        # This exception should never be thrown:
        if new_order['mkt_flag'] == 'Y':
            raise ValueError('cannot modify market order')

        # A modify order contains the number of the existing order to modify and
        # a new limit price or quantity. We use the self._book_orders_to_price
        # dict to look up the existing order:
        book = self._book_data[new_order['buy_sell_indicator']]
        try:
            od = self._book_orders_to_price[new_order['order_number']]
        except:
            self.logger.info('order number %s not found' % new_order['order_number'])
        else:
            old_order = od[new_order['order_number']]
            
            # If the modify changes the price of an order, remove it and
            # then add the modified order to the appropriate price level queue:
            if new_order['limit_price'] != old_order['limit_price']:
                self.logger.info('modified order %i price from %f to %f: ' % \
                                 (new_order['order_number'],
                                  old_order['limit_price'],
                                  new_order['limit_price']))
                self.delete_order(old_order)                                   
                self.add(new_order, 'N')

            # If the modify reduces the original or disclosed volume of an
            # order, update it without altering where it is in the price level queue:
            elif new_order['volume_original'] < old_order['volume_original'] or \
                new_order['volume_disclosed'] < old_order['volume_disclosed']:
                self.logger.info('modified order %i (original, disclosed) volume '                    
                                 'from (%i, %i) to (%i, %i)' % \
                                 (new_order['order_number'],
                                  old_order['volume_original'], old_order['volume_disclosed'],
                                  new_order['volume_original'], new_order['volume_disclosed']))
                od[new_order['order_number']] = new_order

                # Update price level stats:
                self._price_level_stats[new_order['buy_sell_indicator']][new_order['limit_price']]['volume_original_total'] \
                    += -old_order['volume_original']+new_order['volume_original']
                self._price_level_stats[new_order['buy_sell_indicator']][new_order['limit_price']]['volume_disclosed_total'] \
                    += -old_order['volume_disclosed']+new_order['volume_disclosed']                
                
            # If the modify increases the original or disclosed volume of an
            # order, add a order containing the difference in volume between
            # the original and new orders:
            elif new_order['volume_original'] > old_order['volume_original'] or \
                new_order['volume_disclosed'] > old_order['volume_disclosed']:
                self.logger.info('modified order %i (original, disclosed) volume '
                                 'from (%i, %i) to (%i, %i)' % \
                                 (new_order['order_number'],
                                  old_order['volume_original'], old_order['volume_disclosed'],
                                  new_order['volume_original'], new_order['volume_disclosed']))
                new_order_modified = new_order.copy()
                new_order_modified['volume_original'] -= old_order['volume_original']
                new_order_modified['volume_disclosed'] -= old_order['volume_disclosed']
                self.add(new_order_modified, 'N')

                # Update price level stats:
                self._price_level_stats[new_order['buy_sell_indicator']][new_order['limit_price']]['volume_original_total'] \
                    += -old_order['volume_original']+new_order['volume_original']
                self._price_level_stats[new_order['buy_sell_indicator']][new_order['limit_price']]['volume_disclosed_total'] \
                    += -old_order['volume_disclosed']+new_order['volume_disclosed']                

            else:
                self.logger.info('undefined modify scenario')
                            
        self.record_event(**event)
        self.record_stats(event['time'], event['date'])
        
    def cancel(self, order):
        """
        Remove the order with matching order number from the LOB.

        Parameters
        ----------
        order : dict
            Order to cancel.

        """
                
        best_bid_price, best_bid_volume_original, best_bid_volume_disclosed = \
          self.best_bid_data()
        best_ask_price, best_ask_volume_original, best_ask_volume_disclosed = \
          self.best_ask_data()
        event = \
          dict(time=order['trans_time'],
               date=order['trans_date'],
               order_number=order['order_number'],
               indicator=order['buy_sell_indicator'],
               mkt_flag=order['mkt_flag'],
               io_flag=order['io_flag'],
               action='cancel',               
               is_original='Y',               
               price=order['limit_price'],               
               volume_original=order['volume_original'],
               volume_disclosed=order['volume_disclosed'],
               best_bid_price=best_bid_price,
               best_bid_volume_original=best_bid_volume_original,
               best_ask_price=best_ask_price,
               best_ask_volume_original=best_ask_volume_original)

        self.logger.info('attempting cancel of order %s' % order['order_number'])

        # Filter out cancellation orders that are listed as market orders:
        if order['mkt_flag'] == 'Y':
            self.logger.info('cannot cancel market order %s' % order['order_number'])
        else:
            self.delete_order(order)
        self.record_event(**event)
        self.record_stats(event['time'], event['date'])
        
    def print_book(self, indicator):
        """
        Print parts of the specified book dictionary in a neat manner.
        """

        book = self._book_data[indicator]
        prices = self._book_prices[indicator]
        for price in prices.keys():
            print '%06.2f: ' % price,            
            for order_number in book[price]:
                order = book[price][order_number]
                print '(%s,%s)' % (order['volume_original'], order['volume_disclosed']),
            print ''

    def event_to_row(self, event):
        """
        Convert a dictionary containing event data into a row for output to CSV.
        """
        
        row = [event['time'],
               event['date'],
               event['order_number'],
               event['indicator'],
               event['mkt_flag'],
               event['action'],
               event['is_original'],               
               event['price'],               
               event['volume_original'],
               event['volume_disclosed'],
               event['best_bid_price'],
               event['best_bid_volume_original'],
               event['best_ask_price'],
               event['best_ask_volume_original']]
        return row
    
    def print_daily_stats(self):
        """
        Display daily stats.
        """
        
        print '--------------------------------------------'
        print 'Number of orders:             ', self._curr_daily_stats['num_orders']
        print 'Number of trades:             ', self._curr_daily_stats['num_trades']
        print 'Total trade volume:           ', self._curr_daily_stats['trade_volume_total']
        print 'Mean trade price:             ', self._curr_daily_stats['trade_price_mean']
        print 'Trade price STD:              ', self._curr_daily_stats['trade_price_std']
        print 'Mean order interarrival time: ', self._curr_daily_stats['mean_order_interarrival_time']