order_book.hpp

Go to the documentation of this file.

#ifndef ISIMUD_EXCHANGES_ORDER_BOOK_ORDER_BOOK_HPP
#define ISIMUD_EXCHANGES_ORDER_BOOK_ORDER_BOOK_HPP
/******************************************************************************
** Copyright © 2020 by J.M.McGuiness, isimud@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "../common/config.h"
 
#include "core/exception.hpp"
 
#include <algorithm>
/**
 * \todo Update when this is official.
 */
#include <experimental/iterator>
#include <list>
#include <map>
#include <queue>
 
namespace isimud { namespace ISIMUD_VER_NAMESPACE {
 
   /// A simple implementation of a price/time limit order book.
   /**
    * Exchange matching engines use an order book to match orders from buyers and sellers.
    * 
    * \note A production-quality program would place this in shared memory (to be regularly flushed to disk) e.g. to be used in case the order book process crashes, so that the data is not lost, and can be recovered.
    * 
    * \note The algorithmic complexities all assume that the number of symbols is much smaller than the number of trades on the book. If this is not the case, then the log(num_symbols) lookup may dominate, but this is unlikely.
    */
   template<class MsgType>
   class order_book {
   public:
      using msg_details_t=MsgType;
      using price_t=typename msg_details_t::Price_t;
      using quantity_t=typename msg_details_t::Quantity_t;
      using side_t=typename msg_details_t::Side;
      using symbol_t=typename msg_details_t::SecurityID_t;
      using order_t=typename msg_details_t::NewOrder_t;
      using execution_t=typename msg_details_t::ExecutionReport;
      using lock_traits=libjmmcg::ppd::api_lock_traits<libjmmcg::ppd::platform_api, libjmmcg::ppd::heavyweight_threading>;
      using exception_type=lock_traits::exception_type;
 
   private:
      using sequence_number_t=typename msg_details_t::SeqNum_t;
      /**
       * This is needed to add a monotonically increasing number, that effectively orders the trades. This ordering is needed to permit the match() algorithm to select the correct price that the trade occurred at.
       */
      struct internal_order final : public order_t {
         using element_type=order_t;
 
         const sequence_number_t sequence_number_;
 
         internal_order(sequence_number_t seq, element_type const &o) noexcept(true);
         internal_order(internal_order const &) noexcept(true)=default;
 
         /**
          * Needed because of implementation details regarding gcc & std::vector requiring assignment.
          */
         internal_order &operator=(internal_order const &o) noexcept(true);
      };
 
   public:
      using trades_t=std::vector<execution_t>;
      /**
       * We push_back(), so orders towards the beginning of the collection are older than those towards the end.
       * 
       * \todo Consider a faster collection, such as boost circular buffer for something similar.
       */
      using orders_by_time=std::list<internal_order>;
      struct cheapest_t {
         using value_type=orders_by_time;
 
         bool operator()(value_type const &l, value_type const &r) const noexcept(true);
      };
      struct most_expensive_t {
         using value_type=orders_by_time;
 
         bool operator()(value_type const &l, value_type const &r) const noexcept(true);
      };
      struct cheapest_orders_by_time_t final : public std::priority_queue<orders_by_time, std::vector<orders_by_time>, cheapest_t> {
         using base_t=std::priority_queue<orders_by_time, std::vector<orders_by_time>, cheapest_t>;
         using reference=typename base_t::reference;
         using value_type=typename base_t::value_type;
 
         using base_t::top;
         bool empty() const noexcept(true);
         reference top() noexcept(true);
         void insert(typename value_type::value_type::element_type const &o, sequence_number_t &sequence_number);
         void erase(typename value_type::value_type::element_type const &o);
 
         std::ostream &to_stream(std::ostream &os) const;
      };
      class most_expensive_by_time_t final : public std::priority_queue<orders_by_time, std::vector<orders_by_time>, most_expensive_t> {
      public:
         using base_t=std::priority_queue<orders_by_time, std::vector<orders_by_time>, most_expensive_t>;
         using reference=typename base_t::reference;
         using value_type=typename base_t::value_type;
 
         using base_t::top;
         bool empty() const noexcept(true);
         reference top() noexcept(true);
         void insert(typename value_type::value_type::element_type const &o, sequence_number_t &sequence_number);
         void erase(typename value_type::value_type::element_type const &o);
 
         std::ostream &to_stream(std::ostream &os) const;
      };
 
      order_book();
      ~order_book();
 
      /**
       * Algorithmic complexity: O(1)
       * 
       * \return  False if there are any trades that have been placed, otherwise true.
***       */
      bool empty() const noexcept(true);
      /**
       * Algorithmic complexity: O(num_symbols*n) where num_symbols is the total number of symbols that have been placed and  n is the total number of orders in all the books.
       * 
       * \return  False if any there are no bids or no asks, otherwise the result of comparing the top prices.
       */
      bool is_crossed() const noexcept(true);
      /**
       * Algorithmic complexity: O(n) where n is the total number of orders in all the books.
       * 
       * \return  The spread for the specified symbol, if there are prices on both sides, otherwise zero.
       */
      price_t agreed_spread(symbol_t const &symbol) const noexcept(true);
 
      /// Place the requested order in the book.
      /**
       * This may leave the order book in a crossed state, i.e. there may be available trades, so match() may have to be called after calling place().
       * 
       * Algorithmic complexity: O(log(n)) where n is the total number of orders in all the books.
       * 
       * \see cancel(), is_crossed(), match()
       */
      void place(order_t const &order) noexcept(false);
 
      /// Remove the specified order from the order book.
      /**
       * Algorithmic complexity: O(n^2) where n is the total number of orders in all the books.
       * 
       * \see place(), match()
       */
      void cancel(order_t const &order) noexcept(false);
 
      /// Return all possible trades, also uncrossing the order book.
      /**
       * After calling place() this function may need to be called as the order book may be crossed and thus potential executions that only match() can discover.
       * 
       * Algorithmic complexity: O(num_executions*num_symbols*log(n)) where:
       * -# num_executions is the total number of executions that would result,
       * -# num_symbols is the total number of symbols that have been placed,
       * -# n is the largest number of orders in all the books across the symbols.
       * 
       * \return  All possible trades; non-empty if crossed, otherwise empty.
       * 
       * \see place(), cancel()
       */
      trades_t match();
 
      /**
       * Algorithmic complexity: O(n) where n is the total number of orders in all the books.
       */
      template<class MsgTypes1>
      friend std::ostream &operator<<(std::ostream &os, order_book<MsgTypes1> const &o);
 
   private:
      struct open_orders_t {
         most_expensive_by_time_t open_ask_orders{};  ///< Orders for sale.
         cheapest_orders_by_time_t open_bid_orders{}; ///< Orders for purchase/buying.
 
         typename cheapest_orders_by_time_t::value_type::value_type const &best_bid() const noexcept(true);
         typename most_expensive_by_time_t::value_type::value_type const &best_ask() const noexcept(true);
      };
      struct order_id_t {
         using msg_order_id_t=typename msg_details_t::ClientOrderID_t;
 
         msg_order_id_t order_id_;
 
         bool operator==(order_id_t const &) noexcept(true);
 
         order_id_t &operator++() noexcept(true);
         [[nodiscard]] order_id_t operator++(int) noexcept(true);
      };
      /**
       * \todo May want to use a std::unordered_map (or equivalent). I need to benchmark to identify if this is a real issue.
       */
      using all_open_orders_t=std::map<symbol_t, open_orders_t>;
 
      sequence_number_t sequence_number_{};
      order_id_t order_id_{};
      all_open_orders_t all_open_orders_;
   };
 
} }
 
#include "order_book_impl.hpp"
 
#endif