From a5b068767440327f910dfa815be12ff4c0d94309 Mon Sep 17 00:00:00 2001 From: Charles Date: Sun, 19 Jan 2020 08:30:03 +0100 Subject: Added algo functions ft_qsort, ft_is_set, ft_memswap, ft_compar_int --- Makefile | 4 ++- include/ft_algo.h | 32 ++++++++++++++++++++++++ include/libft.h | 6 ++--- src/algo/ft_compar_int.c | 18 ++++++++++++++ src/algo/ft_is_set.c | 31 +++++++++++++++++++++++ src/algo/ft_qsort.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++ src/mem/ft_memswap.c | 29 ++++++++++++++++++++++ 7 files changed, 180 insertions(+), 4 deletions(-) create mode 100644 include/ft_algo.h create mode 100644 src/algo/ft_compar_int.c create mode 100644 src/algo/ft_is_set.c create mode 100644 src/algo/ft_qsort.c create mode 100644 src/mem/ft_memswap.c diff --git a/Makefile b/Makefile index fbe4ee7..97138dc 100644 --- a/Makefile +++ b/Makefile @@ -6,13 +6,15 @@ # By: cacharle +#+ +:+ +#+ # # +#+#+#+#+#+ +#+ # # Created: 2019/10/08 15:45:53 by cacharle #+# #+# # -# Updated: 2020/01/15 09:54:56 by cacharle ### ########.fr # +# Updated: 2020/01/19 08:17:08 by cacharle ### ########.fr # # # # **************************************************************************** # LIB = ar rcs RM = rm -f +INCLUDE_DIR = include + CC = gcc CCFLAGS = -I$(INCLUDE_DIR) -Wall -Wextra -Werror diff --git a/include/ft_algo.h b/include/ft_algo.h new file mode 100644 index 0000000..4175cb5 --- /dev/null +++ b/include/ft_algo.h @@ -0,0 +1,32 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_algo.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 07:22:57 by cacharle #+# #+# */ +/* Updated: 2020/01/19 08:27:44 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef FT_ALGO_H +# define FT_ALGO_H + +typedef int t_bool; + +typedef struct +{ + int lo; + int hi; +} t_ftrange; + +typedef int (*t_ftcompar_func)(const void*, const void*); + +t_bool 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, + t_ftcompar_func compar); +int ft_compar_int(const void *a, const void *b); + +#endif diff --git a/include/libft.h b/include/libft.h index c2215ed..888ac8c 100644 --- a/include/libft.h +++ b/include/libft.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/10/07 09:45:02 by cacharle #+# #+# */ -/* Updated: 2020/01/15 12:52:37 by cacharle ### ########.fr */ +/* Updated: 2020/01/19 08:20:37 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -18,11 +18,10 @@ # include # include # include - # include - # include "get_next_line.h" +# include "ft_algo.h" # ifdef __linux__ # include @@ -118,6 +117,7 @@ int ft_memcmp(const void *s1, const void *s2, size_t n); void *ft_memalloc(size_t size); void ft_memdel(void **ap); void *ft_calloc(size_t count, size_t size); +void ft_memswap(void *a, void *b, size_t size); /* ** str diff --git a/src/algo/ft_compar_int.c b/src/algo/ft_compar_int.c new file mode 100644 index 0000000..848dc71 --- /dev/null +++ b/src/algo/ft_compar_int.c @@ -0,0 +1,18 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_compar_int.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 08:24:43 by cacharle #+# #+# */ +/* Updated: 2020/01/19 08:27:38 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" + +int ft_compar_int(const void *a, const void *b) +{ + return (*(int*)a - *(int*)b); +} diff --git a/src/algo/ft_is_set.c b/src/algo/ft_is_set.c new file mode 100644 index 0000000..8e45b49 --- /dev/null +++ b/src/algo/ft_is_set.c @@ -0,0 +1,31 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_is_set.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 07:17:15 by cacharle #+# #+# */ +/* Updated: 2020/01/19 08:21:12 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" + +t_bool ft_is_set(void *base, size_t nel, size_t width, + t_ftcompar_func compar) +{ + size_t i; + + if (nel < 2) + return (TRUE); + ft_qsort(base, nel, width, compar); + i = 0; + while (i < nel - 1) + { + if (compar(base + (i * width), base + ((i + 1) * width)) == 0) + return (FALSE); + i++; + } + return (TRUE); +} diff --git a/src/algo/ft_qsort.c b/src/algo/ft_qsort.c new file mode 100644 index 0000000..8c125a1 --- /dev/null +++ b/src/algo/ft_qsort.c @@ -0,0 +1,64 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_qsort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 07:25:51 by cacharle #+# #+# */ +/* Updated: 2020/01/19 08:28:32 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" + +static t_ftrange ft_range_new(int lo, int hi) +{ + t_ftrange range; + + range.lo = lo; + range.hi = hi; + return (range); +} + +static int ft_qsort_partition(void *base, t_ftrange range, + size_t width, t_ftcompar_func compar) +{ + void *pivot; + int p; + int i; + + pivot = base + (range.hi * width); + p = range.lo; + i = range.lo - 1; + while (++i < range.hi) + { + if (compar(base + (i * width), pivot) < 0) + { + ft_memswap(base + (i * width), base + (p * width), width); + p++; + } + } + ft_memswap(pivot, base + (p * width), width); + return (p); +} + +static void ft_qsort_rec(void *base, t_ftrange range, + size_t width, t_ftcompar_func compar) +{ + int pivot; + + if (range.lo >= range.hi) + return ; + pivot = ft_qsort_partition(base, range, width, compar); + ft_qsort_rec(base, ft_range_new(range.lo, pivot - 1), width, compar); + ft_qsort_rec(base, ft_range_new(pivot + 1, range.hi), width, compar); +} + +void ft_qsort(void *base, size_t nel, size_t width, + t_ftcompar_func compar) +{ + if (width == 0 || nel < 2) + return ; + ft_qsort_rec(base, ft_range_new(0, nel - 1), width, compar); +} diff --git a/src/mem/ft_memswap.c b/src/mem/ft_memswap.c new file mode 100644 index 0000000..4abaa83 --- /dev/null +++ b/src/mem/ft_memswap.c @@ -0,0 +1,29 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_memswap.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/01/19 07:56:43 by cacharle #+# #+# */ +/* Updated: 2020/01/19 08:22:17 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" + +void ft_memswap(void *a, void *b, size_t size) +{ + t_byte tmp; + t_byte *cast_a; + t_byte *cast_b; + + cast_a = (t_byte*)a; + cast_b = (t_byte*)b; + while (size-- > 0) + { + tmp = cast_a[size]; + cast_a[size] = cast_b[size]; + cast_b[size] = tmp; + } +} -- cgit