/* File: cities.h
 * Desc: Routing functions
 * Anthony Towns
 * 15 August 1997
 */

#ifndef __cityroutes_h
#define __cityroutes_h

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

#include "bool.h"
#include "strlib.h"

/* a cityPath is an array of cities visited, and a count of the cities 
 * visitied 
 */
typedef struct _cityPath {
     City stop[ MAXCITIES ];
     int n_visited;
} cityPath;

/* doess the /city/ occurs somewhere along the /path/? */
bool isIn( cityPath path, City city );

/* how long is the /path/? (total distance) */
int path_distance( cityPath path, FlightRouteType routes );

/* return TRUE if cities /source/ and /destination/ are connected by some
 * path, FALSE otherwise.
 */
bool connected( City source, City destination, FlightRouteType routes );

/* return the shortest path connecting /source/ and /destination/ as a
 * stack of (from,to) cityPairs. If no such path exists, behaviour is
 * undefined.
 */
cityPath shortest_path( City source, City destination,
			FlightRouteType routes );

/* push all the steps from the last city on the /path/ to other cities
 * not on the path (as according to /routes/) onto the given stack of
 * cityPairs (treated as /steps/ from one city to another).
 */
void add_steps( cityPath path, stack *steps, FlightRouteType routes );

/* backtrack along path, until the most recent untaken_step can be
 * taken, and take it. This naturally requires that the from field of
 * the topmost step in the stack is in the path.
 */
void take_step( cityPath* path, stack* untaken_steps );

#endif /* __cityroutes_h */