/* File: citygraph.c
 * Desc: implementation of cityPair graph ADT
 * Anthony Towns
 * 3 Sep 1997
 */

#include "citygraph.h"
#include "bool.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

struct _Graph_Node {
     int distance;
     cityPair pair;
     struct _Graph_Node *next;
};

struct _Graph { 
     int n_steps;
     struct _Graph_Node *first_step;
};

Graph graphNew(void)
{
     Graph g;

     g = (Graph) malloc( sizeof( struct _Graph ) );
     if ( g != NULL ) {
	  g->n_steps = 0;
	  g->first_step = NULL;
     }

     return g;    
}

void graphFree( Graph* pg ) 
{
     struct _Graph_Node *step, *old;
     assert( *pg != NULL );

     step = (*pg)->first_step; 
     while ( step ) {
	  old = step;
	  step = step->next;
	  free( old );
     }
     free( *pg );
     *pg = NULL;
}

void addCityPairDistance( Graph g, cityPair c, int d )
{    
     struct _Graph_Node *new;

     assert( d > 0 && g != NULL );

     new = (struct _Graph_Node *) malloc( sizeof(struct _Graph_Node) );
     if ( new != NULL ) {
	  new->distance = d;
	  new->pair = c;
	  new->next = g->first_step;
	  g->first_step = new;
	  g->n_steps++;
     } else {
	  assert(FALSE); /* there wasn't any memory */
     }
}

int distanceBetweenCities( Graph g, cityPair c )
{
     struct _Graph_Node *st;

     assert( g != NULL );

     for ( st = g->first_step; st != NULL; st = st->next ) {
	  assert( st->pair.to >= 0 && st->pair.to < NoCity );
	  assert( st->pair.from >= 0 && st->pair.from < NoCity );

	  if ( (st->pair.to == c.to && st->pair.from == c.from) ||
	       (st->pair.to == c.from && st->pair.from == c.to) )
	  {
	       return st->distance;
	  }
     }

     return 0;
}

bool graphEmpty( Graph g )
{
     return g->n_steps == 0;
}

void displayGraphContents(Graph g)
{
     struct _Graph_Node *st;

     printf( "Graph contents:\n" );
     for ( st = g->first_step; st != NULL; st = st->next ) {
	  printf( "\t%s to %s, %d km\n", cityName[ st->pair.from ],
		  cityName[ st->pair.to ], st->distance );
     }
     printf( "\n" );
}