<?php

namespace App\Helpers;

class GeoHelper
{
    /**
     * Calculate distance between two coordinates using Haversine formula
     *
     * @param float $lat1 Latitude of point 1
     * @param float $lng1 Longitude of point 1
     * @param float $lat2 Latitude of point 2
     * @param float $lng2 Longitude of point 2
     * @return float Distance in kilometers
     */
    public static function haversineDistance(float $lat1, float $lng1, float $lat2, float $lng2): float
    {
        $R = 6371; // Earth's radius in km

        $dLat = deg2rad($lat2 - $lat1);
        $dLng = deg2rad($lng2 - $lng1);

        $a = sin($dLat / 2) * sin($dLat / 2) +
            cos(deg2rad($lat1)) * cos(deg2rad($lat2)) *
            sin($dLng / 2) * sin($dLng / 2);

        $c = 2 * atan2(sqrt($a), sqrt(1 - $a));

        return $R * $c;
    }

    /**
     * Optimize route using Nearest Neighbor algorithm
     *
     * @param array $targets Array of targets with lat/lng properties
     * @return array ['order' => array, 'totalDistance' => float]
     */
    public static function optimizeRouteNearestNeighbor(array $targets): array
    {
        $n = count($targets);

        if ($n <= 2) {
            $totalDistance = 0;
            if ($n === 2) {
                $totalDistance = self::haversineDistance(
                    $targets[0]['latitude'] ?? $targets[0]['lat'],
                    $targets[0]['longitude'] ?? $targets[0]['lng'],
                    $targets[1]['latitude'] ?? $targets[1]['lat'],
                    $targets[1]['longitude'] ?? $targets[1]['lng']
                );
            }
            return [
                'order' => array_keys($targets),
                'totalDistance' => round($totalDistance, 2)
            ];
        }

        $visited = array_fill(0, $n, false);
        $route = [];
        $totalDistance = 0;

        // Start from first target
        $current = 0;
        $visited[$current] = true;
        $route[] = $current;

        // Find nearest unvisited neighbor
        for ($i = 1; $i < $n; $i++) {
            $nearest = -1;
            $minDist = PHP_FLOAT_MAX;

            $currentLat = $targets[$current]['latitude'] ?? $targets[$current]['lat'];
            $currentLng = $targets[$current]['longitude'] ?? $targets[$current]['lng'];

            for ($j = 0; $j < $n; $j++) {
                if (!$visited[$j]) {
                    $targetLat = $targets[$j]['latitude'] ?? $targets[$j]['lat'];
                    $targetLng = $targets[$j]['longitude'] ?? $targets[$j]['lng'];

                    $dist = self::haversineDistance($currentLat, $currentLng, $targetLat, $targetLng);

                    if ($dist < $minDist) {
                        $minDist = $dist;
                        $nearest = $j;
                    }
                }
            }

            if ($nearest !== -1) {
                $visited[$nearest] = true;
                $route[] = $nearest;
                $totalDistance += $minDist;
                $current = $nearest;
            }
        }

        return [
            'order' => $route,
            'totalDistance' => round($totalDistance, 2)
        ];
    }

    /**
     * Calculate total distance of a route
     *
     * @param array $targets Array of targets in order
     * @return float Total distance in kilometers
     */
    public static function calculateRouteDistance(array $targets): float
    {
        if (count($targets) < 2) {
            return 0;
        }

        $totalDistance = 0;

        for ($i = 0; $i < count($targets) - 1; $i++) {
            $t1 = $targets[$i];
            $t2 = $targets[$i + 1];

            $totalDistance += self::haversineDistance(
                $t1['latitude'] ?? $t1['lat'],
                $t1['longitude'] ?? $t1['lng'],
                $t2['latitude'] ?? $t2['lat'],
                $t2['longitude'] ?? $t2['lng']
            );
        }

        return round($totalDistance, 2);
    }
}