import 'dart:convert';
import 'dart:math' as math;
import 'package:http/http.dart' as http;
import 'package:latlong2/latlong.dart';
import '../models/stop.dart';

class RoutingService {
  static final RoutingService _instance = RoutingService._internal();
  factory RoutingService() => _instance;
  RoutingService._internal();

  static const _osrmBaseUrl = 'https://router.project-osrm.org';

  /// Fetch driving route through all stops via OSRM.
  /// Returns list of polyline points, or null on failure.
  Future<List<LatLng>?> fetchRoute(List<Stop> stops) async {
    if (stops.length < 2) return null;

    final coords = stops.map((s) => '${s.lng},${s.lat}').join(';');
    final url = '$_osrmBaseUrl/route/v1/driving/$coords?overview=full&geometries=polyline';

    try {
      final resp = await http.get(Uri.parse(url)).timeout(const Duration(seconds: 10));
      if (resp.statusCode == 200) {
        final data = jsonDecode(resp.body);
        if (data['code'] == 'Ok') {
          final routes = data['routes'] as List;
          if (routes.isNotEmpty) {
            final geometry = routes[0]['geometry'] as String;
            return decodePolyline(geometry);
          }
        }
      }
    } catch (_) {
      // Network error — caller should fall back
    }
    return null;
  }

  /// Optimize stop order using OSRM Trip (TSP solver).
  /// Returns optimized stops list, or null on failure.
  Future<List<Stop>?> optimizeRoute(List<Stop> stops) async {
    if (stops.length < 2) return null;

    final coords = stops.map((s) => '${s.lng},${s.lat}').join(';');
    final url = '$_osrmBaseUrl/trip/v1/driving/$coords?overview=full&geometries=polyline';

    try {
      final resp = await http.get(Uri.parse(url)).timeout(const Duration(seconds: 10));
      if (resp.statusCode == 200) {
        final data = jsonDecode(resp.body);
        if (data['code'] == 'Ok') {
          final waypoints = data['waypoints'] as List;
          final optimizedOrder = waypoints.map((w) => w['waypoint_index'] as int).toList();

          final optimizedStops = <Stop>[];
          for (var i = 0; i < optimizedOrder.length; i++) {
            final stop = stops[optimizedOrder[i]];
            optimizedStops.add(stop.copyWith(sequence: i));
          }
          return optimizedStops;
        }
      }
    } catch (_) {
      // Network error — caller should fall back
    }
    return null;
  }

  /// Nearest-neighbor TSP heuristic as local fallback.
  static List<Stop> optimizeLocally(List<Stop> route) {
    if (route.length <= 2) return route;

    final opt = <Stop>[];
    final rem = [...route];
    var cur = rem.removeAt(0);
    opt.add(cur);

    while (rem.isNotEmpty) {
      var nearestIdx = 0;
      var nearestDist = double.infinity;
      for (var i = 0; i < rem.length; i++) {
        final d = haversine(cur.lat, cur.lng, rem[i].lat, rem[i].lng);
        if (d < nearestDist) {
          nearestDist = d;
          nearestIdx = i;
        }
      }
      cur = rem.removeAt(nearestIdx);
      opt.add(cur);
    }

    return opt.asMap().entries.map((e) => e.value.copyWith(sequence: e.key)).toList();
  }

  /// Haversine distance in kilometers using dart:math.
  static double haversine(double lat1, double lng1, double lat2, double lng2) {
    const earthRadius = 6371.0; // km
    final dLat = _degToRad(lat2 - lat1);
    final dLng = _degToRad(lng2 - lng1);
    final a = math.sin(dLat / 2) * math.sin(dLat / 2) +
        math.cos(_degToRad(lat1)) * math.cos(_degToRad(lat2)) *
        math.sin(dLng / 2) * math.sin(dLng / 2);
    final c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a));
    return earthRadius * c;
  }

  static double _degToRad(double deg) => deg * math.pi / 180.0;

  /// Decode OSRM-encoded polyline string to list of LatLng.
  static List<LatLng> decodePolyline(String encoded) {
    final points = <LatLng>[];
    var index = 0;
    final len = encoded.length;
    var lat = 0;
    var lng = 0;

    while (index < len) {
      var b = 0;
      var shift = 0;
      var result = 0;
      do {
        b = encoded.codeUnitAt(index++) - 63;
        result |= (b & 0x1f) << shift;
        shift += 5;
      } while (b >= 0x20);
      final dlat = (result & 1) != 0 ? ~(result >> 1) : (result >> 1);
      lat += dlat;

      shift = 0;
      result = 0;
      do {
        b = encoded.codeUnitAt(index++) - 63;
        result |= (b & 0x1f) << shift;
        shift += 5;
      } while (b >= 0x20);
      final dlng = (result & 1) != 0 ? ~(result >> 1) : (result >> 1);
      lng += dlng;

      points.add(LatLng(lat / 1e6, lng / 1e6));
    }
    return points;
  }
}