/* File: cityStk.c
 * Desc: Implementation of cityStk library
 * The cityStk library implements a stack (ie a last-in, first out list)
 * of pairs of cities (to, from).
 * Anthony Towns
 * 15 August 1997
 */

#include "citystk.h"
#include "bool.h"
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

#define  N_CITIES_TO_ALLOCATE  (1)

/* defines _Stack as a singly linked list of cityPairs, where the most
 * recently added element is at the head of the list.
 */

struct _Stack_Node {
     cityPair pair;
     struct _Stack_Node *next;
};

struct _Stack {
     struct _Stack_Node *head;
};

Stack stackNew(void)
{
     Stack s;

     s = (Stack) malloc( sizeof( struct _Stack ) );
     if ( s != NULL ) {
	  s->head = NULL;
     }

     return s;    
}

void stackFree( Stack* ps ) 
{
     struct _Stack_Node *nxt, *c;

     assert( *ps != NULL );  /* is this a problem? */

     /* free each _Stack_Node, beginning at the beginning */
     c = (*ps)->head;
     while ( c != NULL ) {
	  nxt = c->next;
	  free(c);
	  c = nxt;
     }

     /* free the stack structure itself */
     free( *ps );

     /* make sure the user can't use the stack again
      * (this is checked with assertions in each operation */

     *ps = NULL;
}
     

void stackPush( Stack s, cityPair c )
{
     struct _Stack_Node *new;

     assert( s != NULL );

     new = (struct _Stack_Node *) malloc( sizeof( struct _Stack_Node ) );
     
     if ( new ) {
	  new->pair = c;
	  new->next = s->head;
	  s->head = new;
     } else {
	  assert(FALSE); /* couldn't allocate memory */
     }
}

void stackPop( Stack s, cityPair *c )
{
     struct _Stack_Node *nxt;

     assert( s != NULL );  /* bad Stack! */
     assert( s->head != NULL ); /* Stack doesn't have elements! */

     *c = s->head->pair;
     nxt = s->head->next;
     free( s->head );
     s->head = nxt;
}

int stackEmpty( Stack s )
{
     assert( s != NULL ); /* bad Stack! */
     return s->head == NULL;
}