/*
 * Copyright (c) 2005 Peter Postma <peter@pointless.nl>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * Description:
 *   This program calculates the shortest path between two points in a graph.
 *   It uses Dijkstra's algorithm to accomplish this. The points and links
 *   between the points (ways) are both defined in a structure and can be
 *   extended very easily. This program has been used as submission for
 *   Pascals programming assignment #5.
 *
 * Usage:
 *   Compile with a C89 compliant C compiler and make sure to link to the
 *   math library: $ cc -o dijkstra dijkstra.c -lm
 *
 *   The program wants two arguments, point1 and point2 which are both
 *   single characters between A and F, e.g.: $ ./dijkstra e b
 */

#include <sys/types.h>

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

#define arraycount(x)	(sizeof(x) / sizeof(x[0]))

/* Define the points. */
static struct point {
	char p;
	int x, y;
} points[] = {
	{ 'A', 1, 0 },
	{ 'B', 4, 0 },
	{ 'C', 1, 2 },
	{ 'D', 2, 2 },
	{ 'E', 0, 3 },
	{ 'F', 4, 3 }
};

/* Define the ways. */
static struct way {
	char p1, p2;
} ways[] = {
	{ 'A', 'C' },
	{ 'A', 'E' },
	{ 'B', 'D' },
	{ 'C', 'D' },
	{ 'D', 'F' },
	{ 'F', 'E' }
};

/* Structure for the vertex. */
struct vertex {
	struct point *p;	/* reference to points */
	struct way *edges;	/* array with ways for the point */
	size_t nedges;		/* number of ways */
	double distance;	/* total distance */
	size_t predecessor;	/* vertex predecessor */
	int done;		/* completion indicator */
};

/*
 * get_point --
 *	Find the point p. Returns a pointer to struct point when found,
 *	or NULL when not found.
 */
static struct point *
get_point(char p)
{
	size_t i;

	for (i = 0; i < arraycount(points); i++)
		if (points[i].p == p)
			return &points[i];
	return NULL;
}

/*
 * get_index --
 *	Returns the array index of the next point in struct way.
 */
static size_t
get_index(struct way *w, char current)
{
	return ((current == w->p2) ? w->p1 : w->p2) - 'A';
}

/*
 * calc_weight --
 *	Calculates the weight for a way (distance between the points).
 */
static double
calc_weight(struct way *w)
{
	struct point *p1, *p2;

	p1 = get_point(w->p1);
	p2 = get_point(w->p2);

	if (p1 == NULL || p2 == NULL)
		return 0.0;

	return sqrt(pow(p1->x - p2->x, 2) + pow(p1->y - p2->y, 2));
}

/*
 * calc_shortest_path --
 *	Calculate the shortest path in graph g, from p1 to p2 using
 *	Dijkstra's algorithm. Returns the distance of shortest path as
 *	double. If the route is invalid, the function will return INT_MAX.
 *	The graph g will be modified during operation and will be filled
 *	with the distance and predecessor(s) for each vertex.
 */
static double
calc_shortest_path(struct vertex *g, size_t count, char p1, char p2)
{
	size_t i, j, cur, index, start = 0;
	double weight, min, shortest;

	for (i = 0; i < count; i++) {
		if (g[i].p->p == p1) {
			start = i;
			g[i].distance = 0;
		} else
			g[i].distance = INT_MAX;
		g[i].done = 0;
		g[i].predecessor = UINT_MAX;
	}

	cur = start;

	while (!g[cur].done && g[cur].p->p != p2) {
		min = INT_MAX;

		for (j = 0; j < g[cur].nedges; j++) {
			index = get_index(&g[cur].edges[j], g[cur].p->p);
			weight = calc_weight(&g[cur].edges[j]);

			if (g[index].distance > g[cur].distance + weight) {
				g[index].distance = g[cur].distance + weight;
				g[index].predecessor = cur;
			}
		}
		g[cur].done = 1;

		cur = start;
		min = INT_MAX;

		for (j = 0; j < count; j++) {
			if (!g[j].done && min >= g[j].distance) {
				min = g[j].distance;
				cur = j;
			}
		}
	}

	shortest = INT_MAX;
	for (i = 0; i < count; i++) {
		if (p2 == g[i].p->p) {
			shortest = g[i].distance;
			break;
		}
	}

	return shortest;
}

/*
 * main --
 *	Main entry point.
 */
int
main(int argc, char *argv[])
{
	size_t size, start, cur, num, i, j;
	struct vertex *g;	/* array of vertices: graph */
	double shortest;
	char p1, p2;
	char *route;

	if (argc != 3) {
		fprintf(stderr, "Usage: %s point1 point2\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	if (strlen(argv[1]) != 1 || strlen(argv[2]) != 1) {
		fprintf(stderr,
		    "Point1 and point2 should be a single character.\n");
		exit(EXIT_FAILURE);
	}

	p1 = toupper((unsigned char)*argv[1]);
	p2 = toupper((unsigned char)*argv[2]);

	/* Validate the points. */
	if (get_point(p1) == NULL || get_point(p2) == NULL) {
		fprintf(stderr, "Invalid point(s), must be between A and F.\n");
		exit(EXIT_FAILURE);
	}

	/* Bogus, point1 and point2 are the same. */
	if (p1 == p2) {
		fprintf(stderr,
		    "Points are the same, no route to calculate.\n");
		exit(EXIT_FAILURE);
	}

	size = arraycount(points);
	g = malloc(size * sizeof(struct vertex));
	if (g == NULL) {
		fprintf(stderr, "Failed to allocate memory.\n");
		exit(EXIT_FAILURE);
	}

	/*
	 * Fill the graph g with all points. For each vertex, calculate all
	 * ways and add these to the edges array.
	 */
	for (i = 0; i < size; i++) {
		g[i].p = &points[i];
		for (num = 0, j = 0; j < arraycount(ways); j++) {
			if (g[i].p->p == ways[j].p1 ||
			    g[i].p->p == ways[j].p2)
				num++;
		}
		if (num > 0) {
			/* Allocate an array of pointers. */
			g[i].edges = malloc(num * sizeof(struct way *));
			if (g[i].edges == NULL) {
				fprintf(stderr, "Failed to allocate memory.\n");
				exit(EXIT_FAILURE);
			}
			for (cur = 0, j = 0; j < arraycount(ways); j++) {
				if (g[i].p->p == ways[j].p1 ||
				    g[i].p->p == ways[j].p2)
					g[i].edges[cur++] = ways[j];
			}
		}
		g[i].nedges = num;
	}

	/* Calculate the shortest path. */
	shortest = calc_shortest_path(g, size, p1, p2);

	if (shortest == INT_MAX) {
		printf("Invalid route from %c to %c\n", p1, p2);
	} else {
		printf("The shortest route from %c to %c is %.1f\n",
		    p1, p2, shortest);

		/*
		 * Show the route from p1 to p2. We can only read the route
		 * in the graph backwards, so we will need to store it in a
		 * temporary buffer to be able to read the route in forward
		 * direction.
		 */

		/* Start at the last point. */
		start = UINT_MAX;
		for (i = 0; i < size; i++) {
			if (g[i].p->p == p2) {
				start = i;
				break;
			}
		}
		if (start == UINT_MAX) {
			/* Should never happen. */
			printf("Unable to find the route.");

		} else {
			/* First count all points in the path. */
			num = 0;
			cur = start;
			do {
				num++;
				cur = g[cur].predecessor;
			} while (cur != UINT_MAX);

			/* Allocate memory for the array. */
			route = malloc(num * sizeof(char));
			if (route == NULL) {
				fprintf(stderr, "Failed to allocate memory.\n");
				exit(EXIT_FAILURE);
			}

			/*
			 * Store the route in the array. Start at the last
			 * array element and iterate to the first.
			 */
			i = num - 1;
			cur = start;
			do {
				route[i--] = g[cur].p->p;
				cur = g[cur].predecessor;
			} while (cur != UINT_MAX);

			/* Finally, print the route. */
			printf("Route: ");
			for (i = 0; i < num - 1; i++)
				printf("%c -> ", route[i]);
			printf("%c\n", route[i]);
		}
	}

	return 0;
}