/*Merge Sort by linked list*/
/*by Daehee Kim*/

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

#define MAX 12

/*Linear List*/
typedef struct NODE
{
    int data;
    struct NODE* next;  /*Pointing the next list*/
} Node;


/*function prototype*/
Node* merge_sort(Node* x);
Node* merge_list(Node* x, Node* y);
Node* addlist(int);
void printlist(Node* head);
void m_free(Node** head);
void delReturn(char* Str, int size);


int main(void)
{
    Node *head=NULL;
    Node **workpp;
    char Str[MAX];
    char* Str_q = "quit";
    int num;
    int i;
    int size;
    char *endptr;
        printf("\nThis program is a sort program by linked list.\n");
        printf("This program show to you the sorted result.\n");
    while(1) {
        /*get data from user*/
        printf("If you finished input numbers, input 'a'.\nThen you can see the result\n");
        printf("If you want to finish this program, input 'quit'.\n\n");

        workpp =&head;
        while(1)
        {
            /*clear stdin*/
            __fpurge(stdin);

            printf("Input data(Only integer)->");
            fgets(Str, MAX, stdin);
            size = strlen(Str);
            delReturn(Str, size);
            if(size >= 9)
            {
                printf("It's too long input\n");
                continue;
            }
            if(strcmp(Str,Str_q) == 0)
                return 0;
            if(Str[0] == 'a'){
                if(head == NULL){
                    printf("There is no input\n");
                    continue;
                }
                break;
            }
            else if(Str[0] == '\0')
                continue;
            num = strtol(Str, &endptr, 10);
            if(*endptr != '\0')
            {
                printf("'%c'is illegal input\n", *endptr);
                continue;
            }
            *workpp = addlist(num);
            workpp = &(*workpp)->next;
        }

        printf("\n\n#List before sorted\n");
        printlist(head);
        head = merge_sort(head);    /*merge sort*/
        printf("#List after sorted\n");
        printlist(head);        /*output result*/
        printf("\n\n");
        m_free(&head);
    }
}


Node* merge_sort(Node* x)
{
    Node *a, *b, *y;
    if(x->next == NULL)
    {
        return x;
    }
    a = x;
    b = x->next;
    if(b != NULL){b = b->next;}

    while(b != NULL)
    {
        a = a->next;
        b = b->next;
        if(b != NULL){b = b->next;}
    }

    y = a->next;
    a->next =  NULL;

    return merge_list(merge_sort(x), merge_sort(y));
}

Node* merge_list(Node* x, Node* y)
{
    Node z, *p;

    p = &z;

    while(x != NULL && y != NULL)
    {
        if(x->data <= y->data)
        {
            p->next = x;
            p = x;
            x = x->next;
        }
        else
        {
            p->next = y;
            p = y;
            y = y->next;
        }
    }

    if(x == NULL)
    {
        p->next = y;
    }
    else
    {
        p->next = x;
    }

    return z.next;
}

Node* addlist(int num)
{
    Node *x;

    x = (Node*)malloc(sizeof(Node));
    x->data = num;
    x->next = NULL;
    return x;
}


void printlist(Node *head)
{
    while(head->next != NULL)
    {
        printf("%d, ", head->data);
        head = head->next;
    }
    printf("%d\n\n", head->data);
}

void m_free(Node** p_head)
{
    while((*p_head)->next->next != NULL)
    {
        free((*p_head)->next);
        *p_head=(*p_head)->next;
    }
    *p_head = NULL;
}

void delReturn(char* Str, int size)
{
    if(Str[size-1] == '\n')
        Str[size-1] = '\0';
}