Design a Digital Wallet.

# wallet.py, part 1: minor units, entries, receipts, holds, limits and the account
from __future__ import annotations

import threading
from abc import ABC, abstractmethod
from collections.abc import Callable
from dataclasses import dataclass, field
from typing import TypeVar

SECONDS_PER_DAY = 86_400
CASH = "@cash"  # the other side of every top-up and withdrawal; the only account allowed to go negative
T = TypeVar("T")


def money(minor: int) -> str:  # minor units (cents) are integers; this is for display only
    sign = "-" if minor < 0 else ""
    return f"{sign}{abs(minor) // 100}.{abs(minor) % 100:02d}"


def signed(minor: int) -> str:
    return ("+" if minor >= 0 else "") + money(minor)


@dataclass(frozen=True)
class Entry:  # one side of a transaction; a transaction's entries sum to zero
    txn_id: int
    account_id: str
    amount: int


@dataclass(frozen=True)
class Receipt:
    txn_id: int
    src: str
    dst: str
    amount: int


@dataclass(frozen=True)
class Hold:  # funds set aside: not spendable, not yet moved
    hold_id: int
    account_id: str
    amount: int
    expires_at: int


class LimitPolicy(ABC):
    @abstractmethod
    def check(self, spent_today: int, amount: int) -> None:
        """Raise RuntimeError if spending `amount` more today breaks the policy."""


class DailyLimit(LimitPolicy):
    def __init__(self, max_per_day: int) -> None:
        self.max_per_day = max_per_day

    def check(self, spent_today: int, amount: int) -> None:
        if spent_today + amount > self.max_per_day:
            raise RuntimeError("daily limit exceeded")


@dataclass
class Account:
    account_id: str
    allow_negative: bool = False
    balance: int = 0  # a cached sum of `entries`; verify() proves they agree
    entries: list[Entry] = field(default_factory=list)
    holds: dict[int, Hold] = field(default_factory=dict)
    keys: dict[str, tuple[str, Receipt]] = field(default_factory=dict)  # idempotency key -> (request fingerprint, receipt)
    spent: dict[int, int] = field(default_factory=dict)  # day number -> outgoing total
    lock: threading.Lock = field(default_factory=threading.Lock)

    def held(self, now: int) -> int:  # an expired hold no longer holds anything
        return sum(h.amount for h in self.holds.values() if now < h.expires_at)

    def available(self, now: int) -> int:
        return 10**18 if self.allow_negative else self.balance - self.held(now)

    def replay(self, key: str, fingerprint: str) -> Receipt | None:
        seen = self.keys.get(key)
        if seen is None:
            return None
        if seen[0] != fingerprint:
            raise ValueError("idempotency key reused with a different request")
        return seen[1]

// WalletDemo.java: a double-entry ledger, idempotent transfers, holds, limits and ordered locking
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Supplier;

class Money {
    static String format(long minor) { // minor units (cents) are integers; this is for display only
        String sign = minor < 0 ? "-" : "";
        long a = Math.abs(minor);
        return sign + a / 100 + "." + String.format("%02d", a % 100);
    }

    static String signed(long minor) { return (minor >= 0 ? "+" : "") + format(minor); }
}

class Wallets {
    static final long SECONDS_PER_DAY = 86_400;
    static final String CASH = "@cash"; // the other side of every top-up and withdrawal; the only account allowed to go negative
}

record Entry(long txnId, String accountId, long amount) {} // one side of a transaction; a transaction's entries sum to zero

record Receipt(long txnId, String src, String dst, long amount) {}

record Hold(int holdId, String accountId, long amount, long expiresAt) {} // funds set aside: not spendable, not yet moved

interface LimitPolicy {
    void check(long spentToday, long amount); // throws IllegalStateException if spending `amount` more today breaks the policy
}

class DailyLimit implements LimitPolicy {
    private final long maxPerDay;

    DailyLimit(long maxPerDay) { this.maxPerDay = maxPerDay; }

    public void check(long spentToday, long amount) {
        if (spentToday + amount > maxPerDay) throw new IllegalStateException("daily limit exceeded");
    }
}

record Remembered(String fingerprint, Receipt receipt) {}

class Account {
    final String accountId;
    final boolean allowNegative;
    long balance = 0; // a cached sum of `entries`; verify() proves they agree
    final List<Entry> entries = new ArrayList<>();
    final Map<Integer, Hold> holds = new HashMap<>();
    final Map<String, Remembered> keys = new HashMap<>(); // idempotency key -> (request fingerprint, receipt)
    final Map<Long, Long> spent = new HashMap<>(); // day number -> outgoing total
    final ReentrantLock lock = new ReentrantLock();

    Account(String accountId, boolean allowNegative) {
        this.accountId = accountId;
        this.allowNegative = allowNegative;
    }

    long held(long now) { // an expired hold no longer holds anything
        long total = 0;
        for (Hold h : holds.values()) if (now < h.expiresAt()) total += h.amount();
        return total;
    }

    long available(long now) { return allowNegative ? Long.MAX_VALUE : balance - held(now); }

    Receipt replay(String key, String fingerprint) {
        Remembered seen = keys.get(key);
        if (seen == null) return null;
        if (!seen.fingerprint().equals(fingerprint)) throw new IllegalArgumentException("idempotency key reused with a different request");
        return seen.receipt();
    }
}

// wallet.cpp: a double-entry ledger, idempotent transfers, holds, limits and ordered locking
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <mutex>
#include <stdexcept>
#include <string>
#include <thread>
#include <utility>
#include <vector>

const int64_t SECONDS_PER_DAY = 86400;
const std::string CASH = "@cash";  // the other side of every top-up and withdrawal; the only account allowed to go negative

std::string money(int64_t minor) {  // minor units (cents) are integers; this is for display only
    char buf[40];
    std::snprintf(buf, sizeof buf, "%s%lld.%02lld", minor < 0 ? "-" : "", static_cast<long long>(std::llabs(minor) / 100),
                  static_cast<long long>(std::llabs(minor) % 100));
    return buf;
}

std::string signedMoney(int64_t minor) { return (minor >= 0 ? "+" : "") + money(minor); }

struct Entry {  // one side of a transaction; a transaction's entries sum to zero
    int64_t txnId;
    std::string accountId;
    int64_t amount;
};

struct Receipt {
    int64_t txnId;
    std::string src, dst;
    int64_t amount;
};

struct Hold {  // funds set aside: not spendable, not yet moved
    int holdId;
    std::string accountId;
    int64_t amount;
    int64_t expiresAt;
};

class LimitPolicy {
public:
    virtual ~LimitPolicy() = default;
    virtual void check(int64_t spentToday, int64_t amount) const = 0;  // throws logic_error if spending `amount` more breaks the policy
};

class DailyLimit : public LimitPolicy {
public:
    explicit DailyLimit(int64_t m) : maxPerDay(m) {}

    void check(int64_t spentToday, int64_t amount) const override {
        if (spentToday + amount > maxPerDay) throw std::logic_error("daily limit exceeded");
    }

private:
    int64_t maxPerDay;
};

struct Remembered {
    std::string fingerprint;
    Receipt receipt;
};

struct Account {
    std::string accountId;
    bool allowNegative;
    int64_t balance = 0;  // a cached sum of `entries`; verify() proves they agree
    std::vector<Entry> entries;
    std::map<int, Hold> holds;
    std::map<std::string, Remembered> keys;  // idempotency key -> (request fingerprint, receipt)
    std::map<int64_t, int64_t> spent;        // day number -> outgoing total
    std::mutex lock;

    Account(std::string id, bool neg) : accountId(std::move(id)), allowNegative(neg) {}

    int64_t held(int64_t now) const {  // an expired hold no longer holds anything
        int64_t total = 0;
        for (const auto& [id, h] : holds)
            if (now < h.expiresAt) total += h.amount;
        return total;
    }

    int64_t available(int64_t now) const { return allowNegative ? INT64_MAX : balance - held(now); }

    const Receipt* replay(const std::string& key, const std::string& fingerprint) const {
        auto it = keys.find(key);
        if (it == keys.end()) return nullptr;
        if (it->second.fingerprint != fingerprint) throw std::invalid_argument("idempotency key reused with a different request");
        return &it->second.receipt;
    }
};

// wallet.js: a double-entry ledger, idempotent transfers, holds, limits and ordered locking
const SECONDS_PER_DAY = 86400;
const CASH = "@cash"; // the other side of every top-up and withdrawal; the only account allowed to go negative

// minor units (cents) are integers; this is for display only
const money = (minor) => `${minor < 0 ? "-" : ""}${Math.floor(Math.abs(minor) / 100)}.${String(Math.abs(minor) % 100).padStart(2, "0")}`;
const signed = (minor) => (minor >= 0 ? "+" : "") + money(minor);

// one side of a transaction; a transaction's entries sum to zero
const entry = (txnId, accountId, amount) => Object.freeze({ txnId, accountId, amount });
const receipt = (txnId, src, dst, amount) => Object.freeze({ txnId, src, dst, amount });
// funds set aside: not spendable, not yet moved
const hold = (holdId, accountId, amount, expiresAt) => Object.freeze({ holdId, accountId, amount, expiresAt });

class DailyLimit {
  // a LimitPolicy: check(spentToday, amount) throws if spending `amount` more today breaks the policy
  constructor(maxPerDay) {
    this.maxPerDay = maxPerDay;
  }

  check(spentToday, amount) {
    if (spentToday + amount > this.maxPerDay) throw new Error("daily limit exceeded");
  }
}

class Account {
  constructor(accountId, allowNegative = false) {
    this.accountId = accountId;
    this.allowNegative = allowNegative;
    this.balance = 0; // a cached sum of `entries`; verify() proves they agree
    this.entries = [];
    this.holds = new Map();
    this.keys = new Map(); // idempotency key -> { fingerprint, receipt }
    this.spent = new Map(); // day number -> outgoing total
  }

  held(now) {
    // an expired hold no longer holds anything
    let total = 0;
    for (const h of this.holds.values()) if (now < h.expiresAt) total += h.amount;
    return total;
  }

  available(now) {
    return this.allowNegative ? Infinity : this.balance - this.held(now);
  }

  replay(key, fingerprint) {
    const seen = this.keys.get(key);
    if (!seen) return null;
    if (seen.fingerprint !== fingerprint) throw new RangeError("idempotency key reused with a different request");
    return seen.receipt;
  }
}

# part 2: the wallet: open, transfer, deposit, withdraw, verify
class Wallet:
    def __init__(self, limit: LimitPolicy) -> None:
        self.accounts: dict[str, Account] = {}
        self.limit = limit
        self._txn = 0
        self._txn_lock = threading.Lock()
        self.open(CASH, allow_negative=True)

    def open(self, account_id: str, allow_negative: bool = False) -> None:
        if account_id in self.accounts:
            raise ValueError("account exists")
        self.accounts[account_id] = Account(account_id, allow_negative)

    def account(self, account_id: str) -> Account:
        if account_id not in self.accounts:
            raise ValueError("unknown account")
        return self.accounts[account_id]

    def next_txn(self) -> int:
        with self._txn_lock:
            self._txn += 1
            return self._txn

    def with_locks(self, a: Account, b: Account, fn: Callable[[], T]) -> T:
        """Run fn holding both locks, always taken in account-id order: two crossing transfers cannot deadlock."""
        ordered = sorted({a.account_id: a, b.account_id: b}.values(), key=lambda acct: acct.account_id)
        for acct in ordered:
            acct.lock.acquire()
        try:
            return fn()
        finally:
            for acct in reversed(ordered):
                acct.lock.release()

    def post(self, key: str, fingerprint: str, a: Account, b: Account, amount: int, now: int) -> Receipt:
        """Two entries that sum to zero. The caller holds both locks and has checked the funds."""
        day = now // SECONDS_PER_DAY
        if not a.allow_negative:
            self.limit.check(a.spent.get(day, 0), amount)
        txn = self.next_txn()
        a.entries.append(Entry(txn, a.account_id, -amount))
        b.entries.append(Entry(txn, b.account_id, amount))
        a.balance -= amount
        b.balance += amount
        a.spent[day] = a.spent.get(day, 0) + amount
        receipt = Receipt(txn, a.account_id, b.account_id, amount)
        a.keys[key] = (fingerprint, receipt)
        return receipt

    def transfer(self, key: str, src: str, dst: str, amount: int, now: int) -> Receipt:
        if amount <= 0:
            raise ValueError("amount must be positive")
        if src == dst:
            raise ValueError("cannot pay yourself")
        a, b = self.account(src), self.account(dst)

        def run() -> Receipt:
            fingerprint = f"{dst}:{amount}:0"
            replayed = a.replay(key, fingerprint)  # a retry returns the first result and moves nothing
            if replayed is not None:
                return replayed
            if amount > a.available(now):
                raise RuntimeError("insufficient funds")
            return self.post(key, fingerprint, a, b, amount, now)

        return self.with_locks(a, b, run)

    def deposit(self, key: str, account_id: str, amount: int, now: int) -> Receipt:
        return self.transfer(key, CASH, account_id, amount, now)  # money enters from the cash account

    def withdraw(self, key: str, account_id: str, amount: int, now: int) -> Receipt:
        return self.transfer(key, account_id, CASH, amount, now)

    def balance(self, account_id: str) -> int:
        return self.account(account_id).balance

    def verify(self) -> tuple[bool, bool]:
        """(every entry in the system sums to zero, every cached balance equals the sum of its entries)"""
        total = sum(e.amount for acct in self.accounts.values() for e in acct.entries)
        match = all(acct.balance == sum(e.amount for e in acct.entries) for acct in self.accounts.values())
        return total == 0, match

// part 2: the wallet: open, transfer, deposit, withdraw, verify
class Wallet {
    final Map<String, Account> accounts = new TreeMap<>();
    private final LimitPolicy limit;
    private long txn = 0;
    private final Object txnLock = new Object();

    Wallet(LimitPolicy limit) {
        this.limit = limit;
        open(Wallets.CASH, true);
    }

    void open(String accountId, boolean allowNegative) {
        if (accounts.containsKey(accountId)) throw new IllegalArgumentException("account exists");
        accounts.put(accountId, new Account(accountId, allowNegative));
    }

    Account account(String accountId) {
        Account a = accounts.get(accountId);
        if (a == null) throw new IllegalArgumentException("unknown account");
        return a;
    }

    long nextTxn() {
        synchronized (txnLock) {
            return ++txn;
        }
    }

    // run fn holding both locks, always taken in account-id order: two crossing transfers cannot deadlock
    <T> T withLocks(Account a, Account b, Supplier<T> fn) {
        Account first = a.accountId.compareTo(b.accountId) <= 0 ? a : b;
        Account second = first == a ? b : a;
        first.lock.lock();
        try {
            if (second != first) second.lock.lock();
            try {
                return fn.get();
            } finally {
                if (second != first) second.lock.unlock();
            }
        } finally {
            first.lock.unlock();
        }
    }

    // two entries that sum to zero; the caller holds both locks and has checked the funds
    Receipt post(String key, String fingerprint, Account a, Account b, long amount, long now) {
        long day = now / Wallets.SECONDS_PER_DAY;
        if (!a.allowNegative) limit.check(a.spent.getOrDefault(day, 0L), amount);
        long id = nextTxn();
        a.entries.add(new Entry(id, a.accountId, -amount));
        b.entries.add(new Entry(id, b.accountId, amount));
        a.balance -= amount;
        b.balance += amount;
        a.spent.merge(day, amount, Long::sum);
        Receipt receipt = new Receipt(id, a.accountId, b.accountId, amount);
        a.keys.put(key, new Remembered(fingerprint, receipt));
        return receipt;
    }

    Receipt transfer(String key, String src, String dst, long amount, long now) {
        if (amount <= 0) throw new IllegalArgumentException("amount must be positive");
        if (src.equals(dst)) throw new IllegalArgumentException("cannot pay yourself");
        Account a = account(src), b = account(dst);
        return withLocks(a, b, () -> {
            String fingerprint = dst + ":" + amount + ":0";
            Receipt replayed = a.replay(key, fingerprint); // a retry returns the first result and moves nothing
            if (replayed != null) return replayed;
            if (amount > a.available(now)) throw new IllegalStateException("insufficient funds");
            return post(key, fingerprint, a, b, amount, now);
        });
    }

    Receipt deposit(String key, String accountId, long amount, long now) {
        return transfer(key, Wallets.CASH, accountId, amount, now); // money enters from the cash account
    }

    Receipt withdraw(String key, String accountId, long amount, long now) {
        return transfer(key, accountId, Wallets.CASH, amount, now);
    }

    long balance(String accountId) { return account(accountId).balance; }

    // {every entry in the system sums to zero, every cached balance equals the sum of its entries}
    boolean[] verify() {
        long total = 0;
        boolean match = true;
        for (Account acct : accounts.values()) {
            long sum = 0;
            for (Entry e : acct.entries) sum += e.amount();
            total += sum;
            if (acct.balance != sum) match = false;
        }
        return new boolean[] {total == 0, match};
    }
}

// part 2: the wallet: open, transfer, deposit, withdraw, verify
class Wallet {
public:
    explicit Wallet(std::unique_ptr<LimitPolicy> l) : limit(std::move(l)) { open(CASH, true); }

    void open(const std::string& id, bool allowNegative = false) {
        if (accounts.count(id)) throw std::invalid_argument("account exists");
        accounts[id] = std::make_unique<Account>(id, allowNegative);
    }

    Account& account(const std::string& id) {
        auto it = accounts.find(id);
        if (it == accounts.end()) throw std::invalid_argument("unknown account");
        return *it->second;
    }

    int64_t nextTxn() {
        std::lock_guard<std::mutex> g(txnLock);
        return ++txn;
    }

    // run fn holding both locks, always taken in account-id order: two crossing transfers cannot deadlock
    template <class F>
    auto withLocks(Account& a, Account& b, F fn) -> decltype(fn()) {
        Account* first = &a;
        Account* second = &b;
        if (second->accountId < first->accountId) std::swap(first, second);
        std::lock_guard<std::mutex> g1(first->lock);
        if (first == second) return fn();
        std::lock_guard<std::mutex> g2(second->lock);
        return fn();
    }

    // two entries that sum to zero; the caller holds both locks and has checked the funds
    Receipt post(const std::string& key, const std::string& fingerprint, Account& a, Account& b, int64_t amount, int64_t now) {
        int64_t day = now / SECONDS_PER_DAY;
        if (!a.allowNegative) limit->check(a.spent[day], amount);
        int64_t id = nextTxn();
        a.entries.push_back({id, a.accountId, -amount});
        b.entries.push_back({id, b.accountId, amount});
        a.balance -= amount;
        b.balance += amount;
        a.spent[day] += amount;
        Receipt receipt{id, a.accountId, b.accountId, amount};
        a.keys[key] = Remembered{fingerprint, receipt};
        return receipt;
    }

    Receipt transfer(const std::string& key, const std::string& src, const std::string& dst, int64_t amount, int64_t now) {
        if (amount <= 0) throw std::invalid_argument("amount must be positive");
        if (src == dst) throw std::invalid_argument("cannot pay yourself");
        Account& a = account(src);
        Account& b = account(dst);
        return withLocks(a, b, [&]() -> Receipt {
            std::string fingerprint = dst + ":" + std::to_string(amount) + ":0";
            if (const Receipt* replayed = a.replay(key, fingerprint)) return *replayed;  // a retry returns the first result and moves nothing
            if (amount > a.available(now)) throw std::logic_error("insufficient funds");
            return post(key, fingerprint, a, b, amount, now);
        });
    }

    Receipt deposit(const std::string& key, const std::string& id, int64_t amount, int64_t now) {
        return transfer(key, CASH, id, amount, now);  // money enters from the cash account
    }

    Receipt withdraw(const std::string& key, const std::string& id, int64_t amount, int64_t now) {
        return transfer(key, id, CASH, amount, now);
    }

    int64_t balance(const std::string& id) { return account(id).balance; }

    // {every entry in the system sums to zero, every cached balance equals the sum of its entries}
    std::pair<bool, bool> verify() {
        int64_t total = 0;
        bool match = true;
        for (auto& [id, acct] : accounts) {
            int64_t sum = 0;
            for (const Entry& e : acct->entries) sum += e.amount;
            total += sum;
            if (acct->balance != sum) match = false;
        }
        return {total == 0, match};
    }

    std::map<std::string, std::unique_ptr<Account>> accounts;

private:
    std::unique_ptr<LimitPolicy> limit;
    int64_t txn = 0;
    std::mutex txnLock;
};

// part 2: the wallet: open, transfer, deposit, withdraw, verify
class Wallet {
  // JavaScript runs one thing at a time, so these methods are atomic as written. An `await` between the key lookup and the
  // post would break that, and the fix is the same as elsewhere: both accounts locked, in id order, around the whole step.
  constructor(limit) {
    this.accounts = new Map();
    this.limit = limit;
    this.txn = 0;
    this.open(CASH, true);
  }

  open(accountId, allowNegative = false) {
    if (this.accounts.has(accountId)) throw new RangeError("account exists");
    this.accounts.set(accountId, new Account(accountId, allowNegative));
  }

  account(accountId) {
    const a = this.accounts.get(accountId);
    if (!a) throw new RangeError("unknown account");
    return a;
  }

  nextTxn() {
    return ++this.txn;
  }

  // run fn holding both locks, always taken in account-id order (here: nothing to take)
  withLocks(a, b, fn) {
    return fn();
  }

  // two entries that sum to zero; the caller holds both locks and has checked the funds
  post(key, fingerprint, a, b, amount, now) {
    const day = Math.floor(now / SECONDS_PER_DAY);
    if (!a.allowNegative) this.limit.check(a.spent.get(day) ?? 0, amount);
    const id = this.nextTxn();
    a.entries.push(entry(id, a.accountId, -amount));
    b.entries.push(entry(id, b.accountId, amount));
    a.balance -= amount;
    b.balance += amount;
    a.spent.set(day, (a.spent.get(day) ?? 0) + amount);
    const r = receipt(id, a.accountId, b.accountId, amount);
    a.keys.set(key, { fingerprint, receipt: r });
    return r;
  }

  transfer(key, src, dst, amount, now) {
    if (amount <= 0) throw new RangeError("amount must be positive");
    if (src === dst) throw new RangeError("cannot pay yourself");
    const a = this.account(src), b = this.account(dst);
    return this.withLocks(a, b, () => {
      const fingerprint = `${dst}:${amount}:0`;
      const replayed = a.replay(key, fingerprint); // a retry returns the first result and moves nothing
      if (replayed) return replayed;
      if (amount > a.available(now)) throw new Error("insufficient funds");
      return this.post(key, fingerprint, a, b, amount, now);
    });
  }

  deposit(key, accountId, amount, now) {
    return this.transfer(key, CASH, accountId, amount, now); // money enters from the cash account
  }

  withdraw(key, accountId, amount, now) {
    return this.transfer(key, accountId, CASH, amount, now);
  }

  balance(accountId) {
    return this.account(accountId).balance;
  }

  // [every entry in the system sums to zero, every cached balance equals the sum of its entries]
  verify() {
    let total = 0, match = true;
    for (const acct of this.accounts.values()) {
      const sum = acct.entries.reduce((s, e) => s + e.amount, 0);
      total += sum;
      if (acct.balance !== sum) match = false;
    }
    return [total === 0, match];
  }
}

# part 3: holds: set money aside, then capture it or let it go
class Holds:
    def __init__(self, wallet: Wallet) -> None:
        self.wallet = wallet
        self._next = 0
        self._owner: dict[int, str] = {}
        self._lock = threading.Lock()

    def place(self, account_id: str, amount: int, now: int, ttl: int) -> int:
        if amount <= 0:
            raise ValueError("amount must be positive")
        a = self.wallet.account(account_id)

        def run() -> int:
            if amount > a.available(now):
                raise RuntimeError("insufficient funds")
            with self._lock:
                self._next += 1
                hold_id = self._next
                self._owner[hold_id] = account_id
            a.holds[hold_id] = Hold(hold_id, account_id, amount, now + ttl)
            return hold_id

        return self.wallet.with_locks(a, a, run)

    def _find(self, hold_id: int) -> Account:
        with self._lock:
            owner = self._owner.get(hold_id)
        if owner is None:
            raise ValueError("unknown hold")
        return self.wallet.account(owner)

    def capture(self, key: str, hold_id: int, dst: str, amount: int, now: int) -> Receipt:
        a, b = self._find(hold_id), self.wallet.account(dst)

        def run() -> Receipt:
            fingerprint = f"{dst}:{amount}:{hold_id}"
            replayed = a.replay(key, fingerprint)
            if replayed is not None:
                return replayed
            hold = a.holds.get(hold_id)
            if hold is None:
                raise RuntimeError("hold not found")
            if now >= hold.expires_at:
                raise RuntimeError("hold expired")
            if not 0 < amount <= hold.amount:
                raise RuntimeError("amount exceeds the hold")
            receipt = self.wallet.post(key, fingerprint, a, b, amount, now)
            del a.holds[hold_id]  # the rest of the hold, if any, is released with it
            return receipt

        return self.wallet.with_locks(a, b, run)

    def release(self, hold_id: int) -> None:
        a = self._find(hold_id)

        def run() -> None:
            if a.holds.pop(hold_id, None) is None:
                raise RuntimeError("hold not found")

        self.wallet.with_locks(a, a, run)

// part 3: holds: set money aside, then capture it or let it go
class Holds {
    private final Wallet wallet;
    private int next = 0;
    private final Map<Integer, String> owner = new HashMap<>();
    private final Object lock = new Object();

    Holds(Wallet wallet) { this.wallet = wallet; }

    int place(String accountId, long amount, long now, long ttl) {
        if (amount <= 0) throw new IllegalArgumentException("amount must be positive");
        Account a = wallet.account(accountId);
        return wallet.withLocks(a, a, () -> {
            if (amount > a.available(now)) throw new IllegalStateException("insufficient funds");
            int holdId;
            synchronized (lock) {
                holdId = ++next;
                owner.put(holdId, accountId);
            }
            a.holds.put(holdId, new Hold(holdId, accountId, amount, now + ttl));
            return holdId;
        });
    }

    private Account find(int holdId) {
        String id;
        synchronized (lock) {
            id = owner.get(holdId);
        }
        if (id == null) throw new IllegalArgumentException("unknown hold");
        return wallet.account(id);
    }

    Receipt capture(String key, int holdId, String dst, long amount, long now) {
        Account a = find(holdId), b = wallet.account(dst);
        return wallet.withLocks(a, b, () -> {
            String fingerprint = dst + ":" + amount + ":" + holdId;
            Receipt replayed = a.replay(key, fingerprint);
            if (replayed != null) return replayed;
            Hold hold = a.holds.get(holdId);
            if (hold == null) throw new IllegalStateException("hold not found");
            if (now >= hold.expiresAt()) throw new IllegalStateException("hold expired");
            if (amount <= 0 || amount > hold.amount()) throw new IllegalStateException("amount exceeds the hold");
            Receipt receipt = wallet.post(key, fingerprint, a, b, amount, now);
            a.holds.remove(holdId); // the rest of the hold, if any, is released with it
            return receipt;
        });
    }

    void release(int holdId) {
        Account a = find(holdId);
        wallet.withLocks(a, a, () -> {
            if (a.holds.remove(holdId) == null) throw new IllegalStateException("hold not found");
            return null;
        });
    }
}

// part 3: holds: set money aside, then capture it or let it go
class Holds {
public:
    explicit Holds(Wallet& w) : wallet(w) {}

    int place(const std::string& accountId, int64_t amount, int64_t now, int64_t ttl) {
        if (amount <= 0) throw std::invalid_argument("amount must be positive");
        Account& a = wallet.account(accountId);
        return wallet.withLocks(a, a, [&]() -> int {
            if (amount > a.available(now)) throw std::logic_error("insufficient funds");
            int holdId;
            {
                std::lock_guard<std::mutex> g(lock);
                holdId = ++next;
                owner[holdId] = accountId;
            }
            a.holds[holdId] = Hold{holdId, accountId, amount, now + ttl};
            return holdId;
        });
    }

    Receipt capture(const std::string& key, int holdId, const std::string& dst, int64_t amount, int64_t now) {
        Account& a = find(holdId);
        Account& b = wallet.account(dst);
        return wallet.withLocks(a, b, [&]() -> Receipt {
            std::string fingerprint = dst + ":" + std::to_string(amount) + ":" + std::to_string(holdId);
            if (const Receipt* replayed = a.replay(key, fingerprint)) return *replayed;
            auto it = a.holds.find(holdId);
            if (it == a.holds.end()) throw std::logic_error("hold not found");
            if (now >= it->second.expiresAt) throw std::logic_error("hold expired");
            if (amount <= 0 || amount > it->second.amount) throw std::logic_error("amount exceeds the hold");
            Receipt receipt = wallet.post(key, fingerprint, a, b, amount, now);
            a.holds.erase(holdId);  // the rest of the hold, if any, is released with it
            return receipt;
        });
    }

    void release(int holdId) {
        Account& a = find(holdId);
        wallet.withLocks(a, a, [&]() -> int {
            if (a.holds.erase(holdId) == 0) throw std::logic_error("hold not found");
            return 0;
        });
    }

private:
    Wallet& wallet;
    int next = 0;
    std::map<int, std::string> owner;
    std::mutex lock;

    Account& find(int holdId) {
        std::string id;
        {
            std::lock_guard<std::mutex> g(lock);
            auto it = owner.find(holdId);
            if (it == owner.end()) throw std::invalid_argument("unknown hold");
            id = it->second;
        }
        return wallet.account(id);
    }
};

// part 3: holds: set money aside, then capture it or let it go
class Holds {
  constructor(wallet) {
    this.wallet = wallet;
    this.next = 0;
    this.owner = new Map();
  }

  place(accountId, amount, now, ttl) {
    if (amount <= 0) throw new RangeError("amount must be positive");
    const a = this.wallet.account(accountId);
    return this.wallet.withLocks(a, a, () => {
      if (amount > a.available(now)) throw new Error("insufficient funds");
      const holdId = ++this.next;
      this.owner.set(holdId, accountId);
      a.holds.set(holdId, hold(holdId, accountId, amount, now + ttl));
      return holdId;
    });
  }

  find(holdId) {
    if (!this.owner.has(holdId)) throw new RangeError("unknown hold");
    return this.wallet.account(this.owner.get(holdId));
  }

  capture(key, holdId, dst, amount, now) {
    const a = this.find(holdId), b = this.wallet.account(dst);
    return this.wallet.withLocks(a, b, () => {
      const fingerprint = `${dst}:${amount}:${holdId}`;
      const replayed = a.replay(key, fingerprint);
      if (replayed) return replayed;
      const h = a.holds.get(holdId);
      if (!h) throw new Error("hold not found");
      if (now >= h.expiresAt) throw new Error("hold expired");
      if (!(amount > 0 && amount <= h.amount)) throw new Error("amount exceeds the hold");
      const r = this.wallet.post(key, fingerprint, a, b, amount, now);
      a.holds.delete(holdId); // the rest of the hold, if any, is released with it
      return r;
    });
  }

  release(holdId) {
    const a = this.find(holdId);
    this.wallet.withLocks(a, a, () => {
      if (!a.holds.delete(holdId)) throw new Error("hold not found");
    });
  }
}

# part 4: a stress test: opposing transfers from two threads, which would deadlock with src-then-dst locking
def stress(wallet: Wallet, a: str, b: str, rounds: int, amount: int) -> None:
    def pay(src: str, dst: str, tag: str) -> None:
        for i in range(rounds):
            wallet.transfer(f"{tag}-{i}", src, dst, amount, 0)

    threads = [threading.Thread(target=pay, args=(a, b, "ab")), threading.Thread(target=pay, args=(b, a, "ba"))]
    for t in threads:
        t.start()
    for t in threads:
        t.join()

// part 4: a stress test: opposing transfers from two threads, which would deadlock with src-then-dst locking
class Stress {
    static void run(Wallet wallet, String a, String b, int rounds, long amount) throws InterruptedException {
        Thread t1 = new Thread(() -> pay(wallet, a, b, "ab", rounds, amount));
        Thread t2 = new Thread(() -> pay(wallet, b, a, "ba", rounds, amount));
        t1.start();
        t2.start();
        t1.join();
        t2.join();
    }

    private static void pay(Wallet wallet, String src, String dst, String tag, int rounds, long amount) {
        for (int i = 0; i < rounds; i++) wallet.transfer(tag + "-" + i, src, dst, amount, 0);
    }
}

// part 4: a stress test: opposing transfers from two threads, which would deadlock with src-then-dst locking
void stress(Wallet& wallet, const std::string& a, const std::string& b, int rounds, int64_t amount) {
    auto pay = [&](const std::string& src, const std::string& dst, const std::string& tag) {
        for (int i = 0; i < rounds; i++) wallet.transfer(tag + "-" + std::to_string(i), src, dst, amount, 0);
    };
    std::thread t1(pay, a, b, "ab");
    std::thread t2(pay, b, a, "ba");
    t1.join();
    t2.join();
}

// part 4: a stress test: opposing transfers, interleaved (JavaScript has one thread; the ordered locks matter once there are two)
function stress(wallet, a, b, rounds, amount) {
  for (let i = 0; i < rounds; i++) {
    wallet.transfer(`ab-${i}`, a, b, amount, 0);
    wallet.transfer(`ba-${i}`, b, a, amount, 0);
  }
}

# part 5: a day in a small wallet
def statement(wallet: Wallet, account_id: str) -> None:
    for e in wallet.account(account_id).entries:
        print(f"  txn {e.txn_id} {signed(e.amount)}")


if __name__ == "__main__":
    wallet = Wallet(DailyLimit(50_000))  # 500.00 a day
    holds = Holds(wallet)
    for who in ("ann", "ben", "shop"):
        wallet.open(who)

    r = wallet.deposit("dep-1", "ann", 30_000, 0)
    print(f"deposit ann {money(r.amount)} -> txn {r.txn_id}")
    r = wallet.transfer("t-1", "ann", "ben", 12_500, 0)
    print(f"ann pays ben {money(r.amount)} -> txn {r.txn_id}")
    r = wallet.transfer("t-1", "ann", "ben", 12_500, 0)  # the client timed out and retried
    print(f"retry t-1 -> txn {r.txn_id}, ann has {money(wallet.balance('ann'))}")
    for label, call in [
        ("same key, other amount", lambda: wallet.transfer("t-1", "ann", "ben", 9_900, 0)),
        ("20000 from 17500", lambda: wallet.transfer("t-2", "ann", "ben", 20_000, 0)),
    ]:
        try:
            call()
        except (ValueError, RuntimeError) as e:
            print(f"rejected ({label}): {e}")

    h = holds.place("ann", 10_000, 0, 3_600)
    print(f"hold {h}: ann balance {money(wallet.balance('ann'))}, available {money(wallet.account('ann').available(0))}")
    try:
        wallet.transfer("t-3", "ann", "ben", 8_000, 0)
    except RuntimeError as e:
        print("rejected (held money):", e)
    r = holds.capture("cap-1", h, "shop", 9_000, 100)
    print(f"captured {money(r.amount)} to shop -> txn {r.txn_id}; ann has {money(wallet.balance('ann'))}, available {money(wallet.account('ann').available(100))}")
    h2 = holds.place("ann", 5_000, 200, 100)
    try:
        holds.capture("cap-2", h2, "shop", 5_000, 300)
    except RuntimeError as e:
        print("rejected (late capture):", e)
    print(f"after expiry ann available {money(wallet.account('ann').available(300))}")

    wallet.deposit("dep-2", "ann", 60_000, 400)
    wallet.transfer("t-4", "ann", "ben", 25_000, 500)
    try:
        wallet.transfer("t-5", "ann", "ben", 5_000, 600)
    except RuntimeError as e:
        print("rejected (spent 21500 + 25000 + 5000):", e)
    wallet.transfer("t-5", "ann", "ben", 5_000, SECONDS_PER_DAY + 10)
    print("next day t-5 goes through")

    print("ann's statement:")
    statement(wallet, "ann")
    print("books balance:", wallet.verify())

    big = Wallet(DailyLimit(10**9))
    for who in ("a", "b"):
        big.open(who)
        big.deposit(f"fund-{who}", who, 10_000, 0)
    stress(big, "a", "b", 1_000, 10)
    print(f"2000 crossing transfers: a {money(big.balance('a'))}, b {money(big.balance('b'))}, books balance: {big.verify()}")

public class WalletDemo {
    // a day in a small wallet
    static void statement(Wallet wallet, String accountId) {
        for (Entry e : wallet.account(accountId).entries) System.out.println("  txn " + e.txnId() + " " + Money.signed(e.amount()));
    }

    static String books(boolean[] v) { return "(" + (v[0] ? "True" : "False") + ", " + (v[1] ? "True" : "False") + ")"; }

    public static void main(String[] args) throws Exception {
        Wallet wallet = new Wallet(new DailyLimit(50_000)); // 500.00 a day
        Holds holds = new Holds(wallet);
        for (String who : new String[] {"ann", "ben", "shop"}) wallet.open(who, false);

        Receipt r = wallet.deposit("dep-1", "ann", 30_000, 0);
        System.out.println("deposit ann " + Money.format(r.amount()) + " -> txn " + r.txnId());
        r = wallet.transfer("t-1", "ann", "ben", 12_500, 0);
        System.out.println("ann pays ben " + Money.format(r.amount()) + " -> txn " + r.txnId());
        r = wallet.transfer("t-1", "ann", "ben", 12_500, 0); // the client timed out and retried
        System.out.println("retry t-1 -> txn " + r.txnId() + ", ann has " + Money.format(wallet.balance("ann")));
        try {
            wallet.transfer("t-1", "ann", "ben", 9_900, 0);
        } catch (IllegalArgumentException | IllegalStateException e) {
            System.out.println("rejected (same key, other amount): " + e.getMessage());
        }
        try {
            wallet.transfer("t-2", "ann", "ben", 20_000, 0);
        } catch (IllegalArgumentException | IllegalStateException e) {
            System.out.println("rejected (20000 from 17500): " + e.getMessage());
        }

        int h = holds.place("ann", 10_000, 0, 3_600);
        System.out.println("hold " + h + ": ann balance " + Money.format(wallet.balance("ann")) + ", available " + Money.format(wallet.account("ann").available(0)));
        try {
            wallet.transfer("t-3", "ann", "ben", 8_000, 0);
        } catch (IllegalStateException e) {
            System.out.println("rejected (held money): " + e.getMessage());
        }
        r = holds.capture("cap-1", h, "shop", 9_000, 100);
        System.out.println("captured " + Money.format(r.amount()) + " to shop -> txn " + r.txnId() + "; ann has " + Money.format(wallet.balance("ann"))
                + ", available " + Money.format(wallet.account("ann").available(100)));
        int h2 = holds.place("ann", 5_000, 200, 100);
        try {
            holds.capture("cap-2", h2, "shop", 5_000, 300);
        } catch (IllegalStateException e) {
            System.out.println("rejected (late capture): " + e.getMessage());
        }
        System.out.println("after expiry ann available " + Money.format(wallet.account("ann").available(300)));

        wallet.deposit("dep-2", "ann", 60_000, 400);
        wallet.transfer("t-4", "ann", "ben", 25_000, 500);
        try {
            wallet.transfer("t-5", "ann", "ben", 5_000, 600);
        } catch (IllegalStateException e) {
            System.out.println("rejected (spent 21500 + 25000 + 5000): " + e.getMessage());
        }
        wallet.transfer("t-5", "ann", "ben", 5_000, Wallets.SECONDS_PER_DAY + 10);
        System.out.println("next day t-5 goes through");

        System.out.println("ann's statement:");
        statement(wallet, "ann");
        System.out.println("books balance: " + books(wallet.verify()));

        Wallet big = new Wallet(new DailyLimit(1_000_000_000L));
        for (String who : new String[] {"a", "b"}) {
            big.open(who, false);
            big.deposit("fund-" + who, who, 10_000, 0);
        }
        Stress.run(big, "a", "b", 1_000, 10);
        System.out.println("2000 crossing transfers: a " + Money.format(big.balance("a")) + ", b " + Money.format(big.balance("b")) + ", books balance: " + books(big.verify()));
    }
}

// a day in a small wallet
void statement(Wallet& wallet, const std::string& id) {
    for (const Entry& e : wallet.account(id).entries) std::cout << "  txn " << e.txnId << " " << signedMoney(e.amount) << "\n";
}

std::string books(std::pair<bool, bool> v) { return std::string("(") + (v.first ? "True" : "False") + ", " + (v.second ? "True" : "False") + ")"; }

int main() {
    Wallet wallet(std::make_unique<DailyLimit>(50000));  // 500.00 a day
    Holds holds(wallet);
    for (const char* who : {"ann", "ben", "shop"}) wallet.open(who);

    Receipt r = wallet.deposit("dep-1", "ann", 30000, 0);
    std::cout << "deposit ann " << money(r.amount) << " -> txn " << r.txnId << "\n";
    r = wallet.transfer("t-1", "ann", "ben", 12500, 0);
    std::cout << "ann pays ben " << money(r.amount) << " -> txn " << r.txnId << "\n";
    r = wallet.transfer("t-1", "ann", "ben", 12500, 0);  // the client timed out and retried
    std::cout << "retry t-1 -> txn " << r.txnId << ", ann has " << money(wallet.balance("ann")) << "\n";
    try {
        wallet.transfer("t-1", "ann", "ben", 9900, 0);
    } catch (const std::exception& e) {
        std::cout << "rejected (same key, other amount): " << e.what() << "\n";
    }
    try {
        wallet.transfer("t-2", "ann", "ben", 20000, 0);
    } catch (const std::exception& e) {
        std::cout << "rejected (20000 from 17500): " << e.what() << "\n";
    }

    int h = holds.place("ann", 10000, 0, 3600);
    std::cout << "hold " << h << ": ann balance " << money(wallet.balance("ann")) << ", available " << money(wallet.account("ann").available(0)) << "\n";
    try {
        wallet.transfer("t-3", "ann", "ben", 8000, 0);
    } catch (const std::exception& e) {
        std::cout << "rejected (held money): " << e.what() << "\n";
    }
    r = holds.capture("cap-1", h, "shop", 9000, 100);
    std::cout << "captured " << money(r.amount) << " to shop -> txn " << r.txnId << "; ann has " << money(wallet.balance("ann"))
              << ", available " << money(wallet.account("ann").available(100)) << "\n";
    int h2 = holds.place("ann", 5000, 200, 100);
    try {
        holds.capture("cap-2", h2, "shop", 5000, 300);
    } catch (const std::exception& e) {
        std::cout << "rejected (late capture): " << e.what() << "\n";
    }
    std::cout << "after expiry ann available " << money(wallet.account("ann").available(300)) << "\n";

    wallet.deposit("dep-2", "ann", 60000, 400);
    wallet.transfer("t-4", "ann", "ben", 25000, 500);
    try {
        wallet.transfer("t-5", "ann", "ben", 5000, 600);
    } catch (const std::exception& e) {
        std::cout << "rejected (spent 21500 + 25000 + 5000): " << e.what() << "\n";
    }
    wallet.transfer("t-5", "ann", "ben", 5000, SECONDS_PER_DAY + 10);
    std::cout << "next day t-5 goes through\n";

    std::cout << "ann's statement:\n";
    statement(wallet, "ann");
    std::cout << "books balance: " << books(wallet.verify()) << "\n";

    Wallet big(std::make_unique<DailyLimit>(1000000000));
    for (const char* who : {"a", "b"}) {
        big.open(who);
        big.deposit(std::string("fund-") + who, who, 10000, 0);
    }
    stress(big, "a", "b", 1000, 10);
    std::cout << "2000 crossing transfers: a " << money(big.balance("a")) << ", b " << money(big.balance("b")) << ", books balance: " << books(big.verify()) << "\n";
}

// a day in a small wallet
const statement = (wallet, accountId) => {
  for (const e of wallet.account(accountId).entries) console.log(`  txn ${e.txnId} ${signed(e.amount)}`);
};
const books = ([a, b]) => `(${a ? "True" : "False"}, ${b ? "True" : "False"})`;

const wallet = new Wallet(new DailyLimit(50000)); // 500.00 a day
const holds = new Holds(wallet);
for (const who of ["ann", "ben", "shop"]) wallet.open(who);

let r = wallet.deposit("dep-1", "ann", 30000, 0);
console.log(`deposit ann ${money(r.amount)} -> txn ${r.txnId}`);
r = wallet.transfer("t-1", "ann", "ben", 12500, 0);
console.log(`ann pays ben ${money(r.amount)} -> txn ${r.txnId}`);
r = wallet.transfer("t-1", "ann", "ben", 12500, 0); // the client timed out and retried
console.log(`retry t-1 -> txn ${r.txnId}, ann has ${money(wallet.balance("ann"))}`);
try {
  wallet.transfer("t-1", "ann", "ben", 9900, 0);
} catch (e) {
  console.log("rejected (same key, other amount):", e.message);
}
try {
  wallet.transfer("t-2", "ann", "ben", 20000, 0);
} catch (e) {
  console.log("rejected (20000 from 17500):", e.message);
}

const h = holds.place("ann", 10000, 0, 3600);
console.log(`hold ${h}: ann balance ${money(wallet.balance("ann"))}, available ${money(wallet.account("ann").available(0))}`);
try {
  wallet.transfer("t-3", "ann", "ben", 8000, 0);
} catch (e) {
  console.log("rejected (held money):", e.message);
}
r = holds.capture("cap-1", h, "shop", 9000, 100);
console.log(`captured ${money(r.amount)} to shop -> txn ${r.txnId}; ann has ${money(wallet.balance("ann"))}, available ${money(wallet.account("ann").available(100))}`);
const h2 = holds.place("ann", 5000, 200, 100);
try {
  holds.capture("cap-2", h2, "shop", 5000, 300);
} catch (e) {
  console.log("rejected (late capture):", e.message);
}
console.log(`after expiry ann available ${money(wallet.account("ann").available(300))}`);

wallet.deposit("dep-2", "ann", 60000, 400);
wallet.transfer("t-4", "ann", "ben", 25000, 500);
try {
  wallet.transfer("t-5", "ann", "ben", 5000, 600);
} catch (e) {
  console.log("rejected (spent 21500 + 25000 + 5000):", e.message);
}
wallet.transfer("t-5", "ann", "ben", 5000, SECONDS_PER_DAY + 10);
console.log("next day t-5 goes through");

console.log("ann's statement:");
statement(wallet, "ann");
console.log("books balance:", books(wallet.verify()));

const big = new Wallet(new DailyLimit(1e9));
for (const who of ["a", "b"]) {
  big.open(who);
  big.deposit(`fund-${who}`, who, 10000, 0);
}
stress(big, "a", "b", 1000, 10);
console.log(`2000 crossing transfers: a ${money(big.balance("a"))}, b ${money(big.balance("b"))}, books balance: ${books(big.verify())}`);

deposit ann 300.00 -> txn 1
ann pays ben 125.00 -> txn 2
retry t-1 -> txn 2, ann has 175.00
rejected (same key, other amount): idempotency key reused with a different request
rejected (20000 from 17500): insufficient funds
hold 1: ann balance 175.00, available 75.00
rejected (held money): insufficient funds
captured 90.00 to shop -> txn 3; ann has 85.00, available 85.00
rejected (late capture): hold expired
after expiry ann available 85.00
rejected (spent 21500 + 25000 + 5000): daily limit exceeded
next day t-5 goes through
ann's statement:
  txn 1 +300.00
  txn 2 -125.00
  txn 3 -90.00
  txn 4 +600.00
  txn 5 -250.00
  txn 6 -50.00
books balance: (True, True)
2000 crossing transfers: a 100.00, b 100.00, books balance: (True, True)