aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 20:51:39 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 20:53:54 +0100
commit89fd8129817a245afdd758446ffb002467e0815f (patch)
treea94fb1852ab2723de4b77865453be520b4800ec7
parent01468f793fb0566caab9daf0a6a39532f7808b8c (diff)
downloadcw_tree-89fd8129817a245afdd758446ffb002467e0815f.tar.gz
cw_tree-89fd8129817a245afdd758446ffb002467e0815f.tar.bz2
cw_tree-89fd8129817a245afdd758446ffb002467e0815f.zip
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.
-rw-r--r--src/main.cpp20
1 files changed, 13 insertions, 7 deletions
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 <cstdio>
#include <iostream>
#include <sstream>
+#include <stack>
#include <tuple>
#include <raylib.h>
@@ -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<Node> 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()));
}
}