/*
 * Student: S.K. Soekhlal
 * Number: 4860632
 * Assignment: 5.1 + 5.2
 */

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

#include "salloc.h"
#include "city.h"
#include "road.h"

#define MAX_STRING_LENGTH 50


/*
 * Locate city with name city_name on the map
 */
City *find_city (City *list_of_cities, char *city_name)
{
	City *c = list_of_cities;
	while (c != NULL)
	{
		if (strcmp (c->name, city_name) == 0)
			return c;

		c = c->next;
	}
	return NULL;
}


/*
 * Delete a map
 */
static void delete_map (City *map)
{
	City *map_copy;

	while (map != NULL)
	{
		map_copy = map;
		map = map->next;
		delete_city (map_copy);
	}
}


/*
 * Build the map datastructure
 */
static City *create_map (FILE *data_file)
{
	int num_of_cities, i;
    int length_of_road;
    char city_begin[MAX_STRING_LENGTH + 1];
    char city_end[MAX_STRING_LENGTH + 1];
    int num_of_roads;
    char city_name[MAX_STRING_LENGTH + 1];

	City *map = NULL;

	/* Read in city-names	*/
	fscanf (data_file, "%d", &num_of_cities);

	for (i = 0; i < num_of_cities; i++)
	{

		City *city;
		City *c;

		fscanf (data_file, "%s", city_name);

		if (find_city (map, city_name) != NULL)
		{
			fprintf (stderr, "City %s already on the map\n", city_name);
			delete_map (map);
			exit (EXIT_FAILURE);
		}

		city = new_city (safe_strdup (city_name));

		if (map == NULL)
			/* This is the first city of the map */
			map = city;
		else {
			/* Find last of city list */
			c = map;
			while (c->next) c = c->next;
			/* And append new city there */
			c -> next = city;
		}
	}



	fscanf (data_file, "%d", &num_of_roads);

	for (i = 0; i < num_of_roads; i++){

        City *city;
        Road *c;
        Road *road;
        Road *origin;
        Road *destination;


        fscanf(data_file,"%s %s %d", city_begin,city_end, &length_of_road);


        origin = (Road*)find_city(map,city_begin);
        destination =  (Road*)find_city(map,city_end);


        road = new_road((City*)origin, (City*)destination, (int)length_of_road);

        city = (City*)origin;
        if (city->roads == NULL){
			/* This is the first road of the city*/
			city->roads = road;
		}
		else {
			/* Find last of road list */
			c = city->roads;
			while (c->next) c = c->next;
			/* And append new road there */
			c -> next = road;
		}
	}

	return map;
}


static void print_city_roads (City *map)
{
	City *city;
	Road *road;

	for (city = map; city != NULL; city = city->next)
	{
		printf ("Roads from city %s:\n", city->name);

		for (road = city->roads; road != NULL; road=road->next) {
			printf ("   to city %s", road->destination->name);
			printf (" (length %d)\n", road->length);
		}
	}
	free(city);
	free(road);
}


static void find_shortest_roads (City *map)
{

	 char buf[MAX_STRING_LENGTH];
	 char *destination;
	 int length;
	 int smallest_length;
	 City *city;
	 Road *road;

    scanf("%s", buf);
    city = find_city(map,buf);
    road = city->roads;
    smallest_length = road->length;
    destination = road->destination->name;
	 while(strcmp(buf,"0") != 0){
        int a = 1;
        city = find_city(map,buf);
        if(road == NULL){
            printf("There is no road from city %s\n",buf);
        }else{
        for (road = city->roads; road != NULL; road=road->next) {
                if(a || road->length <= smallest_length){
                smallest_length = road->length;
                destination = road->destination->name;
                a=0;/*to set smallest length to some value*/
                }
		/*shortest road found*/
        }
		length = smallest_length;
        printf("Shortest road from city %s is to city %s: %d\n", buf, destination, length);
	 }
        scanf("%s", buf);
	 }
   	free(city);
	free(road);
}

int main (int argc, char *argv[])
{
	FILE *data_file = NULL;
	City *map = NULL;

	/* Check arguments		*/
	if (argc != 2)
	{
		fprintf (stderr, "Usage: %s <datafile>\n", argv[0]);
		exit (EXIT_FAILURE);
	}

	/* Open data-file		*/
	if ((data_file = fopen (argv[1], "r")) == NULL)
	{
		fprintf (stderr, "Error opening file <%s>\n", argv[1]);
		exit (EXIT_FAILURE);
	}

	/* Create map-data-structure	*/
	if ((map = create_map (data_file)) == NULL)
	{
		fprintf (stderr, "No map data found\n");
		exit (EXIT_FAILURE);
	}

	print_city_roads (map);

	find_shortest_roads (map);

	/* Outit			*/
	if (data_file != NULL)
		fclose (data_file);
	if (map != NULL)
		delete_map (map);

	return EXIT_SUCCESS;
}