/*
    airports.c - A solution to CS 12 assignment 2, part 2, Fall 2008

    updated by cmc, 10/9/08
*/

#include <string.h>
#include "airports.h"

/* insertFirst - 2.5 Exercise 1 (called InsertNewFirstNode in text)
        creates a new node with code as its airport field, and
        makes this node the first node in the list */
void insertFirst(AirportCode code, NodeType **listPtr) {
    NodeType *node = createNode(code);
    node->link = *listPtr;
    *listPtr = node;
}

/* deleteFirst - 2.5 Exercise 2
        removes the first node from the list, and frees the memory space
        used by this node; all other nodes remain in the list
        Note: does nothing if the list is empty */
void deleteFirst(NodeType **listPtr) {
    if (*listPtr != NULL) {
        NodeType *oldFirst = *listPtr; /* store pointer to free later */
        *listPtr = oldFirst->link;
        free(oldFirst);
    }
}

/* insertNodeBeforeOther - 2.5 Exercise 3
        inserts the existing node referenced by m before
        the node referenced by n (into the list containing n)
        Note: see hint for this exercise on p. 53
   precondition: n is not NULL - it is okay to assume this condition is true */
void insertNodeBeforeOther(NodeType *m, NodeType *n) {
    AirportCode temp;
    
    /* first insert m after n */
    m->link = n->link;
    n->link = m;

    /* then swap airport codes */
    strcpy(temp, m->airport);
    strcpy(m->airport, n->airport);
    strcpy(n->airport, temp);
}

/* copy - 2.5 Exercise 4
        copies the list, and returns a pointer to the new list
        Note: the new list contains copies of each node in list */
NodeType *copy(NodeType *list) {
    NodeType *newList = NULL, *n = list;
    while (n != NULL) {
        append(n->airport, &newList);
        n = n->link;
    }
    return newList;
}

/* reverse - 2.5 Exercise 5
        reverses the order of the nodes in the list */
void reverse(NodeType **listPtr) {
    if (*listPtr != NULL && (*listPtr)->link != NULL) {
        NodeType *n = *listPtr, *oldLink;
        *listPtr = NULL;
        while (n != NULL) {
            oldLink = n->link;
            n->link = *listPtr;
            *listPtr = n;
            n = oldLink;
        }
    }
}

/* concat - 2.5 Exercise 7
        concatenates list1 and list2 to form a new list, and returns a pointer
        to this new list;
        Note: the new list contains copies of all nodes in list1 and list2 */
NodeType *concat(NodeType *list1, NodeType *list2) {
    NodeType *result = copy(list1), *n = list2;
    while (n != NULL) {
        append(n->airport, &result);
        n = n->link;
    }
    return result;
}

/*************************************************************************
   DO NOT CHANGE THE FUNCTIONS BELOW. SEE airports.h FOR MORE INFORMATION.

   Do study the definitions though, to understand how they work. And pay
   attention to the programming style.
*************************************************************************/

/* createNode - here is a utility function to create a new node;
    node's airport set to a copy of code, and link set to NULL;
    returns a pointer to the new node */
NodeType *createNode(AirportCode code) {
    NodeType *node;
    if ((node = (NodeType *)malloc(sizeof(NodeType))) != NULL) {
        strcpy(node->airport, code);
        node->link = NULL;
    }
    else {
        fprintf(stderr, "out of memory - terminating\n");
        exit(1);
    }
    return node;
}

/* append - creates a new NodeType and adds it to the end of the list;
            called InsertNewLastNode in Standish, p. 50 */
void append(AirportCode code, NodeType **listPtr) {
    NodeType *newNode, *ptr;
    newNode = createNode(code);

    if (*listPtr == NULL) /* empty list is a special case */
        *listPtr = newNode;
        
    else { /* find end of list and set link of last node */
        ptr = *listPtr;
        while (ptr->link != NULL)
            ptr = ptr->link;
        ptr->link = newNode;
    }
}

/* clearList - clears the list of all nodes */
void clearList(NodeType **listPtr) {
    if (*listPtr != NULL) {
        NodeType *n = *listPtr;
        NodeType *next;
        while(n != NULL) {
            next = n->link;  /* store link pointer; then free the node */
            free(n);         /* important step to prevent memory leak */
            n = next;
        }
        *listPtr = NULL;     /* mark the list pointer as an empty list */
    }
}

/* printList - prints the airport codes in list order;
               adapted from Standish, p. 50 */
void printList(NodeType *list) {
    NodeType *n = list;
    putchar('(');
    while (n != NULL) { /* print airport and hop to next node */
        printf("%s", n->airport);
        n = n->link;
        if (n != NULL) printf(", ");
    }
    puts(")");
}