#!/usr/bin/python3
#  $HeadURL: https://svn.pasta.freemyip.com/main/ade/tags/3.0.3/share/templates/xxx/bin/xxx $ $LastChangedRevision: 11136 $

#  Modules
import subprocess
import os
import sys
sys.path.append(subprocess.Popen(['miniade', '--dirname'], stdout=subprocess.PIPE, universal_newlines=True).communicate()[0].rstrip())
import miniade
import matplotlib.pyplot
import geopy.distance
import gpxpy

#  Configurable stuff

#  Other globals

def main():
    global mode

    #  Defaults for options
    mode = 'normal'

    #  Process options
    def special_opts_handler():
        global mode

        if sys.argv[1] == '--explain':
            mode = 'explain'
            return True

        return False
    miniade.process_options(special_opts_handler, help)

    #  Process arguments
    #  (delegated)

    #  Sanity checks and derivations
    #  (delegated)

    #  Guts
    #  (delegated)
    if mode == 'normal':
        mode_normal()
    elif mode == 'explain':
        mode_explain()
    else:
        miniade.internal('main: %s: invalid mode' % (mode))

def mode_normal():
    #  Defaults for options
    plot_enabled = False
    route_point_prefix_enabled = True

    #  Process arguments
    if len(sys.argv) != 3:
        miniade.bad_usage()
    gpx_waypoints_file = sys.argv[1]
    gpx_route_file = sys.argv[2]

    #  Guts
    miniade.debug(10, 'main: loading waypoints ...')
    fh = open(gpx_waypoints_file, 'r')
    gpx = gpxpy.parse(fh)
    fh.close()

    miniade.debug(10, 'main: extracting coordinates ...')
    cities = [(waypoint.longitude,waypoint.latitude) for waypoint in gpx.waypoints]

    miniade.debug(10, 'main: calling get_optimally_ordered_waypoint_indices() to get optimum visiting order ...')
    optimally_ordered_waypoint_indices, total_distance = get_optimally_ordered_waypoint_indices(cities)
    miniade.info('total distance: %.1fkm' % (total_distance))

    miniade.debug(10, 'main: instantiating a GPX data set and a new route and putting the new route in the new data set ...')
    gpx2 = gpxpy.gpx.GPX()
    gpx2_route = gpxpy.gpx.GPXRoute()
    gpx2.routes.append(gpx2_route)

    miniade.debug(10, 'main: copying waypoints to routepoints in optimum visiting order ...')
    for i, waypoint in enumerate([gpx.waypoints[x] for x in optimally_ordered_waypoint_indices]):
        if route_point_prefix_enabled:
            waypoint.name = 'VISIT%03d: %s' % (i, waypoint.name)
        gpx2_route.points.append(waypoint)

    miniade.debug(10, 'main: saving route ...')
    fh = open(gpx_route_file, 'w')
    fh.write(gpx2.to_xml())
    fh.close()

    if plot_enabled:
        miniade.debug(10, 'main: plotting ...')
        x_coords = [cities[i][0] for i in optimally_ordered_waypoint_indices]
        y_coords = [cities[i][1] for i in optimally_ordered_waypoint_indices]
        x_coords.append(x_coords[0])  # Close the loop for plotting
        y_coords.append(y_coords[0])
        matplotlib.pyplot.plot(x_coords, y_coords)
        matplotlib.pyplot.scatter(x_coords, y_coords, s=50, color='red')  # Plot cities as red dots
        matplotlib.pyplot.title("Traveling Salesman Problem - Greedy Algorithm")
        matplotlib.pyplot.show()
    return 0

def mode_explain():
    if len(sys.argv) != 1:
        miniade.bad_usage()
    sys.stdout.write('''\
1. Visit https://overpass-turbo.eu/
2. Paste in the left the following "program":

       [out:json][timeout:60][bbox:{{bbox}}];

       node["amenity"="cafe"];
       out;

       way["amenity"="cafe"];
       out center;

       relation["amenity"="cafe"];
       out center;

       node["amenity"="restaurant"];
       out;

       way["amenity"="restaurant"];
       out center;

       relation["amenity"="restaurant"];
       out center;

3. Position the map according as you want.
4. Click Run.
5. Click Export-->GPX-->Download and save the downloaded GPX file.
6. Run this script with two parameters: the name of the just-downloaded
   GPX file and the name of a new GPX file that will contain the
   optimal route.
''')

def help():
    progname = miniade.get_progname()
    sys.stdout.write('Usage: %s [ <standard-options> ] { --explain | <waypoints-file> <route-file> }\n' % (progname))
    sys.exit(0)

def get_optimally_ordered_waypoint_indices(cities):
    #  This is based on the "greedy algorithm" at
    #  https://www.askpython.com/python/examples/travelling-salesman-problem-python

    visited = [False] * len(cities)
    current_city = 0

    optimally_ordered_waypoint_indices = []
    total_distance = 0

    for _ in range(len(cities)):
        visited[current_city] = True
        optimally_ordered_waypoint_indices.append(current_city)

        next_city = None
        min_distance = float('inf')

        for i in range(len(cities)):
            if visited[i]:
                continue

            d = geopy.distance.geodesic(cities[current_city], cities[i]).km
            if d < min_distance:
                min_distance = d
                next_city = i

        current_city = next_city
        total_distance += min_distance if min_distance != float('inf') else 0.0;

    return optimally_ordered_waypoint_indices, total_distance

#  Entry point
if __name__=="__main__":
    main()