From 018d2c9d464abbdc4165972fb412971701284789 Mon Sep 17 00:00:00 2001 From: = <=> Date: Wed, 3 Dec 2025 18:32:47 +0100 Subject: [PATCH] [non-working] some more merge stuff --- Makefile | 2 +- algoritm_merlin_sort.c | 158 +++++++++++++++++++++++++++++++++++++++++ pushswap.h | 7 +- 3 files changed, 165 insertions(+), 2 deletions(-) create mode 100644 algoritm_merlin_sort.c diff --git a/Makefile b/Makefile index 01878bd..c4472a3 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ NAME=push_swap -SRCS=cheatalloc.c clist.c main_pushswap.c ops.c ops_output.c ops_p.c ops_r.c ops_rr.c ops_s.c output.c psval.c stack.c stacks.c +SRCS=algoritm_merlin_sort.c cheatalloc.c clist.c main_pushswap.c ops.c ops_output.c ops_p.c ops_r.c ops_rr.c ops_s.c output.c psval.c stack.c stacks.c OBJS=${SRCS:%.c=${OBJDIR}/%.o} diff --git a/algoritm_merlin_sort.c b/algoritm_merlin_sort.c new file mode 100644 index 0000000..4b40fa6 --- /dev/null +++ b/algoritm_merlin_sort.c @@ -0,0 +1,158 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* algoritm_merlin_sort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/03 16:07:50 by agilliar #+# #+# */ +/* Updated: 2025/12/03 18:32:31 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +const t_stack *stack_get(const t_stacks *stacks, t_stackid id); +static bool stack_gt(t_stackid id, t_psval lhs, t_psval rhs) +{ + if (lhs == rhs) + cheatexit(1); + if ((lhs > rhs && id == STACKID_A) || (lhs < rhs && id == STACKID_B)) + return (true); + return (false); +} + +// n: > 2 +static void stack_invert_n(size_t n, t_closure cb, t_stackid id) +{ + size_t i; + + i = 1; + while (i++ * 2 < n) + { + (cb.func)(cb.data, id, OP_PB); + (cb.func)(cb.data, id, OP_RR); + } + (cb.func)(cb.data, id, OP_PB); + (cb.func)(cb.data, id, OP_RB); + if (n % 2 == 0) + (cb.func)(cb.data, id, OP_PB); + i = 1; + while (i++ * 2 < n) + { + (cb.func)(cb.data, id, OP_RRR); + (cb.func)(cb.data, id, OP_PB); + } + (cb.func)(cb.data, id, OP_RRB); + i = 0; + while (i++ < n) + (cb.func)(cb.data, id, OP_PA); +} + +static void clamp_disorder(t_stacks *const stacks, size_t len, + t_closure cb, t_stackid id) +{ + (void) stacks; + (void) len; + (void) cb; + (void) id; +} + +// Returns the amount of unordered elements sifted out +static size_t sift_unordered(t_stacks *const stacks, size_t len, + t_closure cb, t_stackid id) +{ + const t_stack *a; + const t_stack *b; + + a = stack_get(stacks, id); + b = stack_get(stacks, !id); + (void) len; + (void) cb; + for (;;) + ; + __builtin_unreachable(); +} + +static void merlin_merge(t_stacks *const stacks, size_t kept, size_t sifted, + t_closure cb, t_stackid id) +{ + const t_stack *a; + const t_stack *b; + + a = stack_get(stacks, id); + b = stack_get(stacks, !id); + while (kept && sifted) + { + if (stack_gt(id, clist_get_at(a->list, 1), clist_get_at(b->list, 0))) + { + (cb.func)(cb.data, id, OP_RRA); + kept--; + } + else + { + (cb.func)(cb.data, id, OP_PA); + sifted--; + } + } + while (kept--) + (cb.func)(cb.data, id, OP_RRA); + while (sifted--) + (cb.func)(cb.data, id, OP_PA); +} + + +static void merlin_sort_inner(t_stacks *const stacks, size_t len, + t_closure cb, t_stackid id) +{ + size_t sifted; + const t_clist *a; + + a = stack_get(stacks, id)->list; + if (len == 2 && stack_gt(id, clist_get_at(a, 0), clist_get_at(a, -1))) + (cb.func)(cb.data, id, OP_SA); + if (len <= 2) + return ; + clamp_disorder(stacks, len, cb, id); + sifted = sift_unordered(stacks, len, cb, id); + merlin_sort_inner(stacks, sifted, cb, !id); + merlin_merge(stacks, len - sifted, sifted, cb, id); +} + +static void stackid_wrap_fn(t_closure *inner, t_stackid id, t_op op) +{ + const t_op translation[] = { + OP_SB, + OP_SA, + OP_SS, + OP_PB, + OP_PA, + OP_RB, + OP_RA, + OP_RR, + OP_RRB, + OP_RRA, + OP_RRR, + }; + if (id == STACKID_B) + op = translation[op]; + (inner->func)(inner->data, op); +} + +void algorithm_merlin_sort(t_stacks *const stacks, t_closure closure) +{ + t_closure cb; + + cb.data = &closure; + cb.func = (void (*)()) &stackid_wrap_fn; + merlin_sort_inner(stacks, stacks->a.len, cb, STACKID_A); +} + +void algorithm_revn(t_stacks *const stacks, t_closure closure) +{ + t_closure cb; + + cb.data = &closure; + cb.func = (void (*)()) &stackid_wrap_fn; + merlin_sort_inner(stacks, stacks->a.len, cb, STACKID_A); +} diff --git a/pushswap.h b/pushswap.h index 488b2cc..eab2671 100644 --- a/pushswap.h +++ b/pushswap.h @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/02 11:02:44 by agilliar #+# #+# */ -/* Updated: 2025/12/03 15:08:03 by agilliar ### ########.fr */ +/* Updated: 2025/12/03 16:25:25 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -75,6 +75,11 @@ typedef struct s_ops t_closure ops[11]; } t_ops; +# define STACKID_A false +# define STACKID_B true + +typedef bool t_stackid; + void cheatexit(int errcode); void *cheatalloc(size_t len); -- 2.51.0