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.

1 files changed, 67 insertions, 1 deletions

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);
 }