From 4545c9f4dc339e94bf6ebe0963db55e9dcc131bd Mon Sep 17 00:00:00 2001
From: Dominik Kaiser <dominik@dominik-XPS.fritz.box>
Date: Mon, 15 Apr 2024 17:54:43 +0200
Subject: [PATCH] Change stacks from linked lists to rotating arrays

---
 command_handling.c   |  8 ++--
 input_handling.c     | 79 +++++++++++++++++++++------------------
 main.c               | 41 +++++++++++---------
 push_swap.h          | 25 ++++++++-----
 sorting.c            | 40 ++------------------
 stack_optimization.c | 89 ++++++++++++++++++++++----------------------
 stack_utils.c        | 83 ++++++++++++++++++++++++++++-------------
 7 files changed, 191 insertions(+), 174 deletions(-)

diff --git a/command_handling.c b/command_handling.c
index b1fe85a..e4dc476 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/13 14:47:55 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 16:35:05 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -31,14 +31,14 @@ static int	add_cmd_to_queue(t_list **cmds, enum e_pscmd cmd)
 	return (0);
 }
 
-static void	run_for_both(t_list **stack_a, t_list **stack_b,
-		void (*f)(t_list **))
+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_list **stack_a, t_list **stack_b, t_list **cmds,
+void	run_command(t_stack *stack_a, t_stack *stack_b, t_list **cmds,
 		enum e_pscmd cmd)
 {
 	if (cmd == SA)
diff --git a/input_handling.c b/input_handling.c
index 7699671..078ab7f 100644
--- a/input_handling.c
+++ b/input_handling.c
@@ -6,10 +6,11 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/12 17:31:49 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/13 14:58:42 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 16:24:51 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
+#include "libft/libft.h"
 #include "push_swap.h"
 
 static int	is_nbr(char *str)
@@ -36,61 +37,65 @@ static int	is_input_only_nbrs(int argc, char *argv[])
 	return (1);
 }
 
-static int	are_numbers_unique(t_list *stack)
+static int	are_numbers_unique(int *stack, int size)
 {
-	t_list	*cmp_elem;
+	int i;
+	int k;
 
-	while (stack->next)
+	i = 0;
+	while (i < size - 1)
 	{
-		cmp_elem = stack->next;
-		while (cmp_elem)
+		k = i + 1;
+		while (k < size)
 		{
-			if (*(int *)stack->content == *(int *)cmp_elem->content)
+			if (stack[i] == stack[k])
 				return (0);
-			cmp_elem = cmp_elem->next;
+			k++;
 		}
-		stack = stack->next;
+		i++;
 	}
+
 	return (1);
 }
 
-static t_list	*get_stack_from_input(int argc, char *argv[])
+static int	*get_array_from_input(int argc, char *argv[])
 {
-	t_list	*result;
-	t_list	*cur;
-	int		*content;
+	int *stack;
+	int i;
 
-	result = NULL;
-	while (argc-- > 1)
+	stack = malloc(sizeof(int) * (argc - 1));
+	if (!stack)
+		return NULL;
+
+	i = 0;
+	while (i < argc - 1)
 	{
-		content = malloc(sizeof(int));
-		if (content)
-		{
-			*content = ft_atoi(argv[argc]);
-			cur = ft_lstnew(content);
-			if (cur)
-			{
-				ft_lstadd_front(&result, cur);
-				continue ;
-			}
-			free(content);
-		}
-		ft_lstclear(&result, free);
-		return (NULL);
+		stack[i] = ft_atoi(argv[i + 1]);
+		i++;
 	}
-	return (result);
+
+	return (stack);
 }
 
-t_list	*create_stack(int argc, char *argv[])
+t_stack	*create_stack(int argc, char *argv[])
 {
-	t_list	*result;
+	t_stack *result;
 
-	if (!is_input_only_nbrs(argc, argv))
-		return (NULL);
-	result = get_stack_from_input(argc, argv);
+	result = malloc(sizeof(t_stack));
 	if (!result)
+		return NULL;
+	if (!is_input_only_nbrs(argc, argv))
+		return (free(result), NULL);
+	result->stack = get_array_from_input(argc, argv);
+	if (!result->stack)
+		return (free(result), NULL);
+	if (!are_numbers_unique(result->stack, argc - 1))
+	{
+		free(result->stack);
+		free(result);
 		return (NULL);
-	if (!are_numbers_unique(result))
-		ft_lstclear(&result, free);
+	}
+	result->size = argc - 1;
+
 	return (result);
 }
diff --git a/main.c b/main.c
index a3e1375..803f6eb 100644
--- a/main.c
+++ b/main.c
@@ -6,21 +6,17 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/12 17:03:30 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/13 16:58:36 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 17:53:19 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
+#include "libft/ft_printf.h"
 #include "push_swap.h"
 
-static void	print_content(void *content)
-{
-	ft_printf("%d ", *(int *)content);
-}
-
 int	main(int argc, char *argv[])
 {
-	t_list	*stack_a;
-	t_list	*stack_b;
+	t_stack	*stack_a;
+	t_stack	*stack_b;
 	t_list	*pscmds;
 
 	stack_a = create_stack(argc, argv);
@@ -29,16 +25,25 @@ int	main(int argc, char *argv[])
 		ft_putendl_fd("Error", 2);
 		return (1);
 	}
-	stack_b = NULL;
-	pscmds = NULL;
-	stack_optimize(&stack_a);
-	stack_sort(&stack_a, &stack_b, &pscmds);
-	optimize_commands(&pscmds);
+
+	stack_b = malloc(sizeof(t_stack));
+	if (!stack_b)
+	{
+		//free everything
+	}
+	stack_b->stack = malloc(sizeof(int) * (argc - 1));
+	if (!stack_b->stack)
+	{
+		//free everything
+	}
+	stack_b->size = 0;
+	stack_optimize(stack_a);
+	pscmds = stack_sort(stack_a, stack_b);
+	/* optimize_commands(&pscmds); */
 	print_commands(pscmds);
-	ft_printf("A:");
-	ft_lstiter(stack_a, print_content);
-	ft_printf("\nB:");
-	ft_lstiter(stack_b, print_content);
-	ft_printf("\nExecuted %d push_swap commands.\n", ft_lstsize(pscmds));
+	ft_printf("\nA: ");
+	stack_print(stack_a);
+	ft_printf("B: ");
+	stack_print(stack_b);
 	return (0);
 }
diff --git a/push_swap.h b/push_swap.h
index 29d0e41..3500171 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/15 12:02:20 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 17:41:05 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -31,20 +31,27 @@ enum	e_pscmd
 	NO_CMD
 };
 
-t_list	*create_stack(int argc, char *argv[]);
+typedef struct s_stack
+{
+	int *stack;
+	int size;
+} t_stack;
+
+t_stack	*create_stack(int argc, char *argv[]);
 
-void	stack_swap(t_list **stack);
-void	stack_push(t_list **dst_stack, t_list **src_stack);
-void	stack_rotate(t_list **stack);
-void	stack_rrotate(t_list **stack);
+void	stack_swap(t_stack *stack);
+void	stack_push(t_stack *dst_stack, t_stack *src_stack);
+void	stack_rotate(t_stack *stack);
+void	stack_rrotate(t_stack *stack);
+void stack_print(t_stack *stack);
 
-void	run_command(t_list **stack_a, t_list **stack_b, t_list **cmds,
+void	run_command(t_stack *stack_a, t_stack *stack_b, t_list **cmds,
 			enum e_pscmd cmd);
 void	print_commands(t_list *cmds);
 
-int	stack_optimize(t_list **stack);
+int	stack_optimize(t_stack *stack);
 void	optimize_commands(t_list **cmds);
 
-void	stack_sort(t_list **stack_a, t_list **stack_b, t_list **cmds);
+t_list	*stack_sort(t_stack *stack_a, t_stack *stack_b);
 
 #endif // PUSH_SWAP_H
diff --git a/sorting.c b/sorting.c
index 6790fa2..f04304f 100644
--- a/sorting.c
+++ b/sorting.c
@@ -6,48 +6,14 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 15:04:19 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/13 19:29:05 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 17:54:23 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
-#include "libft/libft.h"
 #include "push_swap.h"
 
-static void	radixsort_step(t_list **stack_a, t_list **stack_b, t_list **cmds,
-		int bit)
-{
-	int	i;
-	int	max;
-
-	i = 0;
-	max = ft_lstsize(*stack_a);
-	while (i < max)
-	{
-		if (*stack_a && (*(int *)(*stack_a)->content >> bit) % 2 == 0)
-			run_command(stack_a, stack_b, cmds, PB);
-		else if ((*stack_a)->next)
-			run_command(stack_a, stack_b, cmds, RA);
-		i++;
-	}
-	while (*stack_b)
-		run_command(stack_a, stack_b, cmds, PA);
-}
-
-static void	stack_radixsort(t_list **stack_a, t_list **stack_b, t_list **cmds)
-{
-	int	bit;
-	int	max_bits;
-
-	bit = 0;
-	max_bits = 9;
-	while (bit < max_bits)
-	{
-		radixsort_step(stack_a, stack_b, cmds, bit);
-		bit++;
-	}
-}
 
-void	stack_sort(t_list **stack_a, t_list **stack_b, t_list **cmds)
+t_list	*stack_sort(t_stack *stack_a, t_stack *stack_b)
 {
-	stack_radixsort(stack_a, stack_b, cmds);
+    return NULL;
 }
diff --git a/stack_optimization.c b/stack_optimization.c
index 2270896..eabf04a 100644
--- a/stack_optimization.c
+++ b/stack_optimization.c
@@ -6,17 +6,36 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 15:25:05 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/15 12:03:44 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 16:20:51 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "push_swap.h"
+#include <stdlib.h>
 
-static void	sort_array(int size, int *tmp_array)
+static int *copy_stack(int *stack, int size)
 {
-	int	i;
-	int	k;
-	int	tmp;
+	int i;
+	int *cpy;
+
+	cpy = malloc(sizeof(int) * size);
+	if (!cpy)
+		return NULL;
+	i = 0;
+	while (i < size)
+	{
+		cpy[i] = stack[i];
+		i++;
+	}
+
+	return cpy;
+}
+
+static void sort_stack(int *stack, int size)
+{
+	int i;
+	int k;
+	int tmp;
 
 	i = 0;
 	while (i < size - 1)
@@ -24,11 +43,11 @@ static void	sort_array(int size, int *tmp_array)
 		k = i + 1;
 		while (k < size)
 		{
-			if (tmp_array[i] > tmp_array[k])
+			if (stack[i] > stack[k])
 			{
-				tmp = tmp_array[i];
-				tmp_array[i] = tmp_array[k];
-				tmp_array[k] = tmp;
+				tmp = stack[i];
+				stack[i] = stack[k];
+				stack[k] = tmp;
 			}
 			k++;
 		}
@@ -36,49 +55,31 @@ static void	sort_array(int size, int *tmp_array)
 	}
 }
 
-static void	override_stack(t_list **stack, int *tmp_array)
+static void override_stack(int *stack, int *tmp_stack, int size)
 {
-	t_list	*cur;
-	int		content;
-	int		i;
+	int i;
+	int k;
 
-	cur = *stack;
-	while (cur)
+	i = 0;
+	while (i < size)
 	{
-		i = 0;
-		content = *(int *)cur->content;
-		while (content != tmp_array[i])
-			i++;
-		*(int *)cur->content = i;
-		cur = cur->next;
+		k = 0;
+		while (stack[i] != tmp_stack[k])
+			k++;
+		stack[i] = k;
+		i++;
 	}
 }
 
-int	stack_optimize(t_list **stack)
+int	stack_optimize(t_stack *stack)
 {
-	int		size;
-	int		*tmp_array;
-	t_list	*cur;
-	int		i;
+	int *tmp_stack;
 
-	size = ft_lstsize(*stack);
-	cur = *stack;
-	tmp_array = malloc(size * sizeof(int));
-	if (!tmp_array)
+	tmp_stack = copy_stack(stack->stack, stack->size);
+	if (!tmp_stack)
 		return 1;
-	i = 0;
-	while (cur)
-	{
-		tmp_array[i++] = *(int *)cur->content;
-		cur = cur->next;
-	}
-	if (i != size)
-	{
-		free(tmp_array);
-		return 1;
-	}
-	sort_array(size, tmp_array);
-	i = 0;
-	override_stack(stack, tmp_array);
+	sort_stack(tmp_stack, stack->size);
+	override_stack(stack->stack, tmp_stack, stack->size);
+	free(tmp_stack);
 	return 0;
 }
diff --git a/stack_utils.c b/stack_utils.c
index ad14504..ac5c63c 100644
--- a/stack_utils.c
+++ b/stack_utils.c
@@ -6,48 +6,81 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/12 20:31:30 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/13 14:33:35 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/15 17:27:04 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "push_swap.h"
 
-void	stack_swap(t_list **stack)
+void	stack_swap(t_stack *stack)
 {
-	t_list	*first_elem;
+	int tmp;
 
-	first_elem = *stack;
-	*stack = (*stack)->next;
-	first_elem->next = (*stack)->next;
-	(*stack)->next = first_elem;
+	if (stack->size > 1)
+	{
+		tmp = stack->stack[0];
+		stack->stack[0] = stack->stack[1];
+		stack->stack[1] = tmp;
+	}
 }
 
-void	stack_push(t_list **dst_stack, t_list **src_stack)
+void	stack_push(t_stack *dst_stack, t_stack *src_stack)
 {
-	t_list	*elem;
+	int i;
 
-	elem = *src_stack;
-	*src_stack = elem->next;
-	ft_lstadd_front(dst_stack, elem);
+	i = dst_stack->size - 1;
+	while (i > 0)
+	{
+		dst_stack->stack[i] = dst_stack->stack[i-1];
+		i--;
+	}
+	dst_stack->stack[0] = src_stack->stack[0];
+	dst_stack->size++;
+	i = 1;
+	while (i < src_stack->size)
+	{
+		src_stack->stack[i-1] = src_stack->stack[i];
+		i++;
+	}
+	src_stack->size--;
 }
 
-void	stack_rotate(t_list **stack)
+void	stack_rotate(t_stack *stack)
 {
-	t_list	*first_elem;
+	int tmp;
+	int i;
 
-	first_elem = *stack;
-	*stack = (*stack)->next;
-	first_elem->next = NULL;
-	ft_lstlast(*stack)->next = first_elem;
+	tmp = stack->stack[0];
+	i = 1;
+	while (i < stack->size)
+	{
+		stack->stack[i-1] = stack->stack[i];
+		i++;
+	}
+	stack->stack[i-1] = tmp;
 }
 
-void	stack_rrotate(t_list **stack)
+void	stack_rrotate(t_stack *stack)
 {
-	t_list	*first_elem;
+	int tmp;
+	int i;
 
-	first_elem = *stack;
-	while ((*stack)->next->next)
-		*stack = (*stack)->next;
-	(*stack)->next->next = first_elem;
-	(*stack)->next = NULL;
+	i = stack->size - 1;
+	tmp = stack->stack[i];
+	while (i > 0)
+	{
+		stack->stack[i] = stack->stack[i-1];
+		i--;
+	}
+	stack->stack[0] = tmp;
+}
+
+void stack_print(t_stack *stack)
+{
+	int i;
+
+	i = 0;
+	while (i < stack->size)
+		ft_printf("%d ", stack->stack[i++]);
+	ft_printf("\n");
 }
-- 
2.47.2