/****************************************************************
 *                                                              *
 *                        I C A O   M a p  -                    *
 *                                                              *
 *             A n   A v i a t i o n   U t i l i t y            *
 *                                                              *
 *                                                              *
 *            Copyright (C) 1993, 1994  Martin Pauly            *
 *                                                              *
 *                   N e x t   V e r s i o n                    *
 *                                                              *
 *       Copyright (C) 1994  Stefan Leuker & Oliver Meyer       *
 *                                                              *
 *   This file may be freely distributed only if it includes    *
 *                the above copyright notice.                   *
 *                                                              *
 ****************************************************************/

/* icao -- router module */
#import "router.h"
#import <appkit/appkit.h>

OBJECT             *currentroute[] = {NULL, NULL, NULL, NULL, NULL};


/* 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(const void *a, const void *b)
{
	return (int)distance((*(OBJECT **) a)->location, route_to->location) -
	distance((*(OBJECT **) 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 next_findroute(char *wholetext, OBJECT * from, OBJECT * via1, 
		OBJECT * via2, OBJECT * via3, OBJECT * to)
{
	ROUTE               bestroute;
	int                 i, j;
	double              totaldistance;
	OBJECT             *waypoints[5];
	int                 usedwaypoints;
	OBJECT             *routepoints[REC_DEPTH * 4];
	int                 usedroutepoints;
	int                 success;
	char                desc[100], desc2[100];
	double              inbound;

	usedroutepoints = 0;
	success = 1;

	/* 
	 * Das scheint mir nicht ganz richtig! 
	 * Was wenn in via1 nichts, wohl aber in via2 was steht?
	 */
	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];
		}


		sprintf(wholetext, "From %s %s\n", objecttypestring(from->type)
				, from->name);
		if (via1)
			sprintf(wholetext+strlen(wholetext), "via  %s %s\n"
					, objecttypestring(via1->type), via1->name);
		if (via2)
			sprintf(wholetext+strlen(wholetext), "via  %s %s\n"
					, objecttypestring(via2->type), via2->name);
		if (via3)
			sprintf(wholetext+strlen(wholetext), "via  %s %s\n"
					, objecttypestring(via3->type), via3->name);
		sprintf(wholetext+strlen(wholetext), "To   %s %s\n\n"
				, objecttypestring(to->type), to->name);

		if (from != to)
		{
			sprintf(wholetext+strlen(wholetext)
					, "direct course:  Dist:%6.1f %2s, true track: %5.1f (direct)\n\n"
					, distance(from->location, to->location) * UNIT_CHANGE(IPD_AUTOUNIT)
					, UNIT_NAME(IPD_AUTOUNIT)
					,	truetrack(from->location, to->location));
		}
		if (!success)
			strcat(wholetext, "Autorouter couldn't find a sufficient route!\n");
		else
		{
			drawroutenumpoints = 0;

			sprintf(wholetext+strlen(wholetext)
					,	"Inbound                 Waypoint             Outbound       %2s\n"
					, UNIT_NAME(IPD_AUTOUNIT));
			strcat(wholetext,
					"--------------------------------------------------------------\n");
			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);
						
					/* radio beacon */
					if (routepoints[i]->type <= O_BASIC_RADIO_FACILITY)	
						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(wholetext+strlen(wholetext)
								,	"%6.1f %s %5.1f    %6.1f\n",	inbound, desc
								, truetrack(routepoints[i]->location
										, routepoints[i + 1]->location)
								, distance(routepoints[i]->location
										, routepoints[i + 1]->location)*UNIT_CHANGE(IPD_AUTOUNIT));
					else
						sprintf(wholetext+strlen(wholetext), "%6.1f %s\n", inbound, desc);
				} else
					sprintf(wholetext+strlen(wholetext)
							, "       %s %5.1f    %6.1f\n", desc
							, truetrack(routepoints[i]->location
									, routepoints[i + 1]->location)
							, distance(routepoints[i]->location
									, routepoints[i + 1]->location)*UNIT_CHANGE(IPD_AUTOUNIT));
			}

			strcat(wholetext, 
					"--------------------------------------------------------------\n");
			sprintf(wholetext+strlen(wholetext)
					, "                                     total distance: %9.1f\n"
					, totaldistance*UNIT_CHANGE(IPD_AUTOUNIT));
			if (from != to)
				sprintf(wholetext+strlen(wholetext)
						, "                    detour compared to direct route: %9.1f\n"
						, (totaldistance - distance(from->location, to->location))
								* UNIT_CHANGE(IPD_AUTOUNIT));
		}

	}
}
