// Order book micro-benchmark: std::map<price, std::list> vs flat price-level array
// with intrusive FIFO lists and a pooled order store. Same synthetic workload for both.
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <vector>

struct Op { uint8_t type; uint8_t side; uint32_t px; uint32_t qty; uint64_t id; };
// type: 0 = add, 1 = cancel, 2 = aggressive market order (match)

std::vector<Op> make_ops(size_t n, uint64_t seed) {
  std::mt19937_64 rng(seed);
  std::vector<Op> ops; ops.reserve(n);
  std::vector<uint64_t> live; live.reserve(n);
  uint64_t next = 1;
  std::uniform_int_distribution<int> dpx(-50, 50), dq(1, 100), dop(0, 99);
  for (size_t i = 0; i < n; ++i) {
    int r = dop(rng);
    if (r < 60 || live.empty()) {            // 60% adds near the touch
      uint8_t side = rng() & 1;
      uint32_t px = 10000 + (side ? 1 : -1) * (1 + std::abs(dpx(rng)) / 2);
      ops.push_back({0, side, px, (uint32_t)dq(rng), next});
      live.push_back(next++);
    } else if (r < 90) {                     // 30% cancels of a random live id
      size_t k = rng() % live.size();
      ops.push_back({1, 0, 0, 0, live[k]});
      live[k] = live.back(); live.pop_back();
    } else {                                 // 10% market orders
      ops.push_back({2, (uint8_t)(rng() & 1), 0, (uint32_t)dq(rng), 0});
    }
  }
  return ops;
}

// ---------- Baseline: std::map of std::list ----------
struct MapBook {
  struct O { uint64_t id; uint32_t qty; };
  std::map<uint32_t, std::list<O>, std::greater<uint32_t>> bids;
  std::map<uint32_t, std::list<O>> asks;
  struct Loc { uint8_t side; uint32_t px; std::list<O>::iterator it; };
  std::unordered_map<uint64_t, Loc> index;
  uint64_t filled = 0;
  void add(const Op& o) {
    if (o.side) { auto& l = asks[o.px]; l.push_back({o.id, o.qty}); index[o.id] = {1, o.px, std::prev(l.end())}; }
    else        { auto& l = bids[o.px]; l.push_back({o.id, o.qty}); index[o.id] = {0, o.px, std::prev(l.end())}; }
  }
  void cancel(uint64_t id) {
    auto f = index.find(id); if (f == index.end()) return;
    auto& L = f->second;
    if (L.side) { auto m = asks.find(L.px); m->second.erase(L.it); if (m->second.empty()) asks.erase(m); }
    else        { auto m = bids.find(L.px); m->second.erase(L.it); if (m->second.empty()) bids.erase(m); }
    index.erase(f);
  }
  template <class M> void sweep(M& book, uint32_t qty) {
    while (qty && !book.empty()) {
      auto lvl = book.begin(); auto& l = lvl->second;
      while (qty && !l.empty()) {
        auto& o = l.front(); uint32_t q = std::min(qty, o.qty);
        o.qty -= q; qty -= q; filled += q;
        if (!o.qty) { index.erase(o.id); l.pop_front(); }
      }
      if (l.empty()) book.erase(lvl);
    }
  }
  void market(const Op& o) { if (o.side) sweep(bids, o.qty); else sweep(asks, o.qty); }
};

// ---------- Flat book: price-indexed levels, intrusive FIFO, pooled orders ----------
struct FlatBook {
  static constexpr uint32_t BASE = 9000, N = 2048, NIL = 0xffffffff;
  struct O { uint64_t id; uint32_t qty, next, prev, px; uint8_t side; };
  struct Lvl { uint32_t head = NIL, tail = NIL; };
  std::vector<O> pool; std::vector<uint32_t> freelist;
  Lvl lv[2][N];
  uint32_t best[2] = {0, N};               // best bid index (max), best ask index (min)
  std::unordered_map<uint64_t, uint32_t> index;
  uint64_t filled = 0;
  FlatBook() { pool.reserve(1 << 20); index.reserve(1 << 20); }
  uint32_t alloc() { if (!freelist.empty()) { auto i = freelist.back(); freelist.pop_back(); return i; } pool.emplace_back(); return pool.size() - 1; }
  void add(const Op& o) {
    uint32_t i = alloc(), p = o.px - BASE; O& n = pool[i];
    n = {o.id, o.qty, NIL, NIL, p, o.side};
    Lvl& L = lv[o.side][p];
    if (L.tail == NIL) L.head = L.tail = i; else { pool[L.tail].next = i; n.prev = L.tail; L.tail = i; }
    if (o.side) { if (p < best[1]) best[1] = p; } else { if (p > best[0]) best[0] = p; }
    index.emplace(o.id, i);
  }
  void unlink(uint32_t i) {
    O& n = pool[i]; Lvl& L = lv[n.side][n.px];
    if (n.prev != NIL) pool[n.prev].next = n.next; else L.head = n.next;
    if (n.next != NIL) pool[n.next].prev = n.prev; else L.tail = n.prev;
    freelist.push_back(i);
  }
  void cancel(uint64_t id) { auto f = index.find(id); if (f == index.end()) return; unlink(f->second); index.erase(f); }
  void market(const Op& o) {
    uint8_t s = o.side ? 0 : 1;              // buy hits asks (1), sell hits bids (0)
    uint32_t qty = o.qty;
    while (qty) {
      // advance best pointer past empty levels
      if (s) { while (best[1] < N && lv[1][best[1]].head == NIL) ++best[1]; if (best[1] >= N) return; }
      else   { while (best[0] > 0 && lv[0][best[0]].head == NIL) --best[0]; if (lv[0][best[0]].head == NIL) return; }
      Lvl& L = lv[s][best[s]];
      while (qty && L.head != NIL) {
        uint32_t i = L.head; O& n = pool[i]; uint32_t q = std::min(qty, n.qty);
        n.qty -= q; qty -= q; filled += q;
        if (!n.qty) { index.erase(n.id); unlink(i); }
      }
    }
  }
};

template <class B> double run(const std::vector<Op>& ops, std::vector<double>& lat, uint64_t& filled) {
  B b; lat.clear(); lat.reserve(ops.size());
  auto t0 = std::chrono::steady_clock::now();
  for (auto& o : ops) {
    auto a = std::chrono::steady_clock::now();
    if (o.type == 0) b.add(o); else if (o.type == 1) b.cancel(o.id); else b.market(o);
    lat.push_back(std::chrono::duration<double, std::nano>(std::chrono::steady_clock::now() - a).count());
  }
  filled = b.filled;
  return std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
}

template <class B> double run_tp(const std::vector<Op>& ops, uint64_t& filled) {
  B b;
  auto t0 = std::chrono::steady_clock::now();
  for (auto& o : ops) { if (o.type == 0) b.add(o); else if (o.type == 1) b.cancel(o.id); else b.market(o); }
  filled = b.filled;
  return std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
}

int main() {
  {
    auto ops = make_ops(2'000'000, 7);
    for (int which = 0; which < 2; ++which) {
      std::vector<double> r; uint64_t f = 0;
      for (int k = 0; k < 5; ++k) r.push_back(which ? run_tp<FlatBook>(ops, f) : run_tp<MapBook>(ops, f));
      std::sort(r.begin(), r.end());
      std::printf("throughput %-8s median of 5: %.2fM ops/s (%.1f ns/op avg)\n", which ? "flat" : "std::map", 2e6 / r[2] / 1e6, r[2] / 2e6 * 1e9);
    }
  }
  const size_t N = 2'000'000;
  auto ops = make_ops(N, 42);
  for (int rep = 0; rep < 2; ++rep) {
    for (int which = 0; which < 2; ++which) {
      std::vector<double> lat; uint64_t filled; double s;
      s = which == 0 ? run<MapBook>(ops, lat, filled) : run<FlatBook>(ops, lat, filled);
      std::sort(lat.begin(), lat.end());
      auto P = [&](double p) { return lat[std::min(lat.size() - 1, (size_t)(p * lat.size()))]; };
      if (rep == 1)
        std::printf("%-8s ops/s=%.2fM  p50=%.0fns p99=%.0fns p99.9=%.0fns  filled=%llu\n",
                    which ? "flat" : "std::map", N / s / 1e6, P(.5), P(.99), P(.999), (unsigned long long)filled);
    }
  }
}
