TP_11/exo2/lib/clist.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <stdbool.h>
   4
   5 #include "clist.h"
   6
   7 link_t* list_new(int value) {
   8     link_t* link_new;
   9     link_new = malloc(sizeof(link_t));
  10     link_new->value = value;
  11     link_new->next = NULL;
  12     return link_new;
  13 }
  14
  15 link_t* list_append(link_t* head, int value) {
  16
  17     if (head == NULL) {
  18         return head = list_new(value);
  19     } else {
  20         link_t* head_first = head;
  21         while (head->next != NULL) {
  22             head = head->next;
  23         }
  24         head->next = list_new(value);
  25         return head_first;
  26     }
  27 }
  28
  29 link_t* list_prepend(link_t* head, int value) {
  30     link_t* first_link = list_new(value);
  31
  32     first_link->next = head;
  33     return first_link;
  34 }
  35
  36 link_t* list_insert(link_t* head, unsigned index, int value) {
  37     unsigned max_index = list_count(head);
  38
  39     if (index == 0) {
  40         return list_prepend(head, value);
  41     } else if (index == max_index) {
  42         return list_append(head, value);
  43     } else {
  44         link_t* link_insrt = list_new(value);
  45         link_t* head_first = head;
  46         link_t* head_next = NULL;
  47         for (unsigned i = 0; i < index-1; i++) {
  48             head = head->next;
  49         }
  50         head_next = head->next;
  51         head->next = link_insrt;
  52         head = link_insrt;
  53         head->next = head_next;
  54         return head_first;
  55     }
  56 }
  57
  58 link_t* list_delete(link_t* head, unsigned index) {
  59     link_t* head_prev = NULL;
  60     link_t* head_next = NULL;
  61     link_t* head_ret = NULL;
  62
  63     if (head == NULL) {
  64         return NULL;
  65     } else if (index == 0) {
  66         head_next = head->next;
  67         free(head);
  68         head = head_next;
  69         head_ret = head;
  70     } else {
  71         link_t* head_first = head;
  72         for (unsigned i = 0; i < index-1; i++) {
  73             head = head->next;
  74         }
  75         head_prev = head;
  76         head = head->next;
  77         head_next = head->next;
  78         free(head);
  79         head = head_prev;
  80         head->next = head_next;
  81         head_ret = head_first;
  82     }
  83     if (head_ret != NULL) {
  84         return head_ret;
  85     } else {
  86         return NULL;
  87     }
  88 }
  89
  90 link_t* list_concat(link_t* first, link_t* second) {
  91     link_t* head_first = first;
  92
  93     while (first->next != NULL) {
  94         first = first->next;
  95     }
  96     first->next = second;
  97     return head_first;
  98 }
  99
 100 link_t* list_sort(link_t* head) {
 101     int tmp;
 102     bool isswaped;
 103     link_t* head_first = head;
 104
 105     do {
 106         isswaped = false;
 107         while (head->next != NULL) {
 108             if (head->value > head->next->value) {
 109                 tmp = head->value;
 110                 head->value = head->next->value;
 111                 head->next->value = tmp;
 112                 isswaped = true;
 113             }
 114             head = head->next;
 115         }
 116         /* Reloop at the beginning of the list until there's values swaped */
 117         head = head_first;
 118     } while (isswaped);
 119     return head_first;
 120 }
 121
 122 static link_t* _list_merge_sort(link_t* head1, link_t* head2) {
 123     link_t* head_result = NULL;
 124
 125     if (head1 == NULL) {
 126         return head2;
 127     }
 128     if (head2 == NULL) {
 129         return head1;
 130     }
 131     if (head1->value < head2->value) {
 132         head_result = head1;
 133         head_result->next = _list_merge_sort(head1->next, head2);
 134     } else {
 135         head_result = head2;
 136         head_result->next = _list_merge_sort(head1, head2->next);
 137     }
 138     return head_result;
 139 }
 140
 141 link_t* list_merge_sort(link_t* head) {
 142     link_t* head1;
 143     link_t* head2;
 144
 145     if (head == NULL || head->next == NULL) {
 146         return head;
 147     }
 148
 149     head1 = head;
 150     head2 = head->next;
 151     while (head2 != NULL && head2->next != NULL) {
 152         head = head->next;
 153         head2 = head->next->next;
 154     }
 155     head2 = head->next;
 156     head->next = NULL;
 157
 158     head1 = list_merge_sort(head1);
 159     head2 = list_merge_sort(head2);
 160     return _list_merge_sort(head1, head2);
 161 }
 162
 163 unsigned list_count(link_t* head) {
 164     unsigned count = 0;
 165
 166     while (head != NULL) {
 167         ++count;
 168         head = head->next;
 169     }
 170     return count;
 171 }
 172
 173 void list_set(link_t* head, unsigned index, int value) {
 174     unsigned count = 0;
 175
 176     while (head != NULL && count < index) {
 177         ++count;
 178         head = head->next;
 179     }
 180     if (head != NULL) { head->value = value; }
 181 }
 182
 183 int list_get(link_t* head, unsigned index) {
 184     unsigned count = 0;
 185
 186     while (head != NULL && count < index) {
 187         ++count;
 188         head = head->next;
 189     }
 190     if (head != NULL) {
 191         return head->value;
 192     } else {
 193         return -1;
 194     }
 195 }
 196
 197 void list_clear(link_t* head) {
 198     link_t* next_link = NULL;
 199
 200     while (head != NULL) {
 201         next_link = head->next;
 202         free(head);
 203         head = next_link;
 204     }
 205 }
 206
 207 void list_display_values(link_t* head) {
 208     unsigned i = 0;
 209
 210     printf("------Begin------\n");
 211     while (head != NULL) {
 212         printf("value at [%d]=%d\n", i, head->value);
 213         head = head->next;
 214         i++;
 215     }
 216     printf("------End------\n");
 217 }