From e621569332f5b6ae16247e30284968d86fcebedd Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Wed, 15 Dec 2021 20:45:30 -0600 Subject: [PATCH] added a heap data structure to core --- core/container/heap.onyx | 80 +++++++++++++++++++++++++++++++++++++++ core/std.onyx | 1 + include/astnodes.h | 1 + src/checker.c | 35 +++++++++-------- tests/aoc-2021/day15.onyx | 14 +++---- 5 files changed, 108 insertions(+), 23 deletions(-) create mode 100644 core/container/heap.onyx diff --git a/core/container/heap.onyx b/core/container/heap.onyx new file mode 100644 index 00000000..61516f35 --- /dev/null +++ b/core/container/heap.onyx @@ -0,0 +1,80 @@ +package core.heap + +#local { + array :: package core.array +} + +Heap :: struct (T: type_expr) { + data: [..] T; + compare: (T, T) -> i32 = null_proc; +} + +make :: ($T: type_expr, cmp: (T, T) -> i32 = null_proc) -> Heap(T) { + h: Heap(T); + init(^h, cmp); + return h; +} + +init :: (use heap: ^Heap($T), cmp: (T, T) -> i32 = null_proc) { + array.init(^data); + compare = cmp; +} + +insert :: (use heap: ^Heap($T), v: T) { + data << v; + shift_up(heap, data.count - 1); +} + +#operator << macro (heap: Heap($T), v: T) do (package core.heap).insert(^heap, v); + +remove_top :: (use heap: ^Heap($T)) -> T { + x := data[0]; + array.fast_delete(^data, 0); + shift_down(heap, 0); + return x; +} + +#local { + heap_parent :: macro (index) => (index - 1) / 2 + heap_lchild :: macro (index) => (index * 2) + 1 + heap_rchild :: macro (index) => (index * 2) + 2 + + shift_down :: (use heap: ^Heap($T), idx: i32) { + while true { + min_index := idx; + + l := heap_lchild(idx); + if l < data.count { + if compare(data[l], data[min_index]) < 0 { + min_index = l; + } + } + + r := heap_rchild(idx); + if r < data.count { + if compare(data[r], data[min_index]) < 0 { + min_index = r; + } + } + + if idx != min_index { + data[min_index], data[idx] = data[idx], data[min_index]; + idx = min_index; + continue; + } + + break; + } + } + + shift_up :: (use heap: ^Heap($T), idx: i32) { + while idx > 0 { + parent := heap_parent(idx); + if compare(data[parent], data[idx]) <= 0 do break; + + data[parent], data[idx] = data[idx], data[parent]; + idx = parent; + } + } +} + diff --git a/core/std.onyx b/core/std.onyx index 8c3bb028..91f67e4d 100644 --- a/core/std.onyx +++ b/core/std.onyx @@ -10,6 +10,7 @@ package core #load "./container/iter" #load "./container/set" #load "./container/bucket_array" +#load "./container/heap" #load "./conv" #load "./math" diff --git a/include/astnodes.h b/include/astnodes.h index 7690e5a9..b43811b0 100644 --- a/include/astnodes.h +++ b/include/astnodes.h @@ -540,6 +540,7 @@ typedef struct ConstraintContext { bh_arr(AstConstraint *) constraints; ConstraintCheckStatus *constraint_checks; b32 constraints_met : 1; + b32 produce_errors : 1; } ConstraintContext; diff --git a/src/checker.c b/src/checker.c index 92dd8079..36f6f9a2 100644 --- a/src/checker.c +++ b/src/checker.c @@ -2032,6 +2032,7 @@ CheckStatus check_struct(AstStructType* s_node) { YIELD(s_node->token->pos, "Waiting for struct member defaults to pass symbol resolution."); if (s_node->constraints.constraints) { + s_node->constraints.produce_errors = 1; CHECK(constraint_context, &s_node->constraints, s_node->scope, s_node->token->pos); } @@ -2217,6 +2218,7 @@ CheckStatus check_function_header(AstFunction* func) { if (func->return_type != NULL) CHECK(type, func->return_type); if (func->constraints.constraints != NULL) { + func->constraints.produce_errors = (func->flags & Ast_Flag_Header_Check_No_Error) == 0; CHECK(constraint_context, &func->constraints, func->scope, func->token->pos); } @@ -2593,23 +2595,26 @@ CheckStatus check_constraint_context(ConstraintContext *cc, Scope *scope, OnyxFi fori (i, 0, bh_arr_length(cc->constraints)) { if (cc->constraint_checks[i] == Constraint_Check_Status_Failed) { - AstConstraint *constraint = cc->constraints[i]; - char constraint_map[512] = {0}; - fori (i, 0, bh_arr_length(constraint->type_args)) { - if (i != 0) strncat(constraint_map, ", ", 511); - - OnyxToken* symbol = constraint->interface->params[i].token; - token_toggle_end(symbol); - strncat(constraint_map, symbol->text, 511); - token_toggle_end(symbol); - - strncat(constraint_map, " is of type '", 511); - strncat(constraint_map, type_get_name(type_build_from_ast(context.ast_alloc, constraint->type_args[i])), 511); - strncat(constraint_map, "'", 511); + if (cc->produce_errors) { + AstConstraint *constraint = cc->constraints[i]; + char constraint_map[512] = {0}; + fori (i, 0, bh_arr_length(constraint->type_args)) { + if (i != 0) strncat(constraint_map, ", ", 511); + + OnyxToken* symbol = constraint->interface->params[i].token; + token_toggle_end(symbol); + strncat(constraint_map, symbol->text, 511); + token_toggle_end(symbol); + + strncat(constraint_map, " is of type '", 511); + strncat(constraint_map, type_get_name(type_build_from_ast(context.ast_alloc, constraint->type_args[i])), 511); + strncat(constraint_map, "'", 511); + } + + onyx_report_error(constraint->exprs[constraint->expr_idx]->token->pos, "Failed to satisfy constraint where %s.", constraint_map); + onyx_report_error(constraint->token->pos, "Here is where the interface was used."); } - onyx_report_error(constraint->exprs[constraint->expr_idx]->token->pos, "Failed to satisfy constraint where %s.", constraint_map); - onyx_report_error(constraint->token->pos, "Here is where the interface was used."); return Check_Error; } diff --git a/tests/aoc-2021/day15.onyx b/tests/aoc-2021/day15.onyx index bf1e2ebd..a9a869a3 100644 --- a/tests/aoc-2021/day15.onyx +++ b/tests/aoc-2021/day15.onyx @@ -25,14 +25,14 @@ main :: (args) => { width := cells.count / height; - to_try: [..] queued; + to_try := heap.make(queued, (x, y) => x.cost - y.cost); tried := set.make(pos); - to_try << .{ 0, 0, -cast(i32) (cells[0] - #char "0") }; + heap.insert(^to_try, .{ 0, 0, -cast(i32) (cells[0] - #char "0") }); minimum := 0; - while to_try.count != 0 { - try := array.pop(^to_try); + while to_try.data.count != 0 { + try := heap.remove_top(^to_try); tried << .{try.x, try.y}; cell_value := cast(u32) (cells[(try.y % height) * width + (try.x % width)] - #char "0"); @@ -47,10 +47,10 @@ main :: (args) => { attempt_add :: macro (cond: Code, dx, dy: i32) { if #insert cond { if !tried->has(.{try.x + dx, try.y + dy}) { - if found := array.find_ptr(to_try, .{try.x + dx, try.y + dy, 0}); found != null { + if found := array.find_ptr(to_try.data, .{try.x + dx, try.y + dy, 0}); found != null { found.cost = math.min(cell_value, found.cost); } else { - to_try << .{try.x + dx, try.y + dy, cell_value }; + heap.insert(^to_try, .{try.x + dx, try.y + dy, cell_value }); } } } @@ -60,8 +60,6 @@ main :: (args) => { attempt_add(#(try.x < width * 5 - 1), 1, 0); attempt_add(#(try.y > 0), 0, -1); attempt_add(#(try.y < height * 5 - 1), 0, 1); - - array.sort(to_try, (y,x) => x.cost - y.cost); } printf("Part 2: {}\n", minimum); -- 2.25.1