import numpy as np
import pandas as pd
from collections import defaultdict
import heapq

class LimitOrderBook:
    """
    Comprehensive Limit Order Book implementation
    """
    def __init__(self, symbol):
        self.symbol = symbol
        # Price levels: bid (buy) and ask (sell)
        self.bids = defaultdict(list)  # Price -> list of orders
        self.asks = defaultdict(list)  # Price -> list of orders
        self.orders = {}  # Order ID -> Order details
        
        # Best prices
        self.best_bid = None
        self.best_ask = None
        
        # Market depth
        self.bid_depth = {}
        self.ask_depth = {}
    
    def add_order(self, order_id, side, price, quantity, order_type='limit'):
        """
        Add order to the book
        
        Parameters:
        - order_id: Unique order identifier
        - side: 'buy' or 'sell'
        - price: Limit price
        - quantity: Number of shares
        - order_type: 'limit' or 'market'
        """
        order = {
            'id': order_id,
            'side': side,
            'price': price,
            'quantity': quantity,
            'type': order_type,
            'status': 'active'
        }
        
        self.orders[order_id] = order
        
        if side == 'buy':
            self.bids[price].append(order)
            if self.best_bid is None or price > self.best_bid:
                self.best_bid = price
        else:
            self.asks[price].append(order)
            if self.best_ask is None or price < self.best_ask:
                self.best_ask = price
        
        # Update depth
        self.update_depth()
    
    def cancel_order(self, order_id):
        """
        Cancel an active order
        """
        if order_id not in self.orders:
            return False
        
        order = self.orders[order_id]
        if order['status'] != 'active':
            return False
        
        # Remove from price level
        if order['side'] == 'buy':
            self.bids[order['price']] = [o for o in self.bids[order['price']] if o['id'] != order_id]
            if not self.bids[order['price']]:
                del self.bids[order['price']]
        else:
            self.asks[order['price']] = [o for o in self.asks[order['price']] if o['id'] != order_id]
            if not self.asks[order['price']]:
                del self.asks[order['price']]
        
        order['status'] = 'cancelled'
        
        # Update best prices
        self.update_best_prices()
        self.update_depth()
        
        return True
    
    def match_order(self, order_id):
        """
        Match order against existing orders
        """
        if order_id not in self.orders:
            return None
        
        order = self.orders[order_id]
        if order['status'] != 'active':
            return None
        
        trades = []
        remaining_quantity = order['quantity']
        
        if order['side'] == 'buy':
            # Match against asks (sell orders)
            while remaining_quantity > 0 and self.best_ask is not None:
                if order['price'] < self.best_ask:
                    break  # Price too low
                
                # Get best ask orders
                ask_orders = self.asks[self.best_ask]
                if not ask_orders:
                    self.update_best_prices()
                    break
                
                # Match with first order in queue (FIFO)
                ask_order = ask_orders[0]
                match_quantity = min(remaining_quantity, ask_order['quantity'])
                
                # Execute trade
                trade = {
                    'buy_order': order_id,
                    'sell_order': ask_order['id'],
                    'price': self.best_ask,
                    'quantity': match_quantity
                }
                trades.append(trade)
                
                # Update quantities
                remaining_quantity -= match_quantity
                ask_order['quantity'] -= match_quantity
                
                # Remove if fully filled
                if ask_order['quantity'] == 0:
                    ask_orders.pop(0)
                    ask_order['status'] = 'filled'
                    if not ask_orders:
                        del self.asks[self.best_ask]
                        self.update_best_prices()
        
        else:  # Sell order
            # Match against bids (buy orders)
            while remaining_quantity > 0 and self.best_bid is not None:
                if order['price'] > self.best_bid:
                    break
                
                bid_orders = self.bids[self.best_bid]
                if not bid_orders:
                    self.update_best_prices()
                    break
                
                bid_order = bid_orders[0]
                match_quantity = min(remaining_quantity, bid_order['quantity'])
                
                trade = {
                    'buy_order': bid_order['id'],
                    'sell_order': order_id,
                    'price': self.best_bid,
                    'quantity': match_quantity
                }
                trades.append(trade)
                
                remaining_quantity -= match_quantity
                bid_order['quantity'] -= match_quantity
                
                if bid_order['quantity'] == 0:
                    bid_orders.pop(0)
                    bid_order['status'] = 'filled'
                    if not bid_orders:
                        del self.bids[self.best_bid]
                        self.update_best_prices()
        
        # Update order status
        if remaining_quantity == 0:
            order['status'] = 'filled'
        else:
            order['quantity'] = remaining_quantity
        
        return trades
    
    def update_best_prices(self):
        """
        Update best bid and ask prices
        """
        self.best_bid = max(self.bids.keys()) if self.bids else None
        self.best_ask = min(self.asks.keys()) if self.asks else None
    
    def update_depth(self):
        """
        Update market depth at each price level
        """
        self.bid_depth = {
            price: sum(o['quantity'] for o in orders)
            for price, orders in self.bids.items()
        }
        
        self.ask_depth = {
            price: sum(o['quantity'] for o in orders)
            for price, orders in self.asks.items()
        }
    
    def get_top_of_book(self):
        """
        Get top of book (best bid and ask)
        """
        return {
            'best_bid': self.best_bid,
            'best_ask': self.best_ask,
            'bid_depth': self.bid_depth.get(self.best_bid, 0) if self.best_bid else 0,
            'ask_depth': self.ask_depth.get(self.best_ask, 0) if self.best_ask else 0,
            'spread': self.best_ask - self.best_bid if (self.best_bid and self.best_ask) else None
        }
    
    def get_depth_at_price(self, price, side='bid'):
        """
        Get depth at specific price level
        """
        if side == 'bid':
            return self.bid_depth.get(price, 0)
        else:
            return self.ask_depth.get(price, 0)

Price Formation Framework:

The observed price at time t is influenced by:

1. Fundamental Value (V_t):
   V_t = V_{t-1} + ε_t
   Where ε_t is the innovation in fundamental value

2. Order Flow Imbalance (OFI_t):
   OFI_t = Buy_Volume_t - Sell_Volume_t

3. Price Impact:
   ΔP_t = α × OFI_t + β × OFI_{t-1} + γ × V_t

4. Bid-Ask Spread Components:
   Spread_t = (Ask_t - Bid_t) / Mid_Price_t

Components:
- Order Processing Cost: Cost of matching orders
- Inventory Cost: Cost of holding inventory
- Adverse Selection Cost: Cost of trading with informed traders

class VPINCalculator:
    """
    Volume-Synchronized Probability of Informed Trading (VPIN)
    """
    def __init__(self, bucket_size=50):
        self.bucket_size = bucket_size
        self.buckets = []
        self.vpin_values = []
    
    def add_trade(self, trade):
        """
        Add trade to VPIN calculation
        """
        # Add trade to current bucket
        if not self.buckets:
            self.buckets.append({'buy_volume': 0, 'sell_volume': 0, 'total_volume': 0})
        
        bucket = self.buckets[-1]
        if trade['side'] == 'buy':
            bucket['buy_volume'] += trade['volume']
        else:
            bucket['sell_volume'] += trade['volume']
        bucket['total_volume'] += trade['volume']
        
        # Check if bucket is full
        if bucket['total_volume'] >= self.bucket_size:
            self.buckets.append({'buy_volume': 0, 'sell_volume': 0, 'total_volume': 0})
    
    def calculate_vpin(self, n_buckets=50):
        """
        Calculate VPIN
        """
        if len(self.buckets) < n_buckets:
            return None
        
        # Get last n buckets
        recent_buckets = self.buckets[-n_buckets:]
        
        # Calculate volume imbalance
        total_volume = sum(b['total_volume'] for b in recent_buckets)
        buy_volume = sum(b['buy_volume'] for b in recent_buckets)
        sell_volume = sum(b['sell_volume'] for b in recent_buckets)
        
        # Calculate imbalance
        imbalance = abs(buy_volume - sell_volume) / total_volume
        
        # VPIN
        vpin = imbalance
        
        self.vpin_values.append(vpin)
        
        return vpin
    
    def get_toxicity_score(self):
        """
        Get order flow toxicity score
        """
        if len(self.vpin_values) < 10:
            return 0
        
        recent_vpin = np.mean(self.vpin_values[-10:])
        
        # Thresholds
        if recent_vpin < 0.2:
            return 'low_toxicity'
        elif recent_vpin < 0.4:
            return 'medium_toxicity'
        else:
            return 'high_toxicity'

Total Latency Breakdown:

1. Network Latency (60-70%):
   - Fiber optic propagation: ~5 μs/km
   - Switching/routing: ~1-5 μs per hop
   - Protocol processing: ~10-50 μs

2. Hardware Latency (20-30%):
   - FPGA processing: ~1-10 μs
   - ASIC processing: ~0.1-1 μs
   - CPU processing: ~10-100 μs

3. Software Latency (10-20%):
   - Operating system: ~10-50 μs
   - Application logic: ~1-10 μs
   - Middleware: ~5-20 μs

Total Round Trip Time (RTT):
- Colocation: 10-100 μs
- Same city: 100-500 μs
- Same region: 500-1000 μs
- Cross-continent: 10-50 ms

class FPGAAccelerator:
    """
    Simulate FPGA-based order processing
    """
    def __init__(self, logic_blocks=10000, clock_speed=500):  # MHz
        self.logic_blocks = logic_blocks
        self.clock_speed = clock_speed
        self.pipeline_stages = 4  # Pipeline depth
        
        # FPGA resources
        self.luts = 0  # Look-up tables
        self.registers = 0  # Flip-flops
        self.dsp_blocks = 0  # Digital signal processing
    
    def process_market_data(self, data_packet):
        """
        Process market data at hardware speed
        """
        # Parse data packet
        parsed = self.parse_packet(data_packet)
        
        # Execute trading logic
        trade_signal = self.execute_trading_logic(parsed)
        
        # Generate order
        if trade_signal:
            order = self.generate_order(trade_signal)
            return order
        
        return None
    
    def parse_packet(self, data_packet):
        """
        Parse incoming data packet
        """
        # Binary parsing (fast)
        parsed = {
            'symbol': data_packet[0:4],
            'price': int.from_bytes(data_packet[4:12], 'big'),
            'volume': int.from_bytes(data_packet[12:16], 'big'),
            'timestamp': int.from_bytes(data_packet[16:24], 'big')
        }
        return parsed
    
    def execute_trading_logic(self, parsed_data):
        """
        Execute trading logic in hardware
        """
        # Simple moving average (implemented in hardware)
        # In reality, this would be synthesized to hardware logic
        return parsed_data['price'] > 100  # Buy if price > 100
    
    def generate_order(self, trade_signal):
        """
        Generate order from trade signal
        """
        if trade_signal:
            return {
                'type': 'limit',
                'side': 'buy',
                'price': 100,
                'quantity': 1000
            }
        return None

class MarketMaker:
    """
    Automated market making strategy
    """
    def __init__(self, inventory_capacity=10000, target_inventory=5000, spread_multiplier=1.0):
        self.inventory = 0
        self.inventory_capacity = inventory_capacity
        self.target_inventory = target_inventory
        self.spread_multiplier = spread_multiplier
        
        self.inventory_history = []
        self.pnl = 0
    
    def quote_spread(self, mid_price, volatility):
        """
        Calculate optimal quote spread
        """
        # Base spread
        base_spread = volatility * 0.5  # 0.5x volatility
        
        # Inventory adjustment
        inventory_ratio = (self.inventory - self.target_inventory) / self.inventory_capacity
        
        # Adjust spread based on inventory
        spread = base_spread * (1 + abs(inventory_ratio) * 0.5)
        spread *= self.spread_multiplier
        
        # Quote prices
        bid_price = mid_price - spread / 2
        ask_price = mid_price + spread / 2
        
        return bid_price, ask_price
    
    def adjust_inventory(self, trade_side, quantity):
        """
        Adjust inventory based on executed trades
        """
        if trade_side == 'buy':
            self.inventory += quantity
        else:
            self.inventory -= quantity
        
        self.inventory_history.append(self.inventory)
    
    def calculate_pnl(self, trades):
        """
        Calculate P&L from market making
        """
        pnl = 0
        for trade in trades:
            if trade['side'] == 'buy':
                pnl -= trade['price'] * trade['quantity']
            else:
                pnl += trade['price'] * trade['quantity']
        
        self.pnl += pnl
        return self.pnl

class StatisticalArbitrage:
    """
    Statistical arbitrage strategy using cointegration
    """
    def __init__(self, lookback=100, entry_zscore=2.0, exit_zscore=0.5):
        self.lookback = lookback
        self.entry_zscore = entry_zscore
        self.exit_zscore = exit_zscore
        
        # Store prices for cointegrated pairs
        self.prices_a = []
        self.prices_b = []
        self.spread = []
        self.zscore = []
        self.position = 0
    
    def check_cointegration(self, prices_a, prices_b):
        """
        Check cointegration between two price series
        """
        import statsmodels.api as sm
        
        # OLS regression
        X = sm.add_constant(prices_a)
        model = sm.OLS(prices_b, X)
        results = model.fit()
        
        # Residuals
        residuals = results.resid
        
        # ADF test on residuals
        from statsmodels.tsa.stattools import adfuller
        adf_result = adfuller(residuals)
        
        # Cointegrated if ADF test rejects unit root
        is_cointegrated = adf_result[1] < 0.05
        
        return is_cointegrated, results.params[1]  # Hedge ratio
    
    def generate_signal(self, price_a, price_b, hedge_ratio):
        """
        Generate trading signal
        """
        # Update price series
        self.prices_a.append(price_a)
        self.prices_b.append(price_b)
        
        if len(self.prices_a) > self.lookback:
            self.prices_a.pop(0)
            self.prices_b.pop(0)
        
        # Calculate spread
        spread_value = price_b - hedge_ratio * price_a
        self.spread.append(spread_value)
        
        if len(self.spread) > self.lookback:
            self.spread.pop(0)
        
        # Calculate z-score
        if len(self.spread) >= self.lookback:
            mean_spread = np.mean(self.spread)
            std_spread = np.std(self.spread)
            zscore = (spread_value - mean_spread) / std_spread
            self.zscore.append(zscore)
        else:
            zscore = 0
        
        # Generate signal
        if abs(zscore) > self.entry_zscore:
            if zscore > 0:
                # Sell spread (short B, long A)
                return 'short_spread', zscore
            else:
                # Buy spread (long B, short A)
                return 'long_spread', zscore
        elif abs(zscore) < self.exit_zscore and self.position != 0:
            # Exit position
            return 'exit', zscore
        else:
            return 'hold', zscore

class AdverseSelectionMonitor:
    """
    Monitor adverse selection risk
    """
    def __init__(self):
        self.trade_history = []
        self.toxicity_scores = []
    
    def detect_toxic_flow(self, trade, mid_price):
        """
        Detect toxic order flow
        """
        # Calculate price impact
        price_impact = trade['price'] - mid_price
        
        # Classify trades
        if trade['side'] == 'buy' and price_impact > 0:
            # Aggressive buy: likely informed
            toxicity = min(price_impact / mid_price, 0.01)
        elif trade['side'] == 'sell' and price_impact < 0:
            # Aggressive sell: likely informed
            toxicity = min(abs(price_impact) / mid_price, 0.01)
        else:
            toxicity = 0
        
        # Store toxicity
        self.toxicity_scores.append(toxicity)
        
        if len(self.toxicity_scores) > 1000:
            self.toxicity_scores.pop(0)
        
        return toxicity
    
    def get_toxicity_metrics(self):
        """
        Calculate toxicity metrics
        """
        if not self.toxicity_scores:
            return {'avg_toxicity': 0, 'current_toxicity': 0}
        
        return {
            'avg_toxicity': np.mean(self.toxicity_scores),
            'current_toxicity': self.toxicity_scores[-1] if self.toxicity_scores else 0,
            'recent_toxicity': np.mean(self.toxicity_scores[-10:]) if len(self.toxicity_scores) >= 10 else 0,
            'max_toxicity': np.max(self.toxicity_scores)
        }
    
    def adjust_spread_for_toxicity(self, base_spread, toxicity):
        """
        Adjust spread based on toxicity
        """
        # Increase spread when toxicity is high
        spread_multiplier = 1 + toxicity * 10
        
        return base_spread * spread_multiplier

class FlashCrashDetector:
    """
    Detect and analyze flash crashes
    """
    def __init__(self, price_window=100, volatility_threshold=5):
        self.price_window = price_window
        self.volatility_threshold = volatility_threshold
        self.price_history = []
        self.crash_events = []
    
    def detect_flash_crash(self, price, timestamp):
        """
        Detect potential flash crash
        """
        self.price_history.append(price)
        
        if len(self.price_history) > self.price_window:
            self.price_history.pop(0)
        
        if len(self.price_history) < 10:
            return None
        
        # Calculate return and volatility
        recent_prices = np.array(self.price_history)
        returns = np.diff(np.log(recent_prices))
        
        # Extreme return
        extreme_return = abs(returns[-1])
        return_vol = np.std(returns)
        
        if return_vol > 0:
            z_score = extreme_return / return_vol
            
            if z_score > self.volatility_threshold:
                # Potential flash crash
                crash_event = {
                    'timestamp': timestamp,
                    'price': price,
                    'return': returns[-1],
                    'z_score': z_score,
                    'volatility': return_vol,
                    'severity': min(z_score / self.volatility_threshold, 3)
                }
                self.crash_events.append(crash_event)
                return crash_event
        
        return None
    
    def get_crash_statistics(self):
        """
        Get flash crash statistics
        """
        if not self.crash_events:
            return {'total_crashes': 0, 'avg_severity': 0}
        
        severities = [e['severity'] for e in self.crash_events]
        
        return {
            'total_crashes': len(self.crash_events),
            'avg_severity': np.mean(severities),
            'max_severity': np.max(severities),
            'recent_crash': self.crash_events[-1] if self.crash_events else None
        }