nanobook 0.12.0

//! Level: A FIFO queue of orders at a single price point.
//!
//! The Level stores only `OrderId`s, not full `Order` objects.
//! Orders themselves live in a central `HashMap` for O(1) lookup.

use std::collections::VecDeque;

use crate::{OrderId, Price, Quantity};

/// A queue of orders at a single price level.
///
/// Orders are processed FIFO (first-in-first-out) for time priority.
/// The level tracks total quantity for efficient depth queries.
#[derive(Clone, Debug)]
pub struct Level {
    /// The price for all orders in this level
    price: Price,
    /// Order IDs in FIFO order
    pub(crate) orders: VecDeque<OrderId>,
    /// Sum of remaining quantities (cached for O(1) access)
    total_quantity: Quantity,
    /// Number of tombstones (cancelled orders still in the queue)
    tombstone_count: usize,
}

impl Level {
    /// Create a new empty level at the given price.
    pub fn new(price: Price) -> Self {
        Self {
            price,
            orders: VecDeque::new(),
            total_quantity: 0,
            tombstone_count: 0,
        }
    }

    /// Returns the price of this level.
    #[inline]
    pub fn price(&self) -> Price {
        self.price
    }

    /// Returns true if there are no active orders at this level.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.total_quantity == 0
    }

    /// Returns the number of **active** orders at this level (tombstones
    /// excluded). For the raw queue length including tombstones use
    /// `self.orders.len()`; for the tombstone count alone use
    /// [`tombstone_count`](Self::tombstone_count).
    #[inline]
    pub fn order_count(&self) -> usize {
        self.orders.len() - self.tombstone_count
    }

    /// Returns the total quantity across all orders at this level.
    #[inline]
    pub fn total_quantity(&self) -> Quantity {
        self.total_quantity
    }

    /// Returns the number of tombstones in the queue.
    #[inline]
    pub fn tombstone_count(&self) -> usize {
        self.tombstone_count
    }

    /// Returns the raw queue length, including tombstones. Useful for
    /// asserting the structural invariant
    /// `raw_len() == order_count() + tombstone_count()`.
    #[inline]
    pub fn raw_len(&self) -> usize {
        self.orders.len()
    }

    /// Returns the OrderId at the front of the queue (next to fill).
    /// Skips tombstones.
    pub fn front(&mut self) -> Option<OrderId> {
        while let Some(&id) = self.orders.front() {
            if id.0 == 0 {
                // It's a tombstone
                self.orders.pop_front();
                self.tombstone_count -= 1;
            } else {
                return Some(id);
            }
        }
        None
    }

    /// Add an order to the back of the queue.
    ///
    /// The quantity is added to the level's total (saturating on overflow).
    pub fn push_back(&mut self, order_id: OrderId, quantity: Quantity) {
        assert!(order_id.0 != 0, "OrderId(0) reserved for tombstones");
        self.orders.push_back(order_id);
        self.total_quantity = self.total_quantity.saturating_add(quantity);
    }

    /// Remove and return the order at the front of the queue.
    ///
    /// The provided quantity is subtracted from the level's total.
    /// This should be the order's remaining quantity at time of removal.
    ///
    /// Returns `None` if the level is empty.
    pub fn pop_front(&mut self, quantity: Quantity) -> Option<OrderId> {
        while let Some(id) = self.orders.pop_front() {
            if id.0 == 0 {
                self.tombstone_count -= 1;
                continue;
            }
            self.total_quantity = self.total_quantity.saturating_sub(quantity);
            return Some(id);
        }
        None
    }

    /// Mark an order as a tombstone (O(1) cancellation).
    ///
    /// The caller provides the index into the VecDeque (tracked in OrderBook's
    /// HashMap). The order's quantity is subtracted from the level total.
    pub fn mark_tombstone(&mut self, index: usize, quantity: Quantity) {
        if let Some(id_ref) = self.orders.get_mut(index) {
            if id_ref.0 != 0 {
                id_ref.0 = 0; // Set to tombstone ID
                self.total_quantity = self.total_quantity.saturating_sub(quantity);
                self.tombstone_count += 1;
            }
        }
    }

    /// Remove a specific order from anywhere in the queue (for cancellation).
    ///
    /// Returns `true` if the order was found and removed, `false` otherwise.
    /// The provided quantity is subtracted from the level's total.
    ///
    /// Note: This is O(n) where n is the number of orders at this price level.
    /// For O(1) cancel, we now use `mark_tombstone` called from OrderBook.
    pub fn remove(&mut self, order_id: OrderId, quantity: Quantity) -> bool {
        if let Some(pos) = self.orders.iter().position(|&id| id == order_id) {
            self.orders.remove(pos);
            self.total_quantity = self.total_quantity.saturating_sub(quantity);
            true
        } else {
            false
        }
    }

    /// Remove all tombstones from the queue.
    pub fn compact(&mut self) {
        if self.tombstone_count == 0 {
            return;
        }
        self.orders.retain(|id| id.0 != 0);
        self.tombstone_count = 0;
    }

    /// Decrease the total quantity (e.g., after a partial fill).
    ///
    /// Use this when an order is partially filled but remains in the queue.
    pub fn decrease_quantity(&mut self, amount: Quantity) {
        self.total_quantity = self.total_quantity.saturating_sub(amount);
    }

    /// Returns an iterator over the active order IDs in FIFO order.
    pub fn iter(&self) -> impl Iterator<Item = OrderId> + '_ {
        self.orders.iter().copied().filter(|id| id.0 != 0)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn new_level_is_empty() {
        let mut level = Level::new(Price(100_00));

        assert!(level.is_empty());
        assert_eq!(level.order_count(), 0);
        assert_eq!(level.total_quantity(), 0);
        assert_eq!(level.front(), None);
        assert_eq!(level.price(), Price(100_00));
    }

    #[test]
    fn push_back_adds_orders() {
        let mut level = Level::new(Price(100_00));

        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);
        level.push_back(OrderId(3), 150);

        assert!(!level.is_empty());
        assert_eq!(level.order_count(), 3);
        assert_eq!(level.total_quantity(), 450);
        assert_eq!(level.front(), Some(OrderId(1)));
    }

    #[test]
    fn pop_front_fifo_order() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);
        level.push_back(OrderId(3), 150);

        // Pop in FIFO order
        assert_eq!(level.pop_front(100), Some(OrderId(1)));
        assert_eq!(level.total_quantity(), 350);
        assert_eq!(level.front(), Some(OrderId(2)));

        assert_eq!(level.pop_front(200), Some(OrderId(2)));
        assert_eq!(level.total_quantity(), 150);
        assert_eq!(level.front(), Some(OrderId(3)));

        assert_eq!(level.pop_front(150), Some(OrderId(3)));
        assert_eq!(level.total_quantity(), 0);
        assert!(level.is_empty());

        // Empty level returns None
        assert_eq!(level.pop_front(0), None);
    }

    #[test]
    fn remove_from_middle() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);
        level.push_back(OrderId(3), 150);

        // Remove middle order
        assert!(level.remove(OrderId(2), 200));
        assert_eq!(level.order_count(), 2);
        assert_eq!(level.total_quantity(), 250);

        // FIFO order preserved for remaining
        assert_eq!(level.pop_front(100), Some(OrderId(1)));
        assert_eq!(level.pop_front(150), Some(OrderId(3)));
    }

    #[test]
    fn remove_nonexistent_returns_false() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);

        assert!(!level.remove(OrderId(999), 50));
        assert_eq!(level.order_count(), 1);
        assert_eq!(level.total_quantity(), 100);
    }

    #[test]
    fn remove_from_front() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);

        assert!(level.remove(OrderId(1), 100));
        assert_eq!(level.front(), Some(OrderId(2)));
    }

    #[test]
    fn remove_from_back() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);

        assert!(level.remove(OrderId(2), 200));
        assert_eq!(level.front(), Some(OrderId(1)));
        assert_eq!(level.order_count(), 1);
    }

    #[test]
    fn decrease_quantity_for_partial_fill() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);

        // Partial fill of order 1: filled 30, remaining 70
        level.decrease_quantity(30);

        assert_eq!(level.total_quantity(), 270);
        assert_eq!(level.order_count(), 2); // Order still in queue
    }

    #[test]
    fn iter_returns_fifo_order() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);
        level.push_back(OrderId(3), 150);

        let ids: Vec<_> = level.iter().collect();
        assert_eq!(ids, vec![OrderId(1), OrderId(2), OrderId(3)]);
    }

    #[test]
    fn tombstone_marking() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);
        level.push_back(OrderId(3), 150);

        // Mark middle as tombstone
        level.mark_tombstone(1, 200);

        assert_eq!(level.order_count(), 2);
        assert_eq!(level.total_quantity(), 250);
        assert_eq!(level.tombstone_count(), 1);

        // Iterator should skip it
        let ids: Vec<_> = level.iter().collect();
        assert_eq!(ids, vec![OrderId(1), OrderId(3)]);
    }

    #[test]
    fn tombstone_compaction() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);
        level.push_back(OrderId(3), 150);

        level.mark_tombstone(0, 100);
        level.mark_tombstone(2, 150);

        assert_eq!(level.orders.len(), 3);
        assert_eq!(level.tombstone_count(), 2);

        level.compact();

        assert_eq!(level.orders.len(), 1);
        assert_eq!(level.tombstone_count(), 0);
        assert_eq!(level.orders[0], OrderId(2));
    }

    #[test]
    fn front_skips_tombstones() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);
        level.push_back(OrderId(2), 200);

        level.mark_tombstone(0, 100);

        // front() should return OrderId(2) and remove the tombstone from the front
        assert_eq!(level.front(), Some(OrderId(2)));
        assert_eq!(level.orders.len(), 1);
        assert_eq!(level.tombstone_count(), 0);
    }

    #[test]
    fn quantity_saturates_on_underflow() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 100);

        // Try to subtract more than available (shouldn't happen in practice)
        level.decrease_quantity(200);
        assert_eq!(level.total_quantity(), 0);

        // Pop with excessive quantity
        level.push_back(OrderId(2), 50);
        level.pop_front(100);
        assert_eq!(level.total_quantity(), 0);
    }

    // ========================================================================
    // Mutation-testing regression tests (I3 survivors)
    // ========================================================================

    /// Regression for I3: `Level::raw_len` returning the literal
    /// `1` survived the mutation suite because no test exercised
    /// `raw_len()` on a queue of length > 1. The N16 proptest
    /// relied on random price sparsity, which rarely produced
    /// multi-order levels. Pin a direct multi-order assertion.
    #[test]
    fn raw_len_tracks_queue_size_across_pushes_and_tombstones() {
        let mut level = Level::new(Price(100_00));
        assert_eq!(level.raw_len(), 0);

        level.push_back(OrderId(1), 10);
        level.push_back(OrderId(2), 20);
        level.push_back(OrderId(3), 30);
        assert_eq!(level.raw_len(), 3);

        // Tombstoning does not shrink raw_len — it just flips an
        // in-queue entry to the sentinel id. That's the whole
        // point of the structural invariant raw_len ==
        // order_count + tombstone_count.
        level.mark_tombstone(1, 20);
        assert_eq!(level.raw_len(), 3);
        assert_eq!(level.tombstone_count(), 1);
        assert_eq!(level.order_count(), 2);

        level.compact();
        assert_eq!(level.raw_len(), 2);
    }

    /// Regression for I3: the tombstone-decrement branch inside
    /// `Level::pop_front` (`self.tombstone_count -= 1`) was
    /// mutation-surviving (`-= → +=`, `-= → /=`) because the
    /// production code path always pre-strips tombstones via
    /// `level.front()` before calling `pop_front(qty)`, so the
    /// defensive branch was unreachable by the test suite.
    ///
    /// Exercise the defensive branch directly by placing a
    /// tombstone at the head and calling `pop_front` without an
    /// intervening `front()` call.
    #[test]
    fn pop_front_decrements_tombstone_count_when_head_is_tombstone() {
        let mut level = Level::new(Price(100_00));
        level.push_back(OrderId(1), 10);
        level.push_back(OrderId(2), 20);

        // Tombstone the head without calling `front()`.
        level.mark_tombstone(0, 10);
        assert_eq!(level.tombstone_count(), 1);
        assert_eq!(level.raw_len(), 2);

        // pop_front must traverse the head tombstone (decrementing
        // tombstone_count) and return the real front (OrderId(2)).
        let popped = level.pop_front(20);
        assert_eq!(popped, Some(OrderId(2)));
        assert_eq!(
            level.tombstone_count(),
            0,
            "tombstone_count must decrement through the head-skip branch",
        );
        assert_eq!(level.raw_len(), 0);
    }
}