From 6c7ebe29b42f6d1983c09577d9a83ffad2b205c4 Mon Sep 17 00:00:00 2001
From: Lukas Jiriste <ljiriste@student.42prague.com>
Date: Sat, 24 Feb 2024 11:18:02 +0100
Subject: [PATCH] Fix "off by one" errors, fix find_target_ind

The function find_target_ind used (malfunctioning) binary search,
but that proved to be more difficult so I reimplemented it using
basic linear search.
---
 src/push.c | 70 ++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 49 insertions(+), 21 deletions(-)

diff --git a/src/push.c b/src/push.c
index e8893dc..c3b67a9 100644
--- a/src/push.c
+++ b/src/push.c
@@ -6,7 +6,7 @@
 /*   By: ljiriste <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/01/24 13:17:32 by ljiriste          #+#    #+#             */
-/*   Updated: 2024/02/23 11:58:08 by ljiriste         ###   ########.fr       */
+/*   Updated: 2024/02/24 11:15:29 by ljiriste         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -54,7 +54,7 @@ size_t	find_minind(t_stack *s)
 	i = 0;
 	while (i < s->stack.size)
 	{
-		if (min > stack_top(s))
+		if (min >= stack_top(s))
 		{
 			minind = i;
 			min = stack_top(s);
@@ -65,28 +65,56 @@ size_t	find_minind(t_stack *s)
 	return (minind);
 }
 
+int	max_or_min(t_stack *stack, int val)
+{
+	int		max;
+	int		min;
+	size_t	i;
+
+	i = 0;
+	max = INT_MIN;
+	min = INT_MAX;
+	while (i < stack->stack.size)
+	{
+		if (stack_top(stack) > max)
+		{
+			max = stack_top(stack);
+		}
+		if (stack_top(stack) < min)
+		{
+			min = stack_top(stack);
+		}
+		stack_rotate(stack, 1);
+		++i;
+	}
+	return (val < min || val > max);
+}
+
 size_t	find_target_ind(t_stack *stack, int	val)
 {
-	size_t			cur_step;
-	const size_t	initial_ind = stack->ind;
-	size_t			res;
-
-	stack_rotate(stack, find_minind(stack));
-	cur_step = stack->stack.size / 2 + 1;
-	stack_rotate(stack, cur_step);
-	while (cur_step > 1)
+	size_t		i;
+	size_t		res;
+	const int	minind = find_minind(stack);
+
+	i = 0;
+	if (max_or_min(stack, val))
+		return (minind);
+	while (i < stack->stack.size && val < stack_top(stack))
 	{
-		cur_step /= 2;
-		if (stack_top(stack) < val)
-			stack_rotate(stack, cur_step);
-		else
-			stack_rotate(stack, -cur_step);
+		stack_rotate(stack, 1);
+		++i;
+	}
+	while (i < stack->stack.size && val > stack_top(stack))
+	{
+		stack_rotate(stack, 1);
+		++i;
+	}
+	res = i;
+	while (i < stack->stack.size)
+	{
+		stack_rotate(stack, 1);
+		++i;
 	}
-	if (stack->ind > initial_ind)
-		res = (stack->ind - initial_ind);
-	else
-		res = stack->stack.size + stack->ind - initial_ind;
-	stack->ind = initial_ind;
 	return (res);
 }
 
@@ -178,7 +206,7 @@ void	rotate_a_to_sort(t_stacks *s)
 	t_action	*print_action;
 
 	minind = find_minind(&s->a);
-	if (minind < s->a.stack.size / 2)
+	if (minind <= s->a.stack.size / 2)
 		print_action = print_rotate;
 	else
 	{
-- 
2.30.2