From 4428c51329562af9feb26860b56b8b39191ac18b Mon Sep 17 00:00:00 2001
From: Dominik Kaiser <dkaiser@2-E-4.42heilbronn.de>
Date: Sat, 13 Apr 2024 16:29:20 +0200
Subject: [PATCH] Add stack optimization

I want to use lsd radix sort which only works with positive numbers.
The added functions optimize the stack so it is only positive numbers.
As we don't need the actual contents of the stack, we can just override.
---
 optimization.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 67 insertions(+), 1 deletion(-)

diff --git a/optimization.c b/optimization.c
index 4348acf..f1eca7e 100644
--- a/optimization.c
+++ b/optimization.c
@@ -6,13 +6,79 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 15:25:05 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/13 15:29:58 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/13 16:27:05 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
+#include "libft/ft_printf.h"
+#include "libft/libft.h"
 #include "push_swap.h"
+#include <stdlib.h>
+
+static void sort_array(int size, int *tmp_array)
+{
+    int i;
+    int k;
+    int tmp;
+
+    i = 0;
+    while (i < size - 1)
+    {
+        k = i + 1;
+        while (k < size)
+        {
+            if (tmp_array[i] > tmp_array[k])
+            {
+                tmp = tmp_array[i];
+                tmp_array[i] = tmp_array[k];
+                tmp_array[k] = tmp;
+            }
+            k++;
+        }
+        i++;
+    }
+}
+
+static void override_stack(t_list **stack, int *tmp_array)
+{
+    t_list *cur;
+    int content;
+    int i;
+
+    cur = *stack;
+    while (cur)
+    {
+        i = 0;
+        content = *(int*)cur->content;
+        while (content != tmp_array[i])
+            i++;
+        *(int*)cur->content = i;
+        cur = cur->next;
+    }
+}
 
 void stack_optimize(t_list **stack)
 {
+    int size;
+    int *tmp_array;
+    t_list *cur;
+    int i;
+
+    size = ft_lstsize(*stack);
+    cur = *stack;
+    tmp_array = malloc(size * sizeof(int));
+    if (!tmp_array)
+        ; // TODO: Error handling
+    i = 0;
 
+    while(cur)
+    {
+        tmp_array[i++] = *(int*)cur->content;
+        cur = cur->next;
+    }
+    if (i != size)
+        ; // TODO: Error handling
+    sort_array(size, tmp_array);
+    i = 0;
+    override_stack(stack, tmp_array);
 }
-- 
2.47.2