TP 9 exo2: Implement a merge sort function for the linked list.

[TD_C.git] / TP_9 / exo2 / clist.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#include "clist.h"

link_t* list_new(int value) {
    link_t* link_new;	
    link_new = malloc(sizeof(link_t));
    link_new->value = value;
    link_new->next = NULL;
    return link_new;
}

link_t* list_append(link_t* head, int value) {

    if (head == NULL) { 
        return head = list_new(value);
    } else {
        link_t* head_first = head;
        while (head->next != NULL) {
    	    head = head->next; 
        }
        head->next = list_new(value);
        return head_first;
    }
}

link_t* list_prepend(link_t* head, int value) {
    link_t* first_link = list_new(value);
    
    first_link->next = head;
    return first_link;
}

link_t* list_insert(link_t* head, unsigned index, int value) {

    if (index == 0) {
        return list_prepend(head, value);  
    } else if (index == list_count(head)) {
        return list_append(head, value);
    } else {
        link_t* link_insrt = list_new(value);  
        link_t* head_first = head;
        link_t* head_next = NULL;
        for (unsigned i = 0; i < index-1; i++) {
            head = head->next;
        }
        head_next = head->next;
        head->next = link_insrt;
        head = link_insrt;
        head->next = head_next; 
        return head_first;
    }
}

link_t* list_delete(link_t* head, unsigned index) {
    link_t* head_prev = NULL;
    link_t* head_next = NULL;
    link_t* head_ret = NULL;
   
    if (head == NULL) {
        return NULL;
    } else if (index == 0) {
        head_next = head->next;
        free(head);
        head = head_next;
        head_ret = head;
    } else {
        link_t* head_first = head;
        for (unsigned i = 0; i < index-1; i++) {
            head = head->next;
        }
        head_prev = head;
        head = head->next;
        head_next = head->next;
        free(head);
        head = head_prev;
        head->next = head_next;
        head_ret = head_first;
    }
    if (head_ret != NULL) {
        return head_ret;
    } else {
        return NULL;
    }
}

link_t* list_concat(link_t* first, link_t* second) {
    link_t* head_first = first;

    while (first->next != NULL) {
        first = first->next;
    }
    first->next = second;
    return head_first;
}

link_t* list_sort(link_t* head) {
    int tmp;
    bool isswaped;
    link_t* head_first = head;

    do {
        isswaped = false;
        while (head->next != NULL) {
            if (head->value > head->next->value) {
                tmp = head->value;
                head->value = head->next->value;
                head->next->value = tmp;
	        isswaped = true;
            }
	    head = head->next;
        }
	/* Reloop at the beginning of the list until there's values swaped */
	head = head_first;
    } while (isswaped);
    return head_first;
}

static link_t* _list_merge_sort(link_t* head1, link_t* head2) {
    link_t* head_result = NULL;

    if (head1 == NULL) {
        return head2;
    }
    if (head2 == NULL) {
        return head1;
    }
    if (head1->value < head2->value) {
        head_result = head1;
	head_result->next = _list_merge_sort(head1->next, head2);
    } else {
        head_result = head2;
	head_result->next = _list_merge_sort(head1, head2->next);
    }
    return head_result;
}

link_t* list_merge_sort(link_t* head) {
    link_t* head1;
    link_t* head2;

    if (head == NULL || head->next == NULL) {
        return head;
    }

    head1 = head;
    head2 = head->next;
    while (head2 != NULL && head2->next != NULL) {
        head = head->next;
	head2 = head->next->next;
    }
    head2 = head->next;
    head->next = NULL;

    head1 = list_merge_sort(head1);
    head2 = list_merge_sort(head2);
    return _list_merge_sort(head1, head2);
}

unsigned list_count(link_t* head) {
    unsigned count = 0;
    
    while (head != NULL) {
        ++count;
        head = head->next;
    } 
    return count;
}

void list_set(link_t* head, unsigned index, int value) {
    unsigned count = 0;

    while (head != NULL && count < index) {
        ++count;
        head = head->next;
    }
    if (head != NULL) { head->value = value; }
}

int list_get(link_t* head, unsigned index) {
    unsigned count = 0;    

    while (head != NULL && count < index) {
        ++count;
        head = head->next; 
    }
    if (head != NULL) { 
        return head->value;
    } else {
        return -1;
    }
}

void list_clear(link_t* head) {
    link_t* next_link = NULL;

    while (head != NULL) {
        next_link = head->next;
        free(head);
        head = next_link;
    }
}

void list_display_values(link_t* head) {
    unsigned i = 0;

    printf("------Begin------\n");
    while (head != NULL) {
        printf("value at [%d]=%d\n", i, head->value);
	head = head->next;
	i++;
    }
    printf("------End------\n");
}