From 6d1957b25d4e1e3831d7d23ae1e130c44c94795d Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Tue, 5 Mar 2024 10:47:39 +0100 Subject: [PATCH] Refactor code to comply with the 42 Norm --- Makefile | 1 + src/circ_helpers.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++ src/circular_lis.c | 16 +++--------- src/helpers.c | 40 +---------------------------- src/push_swap.h | 6 +++-- 5 files changed, 73 insertions(+), 54 deletions(-) create mode 100644 src/circ_helpers.c diff --git a/Makefile b/Makefile index 644f05d..06a89f0 100644 --- a/Makefile +++ b/Makefile @@ -35,6 +35,7 @@ PUSHSOURCES := push.c \ prepare.c \ find.c \ circular_lis.c \ + circ_helpers.c \ special_a.c \ PUSHSOURCES := $(addprefix $(PUSHSRCDIR)/, $(PUSHSOURCES)) diff --git a/src/circ_helpers.c b/src/circ_helpers.c new file mode 100644 index 0000000..dd2545d --- /dev/null +++ b/src/circ_helpers.c @@ -0,0 +1,64 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* circ_helpers.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/03/05 10:36:20 by ljiriste #+# #+# */ +/* Updated: 2024/03/05 10:41:33 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "push_swap.h" +#include "libft.h" +#include + +void rotate_lis_to_start(t_stack *lis, t_stack *stack, size_t init_ind) +{ + while (stack->ind != init_ind) + { + if (stack_top(lis) == stack_top(stack)) + stack_rotate(lis, 1); + stack_rotate(stack, 1); + } + return ; +} + +static int unrolled_stack_access(t_stack *stack, size_t ind) +{ + int res; + + if (ind > SIZE_MAX - stack->ind) + ind -= SIZE_MAX; + ind += stack->ind; + ind %= stack->stack.size; + res = *(int *)ft_vec_access(&stack->stack, ind); + return (res); +} + +size_t binary_search(t_vec *sorted, t_stack *stack, size_t val_ind) +{ + const int val = unrolled_stack_access(stack, val_ind); + size_t hi; + size_t lo; + size_t mid; + + lo = 0; + hi = sorted->size; + mid = lo + (hi - lo) / 2; + while (lo != hi) + { + if (val > unrolled_stack_access(stack, + *(size_t *)ft_vec_access(sorted, mid))) + { + lo = mid + 1; + } + else + { + hi = mid; + } + mid = lo + (hi - lo) / 2; + } + return (mid); +} diff --git a/src/circular_lis.c b/src/circular_lis.c index 0d229c6..5f38880 100644 --- a/src/circular_lis.c +++ b/src/circular_lis.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/02/27 15:18:21 by ljiriste #+# #+# */ -/* Updated: 2024/03/02 12:48:30 by ljiriste ### ########.fr */ +/* Updated: 2024/03/05 10:41:33 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -67,17 +67,6 @@ static t_arr_stat get_lis_loop(t_stack *stack, t_vec *inds_of_lowest, return (res); } -static void rotate_lis_to_start(t_stack *lis, t_stack *stack, size_t init_ind) -{ - while (stack->ind != init_ind) - { - if (stack_top(lis) == stack_top(stack)) - stack_rotate(lis, 1); - stack_rotate(stack, 1); - } - return ; -} - /* This is the algorithm for finding the longest increasing subsequence found on wikipedia adjusted for circular sequences (stack).*/ static t_arr_stat get_lis(t_stack *lis, t_stack *stack, size_t ind) @@ -93,7 +82,8 @@ static t_arr_stat get_lis(t_stack *lis, t_stack *stack, size_t ind) res = get_lis_loop(stack, &inds_of_lowest, &inds_of_predecessor); if (res == success) { - res = reconstruct_lis(lis, stack, &inds_of_lowest, &inds_of_predecessor); + res = reconstruct_lis(lis, stack, &inds_of_lowest, + &inds_of_predecessor); if (res == success) rotate_lis_to_start(lis, stack, stack_init_ind); } diff --git a/src/helpers.c b/src/helpers.c index 218bb47..b7c65fe 100644 --- a/src/helpers.c +++ b/src/helpers.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/02/22 14:22:08 by ljiriste #+# #+# */ -/* Updated: 2024/03/01 10:07:27 by ljiriste ### ########.fr */ +/* Updated: 2024/03/05 10:39:46 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -72,41 +72,3 @@ size_t cost(t_stacks *s, const size_t b_plus, const size_t a_plus) res = ft_mins(res, a_minus + b_plus); return (res); } - -static int unrolled_stack_access(t_stack *stack, size_t ind) -{ - int res; - - if (ind > SIZE_MAX - stack->ind) - ind -= SIZE_MAX; - ind += stack->ind; - ind %= stack->stack.size; - res = *(int *)ft_vec_access(&stack->stack, ind); - return (res); -} - -size_t binary_search(t_vec *sorted, t_stack *stack, size_t val_ind) -{ - const int val = unrolled_stack_access(stack, val_ind); - size_t hi; - size_t lo; - size_t mid; - - lo = 0; - hi = sorted->size; - mid = lo + (hi - lo) / 2; - while (lo != hi) - { - if (val > unrolled_stack_access(stack, - *(size_t *)ft_vec_access(sorted, mid))) - { - lo = mid + 1; - } - else - { - hi = mid; - } - mid = lo + (hi - lo) / 2; - } - return (mid); -} diff --git a/src/push_swap.h b/src/push_swap.h index b8accd6..49c211a 100644 --- a/src/push_swap.h +++ b/src/push_swap.h @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/01/24 12:13:51 by ljiriste #+# #+# */ -/* Updated: 2024/03/01 10:22:32 by ljiriste ### ########.fr */ +/* Updated: 2024/03/05 10:41:33 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -69,11 +69,13 @@ void stack_pop(t_stack *s); int stack_top(t_stack *s); t_arr_stat get_circular_lis(t_stack *lis, t_stack *stack); +size_t binary_search(t_vec *sorted, t_stack *stack, size_t val_ind); +void rotate_lis_to_start(t_stack *lis, t_stack *stack, size_t init_ind); + int is_sorted(t_stack *s); int parse(int argc, char **argv, t_stack *s); void prepare_stacks(t_stacks *s, size_t ind_a, size_t ind_b); size_t cost(t_stacks *s, const size_t b_plus, const size_t a_plus); -size_t binary_search(t_vec *sorted, t_stack *stack, size_t val_ind); size_t find_best(t_stacks *s, t_vec *target_a_indeces); size_t find_target_ind(t_stack *stack, int val); size_t find_minind(t_stack *s); -- 2.30.2