"""Picks the order in which a picker should visit their active delivery
stops so the total distance driven is as small as possible, instead of
picking stops in whatever order they happen to be listed — the "which one
should I do first" question a picker is otherwise left to guess at.

Uses the standard nearest-neighbor heuristic: from the current position,
go to whichever remaining stop is closest, then from there go to whichever
of the REST is closest, and so on. It doesn't guarantee the mathematically
shortest possible route (true optimal routing is NP-hard), but it's a
well-established, cheap approximation that's normally close to optimal for
the small number of stops (a handful) a picker actually juggles at once —
and it's always at least as good as visiting stops in an arbitrary order.

The neighbor search itself uses straight-line (haversine) distance so it
stays fast with no external calls even as stop count grows; real road
distance/duration for the chosen sequence is then fetched from OSRM once
per leg (not once per candidate), which keeps total external calls at
O(n) instead of O(n^2)."""

from .geo import get_route, haversine_km


def suggest_delivery_order(current_lat, current_lng, stops):
    """stops: list of dicts each with at least 'id', 'lat', 'lng'.
    Returns (ordered_stops, total_distance_km, total_duration_min) where
    ordered_stops is the same dicts, reordered and each annotated with
    'leg_distance_km' / 'leg_duration_min' (real road distance from the
    previous stop, or from the picker's current position for the first
    one) and 'is_start' on the first stop. The first stop also gets a
    'steps' list of short turn-by-turn instructions from the picker's
    current position — only the first leg, so this stays one extra OSRM
    call, not one per stop."""
    if not stops or current_lat is None or current_lng is None:
        return list(stops), None, None

    remaining = list(stops)
    ordered = []
    from_lat, from_lng = current_lat, current_lng

    while remaining:
        nearest = min(remaining, key=lambda s: haversine_km(from_lat, from_lng, s['lat'], s['lng']))
        remaining.remove(nearest)
        ordered.append(nearest)
        from_lat, from_lng = nearest['lat'], nearest['lng']

    total_distance_km = 0.0
    total_duration_min = 0.0
    from_lat, from_lng = current_lat, current_lng
    for i, stop in enumerate(ordered):
        route = get_route(from_lat, from_lng, stop['lat'], stop['lng'], steps=(i == 0))
        if route:
            stop['leg_distance_km'] = route['distance_km']
            stop['leg_duration_min'] = route['duration_min']
            stop['steps'] = route.get('steps') if i == 0 else None
            # The real road-following path for this leg — kept so the map can
            # draw the picker's actual route, not just numbered pins, letting
            # a picker see exactly which roads their route uses alongside the
            # live traffic colors on top of them.
            stop['geometry'] = route.get('geometry')
        else:
            stop['leg_distance_km'] = round(haversine_km(from_lat, from_lng, stop['lat'], stop['lng']), 2)
            stop['leg_duration_min'] = None
            stop['steps'] = None
            stop['geometry'] = None
        stop['is_start'] = i == 0
        total_distance_km += stop['leg_distance_km']
        if stop['leg_duration_min'] is not None:
            total_duration_min += stop['leg_duration_min']
        from_lat, from_lng = stop['lat'], stop['lng']

    return ordered, round(total_distance_km, 2), round(total_duration_min, 1) if total_duration_min else None