//==================================================================
//
//  File: CLists.c
//
//  A simple forward-directed, singly linked list of Nodes;
//  each Node contains a single int datum.
//
//  Author:  Bary W Pollack
//  Version: Nov. 22, 2001
//
//==================================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//==================================================================
//  A single node of the list structure.
//  A Node is implemented as a struct.
//  It contains:
//      nValue - an int,
//      pNext  - a link to the next node in the list
//==================================================================

struct Node;

typedef struct Node NODE;

struct Node
{
    int   nValue;
    NODE  *pNext;
};

//==================================================================
//  Function Prototypes  (in order of definition below)
//==================================================================

void DeleteList (NODE **pH);
NODE *NewNode (int nValue, NODE *pNext);
NODE *InsertNode (int nValue, NODE *pHead);
NODE *AddNode (int nValue, NODE *pHead);
int  RemoveNode (NODE **pHead);
NODE *ReverseList (NODE *pHead);
NODE *MergeLists (NODE **pList1, NODE **pList2);
NODE *InsertionSort (NODE **pNode);
int  Length (NODE *pNode);
NODE *CopyList (NODE *pNode);
void DisplayList (NODE *pNode);
int  Random (void);
NODE *CreateList (int n);
void CLists (void);

//==================================================================
//  Destructor
//==================================================================

void DeleteList (NODE **pH)
{
    if (pH != NULL)
    {
        NODE *pHead = *pH;
        NODE *pNode = pHead;

        while (pHead != NULL)
        {
            pNode = pNode->pNext;
            free (pHead);
            pHead = pNode;
        }

        *pH = NULL;
    }
}

//==================================================================
//  Creates a new node with datum, nValue, and link, pNext
//==================================================================

NODE *NewNode (int nValue, NODE *pNext)
{
    NODE *pN = (NODE *) malloc (sizeof (struct Node));

    pN->nValue = nValue;
    pN->pNext  = pNext;

    return (pN);
}

//==================================================================
//  Inserts the new node at the proper location in the list so 
//  that the list remains sorted in ascending order.
//  nValue - The int value to be Inserted into the list
//==================================================================

NODE *InsertNode (int nValue, NODE *pHead)
{
    if (pHead == NULL || nValue < pHead->nValue)
        pHead = NewNode (nValue, pHead);
    else
    {
        NODE *p = pHead, *q = pHead->pNext;
        while (q != NULL && nValue > q->nValue)
        {
            p = q; q = q->pNext;
        }
        p->pNext = NewNode (nValue, q);
    }

    return pHead;
}

//==================================================================
//  Add a Node (with a given value) at the head of the list
//==================================================================

NODE *AddNode (int nValue, NODE *pHead)
{
    return (NewNode (nValue, pHead));
}

//==================================================================
//  Removes the head node of the list; returns its datum as the value.
//==================================================================

int RemoveNode (NODE **pHead)
{
    int nValue = 0;

    if (*pHead != NULL)
    {
        NODE *node = *pHead;
        nValue = (*pHead)->nValue;
        *pHead = (*pHead)->pNext;
        free (node);
    }

    return (nValue);
}

//==================================================================
//  Reverse a list, destroying the original
//==================================================================

NODE *ReverseList (NODE *pHead)
{
    NODE *pRevList = NULL;

    while (pHead != NULL)
        pRevList = AddNode (RemoveNode (&pHead), pRevList);

    return (pRevList);
}

//==================================================================
//  Merges two sorted lists together, returns the sorted Merged result.
//==================================================================

NODE *MergeLists (NODE **pList1, NODE **pList2)
{
    NODE *pMergedList = NULL;

    while (*pList1 != NULL || *pList2 != NULL)
    {
        if (*pList1 == NULL)
            pMergedList = AddNode (RemoveNode (pList2), pMergedList);

        else if (*pList2 == NULL || (*pList1)->nValue < (*pList2)->nValue)
            pMergedList = AddNode (RemoveNode (pList1), pMergedList);

        else
            pMergedList = AddNode (RemoveNode (pList2), pMergedList);
    }

    return (ReverseList (pMergedList));
}

//==================================================================
//  Sort the current list into ascending order 
//  using the Insertion sort algorithm.
//==================================================================

NODE *InsertionSort (NODE **pNode)
{
    NODE *pList = NULL;

    while (*pNode != NULL)
        pList = InsertNode (RemoveNode (pNode), pList);

    return (pList);
}

//==================================================================
//  Calculate the length of the list; return the list's length.
//==================================================================

int Length (NODE *pNode)
{
    int nLength = 0;

    for ( ; pNode != NULL; pNode = pNode->pNext)
        ++nLength;

    return (nLength);
}

//==================================================================
//  Display a List
//==================================================================

void DisplayList (NODE *pNode)
{
    printf ("(");
    for ( ; pNode != NULL; pNode = pNode->pNext)
        printf (" %d", pNode->nValue);
    printf (" )");
}

//==================================================================
//  Driver to demonstrate use of the List class.
//==================================================================

//==================================================================
//  Create a list containing n random int's in the range 0..99.
//
//  n - The number of items in the list
//  Returns the created list containing n random int's.
//==================================================================

int Random (void) { return ((int) (fabs (100.0 * rand ()) / RAND_MAX + 1.0)); }

NODE *CreateList (int n)
{
    int  i;
    NODE *pList = NULL;

    for (i = 0; i < n; i++)
        pList = AddNode (Random (), pList);

    return (pList);
}

//==================================================================
//  Create several lists of varying Lengths.
//  Demonstrate that InsertionSort() and Merge work properly.
//==================================================================

void CLists (void)
{
    int  i;
    NODE *pMergedList = NULL;

    srand (17231);

    for (i = 0; i < 13; i = (i < 3) ? i + 1 : i + 3)
    {
        NODE *pNode = CreateList (i);
        NODE *pList = NULL;

        printf ("Unsorted:%3d:  ", Length (pNode));
        DisplayList (pNode);
        printf ("\n");

        pList = InsertionSort (&pNode);
        printf ("Sorted:  %3d:  ", Length (pList));
        DisplayList (pList);
        printf ("\n");

        pMergedList = MergeLists (&pList, &pMergedList);
        printf ("Merged:  %3d:  ", Length (pMergedList));
        DisplayList (pMergedList);
        puts ("\n");
    }
    DeleteList (&pMergedList);
}

//==================================================================

int main (void)
{
    puts ("Demonstrate CLists - AddNode InsertNode, InsertionSort, MergeLists...\n");
    CLists ();
    puts ("*** Fin ***\n");

    return 0;
}

//==================================================================


/* ..... Output from the program .....

Demonstrate CLists - AddNode InsertNode, InsertionSort, MergeLists...

Unsorted:  0:  ( )
Sorted:    0:  ( )
Merged:    0:  ( )

Unsorted:  1:  ( 72 )
Sorted:    1:  ( 72 )
Merged:    1:  ( 72 )

Unsorted:  2:  ( 50 27 )
Sorted:    2:  ( 27 50 )
Merged:    3:  ( 27 50 72 )

Unsorted:  3:  ( 23 18 73 )
Sorted:    3:  ( 18 23 73 )
Merged:    6:  ( 18 23 27 50 72 73 )

Unsorted:  6:  ( 2 41 99 92 69 94 )
Sorted:    6:  ( 2 41 69 92 94 99 )
Merged:   12:  ( 2 18 23 27 41 50 69 72 73 92 94 99 )

Unsorted:  9:  ( 47 86 78 68 48 70 34 87 73 )
Sorted:    9:  ( 34 47 48 68 70 73 78 86 87 )
Merged:   21:  ( 2 18 23 27 34 41 47 48 50 68 69 70 72 73 73 78 86 87 92 94 99 )

Unsorted: 12:  ( 64 75 12 44 9 79 95 29 52 41 19 60 )
Sorted:   12:  ( 9 12 19 29 41 44 52 60 64 75 79 95 )
Merged:   33:  ( 2 9 12 18 19 23 27 29 34 41 41 44 47 48 50 52 60 64 68 69 70 72 73 73 75 78 79 86 87 92 94 95 99 )

*** Fin ***

..... end of output ..... */