aboutsummaryrefslogtreecommitdiff
path: root/src/main.cpp
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 01:46:31 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 02:54:02 +0100
commitee1cc0816a2b429952562953d1e1d3768d4c741a (patch)
tree3d59d09dcf310662cdc83d0d526fa0e7d5accce7 /src/main.cpp
parent9769337a9275d6a46373ba8094c2e05eb389dbd5 (diff)
downloadcw_tree-ee1cc0816a2b429952562953d1e1d3768d4c741a.tar.gz
cw_tree-ee1cc0816a2b429952562953d1e1d3768d4c741a.tar.bz2
cw_tree-ee1cc0816a2b429952562953d1e1d3768d4c741a.zip
Queue based iteration procedure
Pops an item off the queue and generate left and right children for it, if those are empty. Then push those children into the queue for the next iteration. NOTE: Because we're using a queue, this does a breadth first generation of the tree, which is what we want.
Diffstat (limited to 'src/main.cpp')
-rw-r--r--src/main.cpp26
1 files changed, 26 insertions, 0 deletions
diff --git a/src/main.cpp b/src/main.cpp
index 680a69b..e89a418 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -17,6 +17,7 @@
#include <cstdint>
#include <cstdio>
+#include <queue>
#include <sstream>
#include <string>
#include <vector>
@@ -86,6 +87,31 @@ struct Node
};
std::vector<Node> nodes;
+std::queue<Node *> to_iterate;
+
+void iterate(void)
+{
+ if (to_iterate.empty())
+ return;
+ Node *node = to_iterate.front();
+ to_iterate.pop();
+ if (!node->left)
+ {
+ Node new_node = Fraction{node->value.numerator,
+ node->value.numerator + node->value.denominator};
+ nodes.push_back(new_node);
+ node->left = nodes.data() + (nodes.size() - 1);
+ }
+ else if (!node->right)
+ {
+ Node new_node = Fraction{node->value.numerator + node->value.denominator,
+ node->value.denominator};
+ nodes.push_back(new_node);
+ node->right = nodes.data() + (nodes.size() - 1);
+ }
+ to_iterate.push(node->left);
+ to_iterate.push(node->right);
+}
int main(void)
{