From ea5d36cf993be4d4143ed44e9f306f5742a3e512 Mon Sep 17 00:00:00 2001 From: = <=> Date: Thu, 11 Dec 2025 20:12:10 +0100 Subject: [PATCH] Partial splitsort --- Makefile | 2 +- algorithm_splitsort.c | 180 ++++++++++++++++++++++++++++++++++++++++++ leaf_sort.c | 4 +- list.c | 35 +++++++- main_pushswap.c | 17 +++- ops.c | 6 +- ops_optimizer.c | 10 +-- pushswap.h | 157 ++++++++++++++++++------------------ stack.c | 17 +++- stacks.c | 13 ++- stacks_get.c | 27 +++++++ 11 files changed, 372 insertions(+), 96 deletions(-) create mode 100644 algorithm_splitsort.c create mode 100644 stacks_get.c diff --git a/Makefile b/Makefile index 742f39d..2d5cfc5 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ NAME=push_swap -SRCS=algorithm_leafsort.c algorithm_quicksort.c algorithm_selection_sort.c cheatalloc.c clist.c closure.c leaf_sort.c leaf_sort_index.c leaf_sort_parse.c list.c main_pushswap.c op_output.c op_parse.c op_p.c op_r.c op_rr.c op_s.c ops.c ops_groups.c ops_optimizer.c output.c psval.c slice.c stack.c stacks.c +SRCS=algorithm_leafsort.c algorithm_quicksort.c algorithm_selection_sort.c algorithm_splitsort.c cheatalloc.c clist.c closure.c leaf_sort.c leaf_sort_index.c leaf_sort_parse.c list.c main_pushswap.c op_output.c op_p.c op_parse.c op_r.c op_rr.c op_s.c ops.c ops_groups.c ops_optimizer.c output.c psval.c slice.c stack.c stacks.c stacks_get.c RESSRCS=_res_leaf_sort_lookup.h diff --git a/algorithm_splitsort.c b/algorithm_splitsort.c new file mode 100644 index 0000000..ed62257 --- /dev/null +++ b/algorithm_splitsort.c @@ -0,0 +1,180 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* algorithm_splitsort.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/11 12:45:16 by agilliar #+# #+# */ +/* Updated: 2025/12/11 20:11:47 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +typedef struct s_splitsort +{ + const t_stacks *stacks; + t_closure cb; + size_t blocks; +} t_splitsort; + +// MODE_NORMAL: sort current elements in ascending order +// top < bottom +// top ascending +// bottom descending +// MODE_REV: sort current elements in descending order +// top > bottom +// top descending +// bottom ascending +// MODE_WRAP: sort current elements in descending order, without unwind +// top < bottom +// top descending +// bottom ascending +typedef enum e_mode +{ + MODE_NORMAL, + MODE_REV, + MODE_WRAP, +} t_mode; + +typedef struct s_iter +{ + t_list top; + t_list bottom; + t_mode mode; + size_t top_blocks; + size_t bottom_blocks; +} t_iter; + +t_iter splitsort_iter_new(t_splitsort sort, t_mode mode, t_list range) +{ + t_iter res; + size_t top_len; + size_t bottom_len; + + if (sort.blocks == 0) + cheatexit(1); + res.top_blocks = sort.blocks / 2; + res.bottom_blocks = sort.blocks - res.top_blocks; + res.mode = mode; + top_len = range.len * res.top_blocks / sort.blocks; + bottom_len = range.len - top_len; + if (mode == MODE_REV) + { + res.bottom = list_split(&range, bottom_len); + res.top = range; + } + else + { + res.top = list_split(&range, top_len); + res.bottom = range; + } + return (res); +} + +static t_list splitsort_split_start(t_list *range, size_t blocks) +{ + size_t count; + + count = 0; + if (blocks) + count = range->len / blocks + ((range->len % blocks) != 0); + return (list_split(range, count)); +} + +static t_list splitsort_split_end(t_list *range, size_t blocks) +{ + size_t count; + t_list res; + + count = 0; + if (blocks) + count = range->len / blocks + ((range->len % blocks) != 0); + res = *range; + *range = list_split(&res, res.len - count); + return (res); +} + +void splitsort_iter_next(t_iter *self, t_list *top, t_list *bottom) +{ + if (self->mode == MODE_NORMAL) + { + *top = splitsort_split_start(&self->top, self->top_blocks); + *bottom = splitsort_split_end(&self->bottom, self->bottom_blocks); + } + else + { + *top = splitsort_split_end(&self->top, self->top_blocks); + *bottom = splitsort_split_start(&self->bottom, self->bottom_blocks); + } + if (self->top_blocks) + self->top_blocks--; + if (self->bottom_blocks) + self->bottom_blocks--; +} + +typedef struct s_part +{ + t_mode mode; + t_list top; + t_list bottom; + bool rev; +} t_part; + +void splitsort_part_once(t_part self, t_splitsort sort, size_t count) +{ + const t_stack *src; + bool mirror; + t_psval val; + + mirror = self.mode == MODE_NORMAL; + src = stacks_geta(sort.stacks, mirror); + while (count--) + { + if (self.rev) + closure_callm(sort.cb, OP_RRA, mirror); + val = clist_get_at(src->list, 0); + if (list_get_sorted(self.top, val) != -1) + { + closure_callm(sort.cb, OP_PB, mirror); + closure_callm(sort.cb, OP_RB, mirror); + } + else if (list_get_sorted(self.bottom, val) != -1) + closure_callm(sort.cb, OP_PB, mirror); + else if (!self.rev) + closure_callm(sort.cb, OP_RA, mirror); + } +} + +void splitsort_part(t_splitsort sort, t_mode mode, t_list range) +{ + t_part part; + t_iter iter; + size_t count; + + part.mode = mode; + part.rev = false; + iter = splitsort_iter_new(sort, mode, range); + count = range.len; + while (splitsort_iter_next(&iter, &part.top, &part.bottom), + part.top.len || part.bottom.len) + { + splitsort_part_once(part, sort, count); + part.rev = !part.rev && mode != MODE_WRAP; + count -= part.top.len + part.bottom.len; + } +} + +void test_splitsort(const t_stacks *stacks, t_closure cb) +{ + t_splitsort sort; + t_list range; + + sort.stacks = stacks; + sort.cb = cb; + sort.blocks = 5; + range = list_new(stacks->a); + list_sort(range); + splitsort_part(sort, MODE_WRAP, range); +} diff --git a/leaf_sort.c b/leaf_sort.c index 626ad85..3abfc2c 100644 --- a/leaf_sort.c +++ b/leaf_sort.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/11 00:27:32 by agilliar #+# #+# */ -/* Updated: 2025/12/11 01:04:35 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 17:21:30 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -37,7 +37,7 @@ static t_leaf_solution *leaf_solution_get(const t_stacks *stacks, size_t size, i = 0; while (i < size) { - store[i] = clist_get_at(stack->list, i); + store[i] = clist_get_at(stack->list, -i); i++; } return (leaf_sort_get(size, store, lookup)); diff --git a/list.c b/list.c index 92d8026..9409266 100644 --- a/list.c +++ b/list.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/08 11:32:24 by agilliar #+# #+# */ -/* Updated: 2025/12/08 17:57:16 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 19:25:04 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -37,6 +37,15 @@ t_list list_sub(t_list self, size_t start, size_t end) return (self); } +t_list list_split(t_list *rem, size_t n) +{ + t_list res; + + res = list_sub(*rem, 0, n); + *rem = list_sub(*rem, n, rem->len); + return (res); +} + void list_sort(t_list list) { size_t i; @@ -57,3 +66,27 @@ void list_sort(t_list list) list.len--; } } + +int64_t list_get_sorted(t_list self, t_psval val) +{ + int64_t res; + size_t offset; + + if (!self.len) + return (-1); + if (self.ptr[0] == val) + return (0); + if (self.len == 1) + return (-1); + offset = 0; + if (val < self.ptr[self.len / 2]) + res = list_get_sorted(list_sub(self, 0, self.len / 2), val); + else + { + offset = self.len / 2; + res = list_get_sorted(list_sub(self, self.len / 2, self.len), val); + } + if (res == -1) + return (res); + return (res + offset); +} diff --git a/main_pushswap.c b/main_pushswap.c index 977041d..6f7ba89 100644 --- a/main_pushswap.c +++ b/main_pushswap.c @@ -6,7 +6,7 @@ /* By: clefrere +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/02 22:15:12 by agilliar #+# #+# */ -/* Updated: 2025/12/11 01:02:32 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 19:22:20 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -22,6 +22,8 @@ static bool ft_streq(char *str1, char *str2) return (str1[i] == '\0' && str2[i] == '\0'); } +void test_splitsort(const t_stacks *stacks, t_closure cb); + static void arg_step(char *str, t_args *arg) { if (ft_streq(str, "--simple")) @@ -34,15 +36,14 @@ static void arg_step(char *str, t_args *arg) arg->algo = NULL; else if (ft_streq(str, "--leaf")) arg->algo = &algorithm_leafsort; + else if (ft_streq(str, "--split")) + arg->algo = &test_splitsort; else if (ft_streq(str, "--bench")) arg->bench = true; else stack_push_back(&arg->state.a, psval_parse(str)); } -#include "leaf_sort.h" -#include - int main(int argc, char **argv) { t_args args; @@ -54,9 +55,17 @@ int main(int argc, char **argv) args.algo = NULL; for (int i = 1; i < argc; i++) arg_step(argv[i], &args); + output_str("\na:\n"); + stack_output(args.state.a); + output_str("\nb:\n"); + stack_output(args.state.b); ops = ops_compose(ops_stackops(), ops_optimizer(ops_output(), &opt)); stacks_apply(&args.state, &ops, args.algo); ops_optimizer_commit(&opt, &args.state); + output_str("\na:\n"); + stack_output(args.state.a); + output_str("\nb:\n"); + stack_output(args.state.b); output_flush(); cheatexit(!stacks_is_solved(&args.state)); } diff --git a/ops.c b/ops.c index 00d45b5..48fca72 100644 --- a/ops.c +++ b/ops.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/03 10:57:30 by agilliar #+# #+# */ -/* Updated: 2025/12/11 01:13:40 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 16:58:11 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,8 +15,8 @@ static void op_compose_fn(t_op_compose *data, t_stacks *stacks) { - closure_call(data->first, stacks); - closure_call(data->second, stacks); + (data->first.func)(data->first.data, stacks); + (data->second.func)(data->second.data, stacks); } t_closure op_compose(t_closure first, t_closure second) diff --git a/ops_optimizer.c b/ops_optimizer.c index 8a1946a..4389deb 100644 --- a/ops_optimizer.c +++ b/ops_optimizer.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/08 17:54:20 by agilliar #+# #+# */ -/* Updated: 2025/12/11 01:13:45 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 19:46:02 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -32,7 +32,7 @@ static void op_optimizer_inner(t_op_optimizer *data, t_stacks *stacks) { ops_optimizer_commit(data->opt, stacks); cb = data->opt->commit.ops[data->op]; - closure_call(cb, stacks); + (cb.func)(cb.data, stacks); } } @@ -85,7 +85,7 @@ static void ops_optimizer_commit_end(t_optimizer *data, t_stacks *stacks) *counter *= -1; while (*counter != 0) { - closure_call(cb, stacks); + (cb.func)(cb.data, stacks); (*counter)++; } } @@ -99,14 +99,14 @@ void ops_optimizer_commit(t_optimizer *data, t_stacks *stacks) { data->a--; data->b--; - closure_call(cb, stacks); + (cb.func)(cb.data, stacks); } cb = data->commit.ops[OP_RRR]; while (data->a < 0 && data->b < 0) { data->a++; data->b++; - closure_call(cb, stacks); + (cb.func)(cb.data, stacks); } ops_optimizer_commit_end(data, stacks); } diff --git a/pushswap.h b/pushswap.h index dacce38..275ab31 100644 --- a/pushswap.h +++ b/pushswap.h @@ -6,7 +6,7 @@ /* By: clefrere +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/02 11:02:44 by agilliar #+# #+# */ -/* Updated: 2025/12/11 01:11:55 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 19:45:26 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -96,80 +96,87 @@ typedef struct s_slice const char *ptr; } t_slice; -void cheatexit(int errcode); -void *cheatalloc(size_t len); +void cheatexit(int errcode); +void *cheatalloc(size_t len); -t_clist *clist_new(t_psval val); +t_clist *clist_new(t_psval val); // Positive numbers are forward, which wraps back to end of stack -t_psval clist_get_at(const t_clist *list, int i); -t_clist *clist_pop(t_clist **src); -// *dst : Nullable -void clist_push(t_clist **dst, t_clist *lst); -// *dst : Nullable -void clist_push_back(t_clist **dst, t_clist *lst); - -void output_char(char c); -void output_str(const char *s); -void output_str_ln(const char *s); -void output_flush(void); - -t_stacks stacks_new(void); -bool stacks_is_solved(const t_stacks *stacks); -void stacks_apply(t_stacks *stacks, const t_ops *ops, t_algorithm algo); - -void stack_push_back(t_stack *stack, t_psval val); -void stack_rotate_n(t_stack *stack, int n); -void stack_swap_top(t_stack *stack); -void stack_move(t_stack *src, t_stack *dst); - -t_psval psval_parse(const char *s); -void psval_output(t_psval val); - -void closure_call(t_closure cb, t_op op); -void closure_callm(t_closure cb, t_op op, bool mirrored); - -t_op op_parse(t_slice s); - -t_closure op_pa(void); -t_closure op_pb(void); -t_closure op_ra(void); -t_closure op_rb(void); -t_closure op_rr(void); -t_closure op_rra(void); -t_closure op_rrb(void); -t_closure op_rrr(void); -t_closure op_sa(void); -t_closure op_sb(void); -t_closure op_ss(void); - -t_closure op_output(t_op op); - -t_closure op_compose(t_closure first, t_closure second); -t_ops ops_compose(t_ops lhs, t_ops rhs); -t_ops ops_init(t_closure (*gen)(t_op)); - -t_ops ops_stackops(void); -t_ops ops_output(void); - -t_ops ops_optimizer(t_ops commit, t_optimizer *data); -void ops_optimizer_commit(t_optimizer *data, t_stacks *stacks); - -t_list list_new(t_stack stack); -t_list list_sub(t_list self, size_t start, size_t end); -void list_sort(t_list list); - -t_slice slice_new(const char *s); -t_slice slice_new_range(void *start, void *end); -bool slice_eq(t_slice lhs, t_slice rhs); -t_slice slice_split(t_slice *rem, char at); -void slice_output(t_slice s); - -void leaf_sort_local(const t_stacks *stacks, t_closure cb, - bool mirrored, size_t size); -void leaf_sort_other(const t_stacks *stacks, t_closure cb, - bool mirrored, size_t size); - -void algorithm_selection_sort(const t_stacks *stacks, t_closure cb); -void algorithm_quicksort(const t_stacks *stacks, t_closure cb); -void algorithm_leafsort(const t_stacks *stacks, t_closure cb); +t_psval clist_get_at(const t_clist *list, int i); +t_clist *clist_pop(t_clist **src); +// *dst : Nullable +void clist_push(t_clist **dst, t_clist *lst); +// *dst : Nullable +void clist_push_back(t_clist **dst, t_clist *lst); + +void output_char(char c); +void output_str(const char *s); +void output_str_ln(const char *s); +void output_flush(void); + +t_stacks stacks_new(void); +bool stacks_is_solved(const t_stacks *stacks); +void stacks_apply(t_stacks *stacks, const t_ops *ops, + t_algorithm algo); + +void stack_push_back(t_stack *stack, t_psval val); +void stack_rotate_n(t_stack *stack, int n); +void stack_swap_top(t_stack *stack); +void stack_move(t_stack *src, t_stack *dst); +void stack_output(t_stack s); + +t_psval psval_parse(const char *s); +void psval_output(t_psval val); + +void closure_call(t_closure cb, t_op op); +void closure_callm(t_closure cb, t_op op, bool mirrored); + +const t_stack *stacks_geta(const t_stacks *stacks, bool mirrored); +const t_stack *stacks_getb(const t_stacks *stacks, bool mirrored); + +t_op op_parse(t_slice s); + +t_closure op_pa(void); +t_closure op_pb(void); +t_closure op_ra(void); +t_closure op_rb(void); +t_closure op_rr(void); +t_closure op_rra(void); +t_closure op_rrb(void); +t_closure op_rrr(void); +t_closure op_sa(void); +t_closure op_sb(void); +t_closure op_ss(void); + +t_closure op_output(t_op op); + +t_closure op_compose(t_closure first, t_closure second); +t_ops ops_compose(t_ops lhs, t_ops rhs); +t_ops ops_init(t_closure (*gen)(t_op)); + +t_ops ops_stackops(void); +t_ops ops_output(void); + +t_ops ops_optimizer(t_ops commit, t_optimizer *data); +void ops_optimizer_commit(t_optimizer *data, t_stacks *stacks); + +t_list list_new(t_stack stack); +t_list list_sub(t_list self, size_t start, size_t end); +t_list list_split(t_list *rem, size_t n); +void list_sort(t_list list); +int64_t list_get_sorted(t_list self, t_psval val); + +t_slice slice_new(const char *s); +t_slice slice_new_range(void *start, void *end); +bool slice_eq(t_slice lhs, t_slice rhs); +t_slice slice_split(t_slice *rem, char at); +void slice_output(t_slice s); + +void leaf_sort_local(const t_stacks *stacks, t_closure cb, + bool mirrored, size_t size); +void leaf_sort_other(const t_stacks *stacks, t_closure cb, + bool mirrored, size_t size); + +void algorithm_selection_sort(const t_stacks *stacks, t_closure cb); +void algorithm_quicksort(const t_stacks *stacks, t_closure cb); +void algorithm_leafsort(const t_stacks *stacks, t_closure cb); #endif diff --git a/stack.c b/stack.c index 0db42a8..2fd3beb 100644 --- a/stack.c +++ b/stack.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/03 12:53:25 by agilliar #+# #+# */ -/* Updated: 2025/12/08 14:00:35 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 18:49:48 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -53,3 +53,18 @@ void stack_move(t_stack *src, t_stack *dst) dst->len++; clist_push(&dst->list, clist_pop(&src->list)); } + +void stack_output(t_stack s) +{ + size_t i; + t_clist *l; + + i = 0; + l = s.list; + while (i++ < s.len) + { + psval_output(l->val); + output_char('\n'); + l = l->prev; + } +} diff --git a/stacks.c b/stacks.c index 50d89ab..45af699 100644 --- a/stacks.c +++ b/stacks.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/02 15:57:41 by agilliar #+# #+# */ -/* Updated: 2025/12/11 01:13:52 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 17:28:02 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -27,13 +27,18 @@ t_stacks stacks_new(void) bool stacks_is_solved(const t_stacks *stacks) { size_t i; + t_stack s; if (stacks->b.len != 0) return (false); i = 0; - while (++i < stacks->a.len) - if (clist_get_at(stacks->a.list, 0) > clist_get_at(stacks->a.list, -1)) + s = stacks->a; + while (++i < s.len) + { + if (clist_get_at(s.list, 0) > clist_get_at(s.list, -1)) return (false); + s.list = s.list->prev; + } return (true); } @@ -46,7 +51,7 @@ static void stacks_apply_op(t_stacks_apply_data *data, t_op op) stacks = data->stacks; ops = data->ops; op_fn = ops->ops[op]; - closure_call(op_fn, stacks); + (op_fn.func)(op_fn.data, stacks); } void stacks_apply(t_stacks *stacks, const t_ops *ops, t_algorithm algo) diff --git a/stacks_get.c b/stacks_get.c new file mode 100644 index 0000000..524cd9c --- /dev/null +++ b/stacks_get.c @@ -0,0 +1,27 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* stacks_get.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: agilliar +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2025/12/11 12:52:27 by agilliar #+# #+# */ +/* Updated: 2025/12/11 19:45:40 by agilliar ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pushswap.h" + +const t_stack *stacks_geta(const t_stacks *stacks, bool mirrored) +{ + if (mirrored) + return (&stacks->b); + return (&stacks->a); +} + +const t_stack *stacks_getb(const t_stacks *stacks, bool mirrored) +{ + if (mirrored) + return (&stacks->a); + return (&stacks->b); +} -- 2.51.0