/* File: search.c
 * Description: implementation file for the module containing
 * algorithms which find the shortest route between cities.
 * The function makes use of stacks to find the shortest route.
 * The stack stores pairs of cities which haven't yet been
 * explored in the current path being tested.
 * Cristina Cifuentes
 * 3 August 1997
 * 18 August 1997 - changed FlightRouteType for Graph data type.
 *    Updated the way varibles of type FlighRouteType for
 *    consistency with the new Graph interface.
*/


#include "cities.h"
#include "citystk.h"
#include "search.h"



/* IMPLEMENTATION OF THE SEARCHING ALGORITHM */

int findShortestPath (Graph fr, cityPair trip,
		      cityPath bestPath, int *pathLength)

{ cityPath visited,		/* the current path 	*/
	   shortest;		/* the best path discovered so far */
  int visPosn = 0,		/* index for the path position which will
				 * be visited next	*/
	  lengthVisited,  	/* length of current route  */
	  lengthShortest = -1,	/* length of shortest route so far  */
	  numberNotVisited = -1,/* the number of cities not visited from
				 * a particular city (the current "location") */
	  i;
  Stack s;              	/* opaque pointer type to a stack */
  cityPair cPair, cPair2;

	s = stackNew();

	clearPath (visited);	/* sets both paths to an empty path */
	clearPath (shortest);

	cPair.from = trip.from;  /* Sets the first city pair on the stack to be */
	cPair.to = trip.from;    /* the journey from the starting city to itself. */
				 /* It is just a convenient way to handle the
				    starting position.		*/

	stackPush (s, cPair);

	while (! stackEmpty(s))	/* When the stack is empty, all possible routes
				   have been tested   */
	{
		stackPop (s, &cPair);   /* 'moves' to a new city (cPair.to) */

		if (numberNotVisited == 0)
				/* This code moves the current position
				   back through the visited path until it
				   reaches the point at which the city
				   visited[visPosn] equals cPair.from
				   (recently popped).
				*/

		{
			while (visited[visPosn-1] != cPair.from)
			{
				visPosn--;
				visited[visPosn] = NoCity;
				 /* Clears the path of incorrect information
				    (This step is essential for the function
				    which finds the length of a given path)  */
			}
		}

		visited[visPosn] = cPair.to;
				/* adds the new city to the visited path */
		visPosn++;

		if (cPair.to == trip.to)
		{
			lengthVisited = getPathLength (visited, fr);
			if ((lengthVisited < lengthShortest)||
			    (lengthShortest == -1))
				/* Checks to see if we have found a better
				   path to our destination */
			{
				lengthShortest = lengthVisited;
				assignPath (visited, shortest);
			}

			numberNotVisited = 0;
				/* forces the program to move back to a
				   previous branch of the route-finding
				   tree  */
		}

		else	/* if not a the destination then...  */

		{
			numberNotVisited=0;
				/* Counts the number of cities not yet
				   visited which can be visited from the
				   current city (cPair.to)  */

			i = 0;	/* counter which scans through all cities */

			cPair2.from = cPair.to;
				/* we are pushing pairs FROM the current
				   city to all unexplored cities on this
				   route to the stack  */

			while (i <= NUMCITIES)
			{
				cPair2.to = (City) i;

				if ((distanceBetweenCities (fr, cPair2) > 0)
				   && (! inPath (cPair2.to, visited)))
				{
					stackPush (s, cPair2);
					numberNotVisited++;
					    /* Adds the untested route (from
					       the current position) to the
					       stack   */
				}

				i++;
			}

		}
	}

	assignPath (shortest, bestPath);
	*pathLength = getPathLength (shortest, fr);

	return 0;
}




int getPathLength (cityPath p, Graph fr)
/* Finds the length of a given path. It determines the endpoint
 * as being the point at which it encounters a NoCity city
 * or the point at which the number of cities equals the maximum number
 * of cities. Note that this means that the type cityPath is not
 * the most general type possible - it doesn't really cater for repeating routes,
 * but these are, of course, not the shortest possible!   */
{ int l=0,
      c=0;
  cityPair pair;

	while ((p[c+1] != NoCity) && (c < NUMCITIES))
	{
		pair.to = p[c];
		pair.from = p[c+1];
		l += distanceBetweenCities (fr, pair);
		c++;
	}
	return l;
}



void clearPath (cityPath p)
{ int i;

	for (i=0; i <= NUMCITIES; i++)
		p[i] = NoCity;
}



void assignPath (cityPath source, cityPath destination)
{ int i;

	for (i=0; i <= NUMCITIES; i++)
		destination[i] = source[i];
}



bool inPath (City c, cityPath P)
{ bool found = FALSE;
  int i;

	for (i=0; i <= NUMCITIES; i++)
		if (P[i] == c)
			found = TRUE;

	return found;
}