rmpca 0.1.1

//! Optimizer module containing the route optimization engine
//!
//! This module provides the core optimization algorithms and data structures
//! for solving the Chinese Postman Problem and finding Eulerian circuits
//! in road networks.
//!
//! // Aligns with Lean4: module `RouteOptimizer`

pub mod error;
pub mod ffi;
pub mod types;
pub mod builder;
pub mod eulerian;
pub mod scc;
pub mod hierholzer;

use error::RouteError;
use petgraph::graph::DiGraph;
use std::collections::HashMap;

pub use types::{Node, Way, OptimizationResult, RoutePoint};
pub use builder::GraphBuilder;
pub use eulerian::EulerianSolver;
pub use scc::SccFilter;

/// Turn penalty configuration for route optimization
#[derive(Debug, Clone, Default, serde::Serialize, serde::Deserialize)]
pub struct TurnPenalties {
    pub left: f64,
    pub right: f64,
    pub u_turn: f64,
}

/// Depot (starting point) for route optimization
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct Depot {
    pub lat: f64,
    pub lon: f64,
}

/// Main optimizer using ported offline-optimizer-v2 algorithm
///
/// This struct provides the entry point for route optimization,
/// combining graph construction, Eulerian balancing, and circuit finding.
///
/// // Aligns with Lean4: structure `RouteOptimizer`
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct RouteOptimizer {
    nodes: Vec<Node>,
    ways: Vec<Way>,
    turn_penalties: TurnPenalties,
    depot: Option<Depot>,
}

impl RouteOptimizer {
    /// Create a new optimizer instance
    #[must_use]
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            ways: Vec::new(),
            turn_penalties: TurnPenalties::default(),
            depot: None,
        }
    }

    /// Build graph from `GeoJSON` features
    ///
    /// # Errors
    /// Returns a `RouteError` if the graph construction fails.
    #[allow(clippy::unnecessary_wraps)]
    pub fn build_graph_from_features(&mut self, features: &[geojson::Feature]) -> Result<(), RouteError> {
        for feature in features {
            if let Some(geometry) = &feature.geometry {
                if let geojson::Value::LineString(coords) = &geometry.value {
                        let id = feature.id.as_ref().map_or_else(
                            || format!("feat_{}", self.nodes.len()),
                            |id| match id {
                                geojson::feature::Id::Number(n) => format!("{n}"),
                                geojson::feature::Id::String(s) => s.clone(),
                            },
                        );
                        
                        let mut node_ids = Vec::new();
                        for coord in coords {
                            let node_id = format!("{}_{}", coord[1], coord[0]);
                            node_ids.push(node_id.clone());
                            self.nodes.push(Node::new(node_id, coord[1], coord[0]));
                        }

                        let mut way = Way::new(id, node_ids);
                        if let Some(props) = &feature.properties {
                            for (k, v) in props {
                                if let Some(s) = v.as_str() {
                                    way = way.with_tag(k, s);
                                }
                            }
                        }
                        self.ways.push(way);
                    }
                }
            }
        Ok(())
    }

    /// Optimize route from input `GeoJSON`
    ///
    /// # Errors
    /// Returns a `RouteError` if the graph has no Eulerian circuit,
    /// the graph is empty, or other optimization errors occur.
    pub fn optimize(&mut self) -> Result<OptimizationResult, RouteError> {
        // 1. Build graph from input
        let builder = GraphBuilder::new();
        let mut registry = HashMap::new();
        for node in &self.nodes {
            registry.insert(node.id.clone(), crate::geo::types::Coordinate { lat: node.lat, lon: node.lon });
        }
        let graph = builder.build_from_ways(&self.ways, registry);

        // 2. Filter to largest SCC
        let graph = SccFilter::retain_largest(&graph)?;

        // 3. Make graph Eulerian (CPP balancing)
        let eulerian_graph = Self::make_eulerian(graph)?;

        // 4. Find Eulerian circuit
        // // Aligns with Lean4: theorem eulerian_circuit_exists
        if eulerian_graph.node_count() == 0 {
            return Ok(OptimizationResult::new(vec![], 0.0));
        }
        let start_node = eulerian_graph.node_indices().next()
            .ok_or(RouteError::EmptyGraph)?;
        let circuit = EulerianSolver::find_circuit(&eulerian_graph, start_node)?;

        // 5. Convert to result
        let mut route = Vec::new();
        let mut total_distance = 0.0;
        let mut prev_node: Option<Node> = None;

        for node_idx in circuit {
            let node = eulerian_graph[node_idx].clone();
            if let Some(prev) = prev_node {
                total_distance += prev.distance_to(&node);
            }
            route.push(RoutePoint::from(node.clone()));
            prev_node = Some(node);
        }

        let mut result = OptimizationResult::new(route, total_distance / 1000.0);
        result.calculate_stats();
        Ok(result)
    }

    /// Balancing logic to make the graph Eulerian (Chinese Postman Problem)
    /// // Aligns with Lean4: theorem `cpp_balancing_produces_eulerian`
    fn make_eulerian(mut graph: DiGraph<Node, f64>) -> Result<DiGraph<Node, f64>, RouteError> {
        // Find nodes with in-degree != out_degree
        let mut sources = Vec::new(); // out > in
        let mut sinks = Vec::new();   // in > out

        for idx in graph.node_indices() {
            let in_deg = graph.edges_directed(idx, petgraph::Direction::Incoming).count();
            let out_deg = graph.edges_directed(idx, petgraph::Direction::Outgoing).count();
            
            if out_deg > in_deg {
                for _ in 0..(out_deg - in_deg) {
                    sources.push(idx);
                }
            } else if in_deg > out_deg {
                for _ in 0..(in_deg - out_deg) {
                    sinks.push(idx);
                }
            }
        }

        // Greedy matching of sources to sinks using shortest paths
        // (In a production environment, use Min-Cost Max-Flow)
        for &source in &sources {
            if let Some((sink_idx, _)) = sinks.iter().enumerate().next() {
                let sink = sinks.remove(sink_idx);
                if let Some((_dist, path)) = petgraph::algo::astar(
                    &graph,
                    source,
                    |finish| finish == sink,
                    |e| *e.weight(),
                    |_| 0.0,
                ) {
                    // Add duplicate edges along the shortest path
                    for window in path.windows(2) {
                        let u = window[0];
                        let v = window[1];
                        let weight = graph.edges_connecting(u, v).next()
                            .ok_or(RouteError::MissingEdge {
                                from: u.index(),
                                to: v.index(),
                            })?
                            .weight();
                        graph.add_edge(u, v, *weight);
                    }
                }
            }
        }

        Ok(graph)
    }

    /// Set turn penalties for route optimization
    pub fn set_turn_penalties(&mut self, left: f64, right: f64, u_turn: f64) {
        self.turn_penalties = TurnPenalties {
            left,
            right,
            u_turn,
        };
    }

    /// Set the depot (starting point) for route optimization
    pub fn set_depot(&mut self, lat: f64, lon: f64) {
        self.depot = Some(Depot { lat, lon });
    }

    /// Get statistics about the current graph state
    #[must_use]
    pub fn get_stats(&self) -> OptimizerStats {
        let node_count = self.nodes.len();
        let edge_count: usize = self.ways.iter().map(|w| w.nodes.len().saturating_sub(1)).sum();
        let max_degree = self.ways.iter().map(|w| w.nodes.len()).max().unwrap_or(0);
        #[allow(clippy::cast_precision_loss)]
        let avg_degree = if node_count > 0 {
            edge_count as f64 / node_count as f64
        } else {
            0.0
        };

        OptimizerStats {
            node_count,
            edge_count,
            component_count: 0, // Requires graph analysis; placeholder
            avg_degree,
            max_degree,
        }
    }
}

impl Default for RouteOptimizer {
    fn default() -> Self {
        Self::new()
    }
}

/// Statistics about the optimizer graph
#[derive(Debug, Clone)]
pub struct OptimizerStats {
    pub node_count: usize,
    pub edge_count: usize,
    pub component_count: usize,
    pub avg_degree: f64,
    pub max_degree: usize,
}

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

    #[test]
    fn test_optimizer_creation() {
        let optimizer = RouteOptimizer::new();
        assert_eq!(optimizer.nodes.len(), 0);
        assert_eq!(optimizer.ways.len(), 0);
    }

    #[test]
    fn test_optimizer_default() {
        let optimizer = RouteOptimizer::default();
        assert_eq!(optimizer.nodes.len(), 0);
        assert_eq!(optimizer.ways.len(), 0);
    }

    #[test]
    fn test_optimizer_stats() {
        let mut optimizer = RouteOptimizer::new();
        optimizer.nodes.push(Node::new("node1", 45.5, -73.6));
        optimizer.nodes.push(Node::new("node2", 45.51, -73.61));
        optimizer.ways.push(Way::new("way1", vec!["node1".to_string(), "node2".to_string()]));

        let stats = optimizer.get_stats();
        assert_eq!(stats.node_count, 2);
        assert_eq!(stats.edge_count, 1);
        assert!(stats.avg_degree > 0.0);
    }
}