<?php

namespace Modules\Transport\Services\Ai;

use App\Models\EmployeeShiftAssignmentModel;
use App\Models\TransportAiSettingsModel;
use App\Models\TransportContractSiteModel;
use App\Models\TransportLocationModel;
use App\Models\TransportVehicleModel;

/**
 * AI Route Optimization engine.
 *
 * Plans from contract sites, staff assigned on each contract, shift timing,
 * and per-staff transport legs (morning / return / both). Vehicles run from a
 * fixed base garage through one or more contract sites on the outbound leg,
 * then pick up return staff (including at other sites) on the way back.
 */
class RouteOptimizerService
{
    protected TransportAiSettingsModel $settingsModel;
    protected TransportContractSiteModel $contractSites;
    protected TransportVehicleModel $vehicles;
    protected TransportLocationModel $locations;
    protected EmployeeShiftAssignmentModel $shiftAssignments;
    protected RoutingService $routing;

    protected array $settings;

    public function __construct(?RoutingService $routing = null)
    {
        $this->settingsModel    = new TransportAiSettingsModel();
        $this->contractSites    = new TransportContractSiteModel();
        $this->vehicles         = new TransportVehicleModel();
        $this->locations        = new TransportLocationModel();
        $this->shiftAssignments = new EmployeeShiftAssignmentModel();

        $this->settings = $this->settingsModel->getSettings();
        $this->routing  = $routing ?? new RoutingService($this->settings);
    }

    public function getSettings(): array
    {
        return $this->settings;
    }

    public function getRouting(): RoutingService
    {
        return $this->routing;
    }

    /**
     * Build optimized route candidates for every date in the range.
     *
     * @param int[]|null $contractIds Restrict planning to these contracts.
     * @param int        $batchLimit  Max contracts per run when none are selected.
     *
     * @return array{routes: array, issues: array, inputs: array}
     */
    public function optimize(string $startDate, string $endDate, ?array $contractIds = null, int $batchLimit = 40): array
    {
        $batchLimit = max(1, $batchLimit);
        $sites      = $this->contractSites->getActivePlannable($contractIds);
        $issues     = [];
        $routes     = [];

        if ($sites === []) {
            $issues[] = [
                'type'    => 'no_contract_sites',
                'message' => 'No active contracts are mapped to a transport site with coordinates. Configure contract sites first.',
            ];

            return ['routes' => [], 'issues' => $issues, 'inputs' => ['sites' => 0, 'employees' => 0, 'vehicles' => 0]];
        }

        if ($contractIds === null && count($sites) > $batchLimit) {
            $issues[] = [
                'type'    => 'too_many_sites',
                'message' => sprintf(
                    'There are %d plannable contract sites. Choose a region and batch size (up to %d per run) on the Generate Plan form instead of planning every site at once.',
                    count($sites),
                    $batchLimit
                ),
            ];

            return [
                'routes' => [],
                'issues' => $issues,
                'inputs' => ['sites' => count($sites), 'employees' => 0, 'vehicles' => 0],
            ];
        }

        if ($contractIds !== null && count($contractIds) > $batchLimit) {
            $issues[] = [
                'type'    => 'batch_capped',
                'message' => sprintf(
                    'Only the first %d contracts in your selection were planned for this run (batch limit).',
                    $batchLimit
                ),
            ];
        }

        $fleet = $this->loadFleet();
        if ($fleet === []) {
            $issues[] = [
                'type'    => 'no_vehicles',
                'message' => 'No active vehicles with a passenger capacity are available.',
            ];
        }

        $depots = $this->locations->where('status', 'active')
            ->where('location_type', 'depot')
            ->where('latitude IS NOT NULL')
            ->where('longitude IS NOT NULL')
            ->findAll();

        $employeesBySite = $this->loadContractEmployees(array_column($sites, 'contract_id'));
        $totalEmployees  = 0;
        $period          = $this->datesBetween($startDate, $endDate);

        $needsHrShift = [];
        foreach ($sites as $site) {
            if (! empty($site['default_shift_id']) && ! empty($site['shift_start_time'])) {
                continue;
            }
            foreach ($employeesBySite[(int) $site['contract_id']] ?? [] as $employee) {
                $needsHrShift[(int) $employee['employee_id']] = true;
            }
        }
        $shiftCacheByDate = [];
        if ($needsHrShift !== []) {
            foreach ($period as $date) {
                $shiftCacheByDate[$date] = $this->loadShiftsForDate(array_keys($needsHrShift), $date);
            }
        }

        foreach ($period as $date) {
            $vehicleWindows = [];
            $shiftBuckets   = [];
            $base           = $this->resolveBase($depots, $sites);

            foreach ($sites as $site) {
                $contractId = (int) $site['contract_id'];

                if (! $this->contractActiveOnDate($site, $date)) {
                    continue;
                }

                $employees = $employeesBySite[$contractId] ?? [];
                if ($employees === []) {
                    if ($date === $period[0]) {
                        $issues[] = [
                            'type'        => 'no_employees',
                            'contract_id' => $contractId,
                            'message'     => sprintf(
                                'Contract "%s" has no active staff assigned. Assign employees on the contract first.',
                                $site['contract_title'] ?? $site['contract_number'] ?? $contractId
                            ),
                        ];
                    }

                    continue;
                }

                if ($date === $period[0]) {
                    $totalEmployees += count($employees);
                }

                $byShift = $this->groupByShift(
                    $employees,
                    $site,
                    $date,
                    $issues,
                    $shiftCacheByDate[$date] ?? []
                );

                foreach ($byShift as $shiftId => $group) {
                    $counts = $this->legCounts($group['employees']);
                    if ($counts['outbound'] === 0 && $counts['return'] === 0) {
                        continue;
                    }

                    $shiftBuckets[$shiftId]['shift'] ??= $group['shift'];
                    $shiftBuckets[$shiftId]['bundles'][] = [
                        'site'       => $site,
                        'employees'  => $group['employees'],
                        'counts'     => $counts,
                        'site_point' => $this->sitePoint($site),
                    ];
                }
            }

            foreach ($shiftBuckets as $bucket) {
                if (($bucket['bundles'] ?? []) === []) {
                    continue;
                }

                $shiftRoutes = $this->optimizeShiftBucket(
                    $date,
                    $bucket['shift'],
                    $bucket['bundles'],
                    $fleet,
                    $base,
                    $vehicleWindows,
                    $issues
                );

                foreach ($shiftRoutes as $route) {
                    $routes[] = $route;
                }
            }
        }

        if ($this->routing->usedFallback()) {
            $issues[] = [
                'type'    => 'routing_fallback',
                'message' => 'The road routing provider (OSRM) was unreachable for part of the computation; straight-line estimates with a road factor were used instead.',
            ];
        }

        return [
            'routes' => $routes,
            'issues' => $issues,
            'inputs' => [
                'sites'     => count($sites),
                'employees' => $totalEmployees,
                'vehicles'  => count($fleet),
                'depots'    => count($depots),
                'dates'     => count($period),
            ],
        ];
    }

    // ------------------------------------------------------------------
    // Input gathering
    // ------------------------------------------------------------------

    protected function loadFleet(): array
    {
        return $this->vehicles->where('status', 'active')
            ->where('capacity >', 0)
            ->orderBy('capacity', 'ASC')
            ->findAll();
    }

    /**
     * Active staff assigned to each contract, keyed by contract id.
     *
     * @param list<int|string> $contractIds
     *
     * @return array<int, list<array{employee_id: int, full_name: string, employee_number: ?string, role_on_contract: ?string, transport_leg: string}>>
     */
    protected function loadContractEmployees(array $contractIds): array
    {
        if ($contractIds === []) {
            return [];
        }

        $rows = $this->contractSites->db->table('contract_employees ce')
            ->select('ce.contract_id, ce.role_on_contract, ce.transport_leg, e.id AS employee_id, e.full_name, e.employee_number')
            ->join('employees e', 'e.id = ce.employee_id')
            ->whereIn('ce.contract_id', $contractIds)
            ->where('e.status', 'active')
            ->orderBy('e.full_name', 'ASC')
            ->get()->getResultArray();

        $bySite = [];
        foreach ($rows as $row) {
            $leg = (string) ($row['transport_leg'] ?? 'both');
            if (! in_array($leg, ['both', 'outbound_only', 'return_only'], true)) {
                $leg = 'both';
            }

            $bySite[(int) $row['contract_id']][] = [
                'employee_id'       => (int) $row['employee_id'],
                'full_name'         => $row['full_name'],
                'employee_number'   => $row['employee_number'],
                'role_on_contract'  => $row['role_on_contract'] ?? null,
                'transport_leg'     => $leg,
            ];
        }

        return $bySite;
    }

    /**
     * @param list<int> $employeeIds
     *
     * @return array<int, array>
     */
    protected function loadShiftsForDate(array $employeeIds, string $date): array
    {
        if ($employeeIds === []) {
            return [];
        }

        $rows = $this->shiftAssignments->db->table('employee_shift_assignments esa')
            ->select('esa.employee_id, esa.shift_id, esa.effective_from, s.name, s.start_time, s.end_time')
            ->join('attendance_shifts s', 's.id = esa.shift_id')
            ->whereIn('esa.employee_id', $employeeIds)
            ->where('esa.effective_from <=', $date)
            ->groupStart()
                ->where('esa.effective_to', null)
                ->orWhere('esa.effective_to >=', $date)
            ->groupEnd()
            ->where('s.status', 'active')
            ->orderBy('esa.effective_from', 'DESC')
            ->get()->getResultArray();

        $map = [];
        foreach ($rows as $row) {
            $employeeId = (int) $row['employee_id'];
            if (! isset($map[$employeeId])) {
                $map[$employeeId] = $row;
            }
        }

        return $map;
    }

    /**
     * @param array<int, array|null> $shiftByEmployee
     */
    protected function groupByShift(array $employees, array $site, string $date, array &$issues, array $shiftByEmployee = []): array
    {
        $defaultShift = null;
        if (! empty($site['default_shift_id']) && ! empty($site['shift_start_time'])) {
            $defaultShift = [
                'id'         => (int) $site['default_shift_id'],
                'name'       => $site['shift_name'] ?? 'Default shift',
                'start_time' => $site['shift_start_time'],
                'end_time'   => $site['shift_end_time'],
            ];
        }

        $groups = [];
        foreach ($employees as $employee) {
            $shift = $defaultShift;

            if ($shift === null) {
                $assignment = $shiftByEmployee[(int) $employee['employee_id']] ?? null;
                $shift      = $assignment
                    ? [
                        'id'         => (int) ($assignment['shift_id'] ?? $assignment['id']),
                        'name'       => $assignment['name'] ?? 'Shift',
                        'start_time' => $assignment['start_time'],
                        'end_time'   => $assignment['end_time'],
                    ]
                    : null;
            }

            if ($shift === null) {
                $issues[] = [
                    'type'        => 'missing_shift',
                    'employee_id' => $employee['employee_id'],
                    'date'        => $date,
                    'message'     => sprintf(
                        '%s has no shift assignment on %s and contract site "%s" has no default shift; excluded for that date.',
                        $employee['full_name'],
                        $date,
                        $site['location_name'] ?? $site['contract_title'] ?? 'site'
                    ),
                ];

                continue;
            }

            $groups[$shift['id']]['shift']       = $shift;
            $groups[$shift['id']]['employees'][] = $employee;
        }

        return $groups;
    }

    protected function contractActiveOnDate(array $site, string $date): bool
    {
        $start = $site['contract_start_date'] ?? null;
        $end   = $site['contract_end_date'] ?? null;

        if ($start && $date < $start) {
            return false;
        }
        if ($end && $date > $end) {
            return false;
        }

        return true;
    }

    // ------------------------------------------------------------------
    // Multi-site optimization per shift bucket
    // ------------------------------------------------------------------

    /**
     * @param list<array> $bundles Site bundles sharing the same shift.
     */
    protected function optimizeShiftBucket(
        string $date,
        array $shift,
        array $bundles,
        array $fleet,
        array $base,
        array &$vehicleWindows,
        array &$issues
    ): array {
        $maxCapacity = 0;
        foreach ($fleet as $vehicle) {
            $maxCapacity = max($maxCapacity, (int) $vehicle['capacity']);
        }

        if ($maxCapacity === 0) {
            $siteNames = implode(', ', array_map(
                static fn (array $b): string => $b['site_point']['name'] ?? 'site',
                $bundles
            ));
            $issues[] = [
                'type'    => 'no_vehicle_capacity',
                'date'    => $date,
                'message' => sprintf(
                    'No vehicle capacity available for shift "%s" (%s) on %s.',
                    $shift['name'],
                    $siteNames,
                    $date
                ),
            ];

            return [];
        }

        $packedGroups = $this->packSiteBundles($bundles, $maxCapacity, $base);
        $routes       = [];

        foreach ($packedGroups as $index => $group) {
            $routes[] = $this->buildMultiSiteRoute(
                $date,
                $shift,
                $group,
                $fleet,
                $base,
                $vehicleWindows,
                $index + 1,
                $issues
            );
        }

        return $routes;
    }

    /**
     * Greedy packing of contract sites into multi-stop routes by vehicle capacity.
     *
     * @param list<array> $bundles
     *
     * @return list<list<array>>
     */
    protected function packSiteBundles(array $bundles, int $maxCapacity, array $base): array
    {
        if ($bundles === []) {
            return [];
        }

        usort($bundles, function (array $a, array $b) use ($base): int {
            $bearingA = $this->bearingFromBase($base, $a['site_point']['lat'], $a['site_point']['lng']);
            $bearingB = $this->bearingFromBase($base, $b['site_point']['lat'], $b['site_point']['lng']);

            return $bearingA <=> $bearingB;
        });

        $groups          = [];
        $current         = [];
        $currentOutbound = 0;
        $currentReturn   = 0;

        foreach ($bundles as $bundle) {
            $nextOutbound = $currentOutbound + $bundle['counts']['outbound'];
            $nextReturn   = $currentReturn + $bundle['counts']['return'];
            $needed       = max($nextOutbound, $nextReturn);

            if ($current !== [] && $needed > $maxCapacity) {
                $groups[]        = $current;
                $current         = [$bundle];
                $currentOutbound = $bundle['counts']['outbound'];
                $currentReturn   = $bundle['counts']['return'];
                continue;
            }

            $current[]        = $bundle;
            $currentOutbound  = $nextOutbound;
            $currentReturn    = $nextReturn;
        }

        if ($current !== []) {
            $groups[] = $current;
        }

        return $groups;
    }

    protected function buildMultiSiteRoute(
        string $date,
        array $shift,
        array $bundles,
        array $fleet,
        array $base,
        array &$vehicleWindows,
        int $routeIndex,
        array &$issues
    ): array {
        $notes = [];

        $shiftStartMin = $this->timeToMinutes($shift['start_time']);
        $shiftEndMin   = $this->timeToMinutes($shift['end_time']);
        if ($shiftEndMin <= $shiftStartMin) {
            $shiftEndMin += 1440;
        }

        $employeeCount = 0;
        $seenEmployees = [];
        foreach ($bundles as $bundle) {
            foreach ($bundle['employees'] as $employee) {
                $id = (int) $employee['employee_id'];
                if (! isset($seenEmployees[$id])) {
                    $seenEmployees[$id] = true;
                    $employeeCount++;
                }
            }
        }

        $outboundBundles = array_values(array_filter(
            $bundles,
            static fn (array $b): bool => $b['counts']['outbound'] > 0
        ));
        $returnBundles = array_values(array_filter(
            $bundles,
            static fn (array $b): bool => $b['counts']['return'] > 0
        ));

        $outboundSites = array_map(static fn (array $b): array => $b['site_point'], $outboundBundles);
        $orderedOutbound = $this->orderSitesNearestNeighbor($base, $outboundSites);

        $lastOutbound = $orderedOutbound !== [] ? $orderedOutbound[array_key_last($orderedOutbound)] : $base;
        $returnSites    = array_map(static fn (array $b): array => $b['site_point'], $returnBundles);
        $orderedReturn  = $this->orderSitesNearestNeighbor($lastOutbound, $returnSites, $base);

        $siteNames = array_map(static fn (array $b): string => $b['site_point']['name'], $bundles);
        $primarySite = $bundles[0]['site'];
        $destination = $orderedOutbound !== []
            ? $orderedOutbound[array_key_last($orderedOutbound)]
            : ($returnSites[0] ?? $bundles[0]['site_point']);

        $requiredCapacity = max(
            array_sum(array_map(static fn (array $b): int => $b['counts']['outbound'], $bundles)),
            $this->returnPeakLoad($orderedReturn, $returnBundles)
        );

        $candidates = array_values(array_filter(
            $fleet,
            static fn (array $v): bool => (int) $v['capacity'] >= $requiredCapacity
        ));
        usort($candidates, static function (array $a, array $b): int {
            return (int) $a['capacity'] <=> (int) $b['capacity'];
        });

        $metrics = $this->computeMultiSiteMetrics(
            $base,
            $orderedOutbound,
            $orderedReturn,
            $bundles,
            $shiftStartMin,
            $shiftEndMin
        );

        $selected = null;
        foreach ($candidates as $candidate) {
            if ($this->windowsOverlap($vehicleWindows[$date][(int) $candidate['id']] ?? [], $metrics['busy_from'], $metrics['busy_to'])) {
                continue;
            }

            $selected = $candidate;
            break;
        }

        if ($selected === null && $candidates !== []) {
            $selected = $candidates[0];
            $notes[]  = 'No vehicle was free in this time window; a replacement vehicle is required.';
        } elseif ($selected === null) {
            $notes[] = sprintf('No active vehicle has capacity for %d passengers (peak load).', $requiredCapacity);
        }

        if ($selected !== null) {
            $vehicleWindows[$date][(int) $selected['id']][] = [$metrics['busy_from'], $metrics['busy_to']];
            $spare = (int) $selected['capacity'] - $requiredCapacity;
            $notes[] = sprintf(
                'Vehicle %s (%s, capacity %d) — %d staff, %d spare seat%s.',
                $selected['registration_number'],
                $selected['vehicle_type'],
                (int) $selected['capacity'],
                $employeeCount,
                max(0, $spare),
                max(0, $spare) === 1 ? '' : 's'
            );
        }

        $outboundLabel = $orderedOutbound !== []
            ? implode(' → ', array_map(static fn (array $s): string => $s['name'], $orderedOutbound))
            : 'no outbound drops';
        $returnLabel = $orderedReturn !== []
            ? implode(' → ', array_map(static fn (array $s): string => $s['name'], $orderedReturn))
            : 'direct to base';

        $notes[] = sprintf(
            'Multi-site route from %s: outbound %s; return pickups %s → %s.',
            $base['name'],
            $outboundLabel,
            $returnLabel,
            $base['name']
        );

        if (count($bundles) > 1) {
            $notes[] = sprintf('%d contract sites served on one trip.', count($bundles));
        }

        if ($metrics['arrival_min'] > $shiftStartMin - (int) $this->settings['arrival_buffer_minutes']) {
            $notes[] = 'Warning: computed arrival is inside the arrival buffer; verify departure time.';
        }

        $vehicle     = $selected;
        $vehicleType = $vehicle['vehicle_type'] ?? 'van';
        $consumption = null;
        if ($vehicle !== null && ! empty($vehicle['fuel_consumption_l_per_100km'])) {
            $consumption = (float) $vehicle['fuel_consumption_l_per_100km'];
        }
        $consumption ??= $this->settingsModel->consumptionForType($this->settings, $vehicleType);

        $totalKm    = $metrics['outbound_km'] + $metrics['return_km'];
        $fuelLitres = round($totalKm * $consumption / 100, 2);
        $cost       = round(
            $fuelLitres * (float) $this->settings['fuel_price_per_litre']
            + $totalKm * (float) $this->settings['cost_per_km'],
            3
        );

        $routeTitle = count($siteNames) === 1
            ? ($primarySite['contract_title'] ?? ('Contract ' . $primarySite['contract_id']))
            : implode(', ', $siteNames);

        return [
            'service_date'               => $date,
            'route_name'                 => sprintf('%s – %s – Route %d', $routeTitle, $shift['name'], $routeIndex),
            'contract_id'                => (int) $primarySite['contract_id'],
            'contract_title'             => $primarySite['contract_title'] ?? null,
            'shift_id'                   => (int) $shift['id'],
            'shift_name'                 => $shift['name'],
            'shift_start_time'           => $this->minutesToTime($shiftStartMin),
            'shift_end_time'             => $this->minutesToTime($shiftEndMin),
            'origin_location_id'         => $base['location_id'] ?? null,
            'origin_name'                => $base['name'],
            'destination_location_id'    => $destination['location_id'] ?? null,
            'destination_name'           => $destination['name'],
            'site_names'                 => $siteNames,
            'outbound_site_names'        => array_map(static fn (array $s): string => $s['name'], $orderedOutbound),
            'return_site_names'          => array_map(static fn (array $s): string => $s['name'], $orderedReturn),
            'vehicle'                    => $vehicle,
            'vehicle_id'                 => $vehicle !== null ? (int) $vehicle['id'] : null,
            'stops'                      => $metrics['stops'],
            'employee_count'             => $employeeCount,
            'total_distance_km'          => round($totalKm, 2),
            'outbound_distance_km'       => round($metrics['outbound_km'], 2),
            'return_distance_km'         => round($metrics['return_km'], 2),
            'estimated_duration_minutes' => (int) round($metrics['outbound_min'] + $metrics['return_min']),
            'departure_time'             => $this->minutesToTime($metrics['departure_min']),
            'arrival_time'               => $this->minutesToTime($metrics['arrival_min']),
            'return_departure_time'      => $this->minutesToTime($metrics['return_departure_min']),
            'return_arrival_time'        => $this->minutesToTime($metrics['return_arrival_min']),
            'departure_min'              => $metrics['departure_min'],
            'arrival_min'                => $metrics['arrival_min'],
            'return_departure_min'       => $metrics['return_departure_min'],
            'return_arrival_min'         => $metrics['return_arrival_min'],
            'estimated_fuel_litres'      => $fuelLitres,
            'estimated_cost'             => $cost,
            'route_geometry'             => $metrics['geometry'],
            'optimization_notes'         => implode(' ', $notes),
        ];
    }

    /**
     * @param list<array> $orderedReturnSites
     * @param list<array> $returnBundles  Bundles keyed by contract/site.
     */
    protected function returnPeakLoad(array $orderedReturnSites, array $returnBundles): int
    {
        if ($orderedReturnSites === []) {
            return 0;
        }

        $countsByLocation = [];
        foreach ($returnBundles as $bundle) {
            $countsByLocation[(int) $bundle['site_point']['location_id']] = $bundle['counts']['return'];
        }

        $onBoard = 0;
        $peak    = 0;
        foreach ($orderedReturnSites as $site) {
            $onBoard += $countsByLocation[(int) $site['location_id']] ?? 0;
            $peak     = max($peak, $onBoard);
        }

        return $peak;
    }

    /**
     * @param list<array> $orderedOutbound
     * @param list<array> $orderedReturn
     * @param list<array> $bundles
     */
    protected function computeMultiSiteMetrics(
        array $base,
        array $orderedOutbound,
        array $orderedReturn,
        array $bundles,
        int $shiftStartMin,
        int $shiftEndMin
    ): array {
        $serviceMin = (int) $this->settings['pickup_service_minutes'];
        $bufferMin  = (int) $this->settings['arrival_buffer_minutes'];

        $bundleByLocation = [];
        foreach ($bundles as $bundle) {
            $bundleByLocation[(int) $bundle['site_point']['location_id']] = $bundle;
        }

        $outboundPoints = [['lat' => $base['lat'], 'lng' => $base['lng']]];
        foreach ($orderedOutbound as $site) {
            $outboundPoints[] = ['lat' => $site['lat'], 'lng' => $site['lng']];
        }

        $outboundGeo  = $this->routing->routeGeometry($outboundPoints);
        $outboundLegs = $outboundGeo['legs'] ?? [];

        $lastOutbound = $orderedOutbound !== [] ? $orderedOutbound[array_key_last($orderedOutbound)] : $base;
        $returnPoints = [['lat' => $lastOutbound['lat'], 'lng' => $lastOutbound['lng']]];
        foreach ($orderedReturn as $site) {
            if ($this->sameCoords($returnPoints[array_key_last($returnPoints)], $site)) {
                continue;
            }
            $returnPoints[] = ['lat' => $site['lat'], 'lng' => $site['lng']];
        }
        if (! $this->sameCoords($returnPoints[array_key_last($returnPoints)], $base)) {
            $returnPoints[] = ['lat' => $base['lat'], 'lng' => $base['lng']];
        }

        $returnGeo  = $this->routing->routeGeometry($returnPoints);
        $returnLegs = $returnGeo['legs'] ?? [];

        $outboundTravelMin = array_sum(array_map(
            static fn (array $leg): float => (float) ($leg['duration_minutes'] ?? 0),
            $outboundLegs
        ));
        $outboundKm = (float) ($outboundGeo['distance_km'] ?? 0);
        $returnTravelMin = array_sum(array_map(
            static fn (array $leg): float => (float) ($leg['duration_minutes'] ?? 0),
            $returnLegs
        ));
        $returnKm = (float) ($returnGeo['distance_km'] ?? 0);

        $outboundStops = count($orderedOutbound);
        $returnStops   = count($orderedReturn);
        $outboundService = $serviceMin * ($outboundStops > 0 ? 1 + $outboundStops : 0);
        $returnService   = $serviceMin * ($returnStops > 0 ? 1 + $returnStops : 1);

        $arrivalMin   = $shiftStartMin - $bufferMin;
        $departureMin = (int) round($arrivalMin - $outboundTravelMin - $outboundService);
        $boardTime    = $this->minutesToTime($departureMin);

        $stops = [];
        foreach ($bundles as $bundle) {
            foreach ($this->employeesForLeg($bundle['employees'], 'outbound') as $employee) {
                $role = trim((string) ($employee['role_on_contract'] ?? ''));
                $stops[] = [
                    'employee_id'          => $employee['employee_id'],
                    'employee_name'        => $employee['full_name'],
                    'employee_number'      => $employee['employee_number'],
                    'latitude'             => $base['lat'],
                    'longitude'            => $base['lng'],
                    'address'              => sprintf(
                        '[BOARD] %s%s',
                        $base['name'],
                        $role !== '' ? ' (' . $role . ')' : ''
                    ),
                    'pickup_time'          => $boardTime,
                    'leg_distance_km'      => 0.0,
                    'leg_duration_minutes' => 0.0,
                ];
            }
        }

        $cursor = $departureMin + $serviceMin;
        $prev   = $base;
        foreach ($orderedOutbound as $index => $site) {
            $leg = $outboundLegs[$index] ?? $this->routing->leg($prev['lat'], $prev['lng'], $site['lat'], $site['lng']);
            $cursor += (float) ($leg['duration_minutes'] ?? 0);
            $dropTime = $this->minutesToTime((int) round($cursor));
            $bundle   = $bundleByLocation[(int) $site['location_id']] ?? null;

            if ($bundle !== null) {
                foreach ($this->employeesForLeg($bundle['employees'], 'outbound') as $employee) {
                    $role = trim((string) ($employee['role_on_contract'] ?? ''));
                    $stops[] = [
                        'employee_id'          => $employee['employee_id'],
                        'employee_name'        => $employee['full_name'],
                        'employee_number'      => $employee['employee_number'],
                        'latitude'             => $site['lat'],
                        'longitude'            => $site['lng'],
                        'address'              => sprintf(
                            '[DROP] %s%s',
                            $site['name'],
                            $role !== '' ? ' (' . $role . ')' : ''
                        ),
                        'pickup_time'          => $dropTime,
                        'leg_distance_km'      => round((float) ($leg['distance_km'] ?? 0), 3),
                        'leg_duration_minutes' => round((float) ($leg['duration_minutes'] ?? 0), 2),
                    ];
                }
            }

            $cursor += $serviceMin;
            $prev = $site;
        }

        $returnDepartureMin = $shiftEndMin + $serviceMin;
        $cursor             = $returnDepartureMin;
        $prev               = $lastOutbound;
        $returnLegIndex     = 0;
        $atReturnOrigin     = true;

        foreach ($orderedReturn as $site) {
            if ($atReturnOrigin && $this->sameCoords($lastOutbound, $site)) {
                $leg = ['distance_km' => 0.0, 'duration_minutes' => 0.0];
            } else {
                $leg = $returnLegs[$returnLegIndex] ?? $this->routing->leg($prev['lat'], $prev['lng'], $site['lat'], $site['lng']);
                $returnLegIndex++;
                $cursor += (float) ($leg['duration_minutes'] ?? 0);
                $atReturnOrigin = false;
            }
            $pickupTime = $this->minutesToTime((int) round($cursor));
            $bundle     = $bundleByLocation[(int) $site['location_id']] ?? null;

            if ($bundle !== null) {
                foreach ($this->employeesForLeg($bundle['employees'], 'return') as $employee) {
                    $role = trim((string) ($employee['role_on_contract'] ?? ''));
                    $stops[] = [
                        'employee_id'          => $employee['employee_id'],
                        'employee_name'        => $employee['full_name'],
                        'employee_number'      => $employee['employee_number'],
                        'latitude'             => $site['lat'],
                        'longitude'            => $site['lng'],
                        'address'              => sprintf(
                            '[RETURN] %s → %s%s',
                            $site['name'],
                            $base['name'],
                            $role !== '' ? ' (' . $role . ')' : ''
                        ),
                        'pickup_time'          => $pickupTime,
                        'leg_distance_km'      => round((float) ($leg['distance_km'] ?? 0), 3),
                        'leg_duration_minutes' => round((float) ($leg['duration_minutes'] ?? 0), 2),
                    ];
                }
            }

            $cursor += $serviceMin;
            $prev = $site;
        }

        $finalReturnLeg = $returnLegs[$returnLegIndex] ?? $this->routing->leg($prev['lat'], $prev['lng'], $base['lat'], $base['lng']);
        $returnArrivalMin = (int) round($cursor + (float) ($finalReturnLeg['duration_minutes'] ?? 0));

        $geometryPoints = $outboundPoints;
        foreach (array_slice($returnPoints, 1) as $point) {
            $geometryPoints[] = $point;
        }
        $geometry = $this->routing->routeGeometry($geometryPoints);

        return [
            'stops'                => $stops,
            'outbound_km'          => $outboundKm,
            'outbound_min'         => $outboundTravelMin + $outboundService,
            'return_km'            => $returnKm,
            'return_min'           => $returnTravelMin + $returnService,
            'departure_min'        => $departureMin,
            'arrival_min'          => $arrivalMin,
            'return_departure_min' => $returnDepartureMin,
            'return_arrival_min'   => $returnArrivalMin,
            'busy_from'            => $departureMin,
            'busy_to'              => $returnArrivalMin,
            'geometry'             => $geometry['geometry'] ?? $outboundGeo['geometry'] ?? null,
        ];
    }

    protected function sameCoords(array $a, array $b): bool
    {
        return abs((float) $a['lat'] - (float) $b['lat']) < 0.00005
            && abs((float) $a['lng'] - (float) $b['lng']) < 0.00005;
    }

    /**
     * @param list<array> $employees
     *
     * @return list<array>
     */
    protected function employeesForLeg(array $employees, string $direction): array
    {
        return array_values(array_filter($employees, function (array $employee) use ($direction): bool {
            $leg = $employee['transport_leg'] ?? 'both';

            return $direction === 'outbound'
                ? ($leg === 'both' || $leg === 'outbound_only')
                : ($leg === 'both' || $leg === 'return_only');
        }));
    }

    /**
     * @param list<array> $employees
     *
     * @return array{outbound: int, return: int, total: int}
     */
    protected function legCounts(array $employees): array
    {
        $outbound = 0;
        $return   = 0;

        foreach ($employees as $employee) {
            $leg = $employee['transport_leg'] ?? 'both';
            if ($leg === 'both' || $leg === 'outbound_only') {
                $outbound++;
            }
            if ($leg === 'both' || $leg === 'return_only') {
                $return++;
            }
        }

        return ['outbound' => $outbound, 'return' => $return, 'total' => count($employees)];
    }

    protected function sitePoint(array $site): array
    {
        return [
            'location_id'    => (int) $site['transport_location_id'],
            'name'           => $site['location_name'],
            'lat'            => (float) $site['location_latitude'],
            'lng'            => (float) $site['location_longitude'],
            'contract_id'    => (int) $site['contract_id'],
            'contract_title' => $site['contract_title'] ?? null,
        ];
    }

    /**
     * Fixed base garage from AI settings, else nearest depot to site centroid.
     */
    protected function resolveBase(array $depots, array $sites): array
    {
        $baseId = (int) ($this->settings['default_base_location_id'] ?? 0);
        if ($baseId > 0) {
            $loc = $this->locations->find($baseId);
            if ($loc && ! empty($loc['latitude']) && ! empty($loc['longitude'])) {
                return [
                    'location_id' => (int) $loc['id'],
                    'name'        => $loc['name'],
                    'lat'         => (float) $loc['latitude'],
                    'lng'         => (float) $loc['longitude'],
                ];
            }
        }

        $centroidLat = 0.0;
        $centroidLng = 0.0;
        $count       = 0;
        foreach ($sites as $site) {
            if (empty($site['location_latitude']) || empty($site['location_longitude'])) {
                continue;
            }
            $centroidLat += (float) $site['location_latitude'];
            $centroidLng += (float) $site['location_longitude'];
            $count++;
        }

        $targetLat = $count > 0 ? $centroidLat / $count : 26.0667;
        $targetLng = $count > 0 ? $centroidLng / $count : 50.5577;

        $best     = null;
        $bestDist = PHP_FLOAT_MAX;
        foreach ($depots as $depot) {
            $dist = $this->routing->haversineKm(
                (float) $depot['latitude'],
                (float) $depot['longitude'],
                $targetLat,
                $targetLng
            );
            if ($dist < $bestDist) {
                $bestDist = $dist;
                $best     = $depot;
            }
        }

        if ($best !== null) {
            return [
                'location_id' => (int) $best['id'],
                'name'        => $best['name'],
                'lat'         => (float) $best['latitude'],
                'lng'         => (float) $best['longitude'],
            ];
        }

        return [
            'location_id' => null,
            'name'        => 'Base (unset)',
            'lat'         => $targetLat,
            'lng'         => $targetLng,
        ];
    }

    /**
     * Nearest-neighbor ordering for site waypoints.
     *
     * @param array       $start  {lat, lng, name?}
     * @param list<array> $sites
     * @param array|null  $end    Optional anchor toward the end of the tour.
     *
     * @return list<array>
     */
    protected function orderSitesNearestNeighbor(array $start, array $sites, ?array $end = null): array
    {
        if ($sites === []) {
            return [];
        }

        $remaining = array_values($sites);
        $ordered   = [];
        $current   = $start;

        while ($remaining !== []) {
            $bestIndex = 0;
            $bestScore = PHP_FLOAT_MAX;

            foreach ($remaining as $index => $site) {
                $dist = $this->routing->haversineKm($current['lat'], $current['lng'], $site['lat'], $site['lng']);
                if ($end !== null) {
                    $dist += $this->routing->haversineKm($site['lat'], $site['lng'], $end['lat'], $end['lng']) * 0.15;
                }
                if ($dist < $bestScore) {
                    $bestScore = $dist;
                    $bestIndex = $index;
                }
            }

            $next    = $remaining[$bestIndex];
            $ordered[] = $next;
            array_splice($remaining, $bestIndex, 1);
            $current = $next;
        }

        return $ordered;
    }

    protected function bearingFromBase(array $base, float $lat, float $lng): float
    {
        $y = sin(deg2rad($lng - $base['lng'])) * cos(deg2rad($lat));
        $x = cos(deg2rad($base['lat'])) * sin(deg2rad($lat))
            - sin(deg2rad($base['lat'])) * cos(deg2rad($lat)) * cos(deg2rad($lng - $base['lng']));

        return fmod(rad2deg(atan2($y, $x)) + 360, 360);
    }

    // ------------------------------------------------------------------
    // Helpers
    // ------------------------------------------------------------------

    /**
     * @param array<int, array{0: int, 1: int}> $windows
     */
    protected function windowsOverlap(array $windows, int $from, int $to): bool
    {
        foreach ($windows as [$busyFrom, $busyTo]) {
            if ($from < $busyTo && $to > $busyFrom) {
                return true;
            }
        }

        return false;
    }

    public function timeToMinutes(string $time): int
    {
        $parts = explode(':', $time);

        return ((int) $parts[0]) * 60 + (int) ($parts[1] ?? 0);
    }

    public function minutesToTime(int $minutes): string
    {
        $minutes = ((int) $minutes % 1440 + 1440) % 1440;

        return sprintf('%02d:%02d:00', intdiv($minutes, 60), $minutes % 60);
    }

    /**
     * @return string[] inclusive list of Y-m-d dates
     */
    protected function datesBetween(string $start, string $end): array
    {
        $dates  = [];
        $cursor = strtotime($start);
        $limit  = strtotime($end);
        while ($cursor !== false && $cursor <= $limit) {
            $dates[] = date('Y-m-d', $cursor);
            $cursor  = strtotime('+1 day', $cursor);
        }

        return $dates !== [] ? $dates : [date('Y-m-d')];
    }
}
