#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

#include "tp1.h"

// Fonctions de tp1.h à implémenter ici
//
//

char *double_upper(char *s) {
    int n = 0;
    for(int i = 0; s[i] != '\0'; i++) {
        n++;
        if(isupper(s[i])) {
            n++;
        }
    }
    char ns[n];
    for(int i = 0, j = 0; i < n; i++, j++) {
        ns[j] = s[i];
        if(isupper(s[i])) {
            j++;
            ns[j] = s[i];
        }
    }
    s = ns;
    return s;
}

dlist *create_empty_dlist() {
    return NULL;
}


dlist *add_left_to_dlist(dlist *list, int value) {
    dlist *new_list = create_empty_dlist();
    new_list = malloc(sizeof(dlist));
    new_list -> value = value;
    if(list == NULL) {
        list -> prev = NULL;
        list -> next = NULL;
    }
    if(list -> prev == NULL) {
        new_list -> prev = NULL;
    } else {
        new_list -> prev = list -> prev;
        list -> prev -> next = new_list;
    }
    new_list -> next = list;
    list -> prev = new_list;
    return new_list;
}


dlist *add_right_to_dlist(dlist *list, int value) {
    dlist *new_list = create_empty_dlist();
    new_list = malloc(sizeof(dlist));
    new_list -> value = value;
    if(list == NULL) {
        list -> prev = NULL;
        list -> next = NULL;
    }
    if(list -> next == NULL) {
        new_list -> next = NULL;
    } else {
        new_list -> next = list -> next;
        list -> next -> prev = new_list;
    }
    new_list -> next = list -> next;
    new_list -> prev = list;
    list -> next = new_list;
    return new_list;
}

void del_cell_dlist(dlist *list) {
    if(list != NULL) {
        if(list -> prev != NULL) {
            list -> prev -> next = list -> next;
        }
        if(list -> next != NULL) {
            list -> next -> prev = list -> prev;
        }
        free(list);
    }
}

void free_dlist(dlist *list) {
    if(list == NULL) return;
    while(list -> prev != NULL) {
        del_cell_dlist(list -> prev);
    }
    while(list -> next != NULL) {
        del_cell_dlist(list -> next);
    }
    del_cell_dlist(list);
}

dlist *iota_dlist(int n) {
    if(n == 0) return NULL;
    dlist *list = create_empty_dlist();
    list = malloc(sizeof(dlist));
    list -> value = 0;
    list -> prev = NULL;
    list -> next = NULL;
    for(int i = 1; i < n; i++) {
        add_right_to_dlist(list, i);
        list = list -> next;
    }
    return list;
}

void print_dlist(dlist *list) {
    if(list == NULL) {
        printf("_\n");
        return;
    }
    while(list -> prev != NULL) {
        list = list -> prev;
    }
    while(list -> next != NULL) {
        printf("%i ", list -> value);
        list = list -> next;
    }
    printf("%i\n", list -> value);
}

dlist *create_random_dlist(int length, int max) {
    dlist *list = create_empty_dlist();
    list = malloc(sizeof(dlist));
    list -> value = random()%max;
    list -> prev = NULL;
    list -> next = NULL;
    for(int i = 1; i < length; i++) {
        add_right_to_dlist(list, random()%max);
        list = list -> next;
    }
    return list;
}

dlist *copy_dlist(dlist *list) {
    if(list == NULL) return NULL;
    while(list -> prev != NULL) {
        list = list -> prev;
    }
    dlist *new_list = create_empty_dlist();
    new_list = malloc(sizeof(dlist));
    new_list -> prev = NULL;
    new_list -> value = list -> value;
    new_list -> next = NULL;
    while(list -> next != NULL) {
        add_right_to_dlist(new_list, list -> next -> value);
        new_list = new_list -> next;
        list = list -> next;
    }
    return new_list;
}

dlist *reverse_dlist(dlist *list) {
    if(list == NULL) return NULL;
    while(list -> prev != NULL) {
        list = list -> prev;
    }
    dlist *new_list = create_empty_dlist();
    new_list = malloc(sizeof(dlist));
    new_list -> prev = NULL;
    new_list -> value = list -> value;
    new_list -> next = NULL;
    while(list -> next != NULL) {
        add_left_to_dlist(new_list, list -> next -> value);
        new_list = new_list -> prev;
        list = list -> next;
    }
    return new_list;
}

dlist *mix_dlist(dlist *list1, dlist *list2) {
    if(list1 == NULL && list2 == NULL) return NULL;
    if(list1 == NULL) {
        return copy_dlist(list2);
    }
    else if(list2 == NULL) {
        return copy_dlist(list1);
    }
    while(list1 -> prev != NULL) {
        list1 = list1 -> prev;
    }
    while(list2 -> prev != NULL) {
        list2 = list2 -> prev;
    }
    dlist *new_list = create_empty_dlist();
    new_list = malloc(sizeof(dlist));
    new_list -> prev = NULL;
    new_list -> value = list1 -> value;
    new_list -> next = NULL;
    add_right_to_dlist(new_list, list2 -> value);
    new_list = new_list -> next;
    while(list1 -> next != NULL || list2 -> next != NULL) {
        if(list1 -> next != NULL) {
            add_right_to_dlist(new_list, list1 -> next -> value);
            new_list = new_list -> next;
            list1 = list1 -> next;
        }
        if(list2 -> next != NULL) {
            add_right_to_dlist(new_list, list2 -> next -> value);
            new_list = new_list -> next;
            list2 = list2 -> next;
        }
    }
    return new_list;
}

void evenodd_dlist(dlist *list) {
    if(list == NULL) return;
    while(list -> next != NULL) {
        list = list -> next;
    }
    dlist *new_list_even = create_empty_dlist();
    new_list_even = malloc(sizeof(dlist));
    new_list_even -> prev = NULL;
    new_list_even -> value = 1;
    new_list_even -> next = NULL;
    dlist *new_list_odd = create_empty_dlist();
    new_list_odd = malloc(sizeof(dlist));
    new_list_odd -> prev = NULL;
    new_list_odd -> value = 0;
    new_list_odd -> next = NULL;
    while(list -> prev != NULL) {
        if(list -> value % 2 == 0) {
            add_left_to_dlist(new_list_even, list -> value);
            new_list_even = new_list_even -> prev;
        }
        else {
            add_left_to_dlist(new_list_odd, list -> value);
            new_list_odd = new_list_odd -> prev;
        }
        list = list -> prev;
    }
    if(list -> value % 2 == 0) {
        add_left_to_dlist(new_list_even, list -> value);
        new_list_even = new_list_even -> prev;
    }
    else {
        add_left_to_dlist(new_list_odd, list -> value);
        new_list_odd = new_list_odd -> prev;
    }

    while(new_list_even -> value != 1) {
        list -> value = new_list_even -> value;
        new_list_even = new_list_even -> next;
        list = list -> next;
    }

    while(new_list_odd -> value != 0) {
        list -> value = new_list_odd -> value;
        new_list_odd = new_list_odd -> next;
        list = list -> next;
    }
}

void bubblesort_dlist(dlist *list) {
    if(list == NULL) return;
    while(list -> prev != NULL) {
        list = list -> prev;
    }
    bool check = true;
    while(check) {
        check = false;
        dlist *list_temp = list;
        while (list_temp -> next != NULL) {
            if(list_temp -> next -> value < list_temp -> value) {
                check = true;
                int value_temp = list_temp -> value;
                list_temp -> value = list_temp -> next -> value;
                list_temp -> next -> value = value_temp;
            }
            list_temp = list_temp -> next;
        }
    }
}

dlist *split_dlist(dlist *list) {
    if(list == NULL) return NULL;
    if(list -> prev == NULL && list -> next == NULL) {
        return NULL;
    }
    dlist *new_list = list;
    while(list -> next != NULL) {
        list = list -> next;
    }
    while(new_list -> prev != NULL) {
        new_list = new_list -> prev;
    }
    while (list != new_list && list -> prev != new_list) {
        list = list -> prev;
        new_list = new_list -> next;
    }
    if(list == new_list) {
        list = list -> next;
    }
    list -> prev = NULL;
    new_list -> next = NULL;
    return new_list;
}

void merge_dlist(dlist *list1, dlist *list2) {
    if(list1 == NULL || list2 == NULL) {
        return;
    }
    while(list1 -> prev != NULL) {
        list1 = list1 -> prev;
    }
    while(list2 -> prev != NULL) {
        list2 = list2 -> prev;
    }
    printf("    2. ");
    print_dlist(list1);
    printf("    2. ");
    print_dlist(list2);
    while(list1 -> next != NULL && list2 != NULL) {
        while(list2 != NULL && list2 -> value <= list1 -> value) {
            add_left_to_dlist(list1, list2 -> value);
            if(list2 -> next != NULL) {
                list2 = list2 -> next;
                del_cell_dlist(list2 -> prev);
            }
            else {
                list2 = NULL;
                return;
            }
        }
        list1 = list1 -> next;
    }
    if(list1 -> next == NULL) {
        while(list2 != NULL && list2 -> value <= list1 -> value) {
            printf("            4. %d - %d\n", list1 -> value, list2 -> value);
            add_left_to_dlist(list1, list2 -> value);
            if(list2 -> next != NULL) {
                list2 = list2 -> next;
                del_cell_dlist(list2 -> prev);
            }
            else {
                list2 = NULL;
                return;
            }
        }
        // printf("dddddddddddddd\n");
    }
    if(list2 != NULL && list1 -> next == NULL) {
        dlist *list_temp = copy_dlist(list2);
        list1 -> next = list_temp;
        list_temp -> prev = list1;
        list2 = NULL;
        printf("                    5. ");
        print_dlist(list1);
    }
}

void mergesort_dlist(dlist *list) {
    if(list == NULL) return;
    if(list -> prev == NULL && list -> next == NULL) return;
    dlist *new_list1 = copy_dlist(list);
    dlist *new_list2 = split_dlist(new_list1);
    printf("1. ");
    print_dlist(new_list1);
    printf("1. ");
    print_dlist(new_list2);
    mergesort_dlist(new_list1);
    mergesort_dlist(new_list2);
    printf("        3. ");
    print_dlist(new_list1);
    printf("        3. ");
    print_dlist(new_list2);
    merge_dlist(new_list1, new_list2);
    printf("                        6. ");
    print_dlist(new_list1);
    printf("                        6. ");
    print_dlist(list);
    while(list -> prev != NULL) {
        list = list -> prev;
    }
    while(new_list1 -> prev != NULL) {
        new_list1 = new_list1 -> prev;
    }
    while(list -> next != NULL && new_list1 -> next != NULL) {
        list -> value = new_list1 -> value;
        list = list -> next;
        new_list1 = new_list1 -> next;
    }
    list -> value = new_list1 -> value;
    list = list -> next;
    printf("                        6. ");
    print_dlist(list);
}

int main(int argc, char *argv[]) {
  srandom(time(NULL));
  // char *s = "Vive le C!!\n";
  // printf("%s", s);
  // s = double_upper(s);
  // printf("%s", s);
  // Tests à écrire ici
  /* ... */
  dlist *list = iota_dlist(10);
  print_dlist(list);
  free_dlist(list);
  list = create_random_dlist(10, 100);
  print_dlist(list);
  dlist *new_list = copy_dlist(list);
  print_dlist(new_list);
  new_list = reverse_dlist(list);
  print_dlist(new_list);
  dlist *new_new_list = mix_dlist(list, new_list);
  print_dlist(new_new_list);
  evenodd_dlist(new_new_list);
  print_dlist(new_new_list);
  bubblesort_dlist(new_new_list);
  print_dlist(new_new_list);
  new_new_list = iota_dlist(10);
  print_dlist(new_new_list);
  evenodd_dlist(new_new_list);
  list = split_dlist(new_new_list);
  print_dlist(new_new_list);
  print_dlist(list);
  merge_dlist(new_new_list, list);
  print_dlist(new_new_list);
  list = iota_dlist(10);
  list = reverse_dlist(list);
  printf("sort\n");
  print_dlist(list);
  mergesort_dlist(list);
  print_dlist(list);
  free_dlist(list);
  free_dlist(new_list);
  free_dlist(new_new_list);

  return EXIT_SUCCESS;
}