From 61926f8658cddccf59b84be222f48edc1e7b8718 Mon Sep 17 00:00:00 2001
From: Dominik Kaiser <dkaiser@3-F-6.42heilbronn.de>
Date: Sat, 27 Apr 2024 16:30:16 +0200
Subject: [PATCH] Add sorting for small stacks

---
 Makefile           |  2 +-
 cmd_optimization.c |  3 +-
 command_handling.c | 70 +++++++++++++++++-----------------
 push_swap.h        |  4 +-
 sort_few.c         | 95 ++++++++++++++++++++++++++++++++++++++++++++++
 sorting.c          | 16 ++------
 6 files changed, 139 insertions(+), 51 deletions(-)
 create mode 100644 sort_few.c

diff --git a/Makefile b/Makefile
index 6a49913..5c4c8c9 100644
--- a/Makefile
+++ b/Makefile
@@ -5,7 +5,7 @@ LIBFT = libft
 CC = cc
 CFLAGS = -Wall -Wextra -Werror
 
-SRC_FILES = main.c ft_atol.c input_handling.c stack_utils.c command_handling.c sorting.c stack_optimization.c cmd_optimization.c
+SRC_FILES = main.c ft_atol.c input_handling.c stack_utils.c command_handling.c sorting.c sort_few.c stack_optimization.c cmd_optimization.c
 OBJ_FILES = $(SRC_FILES:%.c=%.o)
 
 LIB_DIR = $(LIBFT)
diff --git a/cmd_optimization.c b/cmd_optimization.c
index b310f34..b3239a4 100644
--- a/cmd_optimization.c
+++ b/cmd_optimization.c
@@ -6,7 +6,7 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 16:42:34 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/26 15:52:23 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/27 13:51:08 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -93,4 +93,5 @@ void	optimize_commands(t_psdata *data)
 	optimize_redundant(data, PA, PB);
 	optimize_redundant(data, RB, RRB);
 	optimize_two_stack_ops(data, RA, RB, RR);
+	optimize_two_stack_ops(data, SA, SB, SS);
 }
diff --git a/command_handling.c b/command_handling.c
index 7599bdf..7919d4e 100644
--- a/command_handling.c
+++ b/command_handling.c
@@ -6,7 +6,7 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 14:38:47 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/26 13:55:07 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/27 13:38:41 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -31,40 +31,6 @@ static int	add_cmd_to_queue(t_list **cmds, enum e_pscmd cmd)
 	return (0);
 }
 
-static void	run_for_both(t_stack *stack_a, t_stack *stack_b,
-		void (*f)(t_stack *))
-{
-	f(stack_a);
-	f(stack_b);
-}
-
-void	run_command(t_psdata *data, enum e_pscmd cmd)
-{
-	if (cmd == SA)
-		stack_swap(data->a);
-	else if (cmd == SB)
-		stack_swap(data->b);
-	else if (cmd == SS)
-		run_for_both(data->a, data->b, stack_swap);
-	else if (cmd == PA)
-		stack_push(data->a, data->b);
-	else if (cmd == PB)
-		stack_push(data->b, data->a);
-	else if (cmd == RA)
-		stack_rotate(data->a);
-	else if (cmd == RB)
-		stack_rotate(data->b);
-	else if (cmd == RR)
-		run_for_both(data->a, data->b, stack_rotate);
-	else if (cmd == RRA)
-		stack_rrotate(data->a);
-	else if (cmd == RRB)
-		stack_rrotate(data->b);
-	else if (cmd == RRR)
-		run_for_both(data->a, data->b, stack_rrotate);
-	add_cmd_to_queue(&data->cmds, cmd);
-}
-
 static void	print_cmd(void *ptr_cmd)
 {
 	enum e_pscmd	cmd;
@@ -98,3 +64,37 @@ void	print_commands(t_list *cmds)
 {
 	ft_lstiter(cmds, print_cmd);
 }
+
+static void	run_for_both(t_stack *stack_a, t_stack *stack_b,
+		void (*f)(t_stack *))
+{
+	f(stack_a);
+	f(stack_b);
+}
+
+void	run_command(t_psdata *data, enum e_pscmd cmd)
+{
+	if (cmd == SA)
+		stack_swap(data->a);
+	else if (cmd == SB)
+		stack_swap(data->b);
+	else if (cmd == SS)
+		run_for_both(data->a, data->b, stack_swap);
+	else if (cmd == PA)
+		stack_push(data->a, data->b);
+	else if (cmd == PB)
+		stack_push(data->b, data->a);
+	else if (cmd == RA)
+		stack_rotate(data->a);
+	else if (cmd == RB)
+		stack_rotate(data->b);
+	else if (cmd == RR)
+		run_for_both(data->a, data->b, stack_rotate);
+	else if (cmd == RRA)
+		stack_rrotate(data->a);
+	else if (cmd == RRB)
+		stack_rrotate(data->b);
+	else if (cmd == RRR)
+		run_for_both(data->a, data->b, stack_rrotate);
+	add_cmd_to_queue(&data->cmds, cmd);
+}
diff --git a/push_swap.h b/push_swap.h
index 99b99af..14649e0 100644
--- a/push_swap.h
+++ b/push_swap.h
@@ -6,7 +6,7 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/12 16:59:09 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/26 16:19:46 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/27 14:26:01 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -60,5 +60,7 @@ int			stack_optimize(t_stack *stack);
 void		optimize_commands(t_psdata *data);
 
 void		stack_sort(t_psdata *data);
+void		sort_three(t_psdata *data);
+void		sort_few(t_psdata *data);
 
 #endif // PUSH_SWAP_H
diff --git a/sort_few.c b/sort_few.c
new file mode 100644
index 0000000..40bc030
--- /dev/null
+++ b/sort_few.c
@@ -0,0 +1,95 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   sort_few.c                                         :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2024/04/27 14:24:54 by dkaiser           #+#    #+#             */
+/*   Updated: 2024/04/27 15:13:03 by dkaiser          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "push_swap.h"
+
+void	sort_three(t_psdata *data)
+{
+	if (data->a->stack[1] > data->a->stack[0]
+		&& data->a->stack[1] > data->a->stack[2])
+		run_command(data, RRA);
+	else if (data->a->stack[0] > data->a->stack[1]
+		&& data->a->stack[0] > data->a->stack[2])
+		run_command(data, RA);
+	if (data->a->stack[0] > data->a->stack[1])
+		run_command(data, SA);
+}
+
+static int	get_min_pos(t_stack *stack)
+{
+	int	i;
+	int	min;
+
+	i = 0;
+	min = 2147483647;
+	while (i < stack->size)
+	{
+		if (stack->stack[i] < min)
+			min = stack->stack[i];
+		i++;
+	}
+	i = 0;
+	while (stack->stack[i] != min)
+		i++;
+	return (i);
+}
+
+static void	rotate_a_n(t_psdata *data, int n)
+{
+	if (n < (data->a->size + 1) / 2)
+	{
+		while (n--)
+			run_command(data, RA);
+	}
+	else
+	{
+		n = data->a->size - n;
+		while (n--)
+			run_command(data, RRA);
+	}
+}
+
+static void	reinsert_nbrs(t_psdata *data)
+{
+	int	i;
+
+	while (data->b->size > 0)
+	{
+		if (data->b->stack[0] >= data->a->size)
+		{
+			run_command(data, PA);
+			run_command(data, RA);
+		}
+		else
+		{
+			i = 0;
+			while (i < data->a->size && data->b->stack[0] > data->a->stack[i])
+				i++;
+			rotate_a_n(data, i);
+			run_command(data, PA);
+			if (data->a->stack[0] != data->b->stack[0] - 1)
+				rotate_a_n(data, get_min_pos(data->a));
+		}
+	}
+}
+
+void	sort_few(t_psdata *data)
+{
+	if (data->a->stack[0] == data->a->size - 1)
+		run_command(data, RA);
+	while (data->a->size > 3)
+		run_command(data, PB);
+	if (data->b->stack[0] > data->b->stack[1])
+		run_command(data, SB);
+	sort_three(data);
+	reinsert_nbrs(data);
+}
diff --git a/sorting.c b/sorting.c
index 88055e7..43dd541 100644
--- a/sorting.c
+++ b/sorting.c
@@ -6,7 +6,7 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 15:04:19 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/26 18:35:27 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/27 14:36:06 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -28,18 +28,6 @@ static int	is_sorted(t_stack *stack)
 	return (1);
 }
 
-static void	sort_three(t_psdata *data)
-{
-	if (data->a->stack[1] > data->a->stack[0]
-		&& data->a->stack[1] > data->a->stack[2])
-		run_command(data, RRA);
-	else if (data->a->stack[0] > data->a->stack[1]
-		&& data->a->stack[0] > data->a->stack[2])
-		run_command(data, RA);
-	if (data->a->stack[0] > data->a->stack[1])
-		run_command(data, SA);
-}
-
 static void	ps_radixsort(t_psdata *data, int bit)
 {
 	int	i;
@@ -69,6 +57,8 @@ void	stack_sort(t_psdata *data)
 		run_command(data, SA);
 	else if (data->a->size == 3)
 		sort_three(data);
+	else if (data->a->size == 4 || data->a->size == 5)
+		sort_few(data);
 	else
 		ps_radixsort(data, 0);
 }
-- 
2.47.2