Fixing merge compilation error, Added ft_mergesort

7 files changed, 151 insertions, 20 deletions

diff --git a/include/libft_algo.h b/include/libft_algo.h
index 4dc3353..14496dd 100644
--- a/include/libft_algo.h
+++ b/include/libft_algo.h
@@ -6,27 +6,41 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 07:22:57 by cacharle          #+#    #+#             */
-/*   Updated: 2020/02/10 02:21:47 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/10 03:04:17 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #ifndef LIBFT_ALGO_H
 # define LIBFT_ALGO_H
 
-typedef int	t_bool;
+# include <stdlib.h>
+# include <stddef.h>
+# include "libft_mem.h"
+# include "libft_types.h"
 
 typedef struct
 {
-	int		lo;
-	int		hi;
-}			t_ftrange;
+	int			lo;
+	int			hi;
+}				t_ftrange;
 
-typedef int	(*t_ftcompar_func)(const void*, const void*);
+struct			s_merge_sorted_arrays
+{
+	void		*base;
+	void		*left;
+	void		*right;
+};
+
+typedef int		(*t_ftcompar_func)(const void*, const void*);
 
-t_bool		ft_is_set(void *base, size_t nel, size_t width,
+t_ftbool		ft_is_set(void *base, size_t nel, size_t width,
 						t_ftcompar_func compar);
-void		ft_qsort(void *base, size_t nel, size_t width,
+int				ft_compar_int(const void *a, const void *b);
+void			ft_qsort(void *base, size_t nel, size_t width,
 						t_ftcompar_func compar);
-int			ft_compar_int(const void *a, const void *b);
+int				ft_mergesort(void *base, size_t nel, size_t width,
+					int (*compar)(const void *, const void *));
+int				ft_heapsort(void *base, size_t nel, size_t width,
+					int (*compar)(const void *, const void *));
 
 #endif
diff --git a/include/libft_mem.h b/include/libft_mem.h
index 5465d72..af3f4b5 100644
--- a/include/libft_mem.h
+++ b/include/libft_mem.h
@@ -6,7 +6,7 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/31 10:35:57 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/31 10:35:59 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/10 02:55:38 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -21,6 +21,7 @@ void				*ft_memmove(void *dst, const void *src, size_t len);
 void				*ft_memchr(const void *s, int c, size_t n);
 int					ft_memcmp(const void *s1, const void *s2, size_t n);
 void				*ft_calloc(size_t count, size_t size);
+void				ft_memswap(void *a, void *b, size_t size);
 
 /*
 ** bloat ?
diff --git a/src/algo/ft_heapsort.c b/src/algo/ft_heapsort.c
new file mode 100644
index 0000000..afd395d
--- /dev/null
+++ b/src/algo/ft_heapsort.c
@@ -0,0 +1,50 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_heapsort.c                                      :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/02/10 02:59:22 by cacharle          #+#    #+#             */
+/*   Updated: 2020/02/10 03:57:50 by cacharle         ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+/* static void	st_build_max_heap(void *base, size_t nel, size_t width, */
+/* 				int (*compar)(const void *, const void *)) */
+/* { */
+/* 	int	i; */
+/*  */
+/* 	i = 1; */
+/* 	while (i < nel) */
+/* 	{ */
+/* 		compar(base + i * width, base + 2 * i * width) */
+/*  */
+/* 		i++; */
+/* 	} */
+/* } */
+/*  */
+/* static void	st_heapify(void *base, size_t nel, size_t width, */
+/* 				int (*compar)(const void *, const void *)) */
+/* { */
+/*  */
+/* } */
+
+int		ft_heapsort(void *base, size_t nel, size_t width,
+				int (*compar)(const void *, const void *))
+{
+	/* size_t	i; */
+    /*  */
+	/* if (nel < 2) */
+	/* 	return (0); */
+	/* st_build_max_heap(base, nel, width, compar); */
+	/* i = -1; */
+	/* while (++i < nel) */
+	/* { */
+	/* 	ft_memswap(base, base + (nel - i - 1) * width); */
+	/* 	st_heapify(base, nel - i - 1, width, compar); */
+	/* } */
+	return (0);
+}
diff --git a/src/algo/ft_is_set.c b/src/algo/ft_is_set.c
index 8e45b49..3e7ae31 100644
--- a/src/algo/ft_is_set.c
+++ b/src/algo/ft_is_set.c
@@ -6,13 +6,14 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 07:17:15 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/19 08:21:12 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/10 02:51:41 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_algo.h"
 
-t_bool	ft_is_set(void *base, size_t nel, size_t width,
+t_ftbool	ft_is_set(void *base, size_t nel, size_t width,
 						t_ftcompar_func compar)
 {
 	size_t	i;
diff --git a/src/algo/ft_mergesort.c b/src/algo/ft_mergesort.c
new file mode 100644
index 0000000..5af248e
--- /dev/null
+++ b/src/algo/ft_mergesort.c
@@ -0,0 +1,65 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_mergesort.c                                     :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/02/10 02:26:41 by cacharle          #+#    #+#             */
+/*   Updated: 2020/02/10 02:59:10 by cacharle         ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+static int	st_mergesort_error(void *left, void *right)
+{
+	free(left);
+	free(right);
+	return (-1);
+}
+
+static void	st_merge_sorted(struct s_merge_sorted_arrays *arrays, size_t nel,
+				size_t width, int (*compar)(const void *, const void *))
+{
+	size_t	li;
+	size_t	ri;
+
+	li = 0;
+	ri = 0;
+	while (li < nel / 2 && ri < nel - nel / 2)
+	{
+		if (compar(arrays->left + li * width, arrays->right + ri * width) < 0)
+			ft_memcpy(arrays->base, arrays->left + li++ * width, width);
+		else
+			ft_memcpy(arrays->base, arrays->right + ri++ * width, width);
+	}
+	while (li < nel / 2)
+		ft_memcpy(arrays->base, arrays->left + li++ * width, width);
+	while (ri < nel - nel / 2)
+		ft_memcpy(arrays->base, arrays->right + ri++ * width, width);
+}
+
+int			ft_mergesort(void *base, size_t nel, size_t width,
+				int (*compar)(const void *, const void *))
+{
+	size_t							mid;
+	struct s_merge_sorted_arrays	arrays;
+
+	if (nel < 2)
+		return (0);
+	mid = nel / 2;
+	if ((arrays.left = malloc(mid * width)) == NULL)
+		return (-1);
+	if ((arrays.right = malloc((nel - mid) * width)) == NULL)
+		return (st_mergesort_error(arrays.left, NULL));
+	ft_memcpy(arrays.left, base, mid * width);
+	ft_memcpy(arrays.right, base, (nel - mid) * width);
+	if (ft_mergesort(arrays.left, mid, width, compar) == -1)
+		return (st_mergesort_error(arrays.left, arrays.right));
+	if (ft_mergesort(arrays.right, nel - mid, width, compar) == -1)
+		return (st_mergesort_error(arrays.left, arrays.right));
+	arrays.base = base;
+	st_merge_sorted(&arrays, nel, width, compar);
+	return (0);
+}
diff --git a/src/algo/ft_qsort.c b/src/algo/ft_qsort.c
index 8c125a1..9bcfcdf 100644
--- a/src/algo/ft_qsort.c
+++ b/src/algo/ft_qsort.c
@@ -6,11 +6,11 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 07:25:51 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/19 08:28:32 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/10 02:55:14 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
-#include "libft.h"
+#include "libft_algo.h"
 
 static t_ftrange	ft_range_new(int lo, int hi)
 {
diff --git a/src/mem/ft_memswap.c b/src/mem/ft_memswap.c
index 4abaa83..8661fda 100644
--- a/src/mem/ft_memswap.c
+++ b/src/mem/ft_memswap.c
@@ -6,7 +6,7 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 07:56:43 by cacharle          #+#    #+#             */
-/*   Updated: 2020/01/19 08:22:17 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/10 02:55:52 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -14,12 +14,12 @@
 
 void	ft_memswap(void *a, void *b, size_t size)
 {
-	t_byte	tmp;
-	t_byte	*cast_a;
-	t_byte	*cast_b;
+	t_ftbyte	tmp;
+	t_ftbyte	*cast_a;
+	t_ftbyte	*cast_b;
 
-	cast_a = (t_byte*)a;
-	cast_b = (t_byte*)b;
+	cast_a = (t_ftbyte*)a;
+	cast_b = (t_ftbyte*)b;
 	while (size-- > 0)
 	{
 		tmp = cast_a[size];