diff options
| -rw-r--r-- | command_handling.c | 8 | ||||
| -rw-r--r-- | input_handling.c | 79 | ||||
| -rw-r--r-- | main.c | 41 | ||||
| -rw-r--r-- | push_swap.h | 25 | ||||
| -rw-r--r-- | sorting.c | 40 | ||||
| -rw-r--r-- | stack_optimization.c | 89 | ||||
| -rw-r--r-- | 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); } @@ -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 @@ -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..f240395 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 21:53:40 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; + 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"); } |