/* icao -- router module */

#include "popup.h"
#include "objects.h"
#include <stdio.h>
#include <Xm/Xm.h>
#include "busy.h"


/* define max. recursion depth for router */
#define REC_DEPTH  8
#define REC_WIDTH  3


typedef struct {
  int nextpoint;
  OBJECT *waypoints[REC_DEPTH];
  double distance;
} ROUTE;


extern OBJECT **objectlist;   /* object list, from object.c */
extern int db_objects;        /* number of objects in object list */
extern unsigned int display_width;  /* scrren width, from map.c */

extern int drawroutenumpoints;          /* current route to be drawn */
extern LOCATION drawroutepoints[100];


/* define default range in NM */
#define DEF_RANGE 5



int waypointtypes[100];       /* list of waypoint type IDs */
int numberofwaypointtypes;


static OBJECT *route_to, *route_from;
double route_distance;


void router_radionav()        /* select radio navigation waypoints */
{
  waypointtypes[0] = O_VOR;
  waypointtypes[1] = O_VOR_DME;
  waypointtypes[2] = O_VORTAC;
  waypointtypes[3] = O_TACAN;
  waypointtypes[4] = O_NDB;
  numberofwaypointtypes = 5;
}



int rangecompare (OBJECT **a, OBJECT **b)
{
  return (int) distance ((*a)->location, route_to->location) -
    distance ((*b)->location, route_to->location);
}


/* find objects in range of a current position; only returns objects that
   bring you closer to your destination; find no more then maxobj objects */

void objects_in_range (OBJECT *position, OBJECT **in_range, int *numfound, 
		       int maxobj)
{
  double startrange;   /* range of current position's object */
  OBJECT **templist;
  int i, j, match;

  templist = (OBJECT **) malloc (sizeof (OBJECT *) * 1000); 
  *numfound = 0;

  startrange = 0;   /* flying away from a VOR etc.? then use that range, too */
  if ((position->type >= O_VOR) && (position->type <= O_TACAN)) 
    if (position->range != UNKNOWN)
      startrange = position->range;
    else
      startrange = DEF_RANGE;

  if (templist)
    {
      /* go through object list */

      for (i=0; i<db_objects; i++)
	{
	  match = 0;   /* check if this is an allowed object type */
	  for (j=0; j<numberofwaypointtypes; j++)
	    if (waypointtypes[j] == objectlist[i]->type)
	      match = 1;

	  if (match)
	    {
	      if ((distance (objectlist[i]->location, route_to->location) <
		   (distance (position->location, route_to->location))) || 
		  ((position == route_from) && 
		   ((objectlist[i]->type >= O_VOR) && (objectlist[i]->type <= O_TACAN))))
		if (objectlist[i] != position)
		  if ((distance(objectlist[i]->location,position->location) 
		       - startrange)
		      <= ((objectlist[i]->range != UNKNOWN) ?
			  objectlist[i]->range : DEF_RANGE))
		    {
		      templist[*numfound] = objectlist[i];
		      (*numfound)++;
		    }
	    }
	}
      
      /* sort objects by range from destination */

      qsort (templist, *numfound, sizeof (OBJECT *), rangecompare);

      /* copy the maxobj nearest objects to in_range array */

      for (i=0; i<maxobj; i++)
	in_range[i] = templist[i];

      if (*numfound > maxobj)
	*numfound = maxobj;

      free (templist);
    }  
}



/* find optimal route from position to route_to */

ROUTE opt_route (ROUTE currentroute)
{
  OBJECT *currentpos = currentroute.waypoints[currentroute.nextpoint-1];
  OBJECT *possible_next_points[REC_WIDTH];
  ROUTE possible_route[REC_WIDTH];
  int numpoints, i, minindex;
  double olddistance;


  /* don't go too deep into recursion */
  
  if (!(currentroute.nextpoint < REC_DEPTH))
    return currentroute;


  /* first check if current route is too long (twice the shortest distance) already */

  if (currentroute.distance > 2*route_distance)
    return currentroute;
  

  /* check if we have reached  destination already */

  if (currentpos == route_to)
    return currentroute;

  /* check if we can reach the destination from here */
  
  if ((currentpos->type >= O_VOR) && (currentpos->type <= O_TACAN))
    if (distance (currentpos->location, route_to->location) <=
	(currentpos->range != UNKNOWN ? currentpos->range : DEF_RANGE))
      {
	currentroute.waypoints[currentroute.nextpoint] = route_to;
	currentroute.nextpoint++;
	currentroute.distance += distance (currentpos->location, route_to->location);

	return currentroute;
      }


  /* OK, now let's see where we can get from here... */

  objects_in_range (currentpos, possible_next_points, &numpoints, REC_WIDTH);

  /* if we didn't find any points, we can't use this route */

  if (numpoints == 0)
    return currentroute;


  /* otherwise, test how we get on with several points... */

  for (i=0; i<numpoints; i++)
    {
      olddistance = currentroute.distance;
      currentroute.waypoints[currentroute.nextpoint] = possible_next_points[i];
      currentroute.nextpoint++;
      currentroute.distance += distance (currentpos->location, possible_next_points[i]->location);

      possible_route[i] = opt_route (currentroute);

      currentroute.distance = olddistance;
      currentroute.nextpoint--;
    }


  /* now check which of these routes is shortest */

  
  minindex = 0;
  for (i=1; i<numpoints; i++)
    if (possible_route[i].distance < possible_route[minindex].distance)
      if (possible_route[i].waypoints[possible_route[i].nextpoint-1] == route_to)
	minindex = i;

  return possible_route[minindex];
}



/* perform actual routing */

void router_findroute (OBJECT *from, OBJECT *via1, OBJECT *via2, 
		       OBJECT *via3, OBJECT *to)
{
  ROUTE bestroute;
  int i, j, line;
  double totaldistance;
  double directdistance;
  OBJECT *waypoints[5];
  int usedwaypoints;
  OBJECT *routepoints[REC_DEPTH * 4];
  int usedroutepoints;
  int success;
  char desc[100], desc2[100];
  double inbound;
  extern Widget toplevel, shell;

  shell = toplevel;
  usedroutepoints = 0;
  success = 1;

  TimeoutCursors (True, False); 

  if ((from && to) && ((from != to) || ((via1) && (from != via1))))
    {
      usedwaypoints = 0;
      waypoints[usedwaypoints++] = from;
      if (via1) waypoints[usedwaypoints++] = via1;
      if (via2) waypoints[usedwaypoints++] = via2;
      if (via3) waypoints[usedwaypoints++] = via3;
      waypoints[usedwaypoints++] = to;

      for (j=0; j<usedwaypoints-1; j++)
	{
	  route_from = waypoints[j];
	  route_to = waypoints[j+1];
	  route_distance = distance (route_from->location, route_to->location);

	  bestroute.waypoints[0] = route_from;
	  bestroute.nextpoint = 1;
	  bestroute.distance = 0;   /* we haven't moved yet */

	  bestroute = opt_route (bestroute);

	  if (bestroute.waypoints[bestroute.nextpoint-1] != route_to)
	    {
	      /* try to find a route without NDBs */
	      
	      i = 0;
	      while ((i < numberofwaypointtypes) && (waypointtypes[i] != O_NDB))
		i++;
	      if (i < numberofwaypointtypes-1)
		waypointtypes[i] = waypointtypes[numberofwaypointtypes-1];
	      numberofwaypointtypes--;
	      
	      bestroute.waypoints[0] = route_from;
	      bestroute.nextpoint = 1;
	      bestroute.distance = 0;   /* we haven't moved yet */
	      
	      bestroute = opt_route (bestroute);
	    }
	  if (bestroute.waypoints[bestroute.nextpoint-1] != route_to)
	    success = 0;
	  else
	    for (i = (j ? 1 : 0); i<bestroute.nextpoint; i++)
	      routepoints[usedroutepoints++] = bestroute.waypoints[i];
	}


      line = 0;
      sprintf (popupstrings[line++], "From %s %s", objecttypestring(from->type), from->name);
      if (via1) sprintf (popupstrings[line++], "via  %s %s", objecttypestring(via1->type), via1->name);
      if (via2) sprintf (popupstrings[line++], "via  %s %s", objecttypestring(via2->type), via2->name);
      if (via3) sprintf (popupstrings[line++], "via  %s %s", objecttypestring(via3->type), via3->name);
      sprintf (popupstrings[line++], "To   %s %s", objecttypestring(to->type), to->name);
      strcpy (popupstrings[line++], "");
      
      if (from != to)
	{
	  sprintf (popupstrings[line++], "direct course:  Dist:%6.1f, true track: %5.1f (direct)",
		   distance (from->location, to->location),
		   truetrack (from->location, to->location));
	  strcpy (popupstrings[line++], "");
	}

      if (!success)
	strcpy (popupstrings[line++], "Autorouter couldn't find a sufficient route!"); 
      else
	{
	  /* as far as drawing the route is concerned: if a different route is
	     already visible, we should delete it first */

	  if (drawroutenumpoints)
	    undrawroute();

	  drawroutenumpoints = 0;
	  
	  strcpy (popupstrings[line++], "Inbound                 Waypoint             Outbound       NM");
	  strcpy (popupstrings[line++], "--------------------------------------------------------------");
	  totaldistance = 0;

	  for (i=0; i<usedroutepoints; i++)
	    {
	      drawroutepoints[drawroutenumpoints++] = routepoints[i]->location;

	      /* make description string */

	      if (routepoints[i]->type > 100)
		{
		  if (routepoints[i]->type != O_WAYPOINT)
		    sprintf (desc, "%s %s", objecttypestring(routepoints[i]->type), 
			     routepoints[i]->name);
		  else
		    if (routepoints[i]->alias)
		      sprintf (desc, "%s %s", routepoints[i]->alias, routepoints[i]->name);
		    else
		      sprintf (desc, "%s", routepoints[i]->name);

		  if (routepoints[i]->type <= O_BASIC_RADIO_FACILITY)   /* radio beacon */
		    if (routepoints[i]->frequency)
		      if (routepoints[i]->type == O_NDB)
			{
			  if (routepoints[i]->frequency - (int) routepoints[i]->frequency)
			    sprintf (desc+strlen(desc), " (%5.1f)", routepoints[i]->frequency);
			  else
			    sprintf (desc+strlen(desc), " (%3.0f)", routepoints[i]->frequency);
			}
		      else
			sprintf (desc+strlen(desc), " (%6.2f)", routepoints[i]->frequency);
		}
	      else
		sprintf (desc, "%s", routepoints[i]->name);

	      /* make desc wide enough */

	      while (strlen(desc) < 39)
		{
		  strcat (desc, " ");
		  if (strlen(desc) < 39)
		    {
		      strcpy (desc2, desc);
		      sprintf (desc, " %s", desc2);
		    }
		}

	      desc[39] = 0;   /* truncate in case it should have become too long */

	      if (i)
		{
		  inbound = truetrack (routepoints[i]->location, routepoints[i-1]->location) + 180;
		  if (inbound > 360)
		    inbound -= 360;

		  totaldistance += distance(routepoints[i-1]->location, routepoints[i]->location);
		  if (i != usedroutepoints-1)
		    sprintf (popupstrings[line++], 
			     "%6.1f %s %5.1f    %6.1f ", 
			     inbound, desc,
			     truetrack(routepoints[i]->location, routepoints[i+1]->location),
			     distance(routepoints[i]->location, routepoints[i+1]->location));
		  else
		    sprintf (popupstrings[line++], 
			     "%6.1f %s", inbound, desc);
		}
	      else
		sprintf (popupstrings[line++], 
			 "       %s %5.1f    %6.1f ", 
			 desc,
			 truetrack(routepoints[i]->location, routepoints[i+1]->location),
			 distance(routepoints[i]->location, routepoints[i+1]->location));
	    }

	  strcpy (popupstrings[line++], "--------------------------------------------------------------");
	  sprintf (popupstrings[line++], 
		   "                                     total distance: %9.1f", totaldistance);
	  if (from != to)
	    sprintf (popupstrings[line++], 
		     "                    detour compared to direct route: %9.1f", 
		     totaldistance - distance (from->location, to->location));
	}

      drawroute();  /* defined in icao.c, draws line to indicate route */

      TimeoutCursors (False, False); 

      popupbox (line, "Auto Router");
    }
  else
    {
      TimeoutCursors (False, False); 
      strcpy (popupstrings[0], "No proper end points defined!");
      popupbox (1, "Auto Router");
    }
}


