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