From b06799d28f4f7b5f3aab2013ddf00a0adcc6c34e Mon Sep 17 00:00:00 2001 From: Axy Date: Fri, 12 Dec 2025 00:08:06 +0100 Subject: [PATCH] Splitsort visit --- algorithm_splitsort.c | 127 ++++++++++++++++++++++++++++++++++-------- list.c | 2 +- 2 files changed, 104 insertions(+), 25 deletions(-) diff --git a/algorithm_splitsort.c b/algorithm_splitsort.c index ed62257..fdd84f4 100644 --- a/algorithm_splitsort.c +++ b/algorithm_splitsort.c @@ -6,7 +6,7 @@ /* By: agilliar +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2025/12/11 12:45:16 by agilliar #+# #+# */ -/* Updated: 2025/12/11 20:11:47 by agilliar ### ########.fr */ +/* Updated: 2025/12/12 00:07:33 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ @@ -42,12 +42,13 @@ typedef struct s_iter { t_list top; t_list bottom; - t_mode mode; size_t top_blocks; size_t bottom_blocks; + bool top_rev; + bool bottom_rev; } t_iter; -t_iter splitsort_iter_new(t_splitsort sort, t_mode mode, t_list range) +static t_iter splitsort_iter_new(t_splitsort sort, t_mode mode, t_list range) { t_iter res; size_t top_len; @@ -57,19 +58,18 @@ t_iter splitsort_iter_new(t_splitsort sort, t_mode mode, t_list range) 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); + if (mode == MODE_REV) + res.top = range; + else res.bottom = range; - } + res.top_rev = mode != MODE_NORMAL; + res.bottom_rev = mode == MODE_NORMAL; return (res); } @@ -96,18 +96,16 @@ static t_list splitsort_split_end(t_list *range, size_t blocks) return (res); } -void splitsort_iter_next(t_iter *self, t_list *top, t_list *bottom) +static void splitsort_iter_next(t_iter *self, t_list *top, t_list *bottom) { - if (self->mode == MODE_NORMAL) - { + if (self->top_rev) + *top = splitsort_split_end(&self->top, self->top_blocks); + else *top = splitsort_split_start(&self->top, self->top_blocks); + if (self->bottom_rev) *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) @@ -122,7 +120,7 @@ typedef struct s_part bool rev; } t_part; -void splitsort_part_once(t_part self, t_splitsort sort, size_t count) +static void splitsort_part_once(t_part self, t_splitsort sort, size_t count) { const t_stack *src; bool mirror; @@ -147,34 +145,115 @@ void splitsort_part_once(t_part self, t_splitsort sort, size_t count) } } -void splitsort_part(t_splitsort sort, t_mode mode, t_list range) +static void splitsort_part(t_splitsort *sort, t_mode mode, t_list range) { t_part part; t_iter iter; - size_t count; + size_t top_count; + size_t bottom_count; part.mode = mode; part.rev = false; - iter = splitsort_iter_new(sort, mode, range); - count = range.len; + iter = splitsort_iter_new(*sort, mode, range); + top_count = 0; + bottom_count = 0; while (splitsort_iter_next(&iter, &part.top, &part.bottom), part.top.len || part.bottom.len) { - splitsort_part_once(part, sort, count); + splitsort_part_once(part, *sort, range.len - top_count - bottom_count); part.rev = !part.rev && mode != MODE_WRAP; - count -= part.top.len + part.bottom.len; + top_count += part.top.len; + bottom_count += part.bottom.len; } + while (mode != MODE_WRAP && top_count--) + closure_callm(sort->cb, OP_RRB, mode == MODE_NORMAL); +} + +static void splitsort_fortop(t_splitsort sort, t_mode mode, + t_list range, t_closure func) +{ + t_iter iter; + t_list top; + t_list bottom; + + iter = splitsort_iter_new(sort, mode, range); + while (splitsort_iter_next(&iter, &top, &bottom), top.len) + (func.func)(func.data, top); +} + +static void splitsort_forbottom_rev(t_splitsort sort, t_mode mode, + t_list range, t_closure func) +{ + t_iter iter; + t_list top; + t_list bottom; + + iter = splitsort_iter_new(sort, mode, range); + iter.bottom_rev ^= true; + while (splitsort_iter_next(&iter, &top, &bottom), bottom.len) + (func.func)(func.data, bottom); +} + +typedef struct s_visit +{ + t_splitsort sort; + t_closure callback; + size_t depth; + t_mode mode; +} t_visit; + +static void splitsort_visit_inner(t_visit *self, t_list range) +{ + t_visit subdata; + t_closure subvisit; + + if (self->depth == 0) + return ((self->callback.func)(self->callback.data, self->mode, range)); + subdata = *self; + subdata.depth--; + if (subdata.mode == MODE_NORMAL) + subdata.mode = MODE_REV; + else + subdata.mode = MODE_NORMAL; + subvisit.data = &subdata; + subvisit.func = &splitsort_visit_inner; + if (self->mode != MODE_WRAP) + splitsort_fortop(self->sort, self->mode, range, subvisit); + splitsort_forbottom_rev(self->sort, self->mode, range, subvisit); + if (self->mode == MODE_WRAP) + splitsort_fortop(self->sort, self->mode, range, subvisit); } +void splitsort_visit(t_splitsort sort, t_list range, + size_t depth, t_closure callback) +{ + t_visit visit; + + visit.sort = sort; + visit.callback = callback; + visit.depth = depth; + visit.mode = MODE_WRAP; + splitsort_visit_inner(&visit, range); +} + +typedef struct s_layer +{ + t_splitsort sort; +} t_layer; + void test_splitsort(const t_stacks *stacks, t_closure cb) { t_splitsort sort; t_list range; + t_closure part; sort.stacks = stacks; sort.cb = cb; sort.blocks = 5; range = list_new(stacks->a); list_sort(range); - splitsort_part(sort, MODE_WRAP, range); + part.func = &splitsort_part; + part.data = &sort; + for (size_t depth = 0; depth < 2; depth++) + splitsort_visit(sort, range, depth, part); } diff --git a/list.c b/list.c index 9409266..0c57749 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/11 19:25:04 by agilliar ### ########.fr */ +/* Updated: 2025/12/11 23:58:54 by agilliar ### ########.fr */ /* */ /* ************************************************************************** */ -- 2.51.0