Added ft_bsearch, ft_lsearch, ft_lfind

4 files changed, 106 insertions, 15 deletions

diff --git a/include/libft_algo.h b/include/libft_algo.h
index 65308b8..7223e7b 100644
--- a/include/libft_algo.h
+++ b/include/libft_algo.h
@@ -6,7 +6,7 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/01/19 07:22:57 by cacharle          #+#    #+#             */
-/*   Updated: 2020/02/10 05:17:39 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/10 05:58:26 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -18,30 +18,42 @@
 # include "libft_mem.h"
 # include "libft_types.h"
 
+typedef int			(*t_ftcompar_func)(const void*, const void*);
+
 typedef struct
 {
-	int			lo;
-	int			hi;
-}				t_ftrange;
+	int				lo;
+	int				hi;
+}					t_ftrange;
 
-struct			s_merge_sorted_arrays
+struct				s_merge_sorted_arrays
 {
-	void		*base;
-	void		*left;
-	void		*right;
+	void			*base;
+	void			*left;
+	void			*right;
 };
 
-typedef int		(*t_ftcompar_func)(const void*, const void*);
+typedef struct		s_ft_search_const
+{
+	const void		*key;
+	t_ftcompar_func	compar;
+}					t_ftsearch_const;
 
-t_ftbool		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);
-int				ft_compar_int(const void *a, const void *b);
-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_mergesort(void *base, size_t nel, size_t width,
+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					ft_heapsort(void *base, size_t nel, size_t width,
 					int (*compar)(const void *, const void *));
-void			ft_reverse(void *base, size_t nel, size_t width);
+void				ft_reverse(void *base, size_t nel, size_t width);
+void				*ft_bsearch(const void *base, size_t nel, size_t width,
+							t_ftsearch_const *consts);
+void				*ft_lfind(const void *base, size_t *nelp, size_t width,
+						t_ftsearch_const *consts);
+void				*ft_lsearch(const void *base, size_t *nelp, size_t width,
+						t_ftsearch_const *consts);
 
 #endif
diff --git a/src/algo/ft_bsearch.c b/src/algo/ft_bsearch.c
new file mode 100644
index 0000000..8066479
--- /dev/null
+++ b/src/algo/ft_bsearch.c
@@ -0,0 +1,28 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_bsearch.c                                       :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/02/10 05:29:05 by cacharle          #+#    #+#             */
+/*   Updated: 2020/02/10 05:43:18 by cacharle         ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+void	*ft_bsearch(const void *base, size_t nel, size_t width,
+							t_ftsearch_const *consts)
+{
+	void	*found;
+
+	if ((consts->compar)(consts->key, base + (nel / 2) * width) == 0)
+		return ((void*)base + (nel / 2) * width);
+	if ((found = ft_bsearch(base, nel / 2, width, consts)) != NULL)
+		return (found);
+	if ((found = ft_bsearch(base + (nel / 2) * width, nel - nel / 2,
+					width, consts)) != NULL)
+		return (found);
+	return (NULL);
+}
diff --git a/src/algo/ft_lfind.c b/src/algo/ft_lfind.c
new file mode 100644
index 0000000..8538f50
--- /dev/null
+++ b/src/algo/ft_lfind.c
@@ -0,0 +1,28 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_lfind.c                                         :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/02/10 05:49:19 by cacharle          #+#    #+#             */
+/*   Updated: 2020/02/10 05:58:19 by cacharle         ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+void	*ft_lfind(const void *base, size_t *nelp, size_t width,
+				t_ftsearch_const *consts)
+{
+	size_t	i;
+
+	i = 0;
+	while (i < *nelp)
+	{
+		if ((consts->compar)(consts->key, base + i * width) == 0)
+			return ((void*)base + i * width);
+		i++;
+	}
+	return (NULL);
+}
diff --git a/src/algo/ft_lsearch.c b/src/algo/ft_lsearch.c
new file mode 100644
index 0000000..4c77bca
--- /dev/null
+++ b/src/algo/ft_lsearch.c
@@ -0,0 +1,23 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_lsearch.c                                       :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/02/10 05:53:57 by cacharle          #+#    #+#             */
+/*   Updated: 2020/02/10 05:59:33 by cacharle         ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_algo.h"
+
+void	*ft_lsearch(const void *base, size_t *nelp, size_t width,
+				t_ftsearch_const *consts)
+{
+	void	*found;
+
+	if ((found = ft_lfind(base, nelp, width, consts)) != NULL)
+		return (found);
+	return (ft_memcpy((void*)base + (*nelp)++ * width, consts->key, width));
+}