//! Optimized OrderBook Implementation with O(1) Performance
//!
//! This module contains the refactored OrderBook implementation that achieves O(1) performance
//! for critical operations using HashMap index optimization.

use chrono::{DateTime, Utc};
use common::{OrderId, OrderSide, OrderStatus, OrderType, Price, Quantity};
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, VecDeque};

/// Optimized Order struct without redundant instrument field
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
/// OptimizedOrder
///
/// Auto-generated documentation placeholder - enhance with specifics
pub struct OptimizedOrder {
    /// Id
    pub id: OrderId,
    // Removed redundant instrument field - OrderBook now owns this
    /// 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 OptimizedOrder {
    pub fn new(
        side: OrderSide,
        quantity: Quantity,
        price: Option<Price>,
        order_type: OrderType,
    ) -> Self {
        Self {
            id: OrderId::new(),
            side,
            order_type,
            quantity,
            price,
            timestamp: Utc::now(),
            status: OrderStatus::Pending,
        }
    }
}

/// Order location in the order book for O(1) tracking
#[derive(Debug, Clone, Copy, PartialEq)]
/// OrderLocation
///
/// Auto-generated documentation placeholder - enhance with specifics
pub struct OrderLocation {
    /// Price
    pub price: Option<Price>,
    /// Side
    pub side: OrderSide,
    /// Index
    pub index: usize, // Index in the VecDeque for the price level
}

/// Optimized OrderBook with O(1) performance for critical operations
#[derive(Debug, Clone)]
/// FastOrderBook
///
/// Auto-generated documentation placeholder - enhance with specifics
pub struct FastOrderBook {
    /// Instrument
    pub instrument: String,
    /// Bid Orders
    pub bid_orders: VecDeque<OptimizedOrder>,
    /// Ask Orders
    pub ask_orders: VecDeque<OptimizedOrder>,
    /// O(1) OPTIMIZATION: `HashMap` index for instant order lookups
    pub order_index: HashMap<OrderId, OrderLocation>,
}

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

    /// Add order with O(1) performance for duplicate checking
    /// OPTIMIZED: Uses `HashMap` for instant duplicate detection
    pub fn add_order(&mut self, order: OptimizedOrder) -> Result<(), String> {
        // O(1) OPTIMIZATION: Instant duplicate check using HashMap
        if self.order_index.contains_key(&order.id) {
            return Err("Order ID already exists".to_string());
        }

        let order_id = order.id;
        let side = order.side;
        let price = order.price;

        // Add the order (maintaining price-time priority)
        let index = 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.iter().enumerate() {
                        if let Some(existing_price) = existing.price {
                            if order_price > existing_price {
                                insert_index = i;
                                break;
                            }
                        }
                    }
                }

                // Update indices for all orders after insertion point
                for (_existing_order_id, location) in self.order_index.iter_mut() {
                    if location.side == OrderSide::Buy && location.index >= insert_index {
                        location.index += 1;
                    }
                }

                self.bid_orders.insert(insert_index, order);
                insert_index
            },
            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.iter().enumerate() {
                        if let Some(existing_price) = existing.price {
                            if order_price < existing_price {
                                insert_index = i;
                                break;
                            }
                        }
                    }
                }

                // Update indices for all orders after insertion point
                for (_existing_order_id, location) in self.order_index.iter_mut() {
                    if location.side == OrderSide::Sell && location.index >= insert_index {
                        location.index += 1;
                    }
                }

                self.ask_orders.insert(insert_index, order);
                insert_index
            },
        };

        // O(1) OPTIMIZATION: Add to HashMap index for instant future lookups
        let location = OrderLocation { price, side, index };
        self.order_index.insert(order_id, location);

        Ok(())
    }

    /// Cancel order with O(1) performance
    /// OPTIMIZED: Uses `HashMap` to find order instantly, then removes efficiently
    pub fn cancel_order(&mut self, order_id: &OrderId) -> Result<OptimizedOrder, String> {
        // O(1) OPTIMIZATION: Instant lookup using HashMap
        let location = self
            .order_index
            .remove(order_id)
            .ok_or_else(|| "Order not found".to_string())?;

        // Remove from the appropriate side
        let removed_order = match location.side {
            OrderSide::Buy => {
                if location.index >= self.bid_orders.len() {
                    return Err("Invalid order index".to_string());
                }

                let order = self
                    .bid_orders
                    .remove(location.index)
                    .ok_or_else(|| "Failed to remove order".to_string())?;

                // Update indices for all orders after removal point
                for (_existing_order_id, existing_location) in self.order_index.iter_mut() {
                    if existing_location.side == OrderSide::Buy
                        && existing_location.index > location.index
                    {
                        existing_location.index -= 1;
                    }
                }

                order
            },
            OrderSide::Sell => {
                if location.index >= self.ask_orders.len() {
                    return Err("Invalid order index".to_string());
                }

                let order = self
                    .ask_orders
                    .remove(location.index)
                    .ok_or_else(|| "Failed to remove order".to_string())?;

                // Update indices for all orders after removal point
                for (_existing_order_id, existing_location) in self.order_index.iter_mut() {
                    if existing_location.side == OrderSide::Sell
                        && existing_location.index > location.index
                    {
                        existing_location.index -= 1;
                    }
                }

                order
            },
        };

        Ok(removed_order)
    }

    /// Get order by ID with O(1) performance
    /// OPTIMIZED: Uses `HashMap` for instant lookup
    pub fn get_order(&self, order_id: &OrderId) -> Option<&OptimizedOrder> {
        // O(1) OPTIMIZATION: Instant lookup using HashMap
        if let Some(location) = self.order_index.get(order_id) {
            match location.side {
                OrderSide::Buy => self.bid_orders.get(location.index),
                OrderSide::Sell => self.ask_orders.get(location.index),
            }
        } else {
            // None variant
            None
        }
    }

    /// Get mutable order by ID with O(1) performance
    /// OPTIMIZED: Uses `HashMap` for instant lookup
    pub fn get_order_mut(&mut self, order_id: &OrderId) -> Option<&mut OptimizedOrder> {
        // O(1) OPTIMIZATION: Instant lookup using HashMap
        if let Some(location) = self.order_index.get(order_id).cloned() {
            match location.side {
                OrderSide::Buy => self.bid_orders.get_mut(location.index),
                OrderSide::Sell => self.ask_orders.get_mut(location.index),
            }
        } else {
            // None variant
            None
        }
    }

    /// Update order status with O(1) performance
    /// OPTIMIZED: Uses `HashMap` for instant lookup
    pub fn update_order_status(
        &mut self,
        order_id: &OrderId,
        status: OrderStatus,
    ) -> Result<(), String> {
        // O(1) OPTIMIZATION: Instant lookup and update using HashMap
        if let Some(order) = self.get_order_mut(order_id) {
            order.status = status;
            Ok(())
        } else {
            Err("Order not found".to_string())
        }
    }

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

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

    /// Get market depth (O(1) - 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 for iteration
    pub fn get_orders_by_side(&self, side: OrderSide) -> &VecDeque<OptimizedOrder> {
        match side {
            OrderSide::Buy => &self.bid_orders,
            OrderSide::Sell => &self.ask_orders,
        }
    }

    /// Validate internal consistency (for testing)
    pub fn validate_integrity(&self) -> Result<(), String> {
        // Check that all orders in VecDeques are properly indexed
        for (i, order) in self.bid_orders.iter().enumerate() {
            if let Some(location) = self.order_index.get(&order.id) {
                if location.side != OrderSide::Buy || location.index != i {
                    return Err(format!(
                        "Integrity error: Bid order {} has wrong index. Expected: {}, Found: {}",
                        order.id, i, location.index
                    ));
                }
            } else {
                return Err(format!(
                    "Integrity error: Bid order {} not found in index",
                    order.id
                ));
            }
        }

        for (i, order) in self.ask_orders.iter().enumerate() {
            if let Some(location) = self.order_index.get(&order.id) {
                if location.side != OrderSide::Sell || location.index != i {
                    return Err(format!(
                        "Integrity error: Ask order {} has wrong index. Expected: {}, Found: {}",
                        order.id, i, location.index
                    ));
                }
            } else {
                return Err(format!(
                    "Integrity error: Ask order {} not found in index",
                    order.id
                ));
            }
        }

        // Check that all indexed orders exist in VecDeques
        for (order_id, location) in &self.order_index {
            let order_exists = match location.side {
                OrderSide::Buy => self
                    .bid_orders
                    .get(location.index)
                    .map(|o| o.id == *order_id)
                    .unwrap_or(false),
                OrderSide::Sell => self
                    .ask_orders
                    .get(location.index)
                    .map(|o| o.id == *order_id)
                    .unwrap_or(false),
            };

            if !order_exists {
                return Err(format!(
                    "Integrity error: Indexed order {} not found in VecDeque",
                    order_id
                ));
            }
        }

        Ok(())
    }

    /// Get total number of orders - O(1)
    pub fn total_orders(&self) -> usize {
        self.order_index.len()
    }

    /// Check if order book is empty - O(1)
    pub fn is_empty(&self) -> bool {
        self.order_index.is_empty()
    }

    /// Get spread between best bid and ask
    pub fn spread(&self) -> Option<Price> {
        match (self.best_bid(), self.best_ask()) {
            (Some(bid), Some(ask)) => {
                if let (Some(bid_price), Some(ask_price)) = (bid.price, ask.price) {
                    Some(Price::from_raw(
                        ask_price.raw_value() - bid_price.raw_value(),
                    ))
                } else {
                    // None variant
                    None
                }
            },
            _ => None,
        }
    }
}

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

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

    #[test]
    fn test_optimized_order_book_creation() {
        let book = FastOrderBook::new("BTCUSD".to_string());
        assert_eq!(book.instrument, "BTCUSD");
        assert_eq!(book.depth(), (0, 0));
        assert!(book.is_empty());
        assert_eq!(book.total_orders(), 0);
    }

    #[test]
    fn test_add_orders_o1_performance() {
        let mut book = FastOrderBook::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);

        // These operations should be O(1) for duplicate checking
        assert!(book.add_order(bid.clone()).is_ok());
        assert!(book.add_order(ask).is_ok());

        assert_eq!(book.depth(), (1, 1));
        assert_eq!(book.total_orders(), 2);

        // Test duplicate rejection with O(1) performance
        assert!(book.add_order(bid).is_err());
        assert_eq!(book.total_orders(), 2);

        // Validate internal consistency
        assert!(book.validate_integrity().is_ok());
    }

    #[test]
    fn test_cancel_order_o1_performance() {
        let mut book = FastOrderBook::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));

        // O(1) cancellation
        let cancelled = book.cancel_order(&order_id).unwrap();
        assert_eq!(cancelled.id, order_id);
        assert_eq!(book.depth(), (0, 0));
        assert!(book.is_empty());

        // Validate internal consistency
        assert!(book.validate_integrity().is_ok());
    }

    #[test]
    fn test_get_order_o1_performance() {
        let mut book = FastOrderBook::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();

        // O(1) lookup
        let found = book.get_order(&order_id);
        assert!(found.is_some());
        assert_eq!(found.unwrap().id, order_id);

        // Test non-existent order
        let fake_id = OrderId::new();
        assert!(book.get_order(&fake_id).is_none());
    }

    #[test]
    fn test_update_status_o1_performance() {
        let mut book = FastOrderBook::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();

        // O(1) status update
        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_best_bid_ask_and_spread() {
        let mut book = FastOrderBook::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 spread calculation
        let spread = book.spread().unwrap();
        assert_eq!(spread.to_f64(), 100.0);

        // Validate internal consistency
        assert!(book.validate_integrity().is_ok());
    }

    #[test]
    fn test_performance_comparison() {
        let mut book = FastOrderBook::new("BTCUSD".to_string());

        // Add many orders to demonstrate O(1) performance
        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();
        }

        assert_eq!(book.total_orders(), 100);

        // All lookups should be O(1)
        for order_id in &order_ids {
            assert!(book.get_order(order_id).is_some());
        }

        // All cancellations should be O(1)
        for order_id in order_ids {
            assert!(book.cancel_order(&order_id).is_ok());
        }

        assert_eq!(book.depth(), (0, 0));
        assert!(book.is_empty());

        // Validate final state
        assert!(book.validate_integrity().is_ok());
    }

    #[test]
    fn test_index_consistency_under_operations() {
        let mut book = FastOrderBook::new("BTCUSD".to_string());

        // Add multiple orders at different price levels
        let orders = vec![
            create_test_order(OrderSide::Buy, 50000.0, 1.0),
            create_test_order(OrderSide::Buy, 49900.0, 1.0),
            create_test_order(OrderSide::Buy, 50100.0, 1.0), // Best bid
            create_test_order(OrderSide::Sell, 50200.0, 1.0), // Best ask
            create_test_order(OrderSide::Sell, 50300.0, 1.0),
            create_test_order(OrderSide::Sell, 50150.0, 1.0),
        ];

        let mut order_ids = Vec::new();
        for order in orders {
            order_ids.push(order.id);
            book.add_order(order).unwrap();

            // Validate consistency after each addition
            assert!(book.validate_integrity().is_ok());
        }

        // Cancel orders in different order
        book.cancel_order(&order_ids[1]).unwrap(); // Remove middle bid
        assert!(book.validate_integrity().is_ok());

        book.cancel_order(&order_ids[4]).unwrap(); // Remove middle ask
        assert!(book.validate_integrity().is_ok());

        book.cancel_order(&order_ids[2]).unwrap(); // Remove best bid
        assert!(book.validate_integrity().is_ok());

        // Final validation
        assert!(book.validate_integrity().is_ok());
    }
}
