diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/algo/ft_compar_int.c | 18 | ||||
| -rw-r--r-- | src/algo/ft_is_set.c | 31 | ||||
| -rw-r--r-- | src/algo/ft_qsort.c | 64 | ||||
| -rw-r--r-- | src/mem/ft_memswap.c | 29 |
4 files changed, 142 insertions, 0 deletions
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 <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* 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 <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* 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 <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* 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 <marvin@42.fr> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* 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; + } +} |