/****************************************************************************
 * list3.c
 *
 * Computer Science 50
 * David J. Malan
 *
 * Demonstrates a linked list for numbers with ability to print list
 * in reverse.
 ***************************************************************************/
       

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "list3.h"


// linked list
node * first = NULL;


// prototypes
void delete();
void find();
void insert();
void recurse();
void reverse();
void traverse();


int
main(int argc, char * argv[])
{
    int c;
    do
    {
        // print instructions
        printf("\nMENU\n\n"
               "1 - delete\n"
               "2 - find\n"
               "3 - insert\n"
               "4 - traverse\n"
               "5 - reverse\n"
               "0 - quit\n\n");

        // get command
        printf("Command: ");
        c = GetInt();

        // try to execute command
        switch (c)
        {
            case 1: delete(); break;
            case 2: find(); break;
            case 3: insert(); break;
            case 4: traverse(); break;
            case 5: reverse(); break;
        }
    }
    while (c != 0);

    // free list before quitting
    node * ptr = first;
    while (ptr != NULL)
    {
        node * predptr = ptr;
        ptr = ptr->next;
        free(predptr);
    }
    return 0;
}


/*
 * void
 * delete()
 *
 * Tries to delete a number.
 */
void
delete()
{
    // prompt user for number
    printf("Number to delete: ");
    int n = GetInt();

    // get list's first node
    node * ptr = first;

    // try to delete number from list
    node * predptr = NULL;
    while (ptr != NULL)
    {
        // check for number
        if (ptr->n == n)
        {
            // delete from head
            if (ptr == first)
            {
                first = ptr->next;
                free(ptr);
            }

            // delete from middle or tail
            else
            {
                predptr->next = ptr->next;
                free(ptr);
            }

            // all done
            break;
        }
        else
        {
            predptr = ptr;
            ptr = ptr->next;
        }
    }

    // traverse list
    traverse();
}


/*
 * void
 * insert()
 *
 * Tries to insert a number into list.
 */
void
insert()
{
    // try to instantiate node for number
    node * newptr = (node *) malloc(sizeof(node));
    if (newptr == NULL)
        return;

    // initialize node
    printf("Number to insert: ");
    newptr->n = GetInt();
    newptr->next = NULL;

    // check for empty list
    if (first == NULL)
        first = newptr;

    // else check if number belongs at list's head
    else if (newptr->n < first->n)
    {
        newptr->next = first;
        first = newptr;
    }

    // else try to insert number in middle or tail
    else
    {
        node * predptr = first;
        while (TRUE)
        {
            // avoid duplicates
            if (predptr->n == newptr->n)
            {
                free(newptr);
                break;
            }

            // check for insertion at tail
            else if (predptr->next == NULL)
            {
                predptr->next = newptr;
                break;
            }

            // check for insertion in middle
            else if (predptr->next->n > newptr->n)
            {
                newptr->next = predptr->next;
                predptr->next = newptr;
                break;
            }

            // update pointer
            predptr = predptr->next;
        }
    }

    // traverse list
    traverse();
}


/*
 * void
 * find()
 *
 * Tries to find a number in list.
 */
void
find()
{
    // prompt user for number
    printf("Number to find: ");
    int n = GetInt();

    // get list's first node
    node * ptr = first;

    // try to find number
    while (ptr != NULL)
    {
        if (ptr->n == n)
        {
            printf("\nFound %d!\n", n);
            sleep(1);
            break;
        }
        ptr = ptr->next;
    }
}


/* 
 * void
 * reverse()
 * 
 * Prints list in reverse (using recursion).
 */
void
reverse()
{
    // start recursion
    recurse(first);

    // flush standard output since we haven't outputted any newlines yet
    fflush(stdout);

    // pause before continuing
    sleep(1);
    printf("\n\n");
}

void
recurse(node * ptr)
{
    // base case
    if (ptr == NULL)
        return;

    // recursive case
    else
    {
        // recurse on rest of list
        recurse(ptr->next);

        // print node's number
        printf("%d ", ptr->n);
    }
}


/* 
 * void
 * traverse()
 * 
 * Traverses list, printing its numbers.
 */
void
traverse()
{
    // traverse list
    printf("\nLIST IS NOW: ");
    node * ptr = first;
    while (ptr != NULL)
    {
        printf("%d ", ptr->n);
        ptr = ptr->next;
    }

    // flush standard output since we haven't outputted any newlines yet
    fflush(stdout);

    // pause before continuing
    sleep(1);
    printf("\n\n");
}