ruvector-mincut 2.0.6

//! Comprehensive tests for j-Tree hierarchical decomposition.
//!
//! Tests the correctness of:
//! - LazyLevel state machine (Unmaterialized -> Materialized -> Dirty)
//! - BmsspJTreeLevel cut queries and caching
//! - LazyJTreeHierarchy demand-paging and hierarchy consistency
//! - TwoTierCoordinator approximate/exact escalation
//!
//! Based on ADR-002: Dynamic Hierarchical j-Tree Decomposition
//! and its addendums for SOTA optimizations and BMSSP integration.

#![cfg(feature = "jtree")]

use std::collections::{HashMap, HashSet};
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;

// ============================================================================
// Test Helper Structures (mock implementations for testing)
// These mirror the structures defined in ADR-002 and addendums
// ============================================================================

/// Represents the lazy evaluation state for a j-tree level
#[derive(Clone, Debug, PartialEq)]
pub enum LazyLevel<T: Clone> {
    /// Not yet computed - saves memory until needed
    Unmaterialized,
    /// Computed and valid - ready for queries
    Materialized(T),
    /// Previously computed but now stale - can warm-start
    Dirty(T),
}

impl<T: Clone> LazyLevel<T> {
    /// Check if level is materialized and valid
    pub fn is_materialized(&self) -> bool {
        matches!(self, LazyLevel::Materialized(_))
    }

    /// Check if level needs recomputation
    pub fn is_dirty(&self) -> bool {
        matches!(self, LazyLevel::Dirty(_))
    }

    /// Check if level has never been computed
    pub fn is_unmaterialized(&self) -> bool {
        matches!(self, LazyLevel::Unmaterialized)
    }

    /// Get the data if materialized
    pub fn as_materialized(&self) -> Option<&T> {
        match self {
            LazyLevel::Materialized(data) => Some(data),
            _ => None,
        }
    }

    /// Get the stale data for warm-start
    pub fn as_dirty(&self) -> Option<&T> {
        match self {
            LazyLevel::Dirty(data) => Some(data),
            _ => None,
        }
    }

    /// Transition to materialized state
    pub fn materialize(&mut self, data: T) {
        *self = LazyLevel::Materialized(data);
    }

    /// Mark as dirty (needs recomputation)
    pub fn mark_dirty(&mut self) {
        if let LazyLevel::Materialized(data) = self {
            *self = LazyLevel::Dirty(data.clone());
        }
    }

    /// Invalidate (become unmaterialized)
    pub fn invalidate(&mut self) {
        *self = LazyLevel::Unmaterialized;
    }
}

/// Mock j-tree level data for testing
#[derive(Clone, Debug)]
pub struct JTreeLevelData {
    pub level: usize,
    pub vertex_count: usize,
    pub min_cut_value: f64,
    pub computation_count: Arc<AtomicUsize>,
}

impl JTreeLevelData {
    pub fn new(level: usize, vertices: usize) -> Self {
        Self {
            level,
            vertex_count: vertices,
            min_cut_value: vertices as f64 * 0.5,
            computation_count: Arc::new(AtomicUsize::new(0)),
        }
    }
}

/// BMSSP-backed j-tree level for cut queries (mock implementation)
/// Based on ADR-002-addendum-bmssp-integration.md
#[derive(Clone)]
pub struct BmsspJTreeLevel {
    /// Number of vertices at this level
    vertex_count: usize,
    /// Cached path distances (= cut values in dual)
    path_cache: HashMap<(u64, u64), f64>,
    /// Edge weights (source, target) -> weight
    edges: HashMap<(u64, u64), f64>,
    /// Level index in hierarchy
    level: usize,
    /// Cache hit counter for testing
    cache_hits: Arc<AtomicUsize>,
    /// Cache miss counter for testing
    cache_misses: Arc<AtomicUsize>,
}

impl BmsspJTreeLevel {
    /// Create a new BMSSP-backed level
    pub fn new(vertex_count: usize, level: usize) -> Self {
        Self {
            vertex_count,
            path_cache: HashMap::new(),
            edges: HashMap::new(),
            level,
            cache_hits: Arc::new(AtomicUsize::new(0)),
            cache_misses: Arc::new(AtomicUsize::new(0)),
        }
    }

    /// Add an edge with weight (capacity)
    pub fn add_edge(&mut self, source: u64, target: u64, weight: f64) {
        // Store edge in canonical order
        let (u, v) = if source < target {
            (source, target)
        } else {
            (target, source)
        };
        self.edges.insert((u, v), weight);
    }

    /// Min-cut between s and t via path-cut duality
    /// Complexity: O(m*log^(2/3) n) vs O(n log n) direct
    pub fn min_cut(&mut self, s: u64, t: u64) -> f64 {
        // Canonical order for cache
        let (u, v) = if s < t { (s, t) } else { (t, s) };

        // Check cache first
        if let Some(&cached) = self.path_cache.get(&(u, v)) {
            self.cache_hits.fetch_add(1, Ordering::Relaxed);
            return cached;
        }

        self.cache_misses.fetch_add(1, Ordering::Relaxed);

        // Compute shortest path (mock: simple sum of edge weights on path)
        let cut_value = self.compute_min_cut(u, v);

        // Cache for future queries (both directions)
        self.path_cache.insert((u, v), cut_value);

        cut_value
    }

    /// Multi-terminal cut using BMSSP multi-source approach
    pub fn multi_terminal_cut(&mut self, terminals: &[u64]) -> f64 {
        if terminals.len() < 2 {
            return f64::INFINITY;
        }

        let mut min_cut = f64::INFINITY;

        // Find minimum pairwise cut among terminals
        for (i, &s) in terminals.iter().enumerate() {
            for &t in terminals.iter().skip(i + 1) {
                let cut = self.min_cut(s, t);
                min_cut = min_cut.min(cut);
            }
        }

        min_cut
    }

    /// Invalidate cache for affected vertices
    pub fn invalidate_cache(&mut self, affected: &[u64]) {
        let affected_set: HashSet<_> = affected.iter().copied().collect();
        self.path_cache
            .retain(|(u, v), _| !affected_set.contains(u) && !affected_set.contains(v));
    }

    /// Clear entire cache
    pub fn clear_cache(&mut self) {
        self.path_cache.clear();
    }

    /// Get cache statistics
    pub fn cache_stats(&self) -> (usize, usize) {
        (
            self.cache_hits.load(Ordering::Relaxed),
            self.cache_misses.load(Ordering::Relaxed),
        )
    }

    /// Mock computation: find min-cut using simple path analysis
    fn compute_min_cut(&self, _s: u64, _t: u64) -> f64 {
        // Simplified: return sum of minimum edge weight on any path
        // In real implementation, this would use BMSSP shortest path
        self.edges
            .values()
            .copied()
            .min_by(|a, b| a.partial_cmp(b).unwrap())
            .unwrap_or(f64::INFINITY)
    }
}

/// Lazy j-tree hierarchy with demand-paged levels
/// Based on ADR-002-addendum-sota-optimizations.md
pub struct LazyJTreeHierarchy {
    /// Level states
    levels: Vec<LazyLevel<JTreeLevelData>>,
    /// Bit set of materialized levels
    materialized: HashSet<usize>,
    /// Bit set of dirty levels
    dirty: HashSet<usize>,
    /// Approximation quality per level
    alpha: f64,
    /// Total computation count for testing
    total_computations: AtomicUsize,
}

impl LazyJTreeHierarchy {
    /// Create hierarchy with given number of levels
    pub fn new(num_levels: usize, alpha: f64) -> Self {
        let levels = (0..num_levels).map(|_| LazyLevel::Unmaterialized).collect();
        Self {
            levels,
            materialized: HashSet::new(),
            dirty: HashSet::new(),
            alpha,
            total_computations: AtomicUsize::new(0),
        }
    }

    /// Get number of levels
    pub fn num_levels(&self) -> usize {
        self.levels.len()
    }

    /// Query approximate min-cut with lazy materialization
    pub fn approximate_min_cut(&mut self) -> ApproximateCut {
        // Handle empty hierarchy
        if self.levels.is_empty() {
            return ApproximateCut {
                value: f64::INFINITY,
                approximation_factor: f64::INFINITY,
                level_used: 0,
            };
        }

        let mut current_level = self.levels.len() - 1;

        // Start from coarsest level, refine as needed
        while current_level > 0 {
            self.ensure_materialized(current_level);

            if let Some(data) = self.levels[current_level].as_materialized() {
                // Early termination if approximation is good enough
                let approx_factor = self.alpha.powi((self.levels.len() - current_level) as i32);
                if approx_factor < 2.0 {
                    // Acceptable approximation
                    return ApproximateCut {
                        value: data.min_cut_value,
                        approximation_factor: approx_factor,
                        level_used: current_level,
                    };
                }
            }

            current_level -= 1;
        }

        // Use finest level for best accuracy
        self.ensure_materialized(0);
        if let Some(data) = self.levels[0].as_materialized() {
            ApproximateCut {
                value: data.min_cut_value,
                approximation_factor: 1.0,
                level_used: 0,
            }
        } else {
            ApproximateCut {
                value: f64::INFINITY,
                approximation_factor: f64::INFINITY,
                level_used: 0,
            }
        }
    }

    /// Approximate min-cut at specific level
    pub fn approximate_min_cut_at_level(&mut self, level: usize) -> Option<f64> {
        if level >= self.levels.len() {
            return None;
        }
        self.ensure_materialized(level);
        self.levels[level]
            .as_materialized()
            .map(|d| d.min_cut_value)
    }

    /// Ensure level is materialized (demand-paging)
    fn ensure_materialized(&mut self, level: usize) {
        match &self.levels[level] {
            LazyLevel::Unmaterialized => {
                // First-time computation
                self.total_computations.fetch_add(1, Ordering::Relaxed);
                let vertices = 100 / (level + 1); // Decreasing vertices at higher levels
                let data = JTreeLevelData::new(level, vertices);
                self.levels[level] = LazyLevel::Materialized(data);
                self.materialized.insert(level);
            }
            LazyLevel::Dirty(old_data) => {
                // Warm-start from previous state
                self.total_computations.fetch_add(1, Ordering::Relaxed);
                let mut new_data = old_data.clone();
                new_data.computation_count.fetch_add(1, Ordering::Relaxed);
                // Warm-start: reuse structure, only update affected parts
                new_data.min_cut_value *= 0.95; // Simulated adjustment
                self.levels[level] = LazyLevel::Materialized(new_data);
                self.dirty.remove(&level);
            }
            LazyLevel::Materialized(_) => {
                // Already valid, no-op
            }
        }
    }

    /// Mark levels as dirty after edge update
    pub fn mark_dirty(&mut self, affected_levels: &[usize]) {
        for &level in affected_levels {
            if level < self.levels.len() && self.materialized.contains(&level) {
                self.levels[level].mark_dirty();
                self.dirty.insert(level);
            }
        }
    }

    /// Check if level is materialized
    pub fn is_materialized(&self, level: usize) -> bool {
        level < self.levels.len() && self.materialized.contains(&level)
    }

    /// Check if level is dirty
    pub fn is_dirty(&self, level: usize) -> bool {
        self.dirty.contains(&level)
    }

    /// Get total computation count
    pub fn total_computations(&self) -> usize {
        self.total_computations.load(Ordering::Relaxed)
    }
}

/// Result of approximate min-cut query
#[derive(Debug, Clone)]
pub struct ApproximateCut {
    pub value: f64,
    pub approximation_factor: f64,
    pub level_used: usize,
}

/// Two-tier coordinator for approximate/exact escalation
/// Based on ADR-002: Two-Tier Dynamic Cut Architecture
pub struct TwoTierCoordinator {
    /// Tier 1: Fast approximate hierarchy
    jtree: LazyJTreeHierarchy,
    /// Tier 2: Exact min-cut value (mock)
    exact_value: f64,
    /// Trigger threshold for escalation
    critical_threshold: f64,
    /// Maximum acceptable approximation factor
    max_approx_factor: f64,
    /// Cache for results
    cached_result: Option<CutResult>,
    /// Count of exact queries for testing
    exact_queries: AtomicUsize,
    /// Count of approximate queries for testing
    approx_queries: AtomicUsize,
}

impl TwoTierCoordinator {
    /// Create coordinator with given configuration
    pub fn new(num_levels: usize, exact_value: f64, critical_threshold: f64) -> Self {
        Self {
            jtree: LazyJTreeHierarchy::new(num_levels, 1.5),
            exact_value,
            critical_threshold,
            max_approx_factor: 2.0,
            cached_result: None,
            exact_queries: AtomicUsize::new(0),
            approx_queries: AtomicUsize::new(0),
        }
    }

    /// Query min-cut with tiered strategy
    pub fn min_cut(&mut self, exact_required: bool) -> CutResult {
        // Check cache first
        if let Some(cached) = &self.cached_result {
            if !exact_required || cached.is_exact {
                return cached.clone();
            }
        }

        // Tier 1: Fast approximate query
        let approx = self.jtree.approximate_min_cut();
        self.approx_queries.fetch_add(1, Ordering::Relaxed);

        // Decide whether to escalate to Tier 2
        let should_escalate = exact_required
            || approx.value < self.critical_threshold
            || approx.approximation_factor > self.max_approx_factor;

        let result = if should_escalate {
            // Tier 2: Exact verification
            self.exact_queries.fetch_add(1, Ordering::Relaxed);
            CutResult {
                value: self.exact_value,
                is_exact: true,
                approximation_factor: 1.0,
                tier_used: Tier::Exact,
            }
        } else {
            CutResult {
                value: approx.value,
                is_exact: false,
                approximation_factor: approx.approximation_factor,
                tier_used: Tier::Approximate,
            }
        };

        self.cached_result = Some(result.clone());
        result
    }

    /// Handle edge insertion
    pub fn insert_edge(&mut self, _u: u64, _v: u64, _weight: f64) {
        self.cached_result = None;
        // Mark all levels as dirty for simplicity
        let all_levels: Vec<usize> = (0..self.jtree.num_levels()).collect();
        self.jtree.mark_dirty(&all_levels);
    }

    /// Handle edge deletion
    pub fn delete_edge(&mut self, _u: u64, _v: u64) {
        self.cached_result = None;
        let all_levels: Vec<usize> = (0..self.jtree.num_levels()).collect();
        self.jtree.mark_dirty(&all_levels);
    }

    /// Get query statistics
    pub fn query_stats(&self) -> (usize, usize) {
        (
            self.approx_queries.load(Ordering::Relaxed),
            self.exact_queries.load(Ordering::Relaxed),
        )
    }

    /// Update exact value for testing
    pub fn set_exact_value(&mut self, value: f64) {
        self.exact_value = value;
    }
}

/// Result of cut query
#[derive(Debug, Clone)]
pub struct CutResult {
    pub value: f64,
    pub is_exact: bool,
    pub approximation_factor: f64,
    pub tier_used: Tier,
}

/// Which tier was used for the query
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Tier {
    Approximate,
    Exact,
}

// ============================================================================
// Unit Tests for LazyLevel
// ============================================================================

mod lazy_level_tests {
    use super::*;

    #[test]
    fn test_unmaterialized_to_materialized_transition() {
        let mut level: LazyLevel<JTreeLevelData> = LazyLevel::Unmaterialized;

        assert!(level.is_unmaterialized());
        assert!(!level.is_materialized());
        assert!(!level.is_dirty());
        assert!(level.as_materialized().is_none());

        // Transition to Materialized
        let data = JTreeLevelData::new(0, 100);
        level.materialize(data);

        assert!(!level.is_unmaterialized());
        assert!(level.is_materialized());
        assert!(!level.is_dirty());
        assert!(level.as_materialized().is_some());
        assert_eq!(level.as_materialized().unwrap().vertex_count, 100);
    }

    #[test]
    fn test_materialized_to_dirty_transition() {
        let mut level: LazyLevel<JTreeLevelData> = LazyLevel::Unmaterialized;
        let data = JTreeLevelData::new(0, 100);
        level.materialize(data);

        assert!(level.is_materialized());

        // Mark as dirty
        level.mark_dirty();

        assert!(!level.is_unmaterialized());
        assert!(!level.is_materialized());
        assert!(level.is_dirty());
        assert!(level.as_dirty().is_some());
        assert_eq!(level.as_dirty().unwrap().vertex_count, 100);
    }

    #[test]
    fn test_dirty_to_materialized_warm_start() {
        let mut level: LazyLevel<JTreeLevelData> = LazyLevel::Unmaterialized;

        // First computation
        let data = JTreeLevelData::new(0, 100);
        level.materialize(data);

        // Mark dirty
        level.mark_dirty();
        assert!(level.is_dirty());

        // Get old data for warm-start
        let old_data = level.as_dirty().unwrap().clone();

        // Warm-start re-computation
        let mut new_data = old_data;
        new_data.min_cut_value *= 0.9; // Adjusted value
        level.materialize(new_data);

        assert!(level.is_materialized());
        assert!(!level.is_dirty());
    }

    #[test]
    fn test_cache_invalidation() {
        let mut level: LazyLevel<JTreeLevelData> = LazyLevel::Unmaterialized;
        let data = JTreeLevelData::new(0, 100);
        level.materialize(data);

        assert!(level.is_materialized());

        // Full invalidation
        level.invalidate();

        assert!(level.is_unmaterialized());
        assert!(!level.is_materialized());
        assert!(!level.is_dirty());
    }

    #[test]
    fn test_mark_dirty_on_unmaterialized_is_noop() {
        let mut level: LazyLevel<JTreeLevelData> = LazyLevel::Unmaterialized;

        level.mark_dirty();

        // Should still be unmaterialized
        assert!(level.is_unmaterialized());
        assert!(!level.is_dirty());
    }

    #[test]
    fn test_mark_dirty_on_dirty_is_noop() {
        let mut level: LazyLevel<JTreeLevelData> = LazyLevel::Unmaterialized;
        let data = JTreeLevelData::new(0, 100);
        level.materialize(data);
        level.mark_dirty();

        let original_value = level.as_dirty().unwrap().min_cut_value;

        // Mark dirty again
        level.mark_dirty();

        // Should still be dirty with same data
        assert!(level.is_dirty());
        assert_eq!(level.as_dirty().unwrap().min_cut_value, original_value);
    }
}

// ============================================================================
// Unit Tests for BmsspJTreeLevel
// ============================================================================

mod bmssp_jtree_level_tests {
    use super::*;

    fn create_test_level() -> BmsspJTreeLevel {
        let mut level = BmsspJTreeLevel::new(10, 0);
        // Create a simple path: 0-1-2-3-4
        level.add_edge(0, 1, 5.0);
        level.add_edge(1, 2, 3.0);
        level.add_edge(2, 3, 4.0);
        level.add_edge(3, 4, 2.0);
        level
    }

    #[test]
    fn test_min_cut_returns_correct_approximation() {
        let mut level = create_test_level();

        // Minimum edge weight is 2.0
        let cut = level.min_cut(0, 4);

        assert!(cut >= 0.0);
        assert!(cut < f64::INFINITY);
        // Should find minimum weight edge
        assert_eq!(cut, 2.0);
    }

    #[test]
    fn test_multi_terminal_cut_with_various_terminal_sets() {
        let mut level = create_test_level();

        // Two terminals
        let cut_2 = level.multi_terminal_cut(&[0, 4]);
        assert!(cut_2 >= 0.0);

        // Three terminals
        let cut_3 = level.multi_terminal_cut(&[0, 2, 4]);
        assert!(cut_3 >= 0.0);
        // More terminals shouldn't increase minimum pairwise cut
        assert!(cut_3 <= cut_2 || (cut_3 - cut_2).abs() < f64::EPSILON);

        // Single terminal
        let cut_1 = level.multi_terminal_cut(&[0]);
        assert_eq!(cut_1, f64::INFINITY);

        // Empty terminals
        let cut_0 = level.multi_terminal_cut(&[]);
        assert_eq!(cut_0, f64::INFINITY);
    }

    #[test]
    fn test_cache_hits_and_misses() {
        let mut level = create_test_level();

        // First query - cache miss
        let _ = level.min_cut(0, 4);
        let (hits, misses) = level.cache_stats();
        assert_eq!(hits, 0);
        assert_eq!(misses, 1);

        // Same query - cache hit
        let _ = level.min_cut(0, 4);
        let (hits, misses) = level.cache_stats();
        assert_eq!(hits, 1);
        assert_eq!(misses, 1);

        // Reversed query - should also hit (symmetric)
        let _ = level.min_cut(4, 0);
        let (hits, misses) = level.cache_stats();
        assert_eq!(hits, 2);
        assert_eq!(misses, 1);

        // Different query - cache miss
        let _ = level.min_cut(1, 3);
        let (hits, misses) = level.cache_stats();
        assert_eq!(hits, 2);
        assert_eq!(misses, 2);
    }

    #[test]
    fn test_cache_invalidation_for_affected_vertices() {
        let mut level = create_test_level();

        // Populate cache
        let _ = level.min_cut(0, 4);
        let _ = level.min_cut(1, 3);
        let (hits, _) = level.cache_stats();
        assert_eq!(hits, 0);

        // Verify cache is populated
        let _ = level.min_cut(0, 4);
        let (hits, _) = level.cache_stats();
        assert_eq!(hits, 1);

        // Invalidate cache for vertex 2
        level.invalidate_cache(&[2]);

        // Query involving 2 should miss now, but 0-4 doesn't involve 2
        let _ = level.min_cut(0, 4);
        let (hits, _) = level.cache_stats();
        assert_eq!(hits, 2);

        // Query involving 2 should miss
        let _ = level.min_cut(1, 3);
        let (_, misses) = level.cache_stats();
        // 1-3 path includes vertex 2, so it was invalidated
        assert!(misses >= 2);
    }

    #[test]
    fn test_clear_cache() {
        let mut level = create_test_level();

        // Populate cache
        let _ = level.min_cut(0, 4);
        let _ = level.min_cut(1, 3);
        let _ = level.min_cut(0, 4);
        let (hits, _) = level.cache_stats();
        assert_eq!(hits, 1);

        // Clear cache
        level.clear_cache();

        // All queries should miss now
        let _ = level.min_cut(0, 4);
        let _ = level.min_cut(1, 3);
        let (_, misses) = level.cache_stats();
        assert_eq!(misses, 4);
    }

    #[test]
    fn test_symmetry_of_cut_values() {
        let mut level = create_test_level();

        let cut_forward = level.min_cut(0, 4);
        level.clear_cache();
        let cut_backward = level.min_cut(4, 0);

        assert_eq!(cut_forward, cut_backward);
    }

    #[test]
    fn test_self_cut_is_infinity_or_zero() {
        let mut level = create_test_level();

        // Cut from vertex to itself should be infinity (no separation needed)
        // or zero depending on implementation
        let cut = level.min_cut(2, 2);
        assert!(cut == f64::INFINITY || cut == 0.0 || cut == 2.0);
    }
}

// ============================================================================
// Unit Tests for LazyJTreeHierarchy
// ============================================================================

mod lazy_jtree_hierarchy_tests {
    use super::*;

    #[test]
    fn test_level_demand_paging() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        // Initially no levels materialized
        for level in 0..5 {
            assert!(!hierarchy.is_materialized(level));
        }
        assert_eq!(hierarchy.total_computations(), 0);

        // Query triggers materialization
        let _ = hierarchy.approximate_min_cut();

        // At least one level should be materialized
        let materialized_count = (0..5).filter(|&l| hierarchy.is_materialized(l)).count();
        assert!(materialized_count > 0);
        assert!(hierarchy.total_computations() > 0);
    }

    #[test]
    fn test_approximate_min_cut_at_various_levels() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        // Query at level 0 (finest)
        let cut_0 = hierarchy.approximate_min_cut_at_level(0);
        assert!(cut_0.is_some());
        assert!(hierarchy.is_materialized(0));

        // Query at level 4 (coarsest)
        let cut_4 = hierarchy.approximate_min_cut_at_level(4);
        assert!(cut_4.is_some());
        assert!(hierarchy.is_materialized(4));

        // Coarser levels should have fewer vertices, possibly lower cut
        // (this depends on implementation, but they should be comparable)
        assert!(cut_0.unwrap() > 0.0);
        assert!(cut_4.unwrap() > 0.0);
    }

    #[test]
    fn test_out_of_bounds_level() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        let cut = hierarchy.approximate_min_cut_at_level(10);
        assert!(cut.is_none());
    }

    #[test]
    fn test_mark_dirty_propagation() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        // Materialize some levels
        let _ = hierarchy.approximate_min_cut_at_level(2);
        let _ = hierarchy.approximate_min_cut_at_level(3);
        assert!(hierarchy.is_materialized(2));
        assert!(hierarchy.is_materialized(3));
        assert!(!hierarchy.is_dirty(2));
        assert!(!hierarchy.is_dirty(3));

        // Mark levels dirty
        hierarchy.mark_dirty(&[2, 3]);

        assert!(hierarchy.is_dirty(2));
        assert!(hierarchy.is_dirty(3));
        // Not materialized anymore (in clean sense)
        assert!(!hierarchy.is_materialized(2) || hierarchy.is_dirty(2));
    }

    #[test]
    fn test_warm_start_reduces_computation() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        // First computation
        let _ = hierarchy.approximate_min_cut_at_level(2);
        let first_computations = hierarchy.total_computations();

        // Mark dirty
        hierarchy.mark_dirty(&[2]);
        assert!(hierarchy.is_dirty(2));

        // Re-query - should use warm-start
        let _ = hierarchy.approximate_min_cut_at_level(2);
        let second_computations = hierarchy.total_computations();

        // Warm-start still counts as computation but should use old data
        assert_eq!(second_computations, first_computations + 1);
        assert!(!hierarchy.is_dirty(2));
    }

    #[test]
    fn test_hierarchy_consistency_after_updates() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        // Get initial cuts
        let cut_0 = hierarchy.approximate_min_cut_at_level(0).unwrap();
        let cut_2 = hierarchy.approximate_min_cut_at_level(2).unwrap();
        let cut_4 = hierarchy.approximate_min_cut_at_level(4).unwrap();

        // All cuts should be positive and finite
        assert!(cut_0 > 0.0 && cut_0 < f64::INFINITY);
        assert!(cut_2 > 0.0 && cut_2 < f64::INFINITY);
        assert!(cut_4 > 0.0 && cut_4 < f64::INFINITY);

        // After marking dirty and re-querying, consistency should hold
        hierarchy.mark_dirty(&[0, 2, 4]);
        let new_cut_0 = hierarchy.approximate_min_cut_at_level(0).unwrap();
        let new_cut_2 = hierarchy.approximate_min_cut_at_level(2).unwrap();

        // Warm-start adjusts values slightly
        assert!(new_cut_0 > 0.0);
        assert!(new_cut_2 > 0.0);
    }

    #[test]
    fn test_unmaterialized_levels_not_marked_dirty() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        // Only materialize level 2
        let _ = hierarchy.approximate_min_cut_at_level(2);

        // Try to mark all levels dirty
        hierarchy.mark_dirty(&[0, 1, 2, 3, 4]);

        // Only level 2 should be dirty (was materialized)
        assert!(hierarchy.is_dirty(2));
        assert!(!hierarchy.is_dirty(0)); // Never materialized
        assert!(!hierarchy.is_dirty(1)); // Never materialized
        assert!(!hierarchy.is_dirty(3)); // Never materialized
    }
}

// ============================================================================
// Integration Tests for TwoTierCoordinator
// ============================================================================

mod two_tier_coordinator_tests {
    use super::*;

    #[test]
    fn test_approximate_to_exact_escalation() {
        // Create coordinator with critical threshold that will trigger escalation
        let mut coordinator = TwoTierCoordinator::new(5, 10.0, 100.0);

        // Query without requiring exact - approximate cut < critical threshold
        let result = coordinator.min_cut(false);

        // Should escalate because approximate value is likely < 100.0
        assert!(result.is_exact || result.value < 100.0);
    }

    #[test]
    fn test_exact_required_always_escalates() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 10.0);

        // Query with exact required
        let result = coordinator.min_cut(true);

        assert!(result.is_exact);
        assert_eq!(result.tier_used, Tier::Exact);
        assert_eq!(result.approximation_factor, 1.0);
        assert_eq!(result.value, 50.0);
    }

    #[test]
    fn test_cache_behavior() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 10.0);

        // First query
        let result1 = coordinator.min_cut(false);
        let (approx1, exact1) = coordinator.query_stats();

        // Second query - should use cache
        let result2 = coordinator.min_cut(false);
        let (approx2, exact2) = coordinator.query_stats();

        // Cache should be hit (no additional queries)
        assert_eq!(result1.value, result2.value);
        assert_eq!(approx1, approx2);
        assert_eq!(exact1, exact2);
    }

    #[test]
    fn test_cache_invalidation_on_edge_insert() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 10.0);

        // First query
        let _ = coordinator.min_cut(false);
        let (approx1, _) = coordinator.query_stats();

        // Insert edge - invalidates cache
        coordinator.insert_edge(1, 2, 5.0);

        // Query again - should not use cache
        let _ = coordinator.min_cut(false);
        let (approx2, _) = coordinator.query_stats();

        // Should have made additional approximate query
        assert_eq!(approx2, approx1 + 1);
    }

    #[test]
    fn test_cache_invalidation_on_edge_delete() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 10.0);

        // First query
        let _ = coordinator.min_cut(false);
        let (approx1, _) = coordinator.query_stats();

        // Delete edge - invalidates cache
        coordinator.delete_edge(1, 2);

        // Query again - should not use cache
        let _ = coordinator.min_cut(false);
        let (approx2, _) = coordinator.query_stats();

        assert_eq!(approx2, approx1 + 1);
    }

    #[test]
    fn test_edge_update_propagation() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 10.0);

        // Materialize hierarchy
        let _ = coordinator.min_cut(false);

        // Insert edge - should mark levels dirty
        coordinator.insert_edge(1, 2, 5.0);

        // Query should trigger re-computation
        let before = coordinator.jtree.total_computations();
        let _ = coordinator.min_cut(false);
        let after = coordinator.jtree.total_computations();

        assert!(after > before);
    }

    #[test]
    fn test_approximate_only_when_safe() {
        // Set up coordinator where approximate is sufficient
        let mut coordinator = TwoTierCoordinator::new(5, 100.0, 5.0);
        coordinator.set_exact_value(100.0);

        // Query without exact requirement and with high threshold
        // The approximate value should be above critical threshold
        let result = coordinator.min_cut(false);

        // Depending on approximation factor, may or may not escalate
        // But the result should be reasonable
        assert!(result.value > 0.0);
        assert!(result.value < f64::INFINITY);
    }

    #[test]
    fn test_escalation_when_approx_factor_too_high() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 1.0);
        // Set max_approx_factor very low to force escalation
        coordinator.max_approx_factor = 1.0;

        let result = coordinator.min_cut(false);

        // Should escalate because approximation factor > 1.0
        assert!(result.is_exact || result.approximation_factor <= 1.0);
    }
}

// ============================================================================
// Property-Based Tests
// ============================================================================

mod property_tests {
    use super::*;

    /// Property: Approximate cut <= (1 + epsilon) * exact cut
    #[test]
    fn property_approximate_cut_bound() {
        let epsilon = 0.5;
        let exact_value = 100.0;
        let mut coordinator = TwoTierCoordinator::new(5, exact_value, 10.0);

        for _ in 0..10 {
            let approx = coordinator.jtree.approximate_min_cut();

            // Approximate should not be too far from exact
            // (with poly-log approximation factor)
            let ratio = approx.value / exact_value;

            // The approximation factor should be bounded by alpha^L
            assert!(ratio > 0.0, "Approximate cut should be positive");
            assert!(
                ratio < 100.0 || approx.value == f64::INFINITY,
                "Approximation should be bounded"
            );

            // Mark dirty and re-test
            coordinator.jtree.mark_dirty(&[0, 1, 2, 3, 4]);
        }
    }

    /// Property: Hierarchy consistency after updates
    #[test]
    fn property_hierarchy_consistency_after_updates() {
        let mut hierarchy = LazyJTreeHierarchy::new(5, 1.5);

        for iteration in 0..20 {
            // Materialize random levels
            let levels_to_materialize: Vec<usize> = (0..5).filter(|_| iteration % 2 == 0).collect();

            for level in &levels_to_materialize {
                let _ = hierarchy.approximate_min_cut_at_level(*level);
            }

            // Mark some dirty
            hierarchy.mark_dirty(&[iteration % 5]);

            // Query and verify consistency
            let cut = hierarchy.approximate_min_cut();
            assert!(cut.value > 0.0 || cut.value == f64::INFINITY);
            assert!(cut.approximation_factor >= 1.0);
            assert!(cut.level_used < 5);
        }
    }

    /// Property: Cache coherence - same query returns same result
    #[test]
    fn property_cache_coherence() {
        let mut level = BmsspJTreeLevel::new(10, 0);
        level.add_edge(0, 1, 5.0);
        level.add_edge(1, 2, 3.0);
        level.add_edge(2, 3, 4.0);

        for _ in 0..100 {
            let cut1 = level.min_cut(0, 3);
            let cut2 = level.min_cut(0, 3);
            let cut3 = level.min_cut(3, 0);

            assert_eq!(cut1, cut2, "Same query should return same result");
            assert_eq!(cut1, cut3, "Cut should be symmetric");
        }
    }

    /// Property: Invalidation affects only specified vertices
    #[test]
    fn property_selective_invalidation() {
        let mut level = BmsspJTreeLevel::new(10, 0);
        level.add_edge(0, 1, 5.0);
        level.add_edge(1, 2, 3.0);
        level.add_edge(5, 6, 2.0);
        level.add_edge(6, 7, 4.0);

        // Query both regions
        let _ = level.min_cut(0, 2);
        let _ = level.min_cut(5, 7);

        let (hits_before, misses_before) = level.cache_stats();

        // Invalidate only region 0-2
        level.invalidate_cache(&[1]);

        // Query region 5-7 should still hit
        let _ = level.min_cut(5, 7);
        let (hits_after, _) = level.cache_stats();

        assert!(
            hits_after > hits_before,
            "Unaffected region should still be cached"
        );
    }
}

// ============================================================================
// Edge Case Tests
// ============================================================================

mod edge_case_tests {
    use super::*;

    #[test]
    fn test_empty_hierarchy() {
        let mut hierarchy = LazyJTreeHierarchy::new(0, 1.5);
        assert_eq!(hierarchy.num_levels(), 0);

        let cut = hierarchy.approximate_min_cut();
        assert_eq!(cut.value, f64::INFINITY);
    }

    #[test]
    fn test_single_level_hierarchy() {
        let mut hierarchy = LazyJTreeHierarchy::new(1, 1.5);

        let cut = hierarchy.approximate_min_cut();
        assert!(cut.value > 0.0);
        assert_eq!(cut.level_used, 0);
    }

    #[test]
    fn test_empty_bmssp_level() {
        let mut level = BmsspJTreeLevel::new(0, 0);

        let cut = level.min_cut(0, 1);
        assert_eq!(cut, f64::INFINITY);
    }

    #[test]
    fn test_disconnected_vertices() {
        let mut level = BmsspJTreeLevel::new(10, 0);
        level.add_edge(0, 1, 5.0);
        // 3 and 4 are disconnected from 0-1

        let cut = level.min_cut(0, 3);
        // Should be infinity (disconnected) or minimum edge weight
        assert!(cut > 0.0 || cut == f64::INFINITY);
    }

    #[test]
    fn test_very_large_weights() {
        let mut level = BmsspJTreeLevel::new(5, 0);
        level.add_edge(0, 1, 1e100);
        level.add_edge(1, 2, 1e100);

        let cut = level.min_cut(0, 2);
        assert!(cut.is_finite());
        assert!(cut > 0.0);
    }

    #[test]
    fn test_very_small_weights() {
        let mut level = BmsspJTreeLevel::new(5, 0);
        level.add_edge(0, 1, 1e-100);
        level.add_edge(1, 2, 1e-100);

        let cut = level.min_cut(0, 2);
        assert!(cut > 0.0);
    }

    #[test]
    fn test_coordinator_with_zero_threshold() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, 0.0);

        // Should always escalate (threshold is 0)
        let result = coordinator.min_cut(false);

        // Any approximate value >= 0 so might not escalate
        assert!(result.value > 0.0);
    }

    #[test]
    fn test_coordinator_with_infinite_threshold() {
        let mut coordinator = TwoTierCoordinator::new(5, 50.0, f64::INFINITY);

        // Should escalate (approximate value < infinite threshold is always true)
        let result = coordinator.min_cut(false);

        assert!(result.is_exact);
    }

    #[test]
    fn test_rapid_cache_operations() {
        let mut level = BmsspJTreeLevel::new(10, 0);
        level.add_edge(0, 1, 1.0);
        level.add_edge(1, 2, 2.0);

        // Rapid query-invalidate cycles
        for _ in 0..1000 {
            let _ = level.min_cut(0, 2);
            level.invalidate_cache(&[1]);
            let _ = level.min_cut(0, 2);
            level.clear_cache();
        }

        // Should not panic or have memory issues
        let cut = level.min_cut(0, 2);
        assert!(cut > 0.0);
    }
}

// ============================================================================
// Stress Tests
// ============================================================================

mod stress_tests {
    use super::*;

    #[test]
    fn stress_many_levels() {
        let mut hierarchy = LazyJTreeHierarchy::new(100, 1.1);

        // Query various levels
        for level in (0..100).step_by(10) {
            let cut = hierarchy.approximate_min_cut_at_level(level);
            assert!(cut.is_some());
        }

        // Mark all dirty and re-query
        let all_levels: Vec<usize> = (0..100).collect();
        hierarchy.mark_dirty(&all_levels);

        let cut = hierarchy.approximate_min_cut();
        assert!(cut.value > 0.0);
    }

    #[test]
    fn stress_many_queries() {
        let mut level = BmsspJTreeLevel::new(100, 0);

        // Create dense graph
        for i in 0..99u64 {
            level.add_edge(i, i + 1, (i + 1) as f64);
        }

        // First pass: populate cache
        for i in 0u64..50 {
            for j in (i + 1)..50 {
                let _ = level.min_cut(i, j);
            }
        }

        let (_, first_misses) = level.cache_stats();

        // Second pass: should hit cache for same queries
        for i in 0u64..50 {
            for j in (i + 1)..50 {
                let _ = level.min_cut(i, j);
            }
        }

        // Verify cache statistics are reasonable
        let (hits, misses) = level.cache_stats();
        assert!(misses > 0, "Should have cache misses from first pass");
        assert!(hits > 0, "Should have cache hits from second pass");
        // Second pass should have produced hits
        assert!(
            hits >= first_misses,
            "Second pass should hit cache: hits={}, first_misses={}",
            hits,
            first_misses
        );
    }

    #[test]
    fn stress_coordinator_workload() {
        let mut coordinator = TwoTierCoordinator::new(10, 100.0, 50.0);

        // Mixed workload
        for i in 0..1000 {
            match i % 4 {
                0 => {
                    let _ = coordinator.min_cut(false);
                }
                1 => {
                    let _ = coordinator.min_cut(true);
                }
                2 => {
                    coordinator.insert_edge(i as u64, (i + 1) as u64, 1.0);
                }
                3 => {
                    coordinator.delete_edge(i as u64, (i + 1) as u64);
                }
                _ => {}
            }
        }

        // Should complete without errors
        let (approx, exact) = coordinator.query_stats();
        assert!(approx > 0);
        assert!(exact > 0);
    }
}

// ============================================================================
// Thread Safety Tests (for concurrent scenarios)
// ============================================================================

mod thread_safety_tests {
    use super::*;
    use std::sync::Mutex;

    #[test]
    fn test_lazy_level_send_sync() {
        fn assert_send_sync<T: Send + Sync>() {}
        // LazyLevel should be Send + Sync when T is
        // Note: JTreeLevelData contains Arc, which is Send + Sync
    }

    #[test]
    fn test_concurrent_cache_stats() {
        let level = BmsspJTreeLevel::new(10, 0);

        // Arc counters should be thread-safe
        let cache_hits = level.cache_hits.clone();
        let cache_misses = level.cache_misses.clone();

        // Simulate concurrent access
        cache_hits.fetch_add(1, Ordering::Relaxed);
        cache_misses.fetch_add(1, Ordering::Relaxed);

        assert_eq!(cache_hits.load(Ordering::Relaxed), 1);
        assert_eq!(cache_misses.load(Ordering::Relaxed), 1);
    }
}