/* ---------------------------------------------------------- #include ----- */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#ifndef FALSE
#define FALSE (1==0)
#endif

#ifndef TRUE
#define TRUE  (1==1)
#endif

/* ---------------------------------------------------------- non-UNIX ----- */

#ifndef unix
#define ultoa ULTOA
int strcasecmp( char *a, char *b) {
    while( toupper( *a ) == toupper( *b ) ) {
        if ( *a == 0 ) return 0;
	a++;
	b++;
    }

    return ( *a - *b );
}
#endif

/* ------------------------------------------------------- limitations ----- */

#define MAX_CITIES 100   /* Maximum number of cities */
#define MAX_ROUTES 500   /* Maximum number of routes */

#define MAX_NAMELEN 50   /* Maximum length of a city name */

#define N_FACTOR 2       /* The number of `interesting' factors 
			  * If this is changed, many of the 
			  * verbose responses will need rewriting
			  * as will some of the HELP descriptions.
			  */

#define MAX_QUERIES 100  /* The maximum number of queries */

/* ------------------------------------------------------ user options ----- */

int debug = FALSE;    /* Debugging information? */
int verbose = FALSE;  /* Make responses in plain English? */
int batch = FALSE;    /* In batch mode? */

/* ------------------------------------------------------------ cities ----- */

/* Which connected graph is each city in? 
 */

typedef unsigned int segment_t;
segment_t max_segment = 0; 

typedef struct city_s {
    char name[ MAX_NAMELEN ];    /* "Sydney", "A", "2", etc... */
    segment_t segment;
} city_t;

/* Each city is referenced by either its name or its index 
 * in this array, which is valid up to city[ n_city - 1 ]. 
 */

int n_city = 0;
city_t city[ MAX_CITIES ];    

/* Add a city to city[] 
 */

int add_city( char *city_name );

/* Get an index to city[] from its name. If the name doesn't 
 * exist, return n_city.
 */

int get_city( char *city_name );

/* Are *all* cities connected to some route, and is all the 
 * segment info up to date? city_valid *must* be set to FALSE 
 * whenever a route/city is added/deleted. When city_valid is
 * TRUE, max_segment is the number of seperate connected graphs
 * of cities. When city_valid is FALSE, validate_cities() 
 * should be called to clean up the cities, and update 
 * max_segment.
 */

int city_valid = FALSE;
int validate_cities(void);

/* ------------------------------------------------------------ routes ----- */

/* The datatype we use for the 100 and the 10 in 
 * "%ADD A B 100 10"
 * 
 * Note: changing this definition may require some changes
 * to calls to ultoa()/ultoeng().
 */

typedef unsigned long factor_t;

/* How we express a route...
 */

typedef struct route_s {
    int city_l;            /* 'left' city */
    int city_r;            /* 'right' city */
    factor_t factor[N_FACTOR]; 
        /* factor[0]: cost, measured in dollars 
         * factor[1]: distance, measured in hours
	 */
} route_t;

/* Do these routes link the same cities? 
 */

int alternate_route( route_t rt1, route_t rt2 );   

int connects( route_t rt, int city );   /* does rt connect city? */
int other( route_t rt, int city );      /* what's the other city? */

/* All routes are referenced by an index to this array, which is
 * valid up to rt[ n_rt - 1 ].
 */

int n_rt = 0;
route_t rt[ MAX_ROUTES ];  

/* Return the index of the given route in rt[]. If the route doesn't 
 * exist, return n_rt.
 */

int find_route( route_t check_rt );     

/* ----------------------------------------------------------- queries ----- */

/* For each sort of optimization, we assign weights to each 
 * interesting factor.
 */

typedef struct query_s {
    char letter; /* Used by the user to refer to this query */
    factor_t weight[ N_FACTOR ]; 				  
} query_t;

query_t query[ MAX_QUERIES ] = { 
  { 'M', { 1, 0 } }, 
  { 'T', { 0, 1 } }
};

int n_query = 2;

/* Get an index to query[] from its associated letter. If 
 * the letter isn't associated with an element, return 
 * n_query.
 */

int get_query( char letter );

/* Return the sum of the factors in rt, weighted by query.
 */

factor_t weighted_factor( route_t rt, query_t query );

/* ------------------------------------------------------ input/output ----- */

#define MAX_STRING (5000)   /* size for a really big string */
#define TAB_SIZE   (8)      /* distance between tab stops */
#define LINE_LEN   (75)     /* how long to go before wordwrapping */
#define INDENT     (4)      /* how far to indent wrapped lines */

/* Wordwrap string nicely, using the above three #defines
 */

char *paragraph( char *string );

/* Insert n spaces at the start of string, returns
 * string. 
 */

char *insert( char *string, size_t n );

/* Copy the first word in `from' to `to', return the next 
 * char in `from'.
 */

char *wordcpy( char *to, char *from );

/* Write string to output after paragraphing it. Doesn't
 * need extra buffer space in string.
 */

void display( FILE *output, char *string );

/* Display `prompt' on `ouput' and wait for input from `input'. 
 * Uses `batch', global variable.
 */

char *prompt( FILE *input, FILE *output, char *prompt, char *buffer, 
	     size_t bufsize );

/* -------------------------------------------------- command language ----- */

char *command_parse( char *command );  /* call one of... */

char *command_HELP( char *arg );       /* give help */
char *command_ADD( char *arg );        /* add a route */
char *command_DEL( char *arg );        /* delete a route */
char *command_CHANGE( char *arg );     /* change a route */
char *command_DEF( char *arg );        /* define a query style */
char *command_QUERIES( char *arg );    /* list query styles */
char *command_QUERY( char *arg );      /* make a query */
char *command_SUMMARY( char *arg );    /* summarize information */
char *command_VERBOSE( char *arg );    /* respond in English */ 
char *command_TERSE( char *arg );      /* respond briefly */
char *command_DEBUG( char *arg );      /* set debugging on */
char *command_QUIT( char *arg );       /* quit program */

/* Take the two city names off the start of `buffer',
 * call get_city() and dump the results into `pcity_l' 
 * and `pcity_r'. If success, (there were two names) 
 * return the next char in `buffer', else return NULL.
 */

char *strip_cities( char *buffer, int *pcity_l, int *pcity_r );

/* Take the factors from `buffer', dumping them into
 * `factor'. If success, return the next char in `buffer'
 * else return NULL.
 */

char *strip_factors( char *buffer, factor_t factor[] );

/* ------------------------------------------------- general functions ----- */

char *ultoa( char *buffer, unsigned long n );   /* ulong to asciiz */
char *ultoeng( char *buffer, unsigned long n ); /* ulong to phrase */

/* ----------------------------------------------------------- warning ----- */

/* --------------------------------------------------------------- *
 * Please make sure you have read all the comments above before    *
 * attempting any modifications to the following code! There are   *
 * lots of little things that *need* to be done which are not      *
 * mentioned below but *are* mentioned above!                      *
 *                                                                 *
 * It'd probably be a good idea to look through the man page's     *
 * TECHNICAL COMMENTS section once or twice before continuing too. *
 *                                                                 *
 * PROCEED WITH CAUTION                                            *
 * --------------------------------------------------------------- */

/* -------------------------------------------------------- add_city() ----- */

int add_city( char *city_name ) { 
    if ( n_city == MAX_CITIES ) {
        fprintf( stdout, 
		"Internal error (can't add more cities)\n" );
	exit(10);
    }

    /* Add the city, and return its index.
     */

    if ( debug ) 
	fprintf( stdout, "City added: city_name==%s, city==%d\n", 
	       city_name, n_city );

    strcpy( city[n_city].name, city_name );
    city[n_city].segment = ++max_segment;

    return n_city++;
}

/* -------------------------------------------------------- get_city() ----- */

int get_city( char *city_name ) {
    int c_city;

    /* Make sure we get the NULL terminator within the 
     * string memory... This *might* stuff up some of the
     * caller's memory. If it does, too bad. :)
     */

    if ( strlen( city_name ) > MAX_NAMELEN ) 
        city_name[ MAX_NAMELEN ] = '\0';

    /* Look through the city[] for a match...
     */

    for ( c_city = 0; c_city < n_city; c_city++ )  {
  	if ( strcasecmp( city[c_city].name, city_name ) == 0 ) 
	    return c_city;
    }

    return n_city;
}

/* ------------------------------------------------- validate_cities() ----- */

int validate_cities() {
    int hop[MAX_ROUTES];
    int c_hop;
    int c_city;
    int c_rt;

    segment_t c_segment;
    int del_city;

    /* Speaking strictly, the following few tests shouldn't be here...
     * But here _is_ as good a place as any, and they really ought to
     * be somewhere, so... For the sake of early warning, organized 
     * coding has been replaced by a comment.
     * 
     * "Puzzled, the reader asks what the hell is going on."
     *
     * The next section checks that the arrays haven't got too many
     * entries, and that their entries don't reference invalid entries
     * in other arrays.
     */

    if ( n_city > MAX_CITIES ) {
        fprintf( stdout, "Internal error (too many cities)\n" );
	exit(10);
    }

    if ( n_rt > MAX_ROUTES ) {
        fprintf( stdout, "Internal error (too many routes)\n" );
	exit(10);
    }

    if ( n_query > MAX_QUERIES ) {
        fprintf( stdout, "Internal error (too many queries)\n" );
	exit(10);
    }

    for ( c_rt = 0; c_rt < n_rt; c_rt++ ) {
        if ( rt[c_rt].city_l >= n_city 
	    || rt[c_rt].city_r >= n_city ) 
	{
	    fprintf( stdout, "Internal error (bad route info)\n" );
	    exit(10);
	}
    }

    /* Check that all cities have roads to/from them. If they don't
     * replace them by the last city, and update references to that
     * city.
     */
 
    c_city = 0;
    while ( c_city < n_city ) {
        city[c_city].segment = 0;

	del_city = TRUE;
	for ( c_rt = 0; c_rt < n_rt; c_rt++ ) {
	    if ( connects( rt[c_rt], c_city ) ) {
	        del_city = FALSE;
		break;
	    }
	}
	if ( !del_city ) {
	    c_city++;
	    continue;
	}

	/* Otherwise the city needs deleting */

	n_city--;

	if ( debug ) { 
	    fprintf( stdout, 
		    "Deleting city %d by replacing it with %d\n",
		    c_city, n_city );
	    fprintf( stdout, "n_city==%d\n", n_city );
	}

	if ( c_city != n_city ) {
	    strcpy( city[c_city].name, city[n_city].name );

	    for ( c_rt = 0; c_rt < n_rt; c_rt++ ) {
	        if ( rt[c_rt].city_l == n_city ) {
		    rt[c_rt].city_l = c_city;
		} else if ( rt[c_rt].city_r == n_city ) {
		    rt[c_rt].city_r = c_city;
		}
	    }
	}
    }

    /* This loop should behave as follows:
     *
     * Preconditions:
     * 
     *    . c_city             is where we are now
     *    . hop[ 0..c_hop-1 ]  is the path we've already taken
     *
     * Algorithm:
     *     i Mark which segment the current city is in
     * 
     *    ii If there are no (more) routes from here then
     *           If we can, go back
     *           Otherwise:
     *               If there are any unchecked cities
     *                    Begin next segment
     *                    Select the city
     *                    Break back to (i)
     *               Otherwise stop
     *      Otherwise find the next route
     *           If we've been there before go back to (ii)
     *           Otherwise follow the route and break to (i)
     */

    hop[ c_hop = 0 ] = 0;
    c_city = 0;

    c_segment = 1;
        
    for(;;) {
	while ( hop[c_hop] < n_rt ) {
	    city[c_city].segment = c_segment;
	    
	    if ( connects( rt[hop[c_hop]], c_city ) ) {
	        int next_city = other( rt[hop[c_hop]], c_city );
		    
		if ( city[next_city].segment == 0 ) {
		    c_city = next_city;
		    c_hop++;
		    hop[c_hop] = 0;
		   		    
		    if ( debug ) 
		        fprintf( stdout, 
				"--> hop[c_hop]==%d, c_hop==%d\n", 
				hop[c_hop], c_hop );
		
		    continue;
	        }
	    }
	    hop[c_hop]++;
	}

	if ( c_hop == 0 ) {
	    /* bottomed out - we're back home with nowhere to go! */
	    int alldone = TRUE;

	    for ( c_city = 0; c_city < n_city; c_city++ ) {
		if ( city[c_city].segment == 0 ) {
		    hop[0] = 0;
		    c_city = c_city;
		    alldone = FALSE;
		    c_segment++;
		    break;
		}
	    }
	    if ( alldone ) {
	        city_valid = TRUE;
	        return (max_segment = c_segment);
	    }
        } else {
	    c_hop--;
	    c_city = other( rt[hop[c_hop]], c_city );
	    
	    if ( debug ) 
	        fprintf( stdout, "<-- c_city==%d, c_hop==%d\n", 
			c_city, c_hop );

	    hop[c_hop]++; /* Try the next route */
	}
    }
}

/* ------------------------------------------------- alternate_route() ----- */

int alternate_route( route_t rt1, route_t rt2 ) {
    return 
      (( rt1.city_l == rt2.city_l && rt1.city_r == rt2.city_r ) ||
       ( rt1.city_l == rt2.city_r && rt1.city_r == rt2.city_l ) );
}

/* -------------------------------------------------------- connects() ----- */

int connects( route_t rt, int city ) {
    return ( rt.city_l == city || rt.city_r == city );
}

/* ----------------------------------------------------------- other() ----- */
 
int other( route_t rt, int city ) {
    if ( rt.city_l == city ) return rt.city_r;
    else if ( rt.city_r == city ) return rt.city_l;
    else exit(10); /* this is not a valid call of other() */
}

/* ------------------------------------------------------ find_route() ----- */

int find_route( route_t check_rt ) {
    int c_rt;
    int c_factor;

    for ( c_rt = 0; c_rt < n_rt; c_rt++ ) {
        if ( alternate_route( rt[c_rt], check_rt ) ) {
	    int diff = FALSE;	    

	    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
	        diff = ( rt[c_rt].factor[c_factor] 
			!= check_rt.factor[c_factor] );
		if ( diff ) break;
	    }
	    if ( !diff ) return c_rt;
	}
    }
    return n_rt;
}

/* ------------------------------------------------------- get_query() ----- */

int get_query( char letter ) {
    int c_query;

    letter = toupper(letter);
    for ( c_query = 0; c_query < n_query; c_query++ ) {
        if ( toupper(query[c_query].letter) == letter ) {
	    return c_query;
	}
    }
    
    return n_query;
}
    
/* ------------------------------------------------- weighted_factor() ----- */

factor_t weighted_factor( route_t rt, query_t query ) {
    factor_t result = 0;
    int c_factor;

    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
        result += rt.factor[c_factor] * query.weight[c_factor];
    }

    return result;
}    

/* ------------------------------------------------------- paragraph() ----- */

char *paragraph( char *string ) {
    char *pch;
    char *pch_remem;
    int remem;
    int c_pos;
    
    remem = FALSE;
    pch = string;
    c_pos = 1;

    while( *pch ) {
        if ( isspace(*pch) ) {
	    remem = TRUE;
	    pch_remem = pch;
 
	    switch( *pch ) {
	      case '\t':
	        c_pos += TAB_SIZE - ((c_pos - 1) % TAB_SIZE);
	      case '\n':
		remem = FALSE;
		c_pos = 1;
		remem = FALSE;
	      default:
		c_pos++;
	    }
	} else {
	    c_pos++;
	}      

	if ( c_pos >= LINE_LEN ) {
	    if ( remem ) {
	        *pch_remem = '\n';
		insert( pch_remem+1, INDENT );
		c_pos = ( pch - pch_remem) + INDENT + 1;
		pch += INDENT;
		remem = FALSE;
	    } else {
	       insert( pch, INDENT + 1 );
	       *pch = '\n';
	       c_pos = INDENT;
	       pch += INDENT + 1;
	       remem = FALSE;
	    }
	}
	pch++;
    }

    return string;
}

/* ---------------------------------------------------------- insert() ----- */

char *insert( char *string, size_t nch ) {
    size_t index;

    if ( nch == 0 ) return string;

    for ( index = strlen( string ); index > 0; index-- ) {
        string[index + nch] = string[index];
    }
    string[nch] = string[0];

    for ( index = 0; index < nch; index++ ) {
        string[index] = ' ';
    }

    return string;
}	

/* --------------------------------------------------------- wordcpy() ----- */

char *wordcpy( char *to, char *from ) {
    while( !isspace( *from ) && *from != '\0' ) {
        *(to++) = *(from++);
    }
    *to = '\0';
    return from;
}

/* --------------------------------------------------------- display() ----- */

void display( FILE *output, char *string ) {
    char buffer[MAX_STRING];
    strcpy( buffer, string );
    paragraph( buffer );
    fprintf( output, "%s", buffer );
}

/* ---------------------------------------------------------- prompt() ----- */

char *prompt( FILE *input, FILE *output, 
	     char *prompt, 
	     char *buffer, size_t bufsize )
{
    char *pbuf;

    if ( !batch ) {
        fprintf( output, "%s> ", prompt );
    }

    fgets( buffer, bufsize, input );


    pbuf = buffer + strlen(buffer) - 1;
    if ( *pbuf == '\n' ) *pbuf = '\0';

    if ( batch ) {
        fprintf( output, "%s> %s\n", prompt, buffer );
    } 
    
    return buffer;
}

/* --------------------------------------------------- command_parse() ----- */

char *command_parse( char *command ) {
    char name[40];
    char arg[200];

    command = wordcpy( name, command );
    while ( isspace( *command ) ) command++;

    strcpy( arg, command );

    if ( debug )
        fprintf( stdout, 
		"command_parse: name==\"%s\", arg==\"%s\"\n",
		name, arg );

    if ( strcasecmp( name, "HELP" ) == 0 ) {
        return command_HELP( arg );
    } else if ( strcasecmp( name, "ADD" ) == 0 ) {
        return command_ADD( arg );
    } else if ( strcasecmp( name, "DEL" ) == 0 ) {
        return command_DEL( arg );
    } else if ( strcasecmp( name, "CHANGE" ) == 0 ) {
        return command_CHANGE( arg );
    } else if ( strcasecmp( name, "DEF" ) == 0 ) {
        return command_DEF( arg );
    } else if ( strcasecmp( name, "QUERIES" ) == 0 ) {
        return command_QUERIES( arg );
    } else if ( strcasecmp( name, "QUERY" ) == 0 ) {
        return command_QUERY( arg );
    } else if ( strcasecmp( name, "SUMMARY" ) == 0 ) {
        return command_SUMMARY( arg );
    } else if ( strcasecmp( name, "VERBOSE" ) == 0 ) {
        return command_VERBOSE( arg );
    } else if ( strcasecmp( name, "TERSE" ) == 0 ) {
        return command_TERSE( arg );
    } else if ( strcasecmp( name, "DEBUG" ) == 0 ) {
        return command_DEBUG( arg );
    } else if ( strcasecmp( name, "QUIT" ) == 0 ) {
        return command_QUIT( arg );
    } else {
        return "Unknown command\n";
    }
}

/* ---------------------------------------------------- command_HELP() ----- */

char *command_HELP( char *arg ) { 
    if ( strcasecmp( arg, "HELP" ) == 0 ) {
        return "%HELP [command]\n\nHelp on [command]\n";
    } else if ( strcasecmp( arg, "ADD" ) == 0 ) {
        return "%ADD [from] [to] [cost] [time]\n\nAdd a route\n";
    } else if ( strcasecmp( arg, "DEL" ) == 0 ) {
        return "%DEL [from] [to] [cost] [time]\n\nDelete a route\n";
    } else if ( strcasecmp( arg, "CHANGE" ) == 0 ) {
        return "%CHANGE [from] [to] [old cost] [old time] "
	       "[new cost] [new time]\n\n"
	       "Modify a route\n";
    } else if ( strcasecmp( arg, "DEF" ) == 0 ) {
        return "%DEF [letter] [cost] [time]\n\n"
	       "Define a new query. The best route is "
	       "determined by the sum of the route's "
	       "cost multiplied by [cost] and the "
	       "route's time multiplied by [time].\n";
    } else if ( strcasecmp( arg, "QUERIES" ) == 0 ) {
        return "%QUERIES\n\n"
	       "List queries.\n";
    } else if ( strcasecmp( arg, "QUERY" ) == 0 ) {
        return "%QUERY [from] [to] [letter]\n\n" 
               "Determine the best path between [from] and "
	       "[to], based on the query specified by [letter].\n";
    } else if ( strcasecmp( arg, "SUMMARY" ) == 0 ) {
        return "%SUMMARY\n\nSummarise routing information.\n";
    } else if ( strcasecmp( arg, "VERBOSE" ) == 0 ) {
        return "%VERBOSE\n\nRespond in English where possible.\n";
    } else if ( strcasecmp( arg, "TERSE" ) == 0 ) {
        return "%TERSE\n\nRespond as tersely as possible.\n";
    } else if ( strcasecmp( arg, "DEBUG" ) == 0 ) {
        return "%DEBUG\n\nToggle debugging information.\n";
    } else if ( strcasecmp( arg, "QUIT" ) == 0 ) {
        return "%QUIT\n\nQuit the program.\n";
    } else {
        return "Known commands -- HELP, ADD, DEL, CHANGE, QUERY, "
	       "DEF, QUERIES, SUMMARY, VERBOSE, TERSE, DEBUG, "
	       "QUIT\n";
    }
}

/* ----------------------------------------------------- command_ADD() ----- */

char *command_ADD( char *arg ) {
    int valid_arg = TRUE;
    int c_factor;
    int c_rt;
    char *city_name;

    if ( n_rt == MAX_ROUTES ) {
        return "ADD -- Internal error (can't add more routes)\n";
    }

    while ( isspace( *arg ) ) arg++;
    arg = wordcpy( city_name, arg );
    rt[n_rt].city_l = get_city( city_name );
    if ( rt[n_rt].city_l == n_city ) {
        rt[n_rt].city_l = add_city( city_name );
    } 

    while ( isspace( *arg ) ) arg++;
    arg = wordcpy( city_name, arg );
    rt[n_rt].city_r = get_city( city_name );
    if ( rt[n_rt].city_r == n_city ) {
        rt[n_rt].city_r = add_city( city_name );
    }

    if ( arg != NULL ) {
        arg = strip_factors( arg, rt[n_rt].factor );
	if ( arg == NULL ) {
	    valid_arg = FALSE;
	} else {
	    while ( isspace( *arg ) ) arg++;
	    if ( *arg != '\0' ) valid_arg = FALSE;
	}
    } else {
        valid_arg = FALSE;
    }

    if ( !valid_arg ) {
        return "ADD -- Bad arguments.\n";
    }

    if ( find_route( rt[n_rt] ) < n_rt ) {
        return "ADD -- Route already entered.\n";
    } else {
	city_valid = FALSE;
        n_rt++;
	return "";
    }
}

/* ----------------------------------------------------- command_DEL() ----- */

char *command_DEL( char *arg ) {
    int c_rt;
    route_t del_rt;
    int valid_arg = TRUE;
    
    arg = strip_cities( arg, &del_rt.city_l, &del_rt.city_r );

    if ( arg != NULL ) {
        arg = strip_factors( arg, del_rt.factor );
	if ( arg == NULL ) {
	    valid_arg = FALSE;
	} else {
	    while ( *arg != '\0' && isspace( *arg ) ) arg++;
	    if ( *arg != '\0' ) valid_arg = FALSE;
	}
    } else {
        valid_arg = FALSE;
    }

    if ( !valid_arg ) {
        return "DEL -- Bad arguments.\n";
    }

    if ( del_rt.city_l < n_city && del_rt.city_r < n_city ) {
        c_rt = find_route( del_rt );
	if ( c_rt < n_rt ) {
            int c_factor;
	    
	    city_valid = FALSE;
	    n_rt--;
	    
	    rt[c_rt].city_l = rt[n_rt].city_l;
	    rt[c_rt].city_r = rt[n_rt].city_r;
	    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
	        rt[c_rt].factor[c_factor] = rt[n_rt].factor[c_factor];
	    }
	    
	    return "";	
	}
    } 

    return "DEL -- Route not found.\n";
}

/* -------------------------------------------------- command_CHANGE() ----- */

char *command_CHANGE( char *arg ) {
    int c_rt;
    route_t del_rt;
    route_t new_rt;
    int valid_arg = TRUE;
    
    arg = strip_cities( arg, &del_rt.city_l, &del_rt.city_r );

    if ( arg != NULL ) {
        arg = strip_factors( arg, del_rt.factor );
	if ( arg == NULL ) {
	    valid_arg = FALSE;
	} else {
	    arg = strip_factors( arg, new_rt.factor );
	    if ( arg == NULL ) {
	        valid_arg = FALSE;
	    } else {
	        while ( *arg != '\0' && isspace( *arg ) ) arg++;
		if ( *arg != '\0' ) valid_arg = FALSE;
	    }
	}
    } else {
        valid_arg = FALSE;
    }

    if ( !valid_arg ) {
        return "CHANGE -- Bad arguments.\n";
    }

    if ( del_rt.city_l < n_city && del_rt.city_r < n_city ) {
        c_rt = find_route( del_rt );
	if ( c_rt < n_rt ) {
            int c_factor;

	    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
	        rt[c_rt].factor[c_factor] = new_rt.factor[c_factor];
	    }
	    return "";	
        }  
    }

    return "CHANGE -- Route not found.\n";
}

/* ----------------------------------------------------- command_DEF() ----- */

char *command_DEF( char *arg ) {
    int valid_arg = TRUE;
    factor_t lcm;
    int c_factor;
    int c_query;

    if ( n_query == MAX_QUERIES ) {
        return "DEF -- Internal error (can't add more queries)\n";
    }

    while( isspace( *arg ) ) arg++;

    query[n_query].letter = *(arg++);

    if ( !isspace( *arg ) ) {
        valid_arg = FALSE;
    } else {
        arg = strip_factors( arg, query[n_query].weight );
	if ( arg == NULL ) {
	    valid_arg = FALSE;
	} else {
	    valid_arg = FALSE; /* We need to check that at
				* least one weight[] is nonzero.
				*/

	    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
	        if ( query[n_query].weight[c_factor] != 0 ) {
		    valid_arg = TRUE;
		    break;
		}
	    }   
	}
    }

    if ( valid_arg ) {
        for ( c_query = 0; c_query < n_query; c_query++ ) {
	    if ( query[c_query].letter == query[n_query].letter ) {
	        for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) 
		{
		    query[c_query].weight[c_factor] = 
		      query[n_query].weight[c_factor];
		}
		return "";
	    }
	}

        n_query++;
	return "";
    } else {
        return "DEF -- Bad arguments.\n";
    }
}

/* ------------------------------------------------- command_QUERIES() ----- */

char *command_QUERIES( char *arg ) {
    static char buffer[MAX_STRING];
    char *pbuf;
    int c_query;
    int c_factor;

    pbuf = buffer;
    for ( c_query = 0; c_query < n_query; c_query++ ) {
        if ( verbose ) {
	    sprintf( pbuf, 
		    "Query %c has cost weighted at %lu, "
		    "and time weighted at %lu.\n",
		    query[c_query].letter,
		    query[c_query].weight[0],
		    query[c_query].weight[1] );
	    pbuf += strlen(pbuf);
	} else {
  	    sprintf( pbuf, "%c ", 
		    query[c_query].letter );
	    pbuf += 2;

	    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
	        ultoa( pbuf, query[c_query].weight[c_factor] );
		pbuf += strlen( pbuf );
		*(pbuf++) = ' ';
		*pbuf = '\0';
	    }
	    *(pbuf-1) = '\n';
	}
    }

    return buffer;
}

/* --------------------------------------------------- command_QUERY() ----- */

char *command_QUERY( char *arg ) {
    int valid_arg = TRUE;

    static char buffer[500];

    int city_from;
    int city_to;
    int c_query;

    int hop[MAX_ROUTES];
    int c_hop;
    int c_city;
    int next_city;
    factor_t next_sumfactor;

    int check_hop;
    int check_city;

    int best_hop[MAX_ROUTES];
    int best_n_hop;
    factor_t best_sumfactor = 0;

    /* First we check the segment information 
     */

    if ( !city_valid ) validate_cities(); 

    /* Then we interpret our arguments, knowing the any
     * indices to city[] won't change
     */

    arg = strip_cities( arg, &city_from, &city_to );
    if ( arg == NULL || city_from == city_to ) {
        valid_arg = FALSE;
    } else {
        while ( isspace(*arg) ) arg++;
        c_query = get_query( *(arg++) );
	if ( c_query == n_query ) {
	    valid_arg = FALSE;  
	} else {
	    while( isspace(*(arg)) ) arg++;
	    if ( *arg != '\0' ) valid_arg = FALSE;
	}
    }

    if ( !valid_arg || city_from == n_city || city_to == n_city ) 
        return "QUERY -- Bad arguments!\n";  

    if ( city[city_from].segment != city[city_to].segment ) {
        sprintf( buffer, 
		(verbose 
		 ? "You can't get from %s to %s.\n" 
		 : "%s -/-> %s\n"),
		city[city_from].name, city[city_to].name );
	return buffer;
    }

    /* The main loop should behave as follows: 
     * 
     * Preconditions:
     *    . We're not there yet
     *    
     *    . city_from          where we started
     *    . c_hop              >= 0
     *    . hop[ 0..c_hop-1 ]  the routes we followed
     *    . hop[ c_hop ]       has not been checked
     *    . c_city             our current locale
     *
     *    . next_city          our locale after following 
     *                         hop[c_hop] from c_city.
     *    . next_sumfactor     Sum of weighted scores after
     *                         the next hop.
     *
     *    . best_*             Are as expected based on the
     *                         above definitions.
     * 
     * Algorithm:
     *     If there aren't any (more) routes from here
     *         If we can, go back
     *         Otherwise, stop
     * 
     *     Otherwise, find the next route, and...
     *         If it leads to the end, note it
     *         If it makes a loop, ignore it
     *         If we've been to that city already, ignore it
     *         Otherwise, go down it
     *
     * Errata:
     *     c_city is used so the entire hops tree does not have to 
     *     be followed to work out where we are. It *must* remain  
     *     correct!
     * 
     *     next_sumfactor denotes how far it is, how long it will
     *     take etc, to get fro city_from to c_city.
     *
     *     It might be sensible to have a pointer to inc/decrement 
     *     instead of hop[c_hop] (ie `phop' = &hop[c_hop]).
     */

    hop[ c_hop = 0 ] = 0;
    c_city = city_from;
    next_sumfactor = 0;

    for(;;) {
        while ( hop[c_hop] < n_rt ) {
            if ( connects( rt[hop[c_hop]], c_city ) ) {
	        next_city = other( rt[hop[c_hop]], c_city );
		
		next_sumfactor += 
		  weighted_factor( rt[hop[c_hop]], query[c_query] ); 
		
		if ( debug ) { 
		    fprintf( stdout, 
			    "c_city==%d, next_city==%d, c_hop==%d, "
			    "hop[c_hop]==%d, city_from==%d, "
			    "city_to==%d\n",
			    c_city, next_city, c_hop, hop[c_hop],
			    city_from, city_to );
		}

	        if ( next_city == city_to ) {
		    /* WOW! We're where we want to be! */

		    if ( debug ) 
		        fprintf( stdout, 
				"  We're there! next_sumfactor==%lu",
				next_sumfactor );

		    if ( next_sumfactor < best_sumfactor 
			|| best_sumfactor == 0 ) 
		    {
		        if ( debug ) 
			    fprintf( stdout, "...best so far!");

			memcpy( best_hop, hop, sizeof(hop) );
			best_sumfactor = next_sumfactor;
			best_n_hop = c_hop + 1;
		    }
		    if ( debug ) fprintf( stdout, "\n" );
		} else if ( best_sumfactor > 0 
			   && next_sumfactor >= best_sumfactor ) {
		    /* nothing */
		    if ( debug ) 
		        fprintf( stdout, "  This isn't worth it\n" );
		} else if ( c_hop >= n_city ) {
		    /* nothing */
		    if ( debug ) 
		        fprintf( stdout, "  Nesting too deep!\n" );
		} else {
		    int follow = TRUE;
		    check_city = city_from;
		    for ( check_hop = 0; check_hop < c_hop; 
			 check_hop++ ) 
		    {
		        if ( check_city == c_city ) {
			    follow = FALSE;
			    if ( debug )
			        fprintf( stdout, 
					"  Been here before!\n" );
			    break;
			}
			check_city = 
			  other( rt[hop[check_hop]], check_city );
		    }			

		    if ( follow ) {
		        c_city = next_city;
			c_hop++;
			hop[c_hop] = 0;
			if ( debug ) 
			    fprintf( stdout, 
				    "  Let's see where this leads..."
				    " (c_hop==%d, "
				    "next_sumfactor==%lu)\n", 
				    c_city, c_hop, next_sumfactor );
			continue;
		    }
		}
	    
		next_sumfactor -= 
		  weighted_factor( rt[hop[c_hop]], query[c_query] );
	    }
	    hop[c_hop]++;
	}

	if ( c_hop == 0 ) {
	    /* bottomed out - we're back home with nowhere to go! */

	    if ( best_sumfactor == 0 ) {
		return "QUERY -- Internal error (bad segment info)\n";
	    } else {
		unsigned long tot_factor[N_FACTOR];
		int c_factor;
		int *phop;
		char *pbuf = buffer;

		buffer[0] = '\0';

		for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) 
		{
		    tot_factor[c_factor] = 0;
		    for ( phop = best_hop; 
			 phop < best_hop + best_n_hop; 
			 phop++ ) 
		    {
		        tot_factor[c_factor] += 
			  rt[*phop].factor[c_factor];
		    }
		}
		if ( verbose ) {
		    char buffer2[20];

		    sprintf( buffer, 
			    "To get from %s to %s, travel ",
			    city[city_from].name, 
			    city[city_to].name );
		    if ( best_n_hop == 1 ) {
		        strcat( buffer, "directly " );
		    } else {
		        strcat( buffer, "via " );
			c_city = other( rt[best_hop[0]], city_from );
			for ( c_hop = 1; ; c_hop++ ) {
			    strcat( buffer, city[c_city].name );

			    /* EXIT POINT!!! */
			    if ( c_hop == best_n_hop - 1 ) {
			        strcat( buffer, " " );
				break;
			    } else if ( c_hop == best_n_hop - 2 ) {
			        strcat( buffer, " then " );
			    } else {
			        strcat( buffer, ", " );
			    }
			    c_city = 
			      other( rt[best_hop[c_hop]], c_city );
			}
		    }
		    sprintf( buffer+strlen(buffer), 
			    "at a total cost of $%lu, "
			    "taking %s hours.\n",
			    tot_factor[0], 
			    ultoeng( buffer2, tot_factor[1] ) );
		} else {
		    c_city = city_from;
		    for ( phop = best_hop; ; phop++ ) {
		        strcat(buffer, city[c_city].name);
			strcat(buffer, " ");

			/* NB: EXIT POINT!! */
			if ( !( phop < best_hop + best_n_hop ) ) 
			    break;
		    
			c_city = other( rt[*phop], c_city );
		    }

		    pbuf = buffer + strlen(buffer);
		    for ( c_factor = 0; c_factor < N_FACTOR; 
			 c_factor++ ) 
		    {
		        ultoa( pbuf, tot_factor[c_factor] );
			pbuf = buffer + strlen(buffer);
			*(pbuf++) = ' ';
		    }
		    *(pbuf - 1) = '\n'; /* space -> newline */
		    *pbuf = '\0';
		}
		return buffer;
	    }
	} else { 
	    /* Okay, okay, so this ISN'T where we're meant to be. 
	     * Maybe the map's upside down? Let's just try going
	     * backwards...
	     */

	    c_hop--;
	    c_city = other( rt[hop[c_hop]], c_city );
	    next_sumfactor -= 
	      weighted_factor( rt[hop[c_hop]], query[c_query] );

	    if ( debug ) 
	        fprintf( stdout, 
			"<-- c_city==%d, c_hop==%d, "
			"next_sumfactor==%d\n", 
			c_city, c_hop, next_sumfactor );
	
	    hop[c_hop]++; /* Try the next route */
	}
    }			
}

/* ------------------------------------------------- command_SUMMARY() ----- */

char *command_SUMMARY( char *arg ) {
    static char buffer[MAX_STRING];
    char buffer2[20];
    int c_city;
    int c_rt;
    segment_t c_segment;
    int count;

    if ( !city_valid ) validate_cities();
    
    if ( n_city == 0 ) {
        if ( verbose ) {
	    strcpy( buffer, "There aren't any cities!\n" );
	} else {
	    strcpy( buffer, "No cities\n" );
	}
    } else if ( max_segment == 1 ) {
        if ( verbose ) {
	    strcpy( buffer, "All cities are interconnected.\n" );
	} else {
	    strcpy( buffer, "1 connected graph\n" );
	}
    } else {
        if ( verbose ) {
	    sprintf( buffer, 
		    "These %s groups of interconnected cities "
		    "are mutually inaccessible:\n", 
		    ultoeng(buffer2, max_segment) );
	} else { 
	    sprintf( buffer,
            "%u connected graphs:\n",
		    max_segment );
	}

        for ( c_segment = 1; c_segment <= max_segment; c_segment++ ) {
	    strcat( buffer, "\t" );

	    count = 0;
	    for ( c_city = 0; c_city < n_city; c_city++ ) {
	        if ( city[c_city].segment == c_segment ) {
		    count++;
		}
	    }

	    for ( c_city = 0; c_city < n_city; c_city++ ) {
	        if ( city[c_city].segment == c_segment ) {
		    strcat( buffer, city[c_city].name );     
		    count--;
		    switch ( count ) {
		      case 0:
		        strcat( buffer, "\n" );
			break;
		      case 1:
			strcat( buffer, " and " );
			break;
		      default:
			strcat( buffer, ", " );
			break;
		    }
		}
	    }
	}
    }

    strcat( buffer, "\n" );

    for ( c_segment = 1; c_segment <= max_segment; c_segment++ ) {
        for ( c_rt = 0; c_rt < n_rt; c_rt++ ) {
	    if ( city[rt[c_rt].city_l].segment == c_segment ) {
	        int check_rt;
		for ( check_rt = 0; check_rt < c_rt; check_rt++ ) {
		    if ( alternate_route( rt[c_rt], rt[check_rt] ) )
		        break;
		}
		if ( check_rt != c_rt ) continue;
		    
		count = 1;
		for ( check_rt = c_rt + 1; check_rt < n_rt; 
		     check_rt++ ) 
		{
		    if ( alternate_route( rt[c_rt], rt[check_rt] ) ) 
		        count++;
	        }

		if ( verbose ) {
		    sprintf( buffer + strlen(buffer), 
			    "To travel between %s and %s,",
			    city[rt[c_rt].city_l].name, 
			    city[rt[c_rt].city_r].name );
		} else { 
		    sprintf( buffer + strlen(buffer),
			    "%s / %s\n",
			    city[rt[c_rt].city_l].name,
			    city[rt[c_rt].city_r].name );

		    /* if we can fit the first factors on this line
		     * and keep it all aligned, do it.
		     */

		    if ( (strlen(city[rt[c_rt].city_l].name)
			  + strlen(city[rt[c_rt].city_r].name) 
			  + 3)
			< TAB_SIZE ) 
		    {
		        buffer[strlen(buffer)-1] = '\0';
		    }
		}
		for ( check_rt = c_rt; check_rt < n_rt; check_rt++ ) 
		{
  		    if ( alternate_route( rt[c_rt], rt[check_rt] ) ) 
		    {
		        if ( verbose) {
			    sprintf( buffer + strlen(buffer), 
				    " it costs $%lu and " 
				    "takes %s hours",
				    rt[check_rt].factor[0], 
				    ultoeng( buffer2, 
					   rt[check_rt].factor[1] ) 
				    );
			    count--;
			    switch(count) {
			      case 0:
			        strcat( buffer, ".\n" );
				break;
			      case 1:
				strcat( buffer, ", or" );
				break;
			      default:
				strcat( buffer, "," );
				break;
			    }
			} else { /* !verbose */
			    sprintf( buffer + strlen(buffer),
                    "\t%4lu %4lu\n",
				    rt[check_rt].factor[0],
				    rt[check_rt].factor[1] );
			} 
		    }
		}
	    }
	}
	strcat( buffer, "\n" );
    }
    
    return buffer;
}

/* ------------------------------------------------- command_VERBOSE() ----- */

char *command_VERBOSE( char *arg ) {
    verbose = TRUE;
    return "Verbose responses selected.\n";
}

/* --------------------------------------------------- command_TERSE() ----- */

char *command_TERSE( char *arg ) {
    verbose = FALSE;
    return "Terse responses selected.\n";
}

/* --------------------------------------------------- command_DEBUG() ----- */
char *command_DEBUG( char *arg ) { 
    debug = !debug;

    if ( debug ) 
        return "Debugging mode selected.\n";
    else 
	return "Debugging mode aborted.\n";

}
/* ---------------------------------------------------- command_QUIT() ----- */

char *command_QUIT( char *arg ) {
    exit(0); 
}

/* ---------------------------------------------------- strip_cities() ----- */

char *strip_cities( char *buffer, int *pcity_l, int *pcity_r ) {
    char cityname_l[80];
    char cityname_r[80];

    while ( isspace( *buffer ) ) buffer++;
    if ( *buffer == '\0' ) return NULL;

    buffer = wordcpy( cityname_l, buffer );
    
    while ( isspace( *buffer ) ) buffer++;
    if ( *buffer == '\0' ) return NULL;

    buffer = wordcpy( cityname_r, buffer );

    *pcity_l = get_city( cityname_l );
    *pcity_r = get_city( cityname_r );
 
    return buffer;
}

/* --------------------------------------------------- strip_factors() ----- */

char *strip_factors( char *buffer, factor_t factor[] ) {
    int c_factor;

    for ( c_factor = 0; c_factor < N_FACTOR; c_factor++ ) {
        if ( !isspace( *buffer ) ) {
	    return NULL;
	}
	while( isspace( *buffer ) ) buffer++;

	factor[c_factor] = atol( buffer );
	while( isdigit( *buffer ) ) buffer++;
    }

    if ( isspace( *buffer ) || *buffer == '\0' ) return buffer;
    else                                         return NULL;
}

/* ----------------------------------------------------------- ultoa() ----- */

char *ultoa( char *buffer, unsigned long n ) {
    if ( n > 0 ) {
        char reverse[20];
	char *pb = &reverse[19];
    
	*(pb--) = '\0';

	while( n > 0 ) {
	    *(pb--) = ((char) (n % 10)) + '0';
        n /= 10;
	}
	strcpy(buffer, pb+1);
    } else {
        buffer[0] = '0';
	buffer[1] = '\0';
    }
    return buffer;
}

/* --------------------------------------------------------- ultoeng() ----- */

char *ultoeng(char *buffer, unsigned long n ) {
    char *digit[] = { "one", "two", "three", "four", "five",
			"six","seven","eight","nine" };
  
    char *teen[] = { "ten", "eleven", "twelve", "thirteen", "fourteen",
		       "fifteen", "sixteen", "seventeen", "eighteen", 
		       "ninteen" };
  
    char *ten[] = { "twenty", "thirty", "forty", "fifty", 
		      "sixty", "seventy","eighty","ninety" };
    
    if ( n >= 100 ) {
        return ultoa( buffer, n );
    } else if ( n == 0 ) {
        return strcpy( buffer, "zero" );
    } else if ( n < 10 ) {
        return strcpy( buffer, digit[n-1] );
    } else if ( n < 20 ) {
        return strcpy( buffer, teen[n-10] );
    } else if ( n % 10 == 0 ) {
        return strcpy( buffer, ten[n/10-2] );
    } else {
        sprintf( buffer, "%s-%s", ten[n/10-2], digit[n%10-1] );
	return buffer;
    }
}

/* ------------------------------------------------------------ main() ----- */

int main(int argc, char *argv[]) {
    char buffer[80];
    int c_arg;

    for ( c_arg = 1; c_arg < argc; c_arg++ ) {
        if ( strcmp( argv[c_arg], "--batch" ) == 0 ) {
	    batch = TRUE;
	} else if ( strcmp( argv[c_arg], "--verbose" ) == 0 ) {
	    verbose = TRUE;
	} else if ( strcmp( argv[c_arg], "--terse" ) == 0 ) {
	    verbose = FALSE;
	} else if ( strcmp( argv[c_arg], "--debug" ) == 0 ) {
	    debug = TRUE;
	} else if ( strcmp( argv[c_arg], "--help" ) == 0 ) {
	    fprintf( stdout,
		    "Valid options:\n\n"
		    "--help    \tList arguments\n"
		    "--verbose \tStart in VERBOSE mode\n"
		    "--terse   \tStart in TERSE mode\n"
		    "--debug   \tDisplay debugging information\n"
		    "--batch   \tNon-interactive "
		                "(affects prompting)\n\n" );
	    return 0;
	} else {
	    fprintf( stdout, 
		    "transopt -- Unknown option.\n"
		    "Try --help.\n" );
	    return 1;
	}
    }
    
    for(;;) {
        if ( feof(stdin) ) command_QUIT("");

        prompt( stdin, stdout, "Add", buffer, 80 ); 

	if ( buffer[0] == '%' ) { 
	    display( stdout, command_parse( buffer + 1 ) );
	} else if ( buffer[0] != '\0' ) {
	    int city_l, city_r;
	    if ( !strip_cities( buffer, &city_l, &city_r ) ) {
	        display( stdout, "Use %HELP for help\n" );
	        continue;	    
	    }
	    if ( city_l != n_city && city_l == city_r ) break;
	    display( stdout, command_ADD( buffer ) );
	}
    }

    display( stdout, command_SUMMARY("") );

    for(;;) {
        if ( feof(stdin) ) command_QUIT("");

        prompt( stdin, stdout, "Query", buffer, 80 );

	if ( buffer[0] == '%' ) { 
	    display( stdout, command_parse( buffer + 1 ) );
	} else if ( buffer[0] != '\0' ) {
	    int city_l, city_r;
	    if ( !strip_cities( buffer, &city_l, &city_r ) ) {
	        display( stdout, "Use %HELP for help\n" );
	        continue;
	    }
	    if ( city_l != n_city && city_l == city_r ) break;
	    display( stdout, command_QUERY( buffer ) );
	}
    }

    display( stdout, command_QUIT("") );

    return 0;
}