rmpca 0.2.0

//! 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.

pub mod ffi;
pub mod types;

use anyhow::{Context, Result};
use std::collections::HashMap;

use petgraph::graph::{NodeIndex, UnGraph};
use petgraph::visit::EdgeRef;
use rkyv::{Archive, Serialize as RkyvSerialize, Deserialize as RkyvDeserialize};

pub use types::{Node, OptimizationResult, RoutePoint, RouteStats, Way};

/// Edge data stored on each graph edge
#[derive(Debug, Clone)]
struct EdgeData {
    /// Distance in meters (Haversine)
    distance: f64,
    /// Original way ID
    way_id: String,
    /// Whether this is a one-way street
    oneway: bool,
}

/// Internal road graph representation using petgraph
struct RoadGraph {
    /// The underlying undirected graph
    graph: UnGraph<usize, EdgeData>,
    /// Map from node ID string to petgraph NodeIndex
    node_map: HashMap<String, NodeIndex>,
    /// Map from petgraph NodeIndex to Node data
    node_data: HashMap<NodeIndex, Node>,
}

/// Serializable optimizer data for rkyv zero-copy serialization.
/// Only contains the graph data (nodes and ways), not runtime config.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, Archive, RkyvSerialize, RkyvDeserialize)]
pub struct OptimizerData {
    pub nodes: Vec<Node>,
    pub ways: Vec<Way>,
}

impl From<&RouteOptimizer> for OptimizerData {
    fn from(opt: &RouteOptimizer) -> Self {
        Self {
            nodes: opt.nodes.clone(),
            ways: opt.ways.clone(),
        }
    }
}

impl From<OptimizerData> for RouteOptimizer {
    fn from(data: OptimizerData) -> Self {
        Self {
            nodes: data.nodes,
            ways: data.ways,
            depot_lat: None,
            depot_lon: None,
            turn_left_penalty: 0.0,
            turn_right_penalty: 0.0,
            turn_u_penalty: 0.0,
        }
    }
}

/// 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.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct RouteOptimizer {
    pub nodes: Vec<Node>,
    pub ways: Vec<Way>,

    // These aren't serialized — they're set at runtime
    #[serde(skip)]
    depot_lat: Option<f64>,
    #[serde(skip)]
    depot_lon: Option<f64>,
    #[serde(skip)]
    turn_left_penalty: f64,
    #[serde(skip)]
    turn_right_penalty: f64,
    #[serde(skip)]
    turn_u_penalty: f64,
}

impl RouteOptimizer {
    /// Create a new optimizer instance
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            ways: Vec::new(),
            depot_lat: None,
            depot_lon: None,
            turn_left_penalty: 0.0,
            turn_right_penalty: 0.0,
            turn_u_penalty: 0.0,
        }
    }

    /// Build graph from GeoJSON features
    pub fn build_graph_from_features(&mut self, features: &[geojson::Feature]) -> Result<()> {
        // Clear existing data
        self.nodes.clear();
        self.ways.clear();

        let mut node_map: HashMap<String, usize> = HashMap::new();

        for feature in features {
            // Extract geometry
            let geometry = match feature.geometry.as_ref() {
                Some(g) => g,
                None => continue,
            };

            // We only care about LineString (road segments)
            let coords = match &geometry.value {
                geojson::Value::LineString(cs) => cs,
                _ => continue,
            };

            if coords.len() < 2 {
                continue;
            }

            // Extract way ID from properties
            let way_id = feature
                .property("id")
                .and_then(|v| v.as_str())
                .unwrap_or("unknown")
                .to_string();

            // Extract tags from properties
            let mut tags = std::collections::HashMap::new();
            if let Some(props) = &feature.properties {
                for (k, v) in props {
                    if let Some(s) = v.as_str() {
                        tags.insert(k.clone(), s.to_string());
                    }
                }
            }

            // Create nodes for each coordinate
            let mut way_node_ids: Vec<String> = Vec::new();
            for coord in coords {
                if coord.len() < 2 {
                    continue;
                }
                let lon = coord[0];
                let lat = coord[1];

                // Use a precision-based key to deduplicate close nodes
                let node_key = format!("{:.7},{:.7}", lat, lon);

                let node_idx = match node_map.get(&node_key) {
                    Some(&idx) => idx,
                    None => {
                        let idx = self.nodes.len();
                        let node_id = format!("node_{}", idx);
                        self.nodes.push(Node::new(&node_id, lat, lon));
                        node_map.insert(node_key, idx);
                        idx
                    }
                };

                way_node_ids.push(self.nodes[node_idx].id.clone());
            }

            if way_node_ids.len() >= 2 {
                let mut way = Way::new(&way_id, way_node_ids);
                way.tags = tags;
                self.ways.push(way);
            }
        }

        tracing::info!(
            "Built graph from features: {} nodes, {} ways",
            self.nodes.len(),
            self.ways.len()
        );
        Ok(())
    }

    /// Build the internal petgraph from nodes/ways
    fn build_internal_graph(&self) -> Result<RoadGraph> {
        let mut graph: UnGraph<usize, EdgeData> = UnGraph::new_undirected();
        let mut node_map: HashMap<String, NodeIndex> = HashMap::new();
        let mut node_data: HashMap<NodeIndex, Node> = HashMap::new();

        // Add nodes
        for node in &self.nodes {
            let idx = graph.add_node(0); // weight is just index, we store data separately
            node_map.insert(node.id.clone(), idx);
            node_data.insert(idx, node.clone());
        }

        // Add edges from ways
        for way in &self.ways {
            if way.nodes.len() < 2 {
                continue;
            }

            let oneway = way.is_oneway();

            for i in 0..way.nodes.len() - 1 {
                let from_id = &way.nodes[i];
                let to_id = &way.nodes[i + 1];

                let from_idx = match node_map.get(from_id) {
                    Some(&idx) => idx,
                    None => continue,
                };
                let to_idx = match node_map.get(to_id) {
                    Some(&idx) => idx,
                    None => continue,
                };

                // Calculate distance
                let from_node = &self.nodes.iter().find(|n| &n.id == from_id).unwrap();
                let to_node = &self.nodes.iter().find(|n| &n.id == to_id).unwrap();
                let distance = from_node.distance_to(to_node);

                let edge_data = EdgeData {
                    distance,
                    way_id: way.id.clone(),
                    oneway,
                };

                graph.add_edge(from_idx, to_idx, edge_data);
            }
        }

        tracing::info!(
            "Internal graph: {} nodes, {} edges",
            graph.node_count(),
            graph.edge_count()
        );

        Ok(RoadGraph {
            graph,
            node_map,
            node_data,
        })
    }

    /// Optimize route: find Eulerian circuit (or Chinese Postman approximation)
    pub fn optimize(&mut self) -> Result<OptimizationResult> {
        if self.nodes.is_empty() || self.ways.is_empty() {
            anyhow::bail!("Cannot optimize: graph is empty. Load data first.");
        }

        let road_graph = self.build_internal_graph()?;

        // Find start node (depot or first node)
        let start_idx = match self.find_nearest_node() {
            Some(idx) => idx,
            None => road_graph
                .node_map
                .values()
                .next()
                .copied()
                .context("No nodes in graph")?,
        };

        // Check if graph is Eulerian (all even degrees)
        let is_eulerian = self.all_nodes_have_even_degree_with_graph(&road_graph);

        let circuit = if is_eulerian {
            tracing::info!("Graph is Eulerian, finding Eulerian circuit");
            self.hierholzer(&road_graph, start_idx)?
        } else {
            tracing::info!("Graph is not Eulerian, running Chinese Postman algorithm");
            self.chinese_postman(&road_graph, start_idx)?
        };

        // Build route points from circuit
        let mut route: Vec<RoutePoint> = Vec::new();
        let mut total_distance = 0.0_f64;

        for node_idx in &circuit {
            if let Some(node) = road_graph.node_data.get(node_idx) {
                route.push(RoutePoint::with_node_id(node.lat, node.lon, &node.id));
            }
        }

        // Calculate total distance
        for i in 0..route.len().saturating_sub(1) {
            total_distance += route[i].distance_to(&route[i + 1]);
        }

        // Convert to km
        total_distance /= 1000.0;

        let mut result = OptimizationResult::new(route, total_distance);
        result.message = if is_eulerian {
            "Eulerian circuit found".to_string()
        } else {
            "Chinese Postman approximation (odd-degree nodes matched)".to_string()
        };
        result.calculate_stats();

        tracing::info!(
            "Optimization complete: {} points, {:.2} km",
            result.route.len(),
            result.total_distance
        );

        Ok(result)
    }

    /// Hierholzer's algorithm for finding Eulerian circuit
    fn hierholzer(&self, road_graph: &RoadGraph, start: NodeIndex) -> Result<Vec<NodeIndex>> {
        let g = &road_graph.graph;
        let mut circuit: Vec<NodeIndex> = Vec::new();
        let mut stack: Vec<NodeIndex> = vec![start];

        // Track used edges by their endpoints (since petgraph doesn't easily
        // allow removing edges during iteration)
        let mut used_edges: std::collections::HashSet<(NodeIndex, NodeIndex)> =
            std::collections::HashSet::new();

        while let Some(v) = stack.pop() {
            // Find an unused edge from v
            let mut found = false;
            for edge in g.edges(v) {
                let (a, b) = (edge.source(), edge.target());
                let key = if a < b { (a, b) } else { (b, a) };

                if !used_edges.contains(&key) {
                    used_edges.insert(key);
                    let neighbor = if edge.source() == v {
                        edge.target()
                    } else {
                        edge.source()
                    };
                    stack.push(v);
                    stack.push(neighbor);
                    found = true;
                    break;
                }
            }

            if !found {
                circuit.push(v);
            }
        }

        circuit.reverse();
        Ok(circuit)
    }

    /// Chinese Postman algorithm: add matching edges for odd-degree nodes,
    /// then find Eulerian circuit
    fn chinese_postman(&self, road_graph: &RoadGraph, start: NodeIndex) -> Result<Vec<NodeIndex>> {
        // Find odd-degree nodes
        let g = &road_graph.graph;
        let odd_nodes: Vec<NodeIndex> = g
            .node_indices()
            .filter(|&n| {
                let degree: usize = g.edges(n).count();
                degree % 2 == 1
            })
            .collect();

        tracing::info!("Found {} odd-degree nodes", odd_nodes.len());

        if odd_nodes.is_empty() {
            return self.hierholzer(road_graph, start);
        }

        // Add matching edges using greedy nearest-neighbor
        let mut augmented = self.add_matching_edges_greedy(road_graph, &odd_nodes)?;

        // Now find Eulerian circuit on augmented graph
        let mut circuit: Vec<NodeIndex> = Vec::new();
        let mut stack: Vec<NodeIndex> = vec![start];

        let mut used_edges: std::collections::HashSet<(NodeIndex, NodeIndex)> =
            std::collections::HashSet::new();

        while let Some(v) = stack.pop() {
            let mut found = false;
            for edge in augmented.edges(v) {
                let (a, b) = (edge.source(), edge.target());
                let key = if a < b { (a, b) } else { (b, a) };

                if !used_edges.contains(&key) {
                    used_edges.insert(key);
                    let neighbor = if edge.source() == v {
                        edge.target()
                    } else {
                        edge.source()
                    };
                    stack.push(v);
                    stack.push(neighbor);
                    found = true;
                    break;
                }
            }

            if !found {
                circuit.push(v);
            }
        }

        circuit.reverse();
        Ok(circuit)
    }

    /// Greedy nearest-neighbor matching for odd-degree nodes
    fn add_matching_edges_greedy(
        &self,
        road_graph: &RoadGraph,
        odd_nodes: &[NodeIndex],
    ) -> Result<UnGraph<usize, EdgeData>> {
        let mut graph = road_graph.graph.clone();
        let mut unmatched: Vec<NodeIndex> = odd_nodes.to_vec();

        // Sort by index for deterministic matching
        unmatched.sort();

        while unmatched.len() >= 2 {
            let node = unmatched[0];
            let mut best_dist = f64::INFINITY;
            let mut best_partner = unmatched[1];

            // Find nearest unmatched partner
            for &candidate in &unmatched[1..] {
                let dist = self.node_distance(road_graph, node, candidate);
                if dist < best_dist {
                    best_dist = dist;
                    best_partner = candidate;
                }
            }

            // Add duplicate edge for the matching
            let edge_data = EdgeData {
                distance: best_dist,
                way_id: format!("matching_{}_{}", node.index(), best_partner.index()),
                oneway: false,
            };
            graph.add_edge(node, best_partner, edge_data);

            // Remove matched pair
            unmatched.retain(|&n| n != node && n != best_partner);
        }

        Ok(graph)
    }

    /// Calculate distance between two nodes in the graph
    fn node_distance(&self, road_graph: &RoadGraph, a: NodeIndex, b: NodeIndex) -> f64 {
        let node_a = match road_graph.node_data.get(&a) {
            Some(n) => n,
            None => return f64::INFINITY,
        };
        let node_b = match road_graph.node_data.get(&b) {
            Some(n) => n,
            None => return f64::INFINITY,
        };
        node_a.distance_to(node_b)
    }

    /// Find the nearest graph node to the depot coordinates
    fn find_nearest_node(&self) -> Option<NodeIndex> {
        let depot_lat = self.depot_lat?;
        let depot_lon = self.depot_lon?;

        // Build a temporary graph just to find the nearest node
        let road_graph = self.build_internal_graph().ok()?;

        let mut best_dist = f64::INFINITY;
        let mut best_idx: Option<NodeIndex> = None;

        for (&idx, node) in &road_graph.node_data {
            let dist = haversine_distance(depot_lat, depot_lon, node.lat, node.lon);
            if dist < best_dist {
                best_dist = dist;
                best_idx = Some(idx);
            }
        }

        best_idx
    }

    /// Set turn penalties for optimization
    pub fn set_turn_penalties(&mut self, left: f64, right: f64, u: f64) {
        self.turn_left_penalty = left;
        self.turn_right_penalty = right;
        self.turn_u_penalty = u;
    }

    /// Set depot location for optimization
    pub fn set_depot(&mut self, lat: f64, lon: f64) {
        self.depot_lat = Some(lat);
        self.depot_lon = Some(lon);
    }

    /// Get optimizer statistics
    pub fn get_stats(&self) -> OptimizerStats {
        // Try to build the graph for real stats
        match self.build_internal_graph() {
            Ok(road_graph) => {
                let g = &road_graph.graph;
                let node_count = g.node_count();
                let edge_count = g.edge_count();

                // Count connected components using union-find
                let mut uf = petgraph::unionfind::UnionFind::new(node_count);
                for edge in g.edge_references() {
                    let (a, b) = (edge.source().index(), edge.target().index());
                    uf.union(a, b);
                }
                let mut component_set = std::collections::HashSet::new();
                for i in 0..node_count {
                    component_set.insert(uf.find(i));
                }
                let component_count = component_set.len();

                // Calculate max degree
                let max_degree = g
                    .node_indices()
                    .map(|n| g.edges(n).count())
                    .max()
                    .unwrap_or(0);

                let avg_degree = if node_count > 0 {
                    edge_count as f64 * 2.0 / node_count as f64
                } else {
                    0.0
                };

                OptimizerStats {
                    node_count,
                    edge_count,
                    component_count,
                    avg_degree,
                    max_degree,
                }
            }
            Err(_) => OptimizerStats {
                node_count: self.nodes.len(),
                edge_count: self.ways.len(),
                component_count: 0,
                avg_degree: 0.0,
                max_degree: 0,
            },
        }
    }

    /// Check if all nodes have even degree (Eulerian condition)
    pub fn all_nodes_have_even_degree(&self) -> bool {
        match self.build_internal_graph() {
            Ok(road_graph) => self.all_nodes_have_even_degree_with_graph(&road_graph),
            Err(_) => true,
        }
    }

    /// Internal: check even degree with a built graph
    fn all_nodes_have_even_degree_with_graph(&self, road_graph: &RoadGraph) -> bool {
        let g = &road_graph.graph;
        g.node_indices().all(|n| g.edges(n).count() % 2 == 0)
    }
}

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

/// Haversine distance between two lat/lon points in meters
fn haversine_distance(lat1: f64, lon1: f64, lat2: f64, lon2: f64) -> f64 {
    const R: f64 = 6_371_000.0;
    let lat1_r = lat1.to_radians();
    let lat2_r = lat2.to_radians();
    let dlat = (lat2 - lat1).to_radians();
    let dlon = (lon2 - lon1).to_radians();

    let a = (dlat / 2.0).sin().powi(2)
        + lat1_r.cos() * lat2_r.cos() * (dlon / 2.0).sin().powi(2);
    let c = 2.0 * a.sqrt().atan2((1.0 - a).sqrt());

    R * c
}

/// 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_set_depot() {
        let mut optimizer = RouteOptimizer::new();
        optimizer.set_depot(45.5, -73.6);
        assert_eq!(optimizer.depot_lat, Some(45.5));
        assert_eq!(optimizer.depot_lon, Some(-73.6));
    }

    #[test]
    fn test_set_turn_penalties() {
        let mut optimizer = RouteOptimizer::new();
        optimizer.set_turn_penalties(1.0, 0.5, 2.0);
        assert_eq!(optimizer.turn_left_penalty, 1.0);
        assert_eq!(optimizer.turn_right_penalty, 0.5);
        assert_eq!(optimizer.turn_u_penalty, 2.0);
    }

    #[test]
    fn test_build_graph_from_features_triangle() {
        // Create a triangle: 3 nodes, 3 edges (Eulerian)
        let features = vec![
            make_linestring_feature("w1", vec![(0.0, 0.0), (1.0, 0.0)]),
            make_linestring_feature("w2", vec![(1.0, 0.0), (0.5, 1.0)]),
            make_linestring_feature("w3", vec![(0.5, 1.0), (0.0, 0.0)]),
        ];

        let mut optimizer = RouteOptimizer::new();
        optimizer.build_graph_from_features(&features).unwrap();

        assert!(optimizer.nodes.len() >= 3);
        assert!(optimizer.ways.len() >= 3);
    }

    #[test]
    fn test_even_degree_triangle() {
        // Triangle: each node has degree 2 (even) → Eulerian
        let features = vec![
            make_linestring_feature("w1", vec![(0.0, 0.0), (1.0, 0.0)]),
            make_linestring_feature("w2", vec![(1.0, 0.0), (0.5, 1.0)]),
            make_linestring_feature("w3", vec![(0.5, 1.0), (0.0, 0.0)]),
        ];

        let mut optimizer = RouteOptimizer::new();
        optimizer.build_graph_from_features(&features).unwrap();

        assert!(optimizer.all_nodes_have_even_degree());
    }

    #[test]
    fn test_odd_degree_path() {
        // Path: A-B-C (B has degree 2, A and C have degree 1) → not Eulerian
        let features = vec![
            make_linestring_feature("w1", vec![(0.0, 0.0), (1.0, 0.0)]),
            make_linestring_feature("w2", vec![(1.0, 0.0), (2.0, 0.0)]),
        ];

        let mut optimizer = RouteOptimizer::new();
        optimizer.build_graph_from_features(&features).unwrap();

        assert!(!optimizer.all_nodes_have_even_degree());
    }

    #[test]
    fn test_optimize_triangle() {
        let features = vec![
            make_linestring_feature("w1", vec![(0.0, 0.0), (1.0, 0.0)]),
            make_linestring_feature("w2", vec![(1.0, 0.0), (0.5, 1.0)]),
            make_linestring_feature("w3", vec![(0.5, 1.0), (0.0, 0.0)]),
        ];

        let mut optimizer = RouteOptimizer::new();
        optimizer.build_graph_from_features(&features).unwrap();

        let result = optimizer.optimize().unwrap();
        assert!(result.route.len() >= 3);
        assert!(result.total_distance > 0.0);
    }

    #[test]
    fn test_optimize_path() {
        // Path with odd-degree nodes → Chinese Postman
        let features = vec![
            make_linestring_feature("w1", vec![(0.0, 0.0), (1.0, 0.0)]),
            make_linestring_feature("w2", vec![(1.0, 0.0), (2.0, 0.0)]),
        ];

        let mut optimizer = RouteOptimizer::new();
        optimizer.build_graph_from_features(&features).unwrap();

        let result = optimizer.optimize().unwrap();
        assert!(result.route.len() >= 2);
    }

    #[test]
    fn test_haversine_distance() {
        // Montreal: (45.5017, -73.5673) to (45.5088, -73.5542) ≈ 1.2 km
        let dist = haversine_distance(45.5017, -73.5673, 45.5088, -73.5542);
        assert!(dist > 800.0 && dist < 2000.0, "Distance was: {}", dist);
    }

    // ── Helpers ───────────────────────────────────────────────────────────

    fn make_linestring_feature(
        id: &str,
        coords: Vec<(f64, f64)>,
    ) -> geojson::Feature {
        let lonlat: Vec<Vec<f64>> = coords.iter().map(|(lat, lon)| vec![*lon, *lat]).collect();
        let geometry = geojson::Geometry::new(geojson::Value::LineString(lonlat));
        let mut properties = serde_json::Map::new();
        properties.insert("id".to_string(), serde_json::Value::String(id.to_string()));
        geojson::Feature {
            geometry: Some(geometry),
            properties: Some(properties),
            ..Default::default()
        }
    }
}