From 89fd8129817a245afdd758446ffb002467e0815f Mon Sep 17 00:00:00 2001 From: Aryadev Chavali Date: Fri, 26 Jul 2024 20:51:39 +0100 Subject: Make draw_node_number_line non recursive Using a stack or queue, we can replace a function recursive tree traversal with a single call. A stack would make it a DFS while a queue would be a BFS. Since there's only ever two children, and at high iteration counts we're getting quite large depth, it would be best to do a DFS, hence the stack. --- src/main.cpp | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index cec3b5e..808e5ea 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -20,6 +20,7 @@ #include #include #include +#include #include #include @@ -63,16 +64,21 @@ void draw_fraction(Fraction f, word_t x, word_t y) DrawText(s.c_str(), x - width / 2, y - FONT_SIZE, FONT_SIZE, WHITE); } -void draw_node_number_line(index_t index, const NodeAllocator &allocator, - long double lower, long double upper) +void draw_node_number_line(const NodeAllocator &allocator, long double lower, + long double upper) { - if (index.has_value()) + std::stack stack; + stack.push(allocator.getVal(0)); + while (!stack.empty()) { - Node n = allocator.getVal(index.value()); + Node n = stack.top(); + stack.pop(); word_t x = clamp_to_width(n.value.norm, lower, upper); - DrawLine(x, LINE_TOP, x, LINE_BOTTOM, index.value() == 0 ? GREEN : RED); - draw_node_number_line(n.left, allocator, lower, upper); - draw_node_number_line(n.right, allocator, lower, upper); + DrawLine(x, LINE_TOP, x, LINE_BOTTOM, RED); + if (n.left.has_value()) + stack.push(allocator.getVal(n.left.value())); + if (n.right.has_value()) + stack.push(allocator.getVal(n.right.value())); } } -- cgit v1.2.3-13-gbd6f