/********************************************************************
 *  filename   :  learn_c.c                                         *
 *  programmer :  Mark Connor (mconnor@cise.ufl.edu)                *
 *  syntax     :  learn_c inputfile outputfile                      *
 *  description:  This program reads each line of a file specified  *
 *                by the first command-line argument, creates a     *
 *                linked list of structures (one node for each line *
 *                of input), sorts the list by the integer field,   *
 *                and then prints the list to the file specified by *
 *                the second command-line argument.  The input file *
 *                contains any number of lines of the form:         *
 *                    char[20],int                                  *
 ********************************************************************/
#include <stdio.h>
#include <string.h>



/* create the structure and pointer type to the structure */

typedef struct myStruct strType;
typedef strType *strPtr;
struct myStruct {
    char       str[20];
    int        number;
    strPtr  next;
};

/********************************************************************
 * function   : strPtr createNode(void)                             *
 * description: Allocates memory for a node, iniitializes it, and   *
 *              returns a pointer to it.                            *
 ********************************************************************/
strPtr createNode() {
    strPtr    node;
    int       count;

    node = (strPtr) malloc(sizeof(struct myStruct));
    strcpy((*node).str, "");
    (*node).number = 0;
    (*node).next = NULL;

    return node;
}

/********************************************************************
 * function   : strPtr createList(char*)                            *
 * description: Reads each line from the input file and creates a   *
 *              linked list of structures containing the data read  *
 *              and returns a pointer to the head of the list.      *
 ********************************************************************/
strPtr createList(char *filename) {

    FILE    *inputFile;
    char    line[40];
    strPtr  head, oldNode, newNode;
    int     firstNode;               /* substitute boolean variable */
    char    *token;

    inputFile = fopen(filename, "r");

    firstNode = 1;   /* set boolean value to TRUE */
    while (fscanf(inputFile, "%s", line) != EOF) {
        newNode = createNode();
        token = strtok(line, ",");
        strcpy((*newNode).str,token);
        token = strtok(NULL, ",");
        (*newNode).number = atoi(token);
        if (firstNode) {                  /* the first node is the  */
            head = newNode;               /* head of the list.      */
            firstNode = 0;            /* set boolean value to FALSE */
        } else (*oldNode).next = newNode;
        oldNode = newNode;
    }

    fclose(inputFile);
    return head;
}


/********************************************************************
 * function   : strPtr sortList(strPtr)                             *
 * description: Sorts the linked list pointed to by head in order   *
 *              by the integer field using "insertion sort."        *
 ********************************************************************/
strPtr sortList(strPtr head) {
    strPtr node, last, current, next;
    int    nodeCount;
    int    count, index;


    /* start by counting the number of nodes in the list */
    node = head;
    nodeCount = 0;
    while (node != NULL) {
        nodeCount++;
        node = (*node).next;
    }

     /* loop from 2nd node to last node.  pull the indexed node out  */
    /* of the linked list, then loop from the first node to the     */
    /* node just before the removed node.  if you find a node with  */
    /* a larger int value, insert the removed node here and quit    */
    /* the inner loop.  if no int values are larger, insert node    */
    /* where it used to be.  then, increment the outer loop counter */
    /* to process the next node in the list.                        */

    index = 2;
    node = (*head).next;
    last = head;
    while (index <= nodeCount) {
        next = (*node).next;
        (*last).next = next;
        count = 1;
        current = head;
        last = NULL;
        while (count <= index) {
            if (count == index) {
                (*node).next = (*current).next;
                (*current).next = node;
            } else if ((*node).number < (*current).number) {
                if (last == NULL) {
                    (*node).next = current;
                    head = node;
                } else {
                    (*node).next = current;
                    (*last).next = node;
                }
                count = index;
            } else {
                last = current;
                current = (*current).next;
            }
            count++;
        }
        node = next;
        last = head;
        while ((*last).next != next) last = (*last).next;
        index++;
    }

    return head;    
}

/********************************************************************
 * function   : void outputList(char*, strPtr)                      *
 * description: Traverses the linked list in order and writes out   *
 *              each node to a separate line in the output file.    *
 ********************************************************************/
void outputList(char *filename, strPtr node) {
    FILE *outputFile;

    outputFile = fopen(filename, "w");

    while (node != NULL) {
        fprintf(outputFile, "%s,%d\n",(*node).str, (*node).number);
        node = (*node).next;
    }

    fclose(outputFile);
}


/* A good C program has a very small main function that simply
   calls the other functions in the program, which actually
   perform the actions of the program.                              */

int main(int argc, char *argv[]) {
    strPtr head;

    head = createList(argv[1]);
    head = sortList(head);
    outputList(argv[2], head);

    return;
}