Design an Inventory and Order Management System.

# inventory.py, part 1: stock, reservations and the allocation strategy
from __future__ import annotations

import threading
from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum


class OutOfStock(Exception):
    pass


class IllegalTransition(Exception):
    pass


class ResState(Enum):
    HELD = 1       # counted against stock, expires if the order is not paid in time
    CONFIRMED = 2  # paid: no expiry, waiting to ship
    RELEASED = 3   # given back to stock
    SHIPPED = 4    # fully shipped


@dataclass
class Stock:  # one SKU in one warehouse
    on_hand: int = 0   # units physically on the shelf
    reserved: int = 0  # units promised to orders, not yet shipped

    def available(self) -> int:
        return max(0, self.on_hand - self.reserved)


@dataclass
class Reservation:  # a claim on units of one SKU in one warehouse, for one order
    rid: int
    order_id: str
    sku: str
    wh: str
    qty: int
    expires_at: int  # seconds on the caller's clock; ignored once CONFIRMED
    state: ResState = ResState.HELD


class AllocationStrategy(ABC):
    @abstractmethod
    def allocate(self, free: dict[str, int], qty: int) -> list[tuple[str, int]] | None:
        """free: warehouse -> units available. Return [(warehouse, units)] summing to qty, or None."""


class FewestShipments(AllocationStrategy):
    def allocate(self, free, qty):
        fits = sorted((a, wh) for wh, a in free.items() if a >= qty)
        if fits:
            return [(fits[0][1], qty)]  # best fit: the smallest warehouse that holds it all
        plan, need = [], qty
        for a, wh in sorted(((a, wh) for wh, a in free.items()), key=lambda x: (-x[0], x[1])):
            take = min(a, need)
            plan.append((wh, take))
            need -= take
            if need == 0:
                return plan
        return None


class NearestFirst(AllocationStrategy):
    def __init__(self, order: list[str]) -> None:
        self.order = order  # warehouses, nearest to the customer first

    def allocate(self, free, qty):
        plan, need = [], qty
        for wh in self.order:
            take = min(free.get(wh, 0), need)
            if take:
                plan.append((wh, take))
                need -= take
        return plan if need == 0 else None

// InventoryDemo.java: stock per warehouse, reservations that expire, and an order state machine
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.locks.ReentrantLock;

class OutOfStock extends RuntimeException {
    OutOfStock(String message) { super(message); }
}

class IllegalTransition extends RuntimeException {
    IllegalTransition(String message) { super(message); }
}

enum ResState {
    HELD,       // counted against stock, expires if the order is not paid in time
    CONFIRMED,  // paid: no expiry, waiting to ship
    RELEASED,   // given back to stock
    SHIPPED     // fully shipped
}

/** One SKU in one warehouse. */
final class Stock {
    int onHand;   // units physically on the shelf
    int reserved; // units promised to orders, not yet shipped

    int available() { return Math.max(0, onHand - reserved); }
}

/** A claim on units of one SKU in one warehouse, for one order. */
final class Reservation {
    final int rid;
    final String orderId, sku, wh;
    int qty;
    final int expiresAt; // seconds on the caller's clock; ignored once CONFIRMED
    ResState state = ResState.HELD;

    Reservation(int rid, String orderId, String sku, String wh, int qty, int expiresAt) {
        this.rid = rid;
        this.orderId = orderId;
        this.sku = sku;
        this.wh = wh;
        this.qty = qty;
        this.expiresAt = expiresAt;
    }
}

record Take(String wh, int qty) {}

interface AllocationStrategy {
    /** free: warehouse -> units available. Returns takes summing to qty, or null. */
    List<Take> allocate(Map<String, Integer> free, int qty);
}

final class FewestShipments implements AllocationStrategy {
    public List<Take> allocate(Map<String, Integer> free, int qty) {
        String fit = null;
        for (var e : free.entrySet()) { // best fit: the smallest warehouse that holds it all
            if (e.getValue() < qty) continue;
            if (fit == null || e.getValue() < free.get(fit)
                    || (e.getValue().equals(free.get(fit)) && e.getKey().compareTo(fit) < 0)) fit = e.getKey();
        }
        if (fit != null) return List.of(new Take(fit, qty));
        List<Map.Entry<String, Integer>> byBig = new ArrayList<>(free.entrySet());
        byBig.sort(Comparator.<Map.Entry<String, Integer>>comparingInt(e -> -e.getValue()).thenComparing(Map.Entry::getKey));
        List<Take> plan = new ArrayList<>();
        int need = qty;
        for (var e : byBig) {
            int take = Math.min(e.getValue(), need);
            plan.add(new Take(e.getKey(), take));
            need -= take;
            if (need == 0) return plan;
        }
        return null;
    }
}

final class NearestFirst implements AllocationStrategy {
    private final List<String> order; // warehouses, nearest to the customer first

    NearestFirst(List<String> order) { this.order = order; }

    public List<Take> allocate(Map<String, Integer> free, int qty) {
        List<Take> plan = new ArrayList<>();
        int need = qty;
        for (String wh : order) {
            int take = Math.min(free.getOrDefault(wh, 0), need);
            if (take > 0) {
                plan.add(new Take(wh, take));
                need -= take;
            }
        }
        return need == 0 ? plan : null;
    }
}

// inventory.cpp: stock per warehouse, reservations that expire, and an order state machine
#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <mutex>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct OutOfStock : std::runtime_error { using std::runtime_error::runtime_error; };
struct IllegalTransition : std::runtime_error { using std::runtime_error::runtime_error; };

enum class ResState {
    Held,       // counted against stock, expires if the order is not paid in time
    Confirmed,  // paid: no expiry, waiting to ship
    Released,   // given back to stock
    Shipped     // fully shipped
};

struct Stock {  // one SKU in one warehouse
    int onHand = 0;    // units physically on the shelf
    int reserved = 0;  // units promised to orders, not yet shipped
    int available() const { return std::max(0, onHand - reserved); }
};

struct Reservation {  // a claim on units of one SKU in one warehouse, for one order
    int rid;
    std::string orderId, sku, wh;
    int qty;
    int expiresAt;  // seconds on the caller's clock; ignored once Confirmed
    ResState state = ResState::Held;
};

using Take = std::pair<std::string, int>;  // (warehouse, units)

class AllocationStrategy {
public:
    virtual ~AllocationStrategy() = default;
    // free: warehouse -> units available. Returns takes summing to qty; empty when it cannot be met.
    virtual std::vector<Take> allocate(const std::map<std::string, int>& free, int qty) const = 0;
};

class FewestShipments : public AllocationStrategy {
public:
    std::vector<Take> allocate(const std::map<std::string, int>& free, int qty) const override {
        const std::pair<const std::string, int>* fit = nullptr;
        for (const auto& e : free) {  // best fit: the smallest warehouse that holds it all (map order breaks ties)
            if (e.second >= qty && (!fit || e.second < fit->second)) fit = &e;
        }
        if (fit) return {{fit->first, qty}};
        std::vector<Take> byBig(free.begin(), free.end());
        std::stable_sort(byBig.begin(), byBig.end(), [](const Take& a, const Take& b) { return a.second > b.second; });
        std::vector<Take> plan;
        int need = qty;
        for (const auto& e : byBig) {
            int take = std::min(e.second, need);
            plan.push_back({e.first, take});
            need -= take;
            if (need == 0) return plan;
        }
        return {};
    }
};

class NearestFirst : public AllocationStrategy {
public:
    explicit NearestFirst(std::vector<std::string> order) : order_(std::move(order)) {}  // nearest to the customer first

    std::vector<Take> allocate(const std::map<std::string, int>& free, int qty) const override {
        std::vector<Take> plan;
        int need = qty;
        for (const auto& wh : order_) {
            auto it = free.find(wh);
            int take = std::min(it == free.end() ? 0 : it->second, need);
            if (take > 0) {
                plan.push_back({wh, take});
                need -= take;
            }
        }
        return need == 0 ? plan : std::vector<Take>{};
    }

private:
    std::vector<std::string> order_;
};

// inventory.js: stock per warehouse, reservations that expire, and an order state machine
class OutOfStock extends Error {}
class IllegalTransition extends Error {}

const ResState = Object.freeze({
  HELD: "HELD", // counted against stock, expires if the order is not paid in time
  CONFIRMED: "CONFIRMED", // paid: no expiry, waiting to ship
  RELEASED: "RELEASED", // given back to stock
  SHIPPED: "SHIPPED", // fully shipped
});

class Stock { // one SKU in one warehouse
  constructor() {
    this.onHand = 0; // units physically on the shelf
    this.reserved = 0; // units promised to orders, not yet shipped
  }

  available() {
    return Math.max(0, this.onHand - this.reserved);
  }
}

// a claim on units of one SKU in one warehouse, for one order
class Reservation {
  constructor(rid, orderId, sku, wh, qty, expiresAt) {
    Object.assign(this, { rid, orderId, sku, wh, qty, expiresAt }); // expiresAt: seconds on the caller's clock; ignored once CONFIRMED
    this.state = ResState.HELD;
  }
}

class AllocationStrategy {
  // free: Map warehouse -> units available. Return [[warehouse, units], ...] summing to qty, or null.
  allocate(free, qty) { throw new Error("not implemented"); }
}

class FewestShipments extends AllocationStrategy {
  allocate(free, qty) {
    const fits = [...free].filter(([, a]) => a >= qty).sort((x, y) => x[1] - y[1] || (x[0] < y[0] ? -1 : 1));
    if (fits.length) return [[fits[0][0], qty]]; // best fit: the smallest warehouse that holds it all
    const plan = [];
    let need = qty;
    for (const [wh, a] of [...free].sort((x, y) => y[1] - x[1] || (x[0] < y[0] ? -1 : 1))) {
      const take = Math.min(a, need);
      plan.push([wh, take]);
      need -= take;
      if (need === 0) return plan;
    }
    return null;
  }
}

class NearestFirst extends AllocationStrategy {
  constructor(order) {
    super();
    this.order = order; // warehouses, nearest to the customer first
  }

  allocate(free, qty) {
    const plan = [];
    let need = qty;
    for (const wh of this.order) {
      const take = Math.min(free.get(wh) ?? 0, need);
      if (take) {
        plan.push([wh, take]);
        need -= take;
      }
    }
    return need === 0 ? plan : null;
  }
}

# part 2: the inventory: one lock, reserve-then-confirm, expiry on the caller's clock
class Inventory:
    def __init__(self, strategy: AllocationStrategy, ttl: int = 300) -> None:
        self.strategy, self.ttl = strategy, ttl
        self.stock: dict[tuple[str, str], Stock] = {}  # (sku, warehouse) -> Stock
        self.holds: dict[str, list[Reservation]] = {}  # order id -> its reservations
        self._next = 1
        self._lock = threading.RLock()  # check-then-reserve must be one step

    def _at(self, sku: str, wh: str) -> Stock:
        return self.stock.setdefault((sku, wh), Stock())

    def receive(self, wh: str, sku: str, qty: int) -> None:  # a delivery from a supplier
        with self._lock:
            self._at(sku, wh).on_hand += qty

    def adjust(self, wh: str, sku: str, delta: int) -> None:  # a stock count: damage, loss, found units
        with self._lock:
            self._at(sku, wh).on_hand += delta

    def available(self, sku: str) -> int:
        with self._lock:
            return sum(s.available() for (k, _), s in self.stock.items() if k == sku)

    def _release(self, r: Reservation) -> None:
        self._at(r.sku, r.wh).reserved -= r.qty
        r.state = ResState.RELEASED

    def expire(self, now: int) -> int:  # lazy: called before every reserve and confirm, no timer thread
        with self._lock:
            lapsed = [r for rs in self.holds.values() for r in rs if r.state is ResState.HELD and r.expires_at <= now]
            for r in lapsed:
                self._release(r)
            return len(lapsed)

    def reserve(self, order_id: str, lines: dict[str, int], now: int) -> list[Reservation]:
        with self._lock:
            old = self.holds.get(order_id)
            if old and any(r.state is not ResState.RELEASED for r in old):
                return old  # a retried request gets the same holds, not new ones
            self.expire(now)
            plans = []  # plan every line first; touch nothing until all of them fit
            for sku, qty in lines.items():
                free = {wh: s.available() for (k, wh), s in self.stock.items() if k == sku and s.available() > 0}
                plan = self.strategy.allocate(free, qty)
                if plan is None:
                    raise OutOfStock(f"{sku}: wanted {qty}, {sum(free.values())} available")
                plans.append((sku, plan))
            made = []
            for sku, plan in plans:
                for wh, qty in plan:
                    made.append(Reservation(self._next, order_id, sku, wh, qty, now + self.ttl))
                    self._next += 1
                    self._at(sku, wh).reserved += qty
            self.holds[order_id] = made
            return made

    def confirm(self, order_id: str, now: int) -> bool:  # payment arrived: stop the clock, or say it is too late
        with self._lock:
            self.expire(now)
            rs = self.holds.get(order_id, [])
            if not rs or any(r.state is not ResState.HELD for r in rs):
                return False
            for r in rs:
                r.state = ResState.CONFIRMED
            return True

    def release(self, order_id: str) -> None:
        with self._lock:
            for r in self.holds.get(order_id, []):
                if r.state in (ResState.HELD, ResState.CONFIRMED):
                    self._release(r)

    def ship(self, order_id: str) -> int:  # what is physically there, not what was promised; returns units sent
        with self._lock:
            sent = 0
            for r in self.holds.get(order_id, []):
                if r.state is not ResState.CONFIRMED:
                    continue
                s = self._at(r.sku, r.wh)
                n = min(r.qty, max(0, s.on_hand))
                s.on_hand -= n
                s.reserved -= n
                r.qty -= n
                sent += n
                if r.qty == 0:
                    r.state = ResState.SHIPPED
            return sent

    def pending(self, order_id: str) -> int:  # units still owed on this order
        with self._lock:
            return sum(r.qty for r in self.holds.get(order_id, []) if r.state is ResState.CONFIRMED)

/** The inventory: one lock, reserve-then-confirm, expiry on the caller's clock. */
final class Inventory {
    final AllocationStrategy strategy;
    final int ttl;
    final Map<String, Stock> stock = new TreeMap<>(); // "sku@warehouse" -> Stock
    final Map<String, List<Reservation>> holds = new HashMap<>(); // order id -> its reservations
    private int next = 1;
    private final ReentrantLock lock = new ReentrantLock(); // check-then-reserve must be one step

    Inventory(AllocationStrategy strategy, int ttl) {
        this.strategy = strategy;
        this.ttl = ttl;
    }

    private Stock at(String sku, String wh) { return stock.computeIfAbsent(sku + "@" + wh, k -> new Stock()); }

    void receive(String wh, String sku, int qty) { // a delivery from a supplier
        lock.lock();
        try { at(sku, wh).onHand += qty; } finally { lock.unlock(); }
    }

    void adjust(String wh, String sku, int delta) { // a stock count: damage, loss, found units
        lock.lock();
        try { at(sku, wh).onHand += delta; } finally { lock.unlock(); }
    }

    int available(String sku) {
        lock.lock();
        try {
            int total = 0;
            for (var e : stock.entrySet()) if (e.getKey().startsWith(sku + "@")) total += e.getValue().available();
            return total;
        } finally { lock.unlock(); }
    }

    private void release(Reservation r) {
        at(r.sku, r.wh).reserved -= r.qty;
        r.state = ResState.RELEASED;
    }

    int expire(int now) { // lazy: called before every reserve and confirm, no timer thread
        lock.lock();
        try {
            List<Reservation> lapsed = new ArrayList<>();
            for (var rs : holds.values()) {
                for (Reservation r : rs) if (r.state == ResState.HELD && r.expiresAt <= now) lapsed.add(r);
            }
            for (Reservation r : lapsed) release(r);
            return lapsed.size();
        } finally { lock.unlock(); }
    }

    List<Reservation> reserve(String orderId, Map<String, Integer> lines, int now) {
        lock.lock();
        try {
            List<Reservation> old = holds.get(orderId);
            if (old != null && old.stream().anyMatch(r -> r.state != ResState.RELEASED)) {
                return old; // a retried request gets the same holds, not new ones
            }
            expire(now);
            Map<String, List<Take>> plans = new LinkedHashMap<>(); // plan every line first; touch nothing until all fit
            for (var line : lines.entrySet()) {
                String sku = line.getKey();
                Map<String, Integer> free = new HashMap<>();
                for (var e : stock.entrySet()) {
                    if (e.getKey().startsWith(sku + "@") && e.getValue().available() > 0) {
                        free.put(e.getKey().substring(sku.length() + 1), e.getValue().available());
                    }
                }
                List<Take> plan = strategy.allocate(free, line.getValue());
                if (plan == null) {
                    int total = free.values().stream().mapToInt(Integer::intValue).sum();
                    throw new OutOfStock(sku + ": wanted " + line.getValue() + ", " + total + " available");
                }
                plans.put(sku, plan);
            }
            List<Reservation> made = new ArrayList<>();
            for (var p : plans.entrySet()) {
                for (Take t : p.getValue()) {
                    made.add(new Reservation(next++, orderId, p.getKey(), t.wh(), t.qty(), now + ttl));
                    at(p.getKey(), t.wh()).reserved += t.qty();
                }
            }
            holds.put(orderId, made);
            return made;
        } finally { lock.unlock(); }
    }

    boolean confirm(String orderId, int now) { // payment arrived: stop the clock, or say it is too late
        lock.lock();
        try {
            expire(now);
            List<Reservation> rs = holds.getOrDefault(orderId, List.of());
            if (rs.isEmpty() || rs.stream().anyMatch(r -> r.state != ResState.HELD)) return false;
            for (Reservation r : rs) r.state = ResState.CONFIRMED;
            return true;
        } finally { lock.unlock(); }
    }

    void release(String orderId) {
        lock.lock();
        try {
            for (Reservation r : holds.getOrDefault(orderId, List.of())) {
                if (r.state == ResState.HELD || r.state == ResState.CONFIRMED) release(r);
            }
        } finally { lock.unlock(); }
    }

    int ship(String orderId) { // what is physically there, not what was promised; returns units sent
        lock.lock();
        try {
            int sent = 0;
            for (Reservation r : holds.getOrDefault(orderId, List.of())) {
                if (r.state != ResState.CONFIRMED) continue;
                Stock s = at(r.sku, r.wh);
                int n = Math.min(r.qty, Math.max(0, s.onHand));
                s.onHand -= n;
                s.reserved -= n;
                r.qty -= n;
                sent += n;
                if (r.qty == 0) r.state = ResState.SHIPPED;
            }
            return sent;
        } finally { lock.unlock(); }
    }

    int pending(String orderId) { // units still owed on this order
        lock.lock();
        try {
            int owed = 0;
            for (Reservation r : holds.getOrDefault(orderId, List.of())) if (r.state == ResState.CONFIRMED) owed += r.qty;
            return owed;
        } finally { lock.unlock(); }
    }
}

// The inventory: one lock, reserve-then-confirm, expiry on the caller's clock.
class Inventory {
public:
    Inventory(std::unique_ptr<AllocationStrategy> strategy, int ttl) : strategy_(std::move(strategy)), ttl_(ttl) {}

    void receive(const std::string& wh, const std::string& sku, int qty) {  // a delivery from a supplier
        std::lock_guard<std::recursive_mutex> g(lock_);
        at(sku, wh).onHand += qty;
    }

    void adjust(const std::string& wh, const std::string& sku, int delta) {  // a stock count: damage, loss, found units
        std::lock_guard<std::recursive_mutex> g(lock_);
        at(sku, wh).onHand += delta;
    }

    int available(const std::string& sku) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        int total = 0;
        for (const auto& e : stock) if (e.first.first == sku) total += e.second.available();
        return total;
    }

    int expire(int now) {  // lazy: called before every reserve and confirm, no timer thread
        std::lock_guard<std::recursive_mutex> g(lock_);
        int lapsed = 0;
        for (auto& entry : holds) {
            for (auto& r : entry.second) {
                if (r.state == ResState::Held && r.expiresAt <= now) {
                    release(r);
                    lapsed++;
                }
            }
        }
        return lapsed;
    }

    const std::vector<Reservation>& reserve(const std::string& orderId, const std::map<std::string, int>& lines, int now) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        auto old = holds.find(orderId);
        if (old != holds.end() && std::any_of(old->second.begin(), old->second.end(),
                                              [](const Reservation& r) { return r.state != ResState::Released; })) {
            return old->second;  // a retried request gets the same holds, not new ones
        }
        expire(now);
        std::vector<std::pair<std::string, std::vector<Take>>> plans;  // plan every line first; touch nothing until all fit
        for (const auto& line : lines) {
            std::map<std::string, int> free;
            int total = 0;
            for (const auto& e : stock) {
                if (e.first.first == line.first && e.second.available() > 0) {
                    free[e.first.second] = e.second.available();
                    total += e.second.available();
                }
            }
            auto plan = strategy_->allocate(free, line.second);
            if (plan.empty()) {
                throw OutOfStock(line.first + ": wanted " + std::to_string(line.second) + ", " + std::to_string(total) + " available");
            }
            plans.push_back({line.first, plan});
        }
        std::vector<Reservation> made;
        for (const auto& p : plans) {
            for (const auto& t : p.second) {
                made.push_back({next_++, orderId, p.first, t.first, t.second, now + ttl_});
                at(p.first, t.first).reserved += t.second;
            }
        }
        return holds[orderId] = made;
    }

    bool confirm(const std::string& orderId, int now) {  // payment arrived: stop the clock, or say it is too late
        std::lock_guard<std::recursive_mutex> g(lock_);
        expire(now);
        auto it = holds.find(orderId);
        if (it == holds.end() || it->second.empty()) return false;
        for (const auto& r : it->second) if (r.state != ResState::Held) return false;
        for (auto& r : it->second) r.state = ResState::Confirmed;
        return true;
    }

    void releaseOrder(const std::string& orderId) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        for (auto& r : holds[orderId]) {
            if (r.state == ResState::Held || r.state == ResState::Confirmed) release(r);
        }
    }

    int ship(const std::string& orderId) {  // what is physically there, not what was promised; returns units sent
        std::lock_guard<std::recursive_mutex> g(lock_);
        int sent = 0;
        for (auto& r : holds[orderId]) {
            if (r.state != ResState::Confirmed) continue;
            Stock& s = at(r.sku, r.wh);
            int n = std::min(r.qty, std::max(0, s.onHand));
            s.onHand -= n;
            s.reserved -= n;
            r.qty -= n;
            sent += n;
            if (r.qty == 0) r.state = ResState::Shipped;
        }
        return sent;
    }

    int pending(const std::string& orderId) {  // units still owed on this order
        std::lock_guard<std::recursive_mutex> g(lock_);
        int owed = 0;
        for (const auto& r : holds[orderId]) if (r.state == ResState::Confirmed) owed += r.qty;
        return owed;
    }

    std::map<std::pair<std::string, std::string>, Stock> stock;  // (sku, warehouse) -> Stock
    std::map<std::string, std::vector<Reservation>> holds;       // order id -> its reservations

private:
    Stock& at(const std::string& sku, const std::string& wh) { return stock[{sku, wh}]; }

    void release(Reservation& r) {
        at(r.sku, r.wh).reserved -= r.qty;
        r.state = ResState::Released;
    }

    std::unique_ptr<AllocationStrategy> strategy_;
    int ttl_;
    int next_ = 1;
    std::recursive_mutex lock_;  // check-then-reserve must be one step
};

/** The inventory: reserve-then-confirm, expiry on the caller's clock. (No lock: JS runs one call at a time.) */
class Inventory {
  constructor(strategy, ttl = 300) {
    this.strategy = strategy;
    this.ttl = ttl;
    this.stock = new Map(); // "sku@warehouse" -> Stock
    this.holds = new Map(); // order id -> its reservations
    this.next = 1;
  }

  #at(sku, wh) {
    const key = `${sku}@${wh}`;
    if (!this.stock.has(key)) this.stock.set(key, new Stock());
    return this.stock.get(key);
  }

  receive(wh, sku, qty) { this.#at(sku, wh).onHand += qty; } // a delivery from a supplier

  adjust(wh, sku, delta) { this.#at(sku, wh).onHand += delta; } // a stock count: damage, loss, found units

  available(sku) {
    let total = 0;
    for (const [key, s] of this.stock) if (key.startsWith(`${sku}@`)) total += s.available();
    return total;
  }

  #release(r) {
    this.#at(r.sku, r.wh).reserved -= r.qty;
    r.state = ResState.RELEASED;
  }

  expire(now) { // lazy: called before every reserve and confirm, no timer
    const lapsed = [...this.holds.values()].flat().filter((r) => r.state === ResState.HELD && r.expiresAt <= now);
    lapsed.forEach((r) => this.#release(r));
    return lapsed.length;
  }

  reserve(orderId, lines, now) {
    const old = this.holds.get(orderId);
    if (old?.some((r) => r.state !== ResState.RELEASED)) return old; // a retried request gets the same holds, not new ones
    this.expire(now);
    const plans = []; // plan every line first; touch nothing until all of them fit
    for (const [sku, qty] of Object.entries(lines)) {
      const free = new Map();
      for (const [key, s] of this.stock) {
        if (key.startsWith(`${sku}@`) && s.available() > 0) free.set(key.slice(sku.length + 1), s.available());
      }
      const plan = this.strategy.allocate(free, qty);
      if (!plan) {
        const total = [...free.values()].reduce((a, b) => a + b, 0);
        throw new OutOfStock(`${sku}: wanted ${qty}, ${total} available`);
      }
      plans.push([sku, plan]);
    }
    const made = [];
    for (const [sku, plan] of plans) {
      for (const [wh, qty] of plan) {
        made.push(new Reservation(this.next++, orderId, sku, wh, qty, now + this.ttl));
        this.#at(sku, wh).reserved += qty;
      }
    }
    this.holds.set(orderId, made);
    return made;
  }

  confirm(orderId, now) { // payment arrived: stop the clock, or say it is too late
    this.expire(now);
    const rs = this.holds.get(orderId) ?? [];
    if (rs.length === 0 || rs.some((r) => r.state !== ResState.HELD)) return false;
    rs.forEach((r) => { r.state = ResState.CONFIRMED; });
    return true;
  }

  release(orderId) {
    for (const r of this.holds.get(orderId) ?? []) {
      if (r.state === ResState.HELD || r.state === ResState.CONFIRMED) this.#release(r);
    }
  }

  ship(orderId) { // what is physically there, not what was promised; returns units sent
    let sent = 0;
    for (const r of this.holds.get(orderId) ?? []) {
      if (r.state !== ResState.CONFIRMED) continue;
      const s = this.#at(r.sku, r.wh);
      const n = Math.min(r.qty, Math.max(0, s.onHand));
      s.onHand -= n;
      s.reserved -= n;
      r.qty -= n;
      sent += n;
      if (r.qty === 0) r.state = ResState.SHIPPED;
    }
    return sent;
  }

  pending(orderId) { // units still owed on this order
    return (this.holds.get(orderId) ?? []).filter((r) => r.state === ResState.CONFIRMED).reduce((a, r) => a + r.qty, 0);
  }
}

# part 3: the order state machine and the service that drives it
class OrderState(Enum):
    NEW = 1
    RESERVED = 2
    PAID = 3
    PARTIALLY_SHIPPED = 4
    SHIPPED = 5
    CANCELLED = 6
    EXPIRED = 7
    REJECTED = 8


S = OrderState
TRANSITIONS = {  # (state, event) -> next state; anything not listed is illegal
    (S.NEW, "reserved"): S.RESERVED,
    (S.NEW, "rejected"): S.REJECTED,
    (S.RESERVED, "paid"): S.PAID,
    (S.RESERVED, "expired"): S.EXPIRED,
    (S.RESERVED, "cancel"): S.CANCELLED,
    (S.PAID, "ship_some"): S.PARTIALLY_SHIPPED,
    (S.PAID, "ship_all"): S.SHIPPED,
    (S.PAID, "cancel"): S.CANCELLED,
    (S.PARTIALLY_SHIPPED, "ship_some"): S.PARTIALLY_SHIPPED,
    (S.PARTIALLY_SHIPPED, "ship_all"): S.SHIPPED,
}


class Order:
    def __init__(self, oid: str, lines: dict[str, int]) -> None:
        self.oid, self.lines, self.state = oid, lines, S.NEW

    def fire(self, event: str) -> None:
        nxt = TRANSITIONS.get((self.state, event))
        if nxt is None:
            raise IllegalTransition(f"{self.oid}: {event} while {self.state.name}")
        self.state = nxt


class OrderService:
    def __init__(self, inventory: Inventory) -> None:
        self.inv = inventory
        self.orders: dict[str, Order] = {}
        self._lock = threading.RLock()

    def place(self, oid: str, lines: dict[str, int], now: int) -> Order:
        with self._lock:
            order = self.orders.setdefault(oid, Order(oid, lines))
            if order.state is not S.NEW:
                return order  # a retried place() is not a second order
            try:
                self.inv.reserve(oid, lines, now)
                order.fire("reserved")
            except OutOfStock:
                order.fire("rejected")
                raise
            return order

    def pay(self, oid: str, now: int) -> str:
        with self._lock:
            order = self.orders[oid]
            if order.state is S.PAID:
                return "paid"  # a retried payment callback: nothing to do
            if order.state is S.EXPIRED:
                return "refund"  # the money arrived after the hold lapsed
            if order.state is S.RESERVED and not self.inv.confirm(oid, now):
                order.fire("expired")
                return "refund"
            order.fire("paid")
            return "paid"

    def fulfil(self, oid: str) -> Order:
        with self._lock:
            order = self.orders[oid]
            if (order.state, "ship_some") not in TRANSITIONS:
                raise IllegalTransition(f"{oid}: ship while {order.state.name}")
            sent = self.inv.ship(oid)
            if self.inv.pending(oid) == 0:
                order.fire("ship_all")
            elif sent:
                order.fire("ship_some")
            return order

    def cancel(self, oid: str) -> None:
        with self._lock:
            order = self.orders[oid]
            order.fire("cancel")
            self.inv.release(oid)

enum OrderState { NEW, RESERVED, PAID, PARTIALLY_SHIPPED, SHIPPED, CANCELLED, EXPIRED, REJECTED }

final class Order {
    static final Map<String, OrderState> TRANSITIONS = Map.ofEntries( // "STATE/event" -> next state; anything else is illegal
            Map.entry("NEW/reserved", OrderState.RESERVED),
            Map.entry("NEW/rejected", OrderState.REJECTED),
            Map.entry("RESERVED/paid", OrderState.PAID),
            Map.entry("RESERVED/expired", OrderState.EXPIRED),
            Map.entry("RESERVED/cancel", OrderState.CANCELLED),
            Map.entry("PAID/ship_some", OrderState.PARTIALLY_SHIPPED),
            Map.entry("PAID/ship_all", OrderState.SHIPPED),
            Map.entry("PAID/cancel", OrderState.CANCELLED),
            Map.entry("PARTIALLY_SHIPPED/ship_some", OrderState.PARTIALLY_SHIPPED),
            Map.entry("PARTIALLY_SHIPPED/ship_all", OrderState.SHIPPED));

    final String oid;
    final Map<String, Integer> lines;
    OrderState state = OrderState.NEW;

    Order(String oid, Map<String, Integer> lines) {
        this.oid = oid;
        this.lines = lines;
    }

    void fire(String event) {
        OrderState nxt = TRANSITIONS.get(state + "/" + event);
        if (nxt == null) throw new IllegalTransition(oid + ": " + event + " while " + state);
        state = nxt;
    }
}

final class OrderService {
    final Inventory inv;
    final Map<String, Order> orders = new HashMap<>();
    private final ReentrantLock lock = new ReentrantLock();

    OrderService(Inventory inv) { this.inv = inv; }

    Order place(String oid, Map<String, Integer> lines, int now) {
        lock.lock();
        try {
            Order order = orders.computeIfAbsent(oid, k -> new Order(oid, lines));
            if (order.state != OrderState.NEW) return order; // a retried place() is not a second order
            try {
                inv.reserve(oid, lines, now);
                order.fire("reserved");
            } catch (OutOfStock e) {
                order.fire("rejected");
                throw e;
            }
            return order;
        } finally { lock.unlock(); }
    }

    String pay(String oid, int now) {
        lock.lock();
        try {
            Order order = orders.get(oid);
            if (order.state == OrderState.PAID) return "paid"; // a retried payment callback: nothing to do
            if (order.state == OrderState.EXPIRED) return "refund"; // the money arrived after the hold lapsed
            if (order.state == OrderState.RESERVED && !inv.confirm(oid, now)) {
                order.fire("expired");
                return "refund";
            }
            order.fire("paid");
            return "paid";
        } finally { lock.unlock(); }
    }

    Order fulfil(String oid) {
        lock.lock();
        try {
            Order order = orders.get(oid);
            if (!Order.TRANSITIONS.containsKey(order.state + "/ship_some")) {
                throw new IllegalTransition(oid + ": ship while " + order.state);
            }
            int sent = inv.ship(oid);
            if (inv.pending(oid) == 0) order.fire("ship_all");
            else if (sent > 0) order.fire("ship_some");
            return order;
        } finally { lock.unlock(); }
    }

    void cancel(String oid) {
        lock.lock();
        try {
            orders.get(oid).fire("cancel");
            inv.release(oid);
        } finally { lock.unlock(); }
    }
}

enum class OrderState { New, Reserved, Paid, PartiallyShipped, Shipped, Cancelled, Expired, Rejected };

std::string name(OrderState s) {
    static const char* names[] = {"NEW", "RESERVED", "PAID", "PARTIALLY_SHIPPED", "SHIPPED", "CANCELLED", "EXPIRED", "REJECTED"};
    return names[static_cast<int>(s)];
}

using S = OrderState;
const std::map<std::pair<OrderState, std::string>, OrderState> TRANSITIONS = {  // (state, event) -> next; anything else is illegal
    {{S::New, "reserved"}, S::Reserved},
    {{S::New, "rejected"}, S::Rejected},
    {{S::Reserved, "paid"}, S::Paid},
    {{S::Reserved, "expired"}, S::Expired},
    {{S::Reserved, "cancel"}, S::Cancelled},
    {{S::Paid, "ship_some"}, S::PartiallyShipped},
    {{S::Paid, "ship_all"}, S::Shipped},
    {{S::Paid, "cancel"}, S::Cancelled},
    {{S::PartiallyShipped, "ship_some"}, S::PartiallyShipped},
    {{S::PartiallyShipped, "ship_all"}, S::Shipped},
};

struct Order {
    std::string oid;
    std::map<std::string, int> lines;
    OrderState state = OrderState::New;

    void fire(const std::string& event) {
        auto it = TRANSITIONS.find({state, event});
        if (it == TRANSITIONS.end()) throw IllegalTransition(oid + ": " + event + " while " + name(state));
        state = it->second;
    }
};

class OrderService {
public:
    explicit OrderService(Inventory& inv) : inv_(inv) {}

    Order& place(const std::string& oid, const std::map<std::string, int>& lines, int now) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        Order& order = orders.try_emplace(oid, Order{oid, lines}).first->second;
        if (order.state != OrderState::New) return order;  // a retried place() is not a second order
        try {
            inv_.reserve(oid, lines, now);
            order.fire("reserved");
        } catch (const OutOfStock&) {
            order.fire("rejected");
            throw;
        }
        return order;
    }

    std::string pay(const std::string& oid, int now) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        Order& order = orders.at(oid);
        if (order.state == OrderState::Paid) return "paid";  // a retried payment callback: nothing to do
        if (order.state == OrderState::Expired) return "refund";  // the money arrived after the hold lapsed
        if (order.state == OrderState::Reserved && !inv_.confirm(oid, now)) {
            order.fire("expired");
            return "refund";
        }
        order.fire("paid");
        return "paid";
    }

    Order& fulfil(const std::string& oid) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        Order& order = orders.at(oid);
        if (!TRANSITIONS.count({order.state, "ship_some"})) throw IllegalTransition(oid + ": ship while " + name(order.state));
        int sent = inv_.ship(oid);
        if (inv_.pending(oid) == 0) order.fire("ship_all");
        else if (sent > 0) order.fire("ship_some");
        return order;
    }

    void cancel(const std::string& oid) {
        std::lock_guard<std::recursive_mutex> g(lock_);
        orders.at(oid).fire("cancel");
        inv_.releaseOrder(oid);
    }

    std::map<std::string, Order> orders;

private:
    Inventory& inv_;
    std::recursive_mutex lock_;
};

const TRANSITIONS = { // "STATE/event" -> next state; anything not listed is illegal
  "NEW/reserved": "RESERVED",
  "NEW/rejected": "REJECTED",
  "RESERVED/paid": "PAID",
  "RESERVED/expired": "EXPIRED",
  "RESERVED/cancel": "CANCELLED",
  "PAID/ship_some": "PARTIALLY_SHIPPED",
  "PAID/ship_all": "SHIPPED",
  "PAID/cancel": "CANCELLED",
  "PARTIALLY_SHIPPED/ship_some": "PARTIALLY_SHIPPED",
  "PARTIALLY_SHIPPED/ship_all": "SHIPPED",
};

class Order {
  constructor(oid, lines) {
    this.oid = oid;
    this.lines = lines;
    this.state = "NEW";
  }

  fire(event) {
    const next = TRANSITIONS[`${this.state}/${event}`];
    if (!next) throw new IllegalTransition(`${this.oid}: ${event} while ${this.state}`);
    this.state = next;
  }
}

class OrderService {
  constructor(inventory) {
    this.inv = inventory;
    this.orders = new Map();
  }

  place(oid, lines, now) {
    if (!this.orders.has(oid)) this.orders.set(oid, new Order(oid, lines));
    const order = this.orders.get(oid);
    if (order.state !== "NEW") return order; // a retried place() is not a second order
    try {
      this.inv.reserve(oid, lines, now);
      order.fire("reserved");
    } catch (e) {
      if (e instanceof OutOfStock) order.fire("rejected");
      throw e;
    }
    return order;
  }

  pay(oid, now) {
    const order = this.orders.get(oid);
    if (order.state === "PAID") return "paid"; // a retried payment callback: nothing to do
    if (order.state === "EXPIRED") return "refund"; // the money arrived after the hold lapsed
    if (order.state === "RESERVED" && !this.inv.confirm(oid, now)) {
      order.fire("expired");
      return "refund";
    }
    order.fire("paid");
    return "paid";
  }

  fulfil(oid) {
    const order = this.orders.get(oid);
    if (!TRANSITIONS[`${order.state}/ship_some`]) throw new IllegalTransition(`${oid}: ship while ${order.state}`);
    const sent = this.inv.ship(oid);
    if (this.inv.pending(oid) === 0) order.fire("ship_all");
    else if (sent > 0) order.fire("ship_some");
    return order;
  }

  cancel(oid) {
    this.orders.get(oid).fire("cancel");
    this.inv.release(oid);
  }
}

# part 4: two warehouses, four orders
if __name__ == "__main__":
    inv = Inventory(FewestShipments(), ttl=300)
    svc = OrderService(inv)
    inv.receive("W1", "A", 5)
    inv.receive("W2", "A", 3)
    inv.receive("W1", "B", 2)

    o1 = svc.place("o1", {"A": 6, "B": 1}, now=0)
    print("o1", o1.state.name, "[" + ", ".join(f"({r.sku}, {r.wh}, {r.qty})" for r in inv.holds["o1"]) + "]")
    try:
        svc.place("o2", {"A": 3}, now=10)
    except OutOfStock as e:
        print("o2 rejected:", e)
    svc.place("o3", {"A": 2}, now=20)
    print("A available:", inv.available("A"))
    print("o1 pay:", svc.pay("o1", now=100), "| o3 pay at 400:", svc.pay("o3", now=400))
    print("A available:", inv.available("A"), "| o3", svc.orders["o3"].state.name)

    inv.adjust("W1", "A", -2)  # a stock count finds two units damaged
    print("o1 fulfil 1:", svc.fulfil("o1").state.name, "| owed", inv.pending("o1"))
    inv.receive("W1", "A", 4)
    print("o1 fulfil 2:", svc.fulfil("o1").state.name, "| owed", inv.pending("o1"))
    try:
        svc.cancel("o1")
    except IllegalTransition as e:
        print("cancel refused:", e)
    for (sku, wh), s in sorted(inv.stock.items()):
        print(f"  {sku}@{wh}: on_hand {s.on_hand}, reserved {s.reserved}")

public class InventoryDemo {
    // two warehouses, four orders
    public static void main(String[] args) {
        Inventory inv = new Inventory(new FewestShipments(), 300);
        OrderService svc = new OrderService(inv);
        inv.receive("W1", "A", 5);
        inv.receive("W2", "A", 3);
        inv.receive("W1", "B", 2);

        Map<String, Integer> lines1 = new LinkedHashMap<>();
        lines1.put("A", 6);
        lines1.put("B", 1);
        Order o1 = svc.place("o1", lines1, 0);
        StringBuilder held = new StringBuilder();
        for (Reservation r : inv.holds.get("o1")) held.append(held.length() > 0 ? ", " : "").append("(" + r.sku + ", " + r.wh + ", " + r.qty + ")");
        System.out.println("o1 " + o1.state + " [" + held + "]");
        try {
            svc.place("o2", Map.of("A", 3), 10);
        } catch (OutOfStock e) {
            System.out.println("o2 rejected: " + e.getMessage());
        }
        svc.place("o3", Map.of("A", 2), 20);
        System.out.println("A available: " + inv.available("A"));
        System.out.println("o1 pay: " + svc.pay("o1", 100) + " | o3 pay at 400: " + svc.pay("o3", 400));
        System.out.println("A available: " + inv.available("A") + " | o3 " + svc.orders.get("o3").state);

        inv.adjust("W1", "A", -2); // a stock count finds two units damaged
        System.out.println("o1 fulfil 1: " + svc.fulfil("o1").state + " | owed " + inv.pending("o1"));
        inv.receive("W1", "A", 4);
        System.out.println("o1 fulfil 2: " + svc.fulfil("o1").state + " | owed " + inv.pending("o1"));
        try {
            svc.cancel("o1");
        } catch (IllegalTransition e) {
            System.out.println("cancel refused: " + e.getMessage());
        }
        for (var e : inv.stock.entrySet()) {
            String[] k = e.getKey().split("@");
            System.out.println("  " + k[0] + "@" + k[1] + ": on_hand " + e.getValue().onHand + ", reserved " + e.getValue().reserved);
        }
    }
}

// two warehouses, four orders
int main() {
    Inventory inv(std::make_unique<FewestShipments>(), 300);
    OrderService svc(inv);
    inv.receive("W1", "A", 5);
    inv.receive("W2", "A", 3);
    inv.receive("W1", "B", 2);

    Order& o1 = svc.place("o1", {{"A", 6}, {"B", 1}}, 0);
    std::string held;
    for (const auto& r : inv.holds["o1"]) held += (held.empty() ? "" : ", ") + ("(" + r.sku + ", " + r.wh + ", " + std::to_string(r.qty) + ")");
    std::cout << "o1 " << name(o1.state) << " [" << held << "]\n";
    try {
        svc.place("o2", {{"A", 3}}, 10);
    } catch (const OutOfStock& e) {
        std::cout << "o2 rejected: " << e.what() << "\n";
    }
    svc.place("o3", {{"A", 2}}, 20);
    std::cout << "A available: " << inv.available("A") << "\n";
    std::string p1 = svc.pay("o1", 100), p3 = svc.pay("o3", 400);
    std::cout << "o1 pay: " << p1 << " | o3 pay at 400: " << p3 << "\n";
    std::cout << "A available: " << inv.available("A") << " | o3 " << name(svc.orders.at("o3").state) << "\n";

    inv.adjust("W1", "A", -2);  // a stock count finds two units damaged
    std::cout << "o1 fulfil 1: " << name(svc.fulfil("o1").state) << " | owed " << inv.pending("o1") << "\n";
    inv.receive("W1", "A", 4);
    std::cout << "o1 fulfil 2: " << name(svc.fulfil("o1").state) << " | owed " << inv.pending("o1") << "\n";
    try {
        svc.cancel("o1");
    } catch (const IllegalTransition& e) {
        std::cout << "cancel refused: " << e.what() << "\n";
    }
    for (const auto& e : inv.stock) {
        std::cout << "  " << e.first.first << "@" << e.first.second << ": on_hand " << e.second.onHand << ", reserved " << e.second.reserved << "\n";
    }
}

// two warehouses, four orders
const inv = new Inventory(new FewestShipments(), 300);
const svc = new OrderService(inv);
inv.receive("W1", "A", 5);
inv.receive("W2", "A", 3);
inv.receive("W1", "B", 2);

const o1 = svc.place("o1", { A: 6, B: 1 }, 0);
console.log("o1", o1.state, "[" + inv.holds.get("o1").map((r) => `(${r.sku}, ${r.wh}, ${r.qty})`).join(", ") + "]");
try {
  svc.place("o2", { A: 3 }, 10);
} catch (e) {
  if (!(e instanceof OutOfStock)) throw e;
  console.log("o2 rejected:", e.message);
}
svc.place("o3", { A: 2 }, 20);
console.log("A available:", inv.available("A"));
console.log("o1 pay:", svc.pay("o1", 100), "| o3 pay at 400:", svc.pay("o3", 400));
console.log("A available:", inv.available("A"), "| o3", svc.orders.get("o3").state);

inv.adjust("W1", "A", -2); // a stock count finds two units damaged
console.log("o1 fulfil 1:", svc.fulfil("o1").state, "| owed", inv.pending("o1"));
inv.receive("W1", "A", 4);
console.log("o1 fulfil 2:", svc.fulfil("o1").state, "| owed", inv.pending("o1"));
try {
  svc.cancel("o1");
} catch (e) {
  if (!(e instanceof IllegalTransition)) throw e;
  console.log("cancel refused:", e.message);
}
for (const [key, s] of [...inv.stock].sort()) console.log(`  ${key}: on_hand ${s.onHand}, reserved ${s.reserved}`);

o1 RESERVED [(A, W1, 5), (A, W2, 1), (B, W1, 1)]
o2 rejected: A: wanted 3, 2 available
A available: 0
o1 pay: paid | o3 pay at 400: refund
A available: 2 | o3 EXPIRED
o1 fulfil 1: PARTIALLY_SHIPPED | owed 2
o1 fulfil 2: SHIPPED | owed 0
cancel refused: o1: cancel while SHIPPED
  A@W1: on_hand 2, reserved 0
  A@W2: on_hand 2, reserved 0
  B@W1: on_hand 1, reserved 0