//! OrderBook Implementation with Performance Issues
//!
//! This module contains an OrderBook implementation that demonstrates O(N) performance
//! issues that need to be refactored to O(1) using HashMap optimization.

use std::collections::{HashMap, VecDeque};
use serde::{Deserialize, Serialize};
use chrono::{DateTime, Utc};

/// Order struct with redundant instrument field (conflicts with OrderBook.instrument)
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
/// OrderWithInstrument
/// 
/// Auto-generated documentation placeholder - enhance with specifics
pub struct OrderWithInstrument {
    /// Id
    pub id: OrderId,
    /// Instrument
    pub instrument: String,  // REDUNDANT: Duplicates OrderBook.instrument
    /// Side
    pub side: OrderSide,
    /// Order Type
    pub order_type: OrderType,
    /// Quantity
    pub quantity: Quantity,
    /// Price
    pub price: Option<Price>,
    /// Timestamp
    pub timestamp: DateTime<Utc>,
    /// Status
    pub status: OrderStatus,
}

impl OrderWithInstrument {
    pub fn new(
        instrument: String,
        side: OrderSide,
        quantity: Quantity,
        price: Option<Price>,
        order_type: OrderType,
    ) -> Self {
        Self {
            id: OrderId::new(),
            instrument,
            side,
            order_type,
            quantity,
            price,
            timestamp: Utc::now(),
            status: OrderStatus::Pending,
        }
    }
}

/// OrderBook with O(N) performance issues
#[derive(Debug, Clone)]
/// SlowOrderBook
/// 
/// Auto-generated documentation placeholder - enhance with specifics
pub struct SlowOrderBook {
    /// Instrument
    pub instrument: String,
    /// Bid Orders
    pub bid_orders: VecDeque<OrderWithInstrument>,  // O(N) for lookups
    /// Ask Orders
    pub ask_orders: VecDeque<OrderWithInstrument>,  // O(N) for lookups
    // Missing: HashMap<OrderId, (Price, Side)> for O(1) lookups
}

impl SlowOrderBook {
    /// Create a new OrderBook
    pub fn new(instrument: String) -> Self {
        Self {
            instrument,
            bid_orders: VecDeque::new(),
            ask_orders: VecDeque::new(),
        }
    }

    /// Add order with O(N) performance - NEEDS OPTIMIZATION
    /// This method scans through all orders to check for duplicates
    pub fn add_order(&mut self, order: OrderWithInstrument) -> Result<(), String> {
        // O(N) PERFORMANCE ISSUE: Linear scan to check for duplicate order IDs
        let orders_to_check = match order.side {
            OrderSide::Buy => &self.bid_orders,
            OrderSide::Sell => &self.ask_orders,
        };

        // SLOW: O(N) scan through all orders
        for existing_order in orders_to_check {
            if existing_order.id == order.id {
                return Err("Order ID already exists".to_string());
            }
        }

        // Add the order (maintaining price-time priority)
        match order.side {
            OrderSide::Buy => {
                // Find insertion point to maintain price priority (highest first for bids)
                let mut insert_index = self.bid_orders.len();
                if let Some(order_price) = order.price {
                    for (i, existing) in self.bid_orders.into_iter().enumerate() {
                        if let Some(existing_price) = existing.price {
                            if order_price > existing_price {
                                insert_index = i;
                                break;
                            }
                        }
                    }
                }
                self.bid_orders.insert(insert_index, order);
            }
            OrderSide::Sell => {
                // Find insertion point to maintain price priority (lowest first for asks)
                let mut insert_index = self.ask_orders.len();
                if let Some(order_price) = order.price {
                    for (i, existing) in self.ask_orders.into_iter().enumerate() {
                        if let Some(existing_price) = existing.price {
                            if order_price < existing_price {
                                insert_index = i;
                                break;
                            }
                        }
                    }
                }
                self.ask_orders.insert(insert_index, order);
            }
        }

        Ok(())
    }

    /// Cancel order with O(N) performance - NEEDS OPTIMIZATION
    /// This method scans through all orders to find the one to cancel
    pub fn cancel_order(&mut self, order_id: &OrderId) -> Result<OrderWithInstrument, String> {
        // O(N) PERFORMANCE ISSUE: Linear scan through bid orders
        for (i, order) in self.bid_orders.into_iter().enumerate() {
            if order.id == *order_id {
                return self.bid_orders.remove(i)
                    .ok_or_else(|| "Order removal failed".to_string());
            }
        }

        // O(N) PERFORMANCE ISSUE: Linear scan through ask orders
        for (i, order) in self.ask_orders.into_iter().enumerate() {
            if order.id == *order_id {
                return self.ask_orders.remove(i)
                    .ok_or_else(|| "Order removal failed".to_string());
            }
        }

        Err("Order not found".to_string())
    }

    /// Get order by ID with O(N) performance - NEEDS OPTIMIZATION
    pub fn get_order(&self, order_id: &OrderId) -> Option<&OrderWithInstrument> {
        // O(N) PERFORMANCE ISSUE: Linear scan through bid orders
        for order in &self.bid_orders {
            if order.id == *order_id {
                return Some(order);
            }
        }

        // O(N) PERFORMANCE ISSUE: Linear scan through ask orders
        for order in &self.ask_orders {
            if order.id == *order_id {
                return Some(order);
            }
        }

    // None variant
        None
    }

    /// Update order status with O(N) performance - NEEDS OPTIMIZATION
    pub fn update_order_status(&mut self, order_id: &OrderId, status: OrderStatus) -> Result<(), String> {
        // O(N) PERFORMANCE ISSUE: Linear scan through bid orders
        for order in &mut self.bid_orders {
            if order.id == *order_id {
                order.status = status;
                return Ok(());
            }
        }

        // O(N) PERFORMANCE ISSUE: Linear scan through ask orders
        for order in &mut self.ask_orders {
            if order.id == *order_id {
                order.status = status;
                return Ok(());
            }
        }

        Err("Order not found".to_string())
    }

    /// Get best bid (O(1) - this is already optimal)
    pub fn best_bid(&self) -> Option<&OrderWithInstrument> {
        self.bid_orders.front()
    }

    /// Get best ask (O(1) - this is already optimal)
    pub fn best_ask(&self) -> Option<&OrderWithInstrument> {
        self.ask_orders.front()
    }

    /// Get market depth (O(1) - this is already optimal)
    pub fn depth(&self) -> (usize, usize) {
        (self.bid_orders.len(), self.ask_orders.len())
    }

    /// Get all orders for a given side - O(N) but acceptable
    pub fn get_orders_by_side(&self, side: OrderSide) -> &VecDeque<OrderWithInstrument> {
        match side {
            OrderSide::Buy => &self.bid_orders,
            OrderSide::Sell => &self.ask_orders,
        }
    }
}

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

    fn create_test_order(side: OrderSide, price: f64, quantity: f64) -> OrderWithInstrument {
        OrderWithInstrument::new(
            "BTCUSD".to_string(),
            side,
            Quantity::from_f64(quantity).unwrap(),
            Some(Price::from_f64(price).unwrap()),
            OrderType::Limit,
        )
    }

    #[test]
    fn test_order_book_creation() {
        let book = SlowOrderBook::new("BTCUSD".to_string());
        assert_eq!(book.instrument, "BTCUSD");
        assert_eq!(book.depth(), (0, 0));
    }

    #[test]
    fn test_add_orders() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        let bid = create_test_order(OrderSide::Buy, 50000.0, 1.0);
        let ask = create_test_order(OrderSide::Sell, 50100.0, 1.0);

        assert!(book.add_order(bid).is_ok());
        assert!(book.add_order(ask).is_ok());

        assert_eq!(book.depth(), (1, 1));
    }

    #[test]
    fn test_cancel_order() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        let order = create_test_order(OrderSide::Buy, 50000.0, 1.0);
        let order_id = order.id;

        book.add_order(order).unwrap();
        assert_eq!(book.depth(), (1, 0));

        let cancelled = book.cancel_order(&order_id).unwrap();
        assert_eq!(cancelled.id, order_id);
        assert_eq!(book.depth(), (0, 0));
    }

    #[test]
    fn test_get_order() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        let order = create_test_order(OrderSide::Buy, 50000.0, 1.0);
        let order_id = order.id;

        book.add_order(order).unwrap();

        let found = book.get_order(&order_id);
        assert!(found.is_some());
        assert_eq!(found.unwrap().id, order_id);
    }

    #[test]
    fn test_best_bid_ask() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        let bid1 = create_test_order(OrderSide::Buy, 50000.0, 1.0);
        let bid2 = create_test_order(OrderSide::Buy, 49900.0, 1.0);
        let ask1 = create_test_order(OrderSide::Sell, 50100.0, 1.0);
        let ask2 = create_test_order(OrderSide::Sell, 50200.0, 1.0);

        book.add_order(bid2).unwrap(); // Lower price
        book.add_order(bid1).unwrap(); // Higher price - should be best
        book.add_order(ask2).unwrap(); // Higher price
        book.add_order(ask1).unwrap(); // Lower price - should be best

        let best_bid = book.best_bid().unwrap();
        let best_ask = book.best_ask().unwrap();

        assert_eq!(best_bid.price.unwrap().to_f64(), 50000.0);
        assert_eq!(best_ask.price.unwrap().to_f64(), 50100.0);
    }

    #[test]
    fn test_update_order_status() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        let order = create_test_order(OrderSide::Buy, 50000.0, 1.0);
        let order_id = order.id;

        book.add_order(order).unwrap();

        assert!(book.update_order_status(&order_id, OrderStatus::Filled).is_ok());
        
        let updated_order = book.get_order(&order_id).unwrap();
        assert_eq!(updated_order.status, OrderStatus::Filled);
    }

    #[test]
    fn test_duplicate_order_rejection() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        let order1 = create_test_order(OrderSide::Buy, 50000.0, 1.0);
        let mut order2 = create_test_order(OrderSide::Buy, 50100.0, 1.0);
        order2.id = order1.id; // Same ID

        book.add_order(order1).unwrap();
        assert!(book.add_order(order2).is_err());
    }

    #[test]
    fn test_performance_bottlenecks() {
        let mut book = SlowOrderBook::new("BTCUSD".to_string());
        
        // Add many orders to demonstrate O(N) performance issues
        let mut order_ids = Vec::new();
        for i in 0..100 {
            let order = create_test_order(
                if i % 2 == 0 { OrderSide::Buy } else { OrderSide::Sell },
                50000.0 + i as f64,
                1.0
            );
            order_ids.push(order.id);
            book.add_order(order).unwrap();
        }

        // This will be slow because it's O(N) for each lookup
        for order_id in &order_ids {
            assert!(book.get_order(order_id).is_some());
        }

        // This will be slow because it's O(N) for each cancellation
        for order_id in order_ids {
            assert!(book.cancel_order(&order_id).is_ok());
        }

        assert_eq!(book.depth(), (0, 0));
    }
}