Trip planning depth 2

<?php

namespace App\Services\TripPlanning;

use App\Models\Daljinar;
use App\Models\Linija;
use App\Models\OldDaljinar;
use App\Models\Stajaliste;
use App\Models\StajalisteRedVoznje;
use Illuminate\Support\Collection;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Facades\Log;

class TripPlanningService
{
    public function findRoutesBetweenStops(Stajaliste $firstStop, Stajaliste $lastStop, $daljinari, $dist): array
    {
        $solutions = [];

        $startDaljinari = $firstStop->old_daljinari;
        $endDaljinari = $lastStop->old_daljinari;

        $allStartLinijaIds = $startDaljinari->pluck('linija_id');
        $allEndLinijaIds = $endDaljinari->pluck('linija_id');

        $allOtherRoutes = $daljinari->whereIn('linija_id', $allStartLinijaIds->merge($allEndLinijaIds)->unique());

        $routesByLinijaId = $allOtherRoutes->groupBy('linija_id');

        foreach ($startDaljinari as $startDaljinar) {
            if (!isset($routesByLinijaId[$startDaljinar->linija_id])) {
                continue;
            }

            $startStops = $routesByLinijaId[$startDaljinar->linija_id]->filter(function ($item) use ($startDaljinar) {
                return $item->smer === $startDaljinar->smer &&
                    $item->redni_broj_stajalista > $startDaljinar->redni_broj_stajalista;
            });

            foreach ($endDaljinari as $endDaljinar) {
                if (!isset($routesByLinijaId[$endDaljinar->linija_id])) {
                    continue;
                }

                $endStops = $routesByLinijaId[$endDaljinar->linija_id]->filter(function ($item) use ($endDaljinar) {
                    return $item->smer === $endDaljinar->smer &&
                        $item->redni_broj_stajalista < $endDaljinar->redni_broj_stajalista;
                });

                // Check for direct single line solution
                if ($startDaljinar->linija_id === $endDaljinar->linija_id &&
                    $startDaljinar->smer === $endDaljinar->smer &&
                    $startDaljinar->redni_broj_stajalista < $endDaljinar->redni_broj_stajalista) {
                    $solutions[] = (object)[
                        'segments' => [
                            (object)[
                                'linija' => $startDaljinar->linija,
                                'start_stop' => $startDaljinar->stajaliste,
                                'end_stop' => $endDaljinar->stajaliste,
                            ]
                        ]
                    ];
                }

                foreach ($endStops as $endStop) {
                    foreach ($startStops as $startStop) {
                        if ($this->calculateDistance(
                                $startStop->stajaliste->sirina, $startStop->stajaliste->duzina,
                                $endStop->stajaliste->sirina, $endStop->stajaliste->duzina
                            ) < $dist / 1000) {
                            $solutions[] = (object)[
                                'segments' => [
                                    (object)[
                                        'linija' => $startDaljinar->linija,
                                        'start_stop' => $startDaljinar->stajaliste,
                                        'end_stop' => $startStop->stajaliste,
                                    ],
                                    (object)[
                                        'linija' => $endDaljinar->linija,
                                        'start_stop' => $endStop->stajaliste,
                                        'end_stop' => $endDaljinar->stajaliste,
                                    ]
                                ]
                            ];
                        }
                    }
                }
            }
        }

        return $solutions;
    }

    public function findRoute2($startLat, $startLng, $endLat, $endLng, $dist): array
    {
        $solutions = [];

        $limit = 8;

        $initialStops = $this->findNearbyStops($startLat, $startLng, $dist, $limit);
        $finalStops = $this->findNearbyStops($endLat, $endLng, $dist, $limit);

        $stopsIds = array_merge($initialStops->pluck('id')->toArray(), $finalStops->pluck('id')->toArray());

        $daljinari = OldDaljinar::whereIn('stajaliste_id', $stopsIds)->get();

        $linijeIds = $daljinari->pluck('linija_id')->toArray();

        $activeLinijeIds = Linija::whereIn('kod_linije', $linijeIds)->active()->where('tip_linije', '!=', 'ноћне-линије')->pluck('kod_linije')->toArray();

        $daljinari = OldDaljinar::with(['linija.shapes', 'stajaliste'])->whereIn('linija_id', $activeLinijeIds)->get();

        foreach ($initialStops as $initialStop) {
            foreach ($finalStops as $finalStop) {
                $solutions = array_merge($solutions, $this->findRoutesBetweenStops($initialStop, $finalStop, $daljinari, $dist));
            }
        }

        return $this->groupSolutions($solutions);
    }

    private function decorateWithStopTimes()
    {

    }

    private function groupSolutions($solutions): array
    {
        $solutions = $this->groupSolutionsByStops($solutions);
        $solutions = $this->groupSolutionsByLines($solutions);

        return array_values($solutions);
    }

    private function groupSolutionsByStops($solutions): array
    {
        $groupedSolutions = [];

        foreach ($solutions as $solution) {
            $uniqueArray = [];

            foreach ($solution->segments as $segment) {
                $uniqueArray[] = $segment->start_stop->id;
                $uniqueArray[] = $segment->end_stop->id;
            }

            $uniqueString = implode('-', $uniqueArray);

            if (isset($groupedSolutions[$uniqueString])) {
                foreach ($groupedSolutions[$uniqueString]->segments as $index => $groupedSegment) {
                    $newLinija = $solution->segments[$index]->linija;

                    if (!in_array($newLinija, $groupedSegment->linija)) {
                        $groupedSegment->linija[] = $newLinija;
                    }
                }
            } else {
                $groupedSolutions[$uniqueString] = $solution;

                foreach ($groupedSolutions[$uniqueString]->segments as $segment) {
                    $segment->linija = [$segment->linija];
                }
            }
        }

        return array_values($groupedSolutions);
    }

    private function groupSolutionsByLines($solutions): array
    {
        $groupedSolutions = [];

        foreach ($solutions as $solution) {
            $linije = [];

            foreach ($solution->segments as $segment) {
                // Extract kod_linija from the linija array
                $linije[] = array_map(function($linija) {
                    return $linija->kod_linije;
                }, $segment->linija);
            }

            $alreadyIncluded = false;

            foreach ($groupedSolutions as $solutionIndex => $groupedSolution) {
                $groupedLinije = [];

                foreach ($groupedSolution->segments as $groupedSegment) {
                    $groupedLinije[] = array_map(function($linija) {
                        return $linija->kod_linije;
                    }, $groupedSegment->linija);
                }

                if (count($linije) === count($groupedLinije)) {
                    $includes = true;
                    $included = true;

                    foreach ($linije as $index => $linijaSegment) {
                        $status = $this->arrayContainsOrContained($groupedLinije[$index], $linijaSegment);
                        if ($status !== 1) {
                            $includes = false;
                        }
                        if ($status !== -1 && !($status === 1 && count($linijaSegment) === count($groupedLinije[$index]))) {
                            $included = false;
                        }
                    }

                    $allSegmentsMatch = $included || $includes;

                    if (!$includes && $included) {
                        $groupedSolutions[$solutionIndex] = $solution;
                    }

                    if ($allSegmentsMatch) {
                        $alreadyIncluded = true;
                        break;
                    }
                }
            }

            if (!$alreadyIncluded) {
                $groupedSolutions[] = $solution;
            }
        }

        return array_values($groupedSolutions);
    }

    /**
     * Returns 1 if $array1 contains $array2, -1 if $array2 contains $array1, and 0 if neither.
     *
     * @param array $array1
     * @param array $array2
     * @return int
     */
    public function arrayContainsOrContained(array $array1, array $array2): int
    {
        if ($this->isSubset($array2, $array1)) {
            return 1;
        }

        if ($this->isSubset($array1, $array2)) {
            return -1;
        }

        return 0;
    }

    /**
     * Checks if $subset is a subset of $set.
     *
     * @param array $subset
     * @param array $set
     * @return bool
     */
    private function isSubset(array $subset, array $set): bool
    {
        return empty(array_diff($subset, $set));
    }

    public function findNearbyStopsSquare($lat, $lng, $squareSide)
    {
        $latitudeDegree = 111320; // Meters
        $longitudeDegree = 78850; // Meters for Serbia (44-45 degrees)

        $latDiff = $squareSide / $latitudeDegree;
        $lngDiff = $squareSide / $longitudeDegree;

        return Stajaliste::where('sirina', '<', $lat + $latDiff)->where('sirina', '>', $lat - $latDiff)
            ->where('duzina', '<', $lng + $lngDiff)->where('duzina', '>', $lng - $lngDiff)
            ->with('old_daljinari.linija.shapes')->get();
    }

    private function calculateDistance2($lat1, $lon1, $lat2, $lon2)
    {
        $latitudeDegree = 111320; // Meters per degree of latitude
        $longitudeDegree = 78850; // Meters per degree of longitude (approximation for Serbia)

        // Convert latitude and longitude differences to meters
        $latDiff = abs($lat2 - $lat1) * $latitudeDegree;
        $lngDiff = abs($lon2 - $lon1) * $longitudeDegree;

        // Calculate the Euclidean distance
        return sqrt($latDiff ** 2 + $lngDiff ** 2); // Distance in meters
    }

    /**
     * Returns the close stops defined by the distance, given by $dist, in meters, and $limit.
     *
     * @param $lat
     * @param $lng
     * @param float $dist
     * @param int $limit
     * @param string $with
     * @return mixed
     */
    public function findNearbyStops($lat, $lng, float $dist = 0, int $limit = 10, $with = '')
    {
        $dist = $dist / 1000; //Convert meters into kilometers

        $query = Stajaliste::selectRaw("*, ( 6371 * acos( cos( radians(?) ) * cos( radians( sirina ) ) * cos( radians( duzina ) - radians(?) ) + sin( radians(?) ) * sin( radians( sirina ) ) ) ) AS distance", [$lat, $lng, $lat])
            ->orderBy('distance');

        if ($with) {
            $query->with('old_daljinari.linija.shapes');
        }

        if ($dist !== 0) {
            $query->having('distance', '<', $dist);
        }

        return $query->take($limit)->get();
    }

    private function calculateDistance($lat1, $lon1, $lat2, $lon2)
    {
        $earthRadius = 6371; // Kilometers

        $dLat = deg2rad($lat2 - $lat1);
        $dLon = deg2rad($lon2 - $lon1);

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

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

        return $earthRadius * $c; // Distance in kilometers
    }

    public function decodePolyline($encoded) {
        $points = [];
        $index = 0;
        $lat = 0;
        $lng = 0;

        while ($index < strlen($encoded)) {
            $b = 0;
            $shift = 0;
            $result = 0;
            do {
                $b = ord($encoded[$index++]) - 63;
                $result |= ($b & 0x1f) << $shift;
                $shift += 5;
            } while ($b >= 0x20);
            $deltaLat = ($result & 1) ? ~(($result >> 1)) : ($result >> 1);
            $lat += $deltaLat;

            $b = 0;
            $shift = 0;
            $result = 0;
            do {
                $b = ord($encoded[$index++]) - 63;
                $result |= ($b & 0x1f) << $shift;
                $shift += 5;
            } while ($b >= 0x20);
            $deltaLng = ($result & 1) ? ~(($result >> 1)) : ($result >> 1);
            $lng += $deltaLng;

            $points[] = [($lat / 1E5), ($lng / 1E5)];
        }

        return $points;
    }
}