open-standards/map/map-rs/crates/map-route/src/lib.rs

//! Map route — local geospatial capabilities over a tileset (SPEC §9): WGS84
//! geometry, POI geocoding, weighted-graph routing, and polygon geofencing.
//!
//! These are *local capabilities a reader runs over the bytes it has* — not a
//! hosted service; the standard carries no routing API. The [`feed`] module is
//! the feed-agnostic adapter: any live source — flights, vessels, satellites,
//! CVEs, incidents, supply-chain nodes, enterprise signals — implements one
//! trait to become an [`feed::Entity`] that resolves to a `map-schema`
//! `CellKey`, so "swap the feeds and it visualizes anything with a location or a
//! time" is a first-class property, not a per-feed rewrite. Ported from
//! `joule-maps` (energy metering removed — that is `map-receipt`'s job).
//!
//! - **Core geometry** — coordinates, bounding boxes, polygons, haversine distance
//! - **Places / POI** — typed point-of-interest catalog with addresses and categories
//! - **Geocoding** — fuzzy forward geocoding and reverse geocoding by radius
//! - **Routing** — Dijkstra and A* shortest-path on a weighted road graph
//! - **Geofencing** — polygon-based enter/exit event detection

use std::collections::BTreeMap;

use chrono::{DateTime, Utc};
use serde::{Deserialize, Serialize};
use thiserror::Error;
use uuid::Uuid;

pub mod bridge;
pub mod cost;
pub mod directions;
pub mod feed;
pub mod isochrone;
pub mod transit;

// ---------------------------------------------------------------------------
// Errors
// ---------------------------------------------------------------------------

/// Errors produced by map operations.
#[derive(Debug, Error, Serialize)]
pub enum MapsError {
    #[error("place not found: {0}")]
    PlaceNotFound(Uuid),

    #[error("geofence not found: {0}")]
    GeofenceNotFound(Uuid),

    #[error("route node not found: {0}")]
    RouteNodeNotFound(u64),

    #[error("no route between {from} and {to}")]
    NoRoute { from: u64, to: u64 },

    #[error("invalid coordinate: lat={lat}, lng={lng}")]
    InvalidCoordinate { lat: f64, lng: f64 },

    #[error("invalid zoom level: {0} (must be 0..=22)")]
    InvalidZoom(u8),

    #[error("duplicate place id: {0}")]
    DuplicatePlace(Uuid),

    #[error("duplicate geofence id: {0}")]
    DuplicateGeofence(Uuid),

    #[error("energy budget exceeded: {used_uj} uJ used, {budget_uj} uJ allowed")]
    EnergyBudgetExceeded { used_uj: u64, budget_uj: u64 },

    #[error("serialization error: {0}")]
    Serialization(String),
}

// ---------------------------------------------------------------------------
// Core Geometry
// ---------------------------------------------------------------------------

/// A geographic coordinate (WGS 84).
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct Coordinate {
    pub lat: f64,
    pub lng: f64,
    pub altitude: Option<f64>,
}

impl Coordinate {
    /// Create a new coordinate without altitude.
    pub fn new(lat: f64, lng: f64) -> Self {
        Self { lat, lng, altitude: None }
    }

    /// Create a new coordinate with altitude in meters.
    pub fn with_altitude(lat: f64, lng: f64, altitude: f64) -> Self {
        Self { lat, lng, altitude: Some(altitude) }
    }
}

/// Axis-aligned bounding box in geographic coordinates.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct BoundingBox {
    pub min: Coordinate,
    pub max: Coordinate,
}

impl BoundingBox {
    /// Does the bounding box contain the given coordinate?
    pub fn contains(&self, coord: &Coordinate) -> bool {
        coord.lat >= self.min.lat
            && coord.lat <= self.max.lat
            && coord.lng >= self.min.lng
            && coord.lng <= self.max.lng
    }

    /// Does this bounding box intersect another?
    pub fn intersects(&self, other: &BoundingBox) -> bool {
        self.min.lat <= other.max.lat
            && self.max.lat >= other.min.lat
            && self.min.lng <= other.max.lng
            && self.max.lng >= other.min.lng
    }

    /// Expand the bounding box by approximately `meters` in all directions.
    /// Uses a rough approximation: 1 degree latitude ≈ 111_320 m.
    pub fn expand_by(&self, meters: f64) -> BoundingBox {
        let dlat = meters / 111_320.0;
        let mid_lat = (self.min.lat + self.max.lat) / 2.0;
        let dlng = meters / (111_320.0 * mid_lat.to_radians().cos());
        BoundingBox {
            min: Coordinate::new(self.min.lat - dlat, self.min.lng - dlng),
            max: Coordinate::new(self.max.lat + dlat, self.max.lng + dlng),
        }
    }
}

/// A geographic point with associated properties.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GeoPoint {
    pub coord: Coordinate,
    pub properties: BTreeMap<String, serde_json::Value>,
}

/// A line (polyline) in geographic space.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GeoLine {
    pub points: Vec<Coordinate>,
}

/// A polygon with an exterior ring and optional holes.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GeoPolygon {
    pub exterior: Vec<Coordinate>,
    pub holes: Vec<Vec<Coordinate>>,
}

/// A geographic feature.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub enum GeoFeature {
    Point(GeoPoint),
    Line(GeoLine),
    Polygon(GeoPolygon),
    MultiPoint(Vec<GeoPoint>),
    MultiLine(Vec<GeoLine>),
    MultiPolygon(Vec<GeoPolygon>),
}

// ---------------------------------------------------------------------------
// Geometry functions
// ---------------------------------------------------------------------------

const EARTH_RADIUS_M: f64 = 6_371_000.0;

/// Great-circle distance between two coordinates in meters (Haversine formula).
pub fn haversine_distance(a: &Coordinate, b: &Coordinate) -> f64 {
    let lat1 = a.lat.to_radians();
    let lat2 = b.lat.to_radians();
    let dlat = (b.lat - a.lat).to_radians();
    let dlng = (b.lng - a.lng).to_radians();

    let h = (dlat / 2.0).sin().powi(2)
        + lat1.cos() * lat2.cos() * (dlng / 2.0).sin().powi(2);
    let c = 2.0 * h.sqrt().asin();
    EARTH_RADIUS_M * c
}

/// Initial compass bearing from `from` to `to`, in degrees [0, 360).
pub fn bearing(from: &Coordinate, to: &Coordinate) -> f64 {
    let lat1 = from.lat.to_radians();
    let lat2 = to.lat.to_radians();
    let dlng = (to.lng - from.lng).to_radians();

    let x = dlng.sin() * lat2.cos();
    let y = lat1.cos() * lat2.sin() - lat1.sin() * lat2.cos() * dlng.cos();
    let theta = x.atan2(y).to_degrees();
    (theta + 360.0) % 360.0
}

/// Geographic midpoint of two coordinates.
pub fn midpoint(a: &Coordinate, b: &Coordinate) -> Coordinate {
    let lat1 = a.lat.to_radians();
    let lat2 = b.lat.to_radians();
    let lng1 = a.lng.to_radians();
    let dlng = (b.lng - a.lng).to_radians();

    let bx = lat2.cos() * dlng.cos();
    let by = lat2.cos() * dlng.sin();
    let lat3 = (lat1.sin() + lat2.sin()).atan2(((lat1.cos() + bx).powi(2) + by.powi(2)).sqrt());
    let lng3 = lng1 + by.atan2(lat1.cos() + bx);

    Coordinate::new(lat3.to_degrees(), lng3.to_degrees())
}

/// Test whether a point lies inside a polygon using the ray-casting algorithm.
pub fn point_in_polygon(point: &Coordinate, polygon: &GeoPolygon) -> bool {
    // Check exterior ring
    if !ray_cast(point, &polygon.exterior) {
        return false;
    }
    // Check holes — if inside any hole, outside the polygon
    for hole in &polygon.holes {
        if ray_cast(point, hole) {
            return false;
        }
    }
    true
}

/// Ray-casting algorithm for a single ring.
fn ray_cast(point: &Coordinate, ring: &[Coordinate]) -> bool {
    let n = ring.len();
    if n < 3 {
        return false;
    }
    let mut inside = false;
    let mut j = n - 1;
    for i in 0..n {
        let yi = ring[i].lat;
        let xi = ring[i].lng;
        let yj = ring[j].lat;
        let xj = ring[j].lng;

        if ((yi > point.lat) != (yj > point.lat))
            && (point.lng < (xj - xi) * (point.lat - yi) / (yj - yi) + xi)
        {
            inside = !inside;
        }
        j = i;
    }
    inside
}

/// Compute the minimum bounding box for a set of coordinates.
pub fn bounding_box_for(coords: &[Coordinate]) -> BoundingBox {
    let mut min_lat = f64::MAX;
    let mut max_lat = f64::MIN;
    let mut min_lng = f64::MAX;
    let mut max_lng = f64::MIN;

    for c in coords {
        if c.lat < min_lat { min_lat = c.lat; }
        if c.lat > max_lat { max_lat = c.lat; }
        if c.lng < min_lng { min_lng = c.lng; }
        if c.lng > max_lng { max_lng = c.lng; }
    }

    BoundingBox {
        min: Coordinate::new(min_lat, min_lng),
        max: Coordinate::new(max_lat, max_lng),
    }
}

// ---------------------------------------------------------------------------
// Places / POI
// ---------------------------------------------------------------------------

/// Category of a point of interest.
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum PlaceCategory {
    Restaurant,
    Cafe,
    Hotel,
    Hospital,
    School,
    Park,
    Museum,
    Airport,
    TrainStation,
    BusStop,
    GasStation,
    Pharmacy,
    Bank,
    Supermarket,
    Gym,
    Library,
    Theater,
    Stadium,
    Beach,
    Mountain,
    Other(String),
}

/// A postal/physical address.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Address {
    pub street: Option<String>,
    pub city: Option<String>,
    pub state: Option<String>,
    pub country: Option<String>,
    pub postal_code: Option<String>,
    pub formatted: String,
}

/// A point of interest.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Place {
    pub id: Uuid,
    pub name: String,
    pub category: PlaceCategory,
    pub coordinate: Coordinate,
    pub address: Address,
    pub rating: Option<f64>,
    pub tags: Vec<String>,
    pub created_at: DateTime<Utc>,
}

// ---------------------------------------------------------------------------
// Geocoding
// ---------------------------------------------------------------------------

/// Forward geocode: fuzzy match `query` against place names and addresses.
/// Returns matching places with a relevance score in [0.0, 1.0], sorted descending.
pub fn geocode(query: &str, places: &[Place]) -> Vec<(Place, f64)> {
    let query_lower = query.to_lowercase();
    let mut results: Vec<(Place, f64)> = Vec::new();

    for place in places {
        let mut score = 0.0_f64;

        // Name matching
        let name_lower = place.name.to_lowercase();
        if name_lower == query_lower {
            score = 1.0;
        } else if name_lower.contains(&query_lower) {
            score = 0.7;
        } else if query_lower.contains(&name_lower) {
            score = 0.5;
        } else {
            // Token overlap
            let query_tokens: Vec<&str> = query_lower.split_whitespace().collect();
            let name_tokens: Vec<&str> = name_lower.split_whitespace().collect();
            let matching = query_tokens.iter()
                .filter(|qt| name_tokens.iter().any(|nt| nt.contains(*qt) || qt.contains(nt)))
                .count();
            if matching > 0 {
                score = 0.3 * (matching as f64 / query_tokens.len().max(1) as f64);
            }
        }

        // Address matching boost
        let addr_lower = place.address.formatted.to_lowercase();
        if addr_lower.contains(&query_lower) {
            score = score.max(0.6);
        } else {
            let query_tokens: Vec<&str> = query_lower.split_whitespace().collect();
            let addr_matching = query_tokens.iter()
                .filter(|qt| addr_lower.contains(*qt))
                .count();
            if addr_matching > 0 {
                let addr_score = 0.3 * (addr_matching as f64 / query_tokens.len().max(1) as f64);
                score = score.max(addr_score);
            }
        }

        if score > 0.0 {
            results.push((place.clone(), score));
        }
    }

    results.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
    results
}

/// Reverse geocode: find places within `radius_m` of `coord`.
/// Returns places with distance in meters, sorted by proximity (nearest first).
pub fn reverse_geocode(coord: &Coordinate, places: &[Place], radius_m: f64) -> Vec<(Place, f64)> {
    let mut results: Vec<(Place, f64)> = Vec::new();

    for place in places {
        let dist = haversine_distance(coord, &place.coordinate);
        if dist <= radius_m {
            results.push((place.clone(), dist));
        }
    }

    results.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
    results
}

// ---------------------------------------------------------------------------
// Routing
// ---------------------------------------------------------------------------

/// Type of road segment.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum RoadType {
    Highway,
    Primary,
    Secondary,
    Residential,
    Footpath,
    Cycleway,
}

/// A node in the routing graph.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RouteNode {
    pub id: u64,
    pub coord: Coordinate,
}

/// A directed edge in the routing graph.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RouteEdge {
    pub from: u64,
    pub to: u64,
    pub distance_m: f64,
    pub duration_secs: f64,
    pub road_type: RoadType,
}

/// A weighted, directed routing graph.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RouteGraph {
    pub nodes: BTreeMap<u64, RouteNode>,
    pub edges: Vec<RouteEdge>,
    pub adjacency: BTreeMap<u64, Vec<usize>>,
}

impl RouteGraph {
    /// Create an empty routing graph.
    pub fn new() -> Self {
        Self {
            nodes: BTreeMap::new(),
            edges: Vec::new(),
            adjacency: BTreeMap::new(),
        }
    }

    /// Add a node.
    pub fn add_node(&mut self, node: RouteNode) {
        self.nodes.insert(node.id, node);
    }

    /// Add a directed edge. Returns its index.
    pub fn add_edge(&mut self, edge: RouteEdge) -> usize {
        let idx = self.edges.len();
        self.adjacency.entry(edge.from).or_default().push(idx);
        self.edges.push(edge);
        idx
    }
}

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

/// A segment of a computed route.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RouteSegment {
    pub from: Coordinate,
    pub to: Coordinate,
    pub distance_m: f64,
    pub duration_secs: f64,
    pub instruction: String,
}

/// Result of a routing query.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RouteResult {
    pub waypoints: Vec<Coordinate>,
    pub total_distance_m: f64,
    pub total_duration_secs: f64,
    pub segments: Vec<RouteSegment>,
}

/// Find the shortest route using Dijkstra's algorithm (by distance).
pub fn find_route(graph: &RouteGraph, start: u64, end: u64) -> Option<RouteResult> {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    if !graph.nodes.contains_key(&start) || !graph.nodes.contains_key(&end) {
        return None;
    }
    if start == end {
        let coord = graph.nodes[&start].coord;
        return Some(RouteResult {
            waypoints: vec![coord],
            total_distance_m: 0.0,
            total_duration_secs: 0.0,
            segments: Vec::new(),
        });
    }

    let mut dist: BTreeMap<u64, f64> = BTreeMap::new();
    let mut prev: BTreeMap<u64, (u64, usize)> = BTreeMap::new(); // node -> (prev_node, edge_idx)
    dist.insert(start, 0.0);

    // (distance * 1000 as u64 for ordering, node_id)
    let mut heap: BinaryHeap<Reverse<(u64, u64)>> = BinaryHeap::new();
    heap.push(Reverse((0, start)));

    while let Some(Reverse((cost_key, u))) = heap.pop() {
        let cost_u = cost_key as f64 / 1000.0;
        if let Some(&best) = dist.get(&u) {
            if cost_u > best + 0.001 {
                continue;
            }
        }
        if u == end {
            break;
        }
        if let Some(adj) = graph.adjacency.get(&u) {
            for &edge_idx in adj {
                let edge = &graph.edges[edge_idx];
                let new_dist = cost_u + edge.distance_m;
                let current = dist.get(&edge.to).copied().unwrap_or(f64::INFINITY);
                if new_dist < current {
                    dist.insert(edge.to, new_dist);
                    prev.insert(edge.to, (u, edge_idx));
                    heap.push(Reverse(((new_dist * 1000.0) as u64, edge.to)));
                }
            }
        }
    }

    if !prev.contains_key(&end) {
        return None;
    }

    // Reconstruct path
    let mut path_edges: Vec<usize> = Vec::new();
    let mut current = end;
    while let Some(&(p, edge_idx)) = prev.get(&current) {
        path_edges.push(edge_idx);
        current = p;
    }
    path_edges.reverse();

    build_route_result(graph, &path_edges)
}

/// Find the shortest route using A* with haversine heuristic.
pub fn find_route_a_star(graph: &RouteGraph, start: u64, end: u64) -> Option<RouteResult> {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    if !graph.nodes.contains_key(&start) || !graph.nodes.contains_key(&end) {
        return None;
    }
    if start == end {
        let coord = graph.nodes[&start].coord;
        return Some(RouteResult {
            waypoints: vec![coord],
            total_distance_m: 0.0,
            total_duration_secs: 0.0,
            segments: Vec::new(),
        });
    }

    let goal_coord = &graph.nodes[&end].coord;

    let mut g_score: BTreeMap<u64, f64> = BTreeMap::new();
    let mut prev: BTreeMap<u64, (u64, usize)> = BTreeMap::new();
    g_score.insert(start, 0.0);

    // (f_score * 1000 as u64, node_id)
    let h_start = haversine_distance(&graph.nodes[&start].coord, goal_coord);
    let mut heap: BinaryHeap<Reverse<(u64, u64)>> = BinaryHeap::new();
    heap.push(Reverse(((h_start * 1000.0) as u64, start)));

    while let Some(Reverse((_f_key, u))) = heap.pop() {
        if u == end {
            break;
        }
        let g_u = g_score.get(&u).copied().unwrap_or(f64::INFINITY);

        if let Some(adj) = graph.adjacency.get(&u) {
            for &edge_idx in adj {
                let edge = &graph.edges[edge_idx];
                let tentative_g = g_u + edge.distance_m;
                let current_g = g_score.get(&edge.to).copied().unwrap_or(f64::INFINITY);
                if tentative_g < current_g {
                    g_score.insert(edge.to, tentative_g);
                    prev.insert(edge.to, (u, edge_idx));
                    let h = haversine_distance(&graph.nodes[&edge.to].coord, goal_coord);
                    let f = tentative_g + h;
                    heap.push(Reverse(((f * 1000.0) as u64, edge.to)));
                }
            }
        }
    }

    if !prev.contains_key(&end) {
        return None;
    }

    let mut path_edges: Vec<usize> = Vec::new();
    let mut current = end;
    while let Some(&(p, edge_idx)) = prev.get(&current) {
        path_edges.push(edge_idx);
        current = p;
    }
    path_edges.reverse();

    build_route_result(graph, &path_edges)
}

/// Build a `RouteResult` from a sequence of edge indices.
fn build_route_result(graph: &RouteGraph, path_edges: &[usize]) -> Option<RouteResult> {
    let mut waypoints: Vec<Coordinate> = Vec::new();
    let mut segments: Vec<RouteSegment> = Vec::new();
    let mut total_distance_m = 0.0;
    let mut total_duration_secs = 0.0;

    for (i, &edge_idx) in path_edges.iter().enumerate() {
        let edge = &graph.edges[edge_idx];
        let from_coord = graph.nodes[&edge.from].coord;
        let to_coord = graph.nodes[&edge.to].coord;

        if i == 0 {
            waypoints.push(from_coord);
        }
        waypoints.push(to_coord);

        total_distance_m += edge.distance_m;
        total_duration_secs += edge.duration_secs;

        let instruction = format!(
            "Continue on {:?} for {:.0} m",
            edge.road_type, edge.distance_m
        );
        segments.push(RouteSegment {
            from: from_coord,
            to: to_coord,
            distance_m: edge.distance_m,
            duration_secs: edge.duration_secs,
            instruction,
        });
    }

    Some(RouteResult {
        waypoints,
        total_distance_m,
        total_duration_secs,
        segments,
    })
}

// ---------------------------------------------------------------------------
// Geofencing
// ---------------------------------------------------------------------------

/// Trigger mode for a geofence.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum GeofenceTrigger {
    Enter,
    Exit,
    Both,
}

/// A named geofence region.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Geofence {
    pub id: Uuid,
    pub name: String,
    pub polygon: GeoPolygon,
    pub trigger: GeofenceTrigger,
    pub active: bool,
}

/// Kind of geofence transition.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum GeofenceEventKind {
    Entered,
    Exited,
}

/// A geofence transition event.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GeofenceEvent {
    pub fence_id: Uuid,
    pub entity_id: Uuid,
    pub kind: GeofenceEventKind,
    pub coord: Coordinate,
    pub timestamp: DateTime<Utc>,
}

/// Check an entity's position against a set of geofences.
///
/// `was_inside` maps fence_id → whether the entity was previously inside.
/// Returns events for fences whose state changed.
pub fn check_geofences(
    coord: &Coordinate,
    entity_id: Uuid,
    fences: &[Geofence],
    was_inside: &BTreeMap<Uuid, bool>,
) -> Vec<GeofenceEvent> {
    let now = Utc::now();
    let mut events = Vec::new();

    for fence in fences {
        if !fence.active {
            continue;
        }
        let inside_now = point_in_polygon(coord, &fence.polygon);
        let inside_before = was_inside.get(&fence.id).copied().unwrap_or(false);

        if inside_now && !inside_before {
            if fence.trigger == GeofenceTrigger::Enter || fence.trigger == GeofenceTrigger::Both {
                events.push(GeofenceEvent {
                    fence_id: fence.id,
                    entity_id,
                    kind: GeofenceEventKind::Entered,
                    coord: *coord,
                    timestamp: now,
                });
            }
        } else if !inside_now
            && inside_before
            && (fence.trigger == GeofenceTrigger::Exit || fence.trigger == GeofenceTrigger::Both)
        {
            events.push(GeofenceEvent {
                fence_id: fence.id,
                entity_id,
                kind: GeofenceEventKind::Exited,
                coord: *coord,
                timestamp: now,
            });
        }
    }

    events
}


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

    fn place(name: &str, lat: f64, lng: f64, category: PlaceCategory) -> Place {
        Place {
            id: Uuid::new_v4(),
            name: name.to_string(),
            category,
            coordinate: Coordinate::new(lat, lng),
            address: Address {
                street: None,
                city: None,
                state: None,
                country: None,
                postal_code: None,
                formatted: String::new(),
            },
            rating: None,
            tags: vec![],
            created_at: Utc::now(),
        }
    }

    #[test]
    fn haversine_one_degree_latitude_is_about_111km() {
        let d = haversine_distance(&Coordinate::new(0.0, 0.0), &Coordinate::new(1.0, 0.0));
        assert!((d - 111_195.0).abs() < 500.0, "1° lat ≈ 111 km, got {d}");
    }

    #[test]
    fn point_in_polygon_inside_and_outside() {
        let poly = GeoPolygon {
            exterior: vec![
                Coordinate::new(0.0, 0.0),
                Coordinate::new(1.0, 0.0),
                Coordinate::new(1.0, 1.0),
                Coordinate::new(0.0, 1.0),
            ],
            holes: vec![],
        };
        assert!(point_in_polygon(&Coordinate::new(0.5, 0.5), &poly));
        assert!(!point_in_polygon(&Coordinate::new(2.0, 2.0), &poly));
    }

    #[test]
    fn geocode_ranks_name_match_first() {
        let places = vec![
            place("Blue Bottle Coffee", 37.77, -122.42, PlaceCategory::Cafe),
            place("City Hospital", 37.78, -122.41, PlaceCategory::Hospital),
        ];
        let results = geocode("blue bottle", &places);
        assert!(!results.is_empty());
        assert_eq!(results[0].0.name, "Blue Bottle Coffee");
    }

    #[test]
    fn find_route_traverses_intermediate_node() {
        let mut g = RouteGraph::new();
        g.add_node(RouteNode { id: 1, coord: Coordinate::new(0.0, 0.0) });
        g.add_node(RouteNode { id: 2, coord: Coordinate::new(0.0, 1.0) });
        g.add_node(RouteNode { id: 3, coord: Coordinate::new(0.0, 2.0) });
        let edge = |from, to| RouteEdge {
            from,
            to,
            distance_m: 100.0,
            duration_secs: 10.0,
            road_type: RoadType::Residential,
        };
        g.add_edge(edge(1, 2));
        g.add_edge(edge(2, 3));
        let route = find_route(&g, 1, 3).expect("a route from 1 to 3 exists");
        assert!(route.total_distance_m > 0.0);
        assert!(route.waypoints.len() >= 2);
    }

    #[test]
    fn geofence_enter_event_fires() {
        let fence = Geofence {
            id: Uuid::new_v4(),
            name: "zone".to_string(),
            polygon: GeoPolygon {
                exterior: vec![
                    Coordinate::new(0.0, 0.0),
                    Coordinate::new(1.0, 0.0),
                    Coordinate::new(1.0, 1.0),
                    Coordinate::new(0.0, 1.0),
                ],
                holes: vec![],
            },
            trigger: GeofenceTrigger::Both,
            active: true,
        };
        let was_inside = BTreeMap::new(); // nothing seen yet → entering
        let events =
            check_geofences(&Coordinate::new(0.5, 0.5), Uuid::new_v4(), &[fence], &was_inside);
        assert_eq!(events.len(), 1);
        assert_eq!(events[0].kind, GeofenceEventKind::Entered);
    }
}