diff options
author | Aryadev Chavali <aryadev@aryadevchavali.com> | 2024-07-26 01:46:31 +0100 |
---|---|---|
committer | Aryadev Chavali <aryadev@aryadevchavali.com> | 2024-07-26 02:54:02 +0100 |
commit | ee1cc0816a2b429952562953d1e1d3768d4c741a (patch) | |
tree | 3d59d09dcf310662cdc83d0d526fa0e7d5accce7 | |
parent | 9769337a9275d6a46373ba8094c2e05eb389dbd5 (diff) | |
download | cw_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.
-rw-r--r-- | src/main.cpp | 26 |
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) { |