aboutsummaryrefslogtreecommitdiff
path: root/src/main.cpp
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 02:11:03 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 02:54:02 +0100
commitaad22a1b203c2e8dcdc564da9e94f7b7796d0221 (patch)
treed96a5ac8f3880b148094bd9ffce06e9817c71d50 /src/main.cpp
parentcb0d4f52071409a02cb3fbb0180f41f32e5bc3a6 (diff)
downloadcw_tree-aad22a1b203c2e8dcdc564da9e94f7b7796d0221.tar.gz
cw_tree-aad22a1b203c2e8dcdc564da9e94f7b7796d0221.tar.bz2
cw_tree-aad22a1b203c2e8dcdc564da9e94f7b7796d0221.zip
Rework binary tree to use indexes in nodes vector
An index is a pointer, and they don't change if the vector decides to reallocate internally unlike the bastardised pointers I was rolling up before. This simplifies design a bit.
Diffstat (limited to 'src/main.cpp')
-rw-r--r--src/main.cpp34
1 files changed, 17 insertions, 17 deletions
diff --git a/src/main.cpp b/src/main.cpp
index fb29a93..d355694 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -78,9 +78,9 @@ struct Fraction
struct Node
{
Fraction value;
- Node *left, *right;
+ int64_t left, right;
- Node(Fraction val, Node *left = nullptr, Node *right = nullptr)
+ Node(Fraction val, int64_t left = -1, int64_t right = -1)
: value{val}, left{left}, right{right}
{
}
@@ -88,34 +88,34 @@ struct Node
std::vector<Node> nodes;
-Node *alloc_node(Node n)
+word_t alloc_node(Node n)
{
nodes.push_back(n);
- return nodes.data() + (nodes.size() - 1);
+ return nodes.size() - 1;
}
-std::queue<Node *> to_iterate;
+std::queue<word_t> to_iterate;
void iterate(void)
{
if (to_iterate.empty())
return;
- Node *node = to_iterate.front();
- to_iterate.pop();
- if (!node->left)
+ word_t index = to_iterate.front();
+ if (nodes[index].left == -1)
{
- node->left =
- alloc_node(Fraction{node->value.numerator,
- node->value.numerator + node->value.denominator});
+ nodes[index].left = alloc_node(Fraction{
+ nodes[index].value.numerator,
+ nodes[index].value.numerator + nodes[index].value.denominator});
}
- else if (!node->right)
+ if (nodes[index].right == -1)
{
- node->right =
- alloc_node(Fraction{node->value.numerator + node->value.denominator,
- node->value.denominator});
+ nodes[index].right = alloc_node(
+ Fraction{nodes[index].value.numerator + nodes[index].value.denominator,
+ nodes[index].value.denominator});
}
- to_iterate.push(node->left);
- to_iterate.push(node->right);
+ to_iterate.pop();
+ to_iterate.push(nodes[index].left);
+ to_iterate.push(nodes[index].right);
}
int main(void)