From 8f76bcb706118ed31654204f863c9398f6f18b8a Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Sat, 2 Mar 2024 12:59:54 +0100 Subject: [PATCH] Fix the usage of lis The lis was created in such a way, that the top may not have been the first number of the stack that is part of the found lis. This has been fixed by synchronously rotating lis and stack to the initial rotation of stack. --- src/circular_lis.c | 32 ++++++++++++++++++++++++-------- 1 file changed, 24 insertions(+), 8 deletions(-) diff --git a/src/circular_lis.c b/src/circular_lis.c index d2fa385..0d229c6 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/01 10:07:26 by ljiriste ### ########.fr */ +/* Updated: 2024/03/02 12:48:30 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -67,6 +67,17 @@ 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) @@ -81,10 +92,13 @@ static t_arr_stat get_lis(t_stack *lis, t_stack *stack, size_t ind) stack_rotate(stack, ind); res = get_lis_loop(stack, &inds_of_lowest, &inds_of_predecessor); if (res == success) - 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); + } ft_vec_free(&inds_of_lowest, NULL); ft_vec_free(&inds_of_predecessor, NULL); - stack->ind = stack_init_ind; return (res); } @@ -104,10 +118,11 @@ static size_t lis_length(t_stack *stack) t_arr_stat get_circular_lis(t_stack *lis, t_stack *stack) { - size_t max; - size_t max_ind; - size_t i; - size_t len_i; + size_t max; + size_t max_ind; + size_t i; + size_t len_i; + t_arr_stat res; max = 0; i = 0; @@ -122,5 +137,6 @@ t_arr_stat get_circular_lis(t_stack *lis, t_stack *stack) ++i; stack_rotate(stack, 1); } - return (get_lis(lis, stack, max_ind)); + res = get_lis(lis, stack, max_ind); + return (res); } -- 2.30.2