add: graphs et rushs

6 files changed, 430 insertions, 0 deletions

diff --git a/graphs/piscine/dlist/Makefile b/graphs/piscine/dlist/Makefile
new file mode 100644
index 0000000..1251967
--- /dev/null
+++ b/graphs/piscine/dlist/Makefile
@@ -0,0 +1,15 @@
+CC = gcc
+CFLAGS = -std=c99 -pedantic -Werror -Wall -Wextra -Wvla
+
+SRC = dlist-1.c dlist-2.c dlist-3.c dlist-4.c
+OBJ = $(SRC:.c=.o)
+
+.PHONY: library clean
+
+library: $(OBJ)
+	ar csr libdlist.a $(OBJ)
+
+clean: $(OBJ)
+	$(RM) *.a $(OBJ)
+
+$(OBJ): $(SRC)
diff --git a/graphs/piscine/dlist/dlist-1.c b/graphs/piscine/dlist/dlist-1.c
new file mode 100644
index 0000000..443ebca
--- /dev/null
+++ b/graphs/piscine/dlist/dlist-1.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dlist.h"
+
+struct dlist *dlist_init(void)
+{
+    struct dlist *res = malloc(sizeof(struct dlist));
+    if (res == NULL)
+        return NULL;
+
+    res->size = 0;
+    res->head = NULL;
+    res->tail = NULL;
+    return res;
+}
+
+int dlist_push_front(struct dlist *list, int element)
+{
+    if (element < 0)
+        return 0;
+    struct dlist_item *new = malloc(sizeof(struct dlist_item));
+    if (new == NULL)
+        return 0;
+
+    new->data = element;
+    new->next = list->head;
+    new->prev = NULL;
+
+    if (list->size == 0)
+        list->tail = new;
+    else
+        list->head->prev = new;
+
+    list->head = new;
+    list->size++;
+
+    return 1;
+}
+
+void dlist_print(const struct dlist *list)
+{
+    if (list->size == 0)
+        return;
+
+    for (struct dlist_item *i = list->head; i != list->tail; i = i->next)
+    {
+        printf("%d\n", i->data);
+    }
+    printf("%d\n", list->tail->data);
+}
+
+int dlist_push_back(struct dlist *list, int element)
+{
+    if (element < 0)
+        return 0;
+    struct dlist_item *new = malloc(sizeof(struct dlist_item));
+    if (new == NULL)
+        return 0;
+
+    new->data = element;
+    new->prev = list->tail;
+    new->next = NULL;
+
+    if (list->size == 0)
+        list->head = new;
+    else
+        list->tail->next = new;
+    list->tail = new;
+    list->size++;
+
+    return 1;
+}
+
+size_t dlist_size(const struct dlist *list)
+{
+    return list->size;
+}
diff --git a/graphs/piscine/dlist/dlist-2.c b/graphs/piscine/dlist/dlist-2.c
new file mode 100644
index 0000000..5ccdaa3
--- /dev/null
+++ b/graphs/piscine/dlist/dlist-2.c
@@ -0,0 +1,113 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dlist.h"
+
+int dlist_get(const struct dlist *list, size_t index)
+{
+    if (index >= list->size)
+        return -1;
+
+    struct dlist_item *i;
+    for (i = list->head; index; index--, i = i->next)
+    {
+        continue;
+    }
+
+    return i->data;
+}
+
+int dlist_insert_at(struct dlist *list, int element, size_t index)
+{
+    if (index > list->size || element < 0)
+        return 0;
+    else if (index == list->size)
+        dlist_push_back(list, element);
+    else if (index == 0)
+        dlist_push_front(list, element);
+    else
+    {
+        struct dlist_item *new = malloc(sizeof(struct dlist_item));
+        if (new == NULL)
+            return 0;
+        new->data = element;
+
+        struct dlist_item *i;
+        for (i = list->head; index - 1; index--, i = i->next)
+            continue;
+        new->next = i->next;
+        i->next->prev = new;
+        i->next = new;
+        new->prev = i;
+        list->size++;
+    }
+    return 1;
+}
+
+int dlist_find(const struct dlist *list, int element)
+{
+    int index = 0;
+    struct dlist_item *i;
+    for (i = list->head; i && i->data != element; index++, i = i->next)
+        continue;
+    if (!i)
+        return -1;
+    return index;
+}
+
+int dlist_remove_at(struct dlist *list, size_t index)
+{
+    if (index >= list->size)
+        return -1;
+    int res;
+    struct dlist_item *item;
+    if (list->size == 1)
+    {
+        item = list->head;
+        res = list->head->data;
+        list->head = NULL;
+        list->tail = NULL;
+    }
+    else if (index == 0)
+    {
+        item = list->head;
+        res = item->data;
+        item->next->prev = NULL;
+        list->head = item->next;
+    }
+    else if (index == list->size - 1)
+    {
+        item = list->tail;
+        res = item->data;
+        item->prev->next = NULL;
+        list->tail = item->prev;
+    }
+    else
+    {
+        for (item = list->head; index; index--, item = item->next)
+            continue;
+
+        res = item->data;
+        item->prev->next = item->next;
+        item->next->prev = item->prev;
+    }
+
+    free(item);
+    list->size--;
+    return res;
+}
+
+void dlist_clear(struct dlist *list)
+{
+    if (list->size == 0)
+        return;
+    for (struct dlist_item *i = list->head; i;)
+    {
+        struct dlist_item *tmp = i->next;
+        free(i);
+        i = tmp;
+    }
+    list->size = 0;
+    list->head = NULL;
+    list->tail = NULL;
+}
diff --git a/graphs/piscine/dlist/dlist-3.c b/graphs/piscine/dlist/dlist-3.c
new file mode 100644
index 0000000..22b4b52
--- /dev/null
+++ b/graphs/piscine/dlist/dlist-3.c
@@ -0,0 +1,83 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dlist.h"
+
+void dlist_map_square(struct dlist *list)
+{
+    for (struct dlist_item *i = list->head; i; i = i->next)
+    {
+        i->data *= i->data;
+    }
+}
+
+void dlist_reverse(struct dlist *list)
+{
+    struct dlist_item *tmp;
+    for (struct dlist_item *i = list->head; i; i = i->prev)
+    {
+        tmp = i->next;
+        i->next = i->prev;
+        i->prev = tmp;
+    }
+    tmp = list->tail;
+    list->tail = list->head;
+    list->head = tmp;
+}
+
+struct dlist *dlist_split_at(struct dlist *list, size_t index)
+{
+    if (list->size == 0)
+        return dlist_init();
+    if (index >= list->size)
+    {
+        return NULL;
+    }
+
+    struct dlist *new = dlist_init();
+    if (new == NULL)
+        return NULL;
+    new->size = list->size - index;
+    list->size = index;
+
+    struct dlist_item *i;
+    for (i = list->head; index; index--, i = i->next)
+    {
+        continue;
+    }
+
+    new->head = i;
+    new->tail = list->tail;
+    list->tail = i->prev;
+    if (i->prev)
+    {
+        i->prev->next = NULL;
+    }
+    else
+    {
+        list->head = NULL;
+    }
+    i->prev = NULL;
+    return new;
+}
+
+void dlist_concat(struct dlist *list1, struct dlist *list2)
+{
+    if (list2->head == NULL)
+        return;
+    if (list1->tail == NULL)
+    {
+        list1->head = list2->head;
+        list1->tail = list2->tail;
+        list1->size = list2->size;
+        return;
+    }
+
+    list1->tail->next = list2->head;
+    list2->head->prev = list1->tail;
+    list1->tail = list2->tail;
+    list1->size += list2->size;
+    list2->size = 0;
+    list2->head = NULL;
+    list2->tail = NULL;
+}
diff --git a/graphs/piscine/dlist/dlist-4.c b/graphs/piscine/dlist/dlist-4.c
new file mode 100644
index 0000000..9ed7aaa
--- /dev/null
+++ b/graphs/piscine/dlist/dlist-4.c
@@ -0,0 +1,97 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dlist.h"
+
+size_t max(size_t a, size_t b)
+{
+    if (a >= b)
+    {
+        return a;
+    }
+    return b;
+}
+
+size_t min(size_t a, size_t b)
+{
+    if (a <= b)
+    {
+        return a;
+    }
+    return b;
+}
+
+size_t min_3(size_t a, size_t b, size_t c)
+{
+    if (a <= b)
+    {
+        if (a <= c)
+        {
+            return a;
+        }
+        return c;
+    }
+    else
+    {
+        if (b <= c)
+        {
+            return b;
+        }
+        return c;
+    }
+}
+
+size_t my_strlen(const int *s)
+{
+    size_t i;
+    for (i = 0; s[i] != -1; i++)
+    {
+        continue;
+    }
+    return i;
+}
+
+size_t levenshtein(const int *s1, const int *s2)
+{
+    size_t l1 = my_strlen(s1);
+    size_t l2 = my_strlen(s2);
+    if (min(l1, l2) == 0)
+    {
+        return max(l1, l2);
+    }
+
+    if (s1[0] == s2[0])
+    {
+        return levenshtein(s1 + 1, s2 + 1);
+    }
+
+    size_t lev1 = levenshtein(s1 + 1, s2);
+    size_t lev2 = levenshtein(s1, s2 + 1);
+    size_t lev3 = levenshtein(s1 + 1, s2 + 1);
+
+    return 1 + min_3(lev1, lev2, lev3);
+}
+
+int *to_str(const struct dlist *l)
+{
+    int *res = malloc((l->size + 1) * sizeof(int));
+    res[l->size] = -1;
+    size_t j = 0;
+    for (struct dlist_item *i = l->head; i; i = i->next, j++)
+    {
+        res[j] = i->data;
+    }
+    return res;
+}
+
+unsigned int dlist_levenshtein(const struct dlist *list1,
+                               const struct dlist *list2)
+{
+    int *l1 = to_str(list1);
+    int *l2 = to_str(list2);
+
+    unsigned int res = levenshtein(l1, l2);
+    free(l1);
+    free(l2);
+    return res;
+}
diff --git a/graphs/piscine/dlist/dlist.h b/graphs/piscine/dlist/dlist.h
new file mode 100644
index 0000000..97cde1a
--- /dev/null
+++ b/graphs/piscine/dlist/dlist.h
@@ -0,0 +1,44 @@
+#ifndef DLIST_H
+#define DLIST_H
+
+#include <stddef.h>
+
+struct dlist_item
+{
+    int data;
+    struct dlist_item *next;
+    struct dlist_item *prev;
+};
+
+struct dlist
+{
+    size_t size;
+    struct dlist_item *head;
+    struct dlist_item *tail;
+};
+
+// Threshold 1
+struct dlist *dlist_init(void);
+int dlist_push_front(struct dlist *list, int element);
+void dlist_print(const struct dlist *list);
+int dlist_push_back(struct dlist *list, int element);
+size_t dlist_size(const struct dlist *list);
+
+// Threshold 2
+int dlist_get(const struct dlist *list, size_t index);
+int dlist_insert_at(struct dlist *list, int element, size_t index);
+int dlist_find(const struct dlist *list, int element);
+int dlist_remove_at(struct dlist *list, size_t index);
+void dlist_clear(struct dlist *list);
+
+// Threshold 3
+void dlist_map_square(struct dlist *list);
+void dlist_reverse(struct dlist *list);
+struct dlist *dlist_split_at(struct dlist *list, size_t index);
+void dlist_concat(struct dlist *list1, struct dlist *list2);
+
+// Threshold 4
+unsigned int dlist_levenshtein(const struct dlist *list1,
+                               const struct dlist *list2);
+
+#endif /* !DLIST_H */