1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
/* Copyright (C) 2024 Aryadev Chavali
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU General Public License Version 2 for
* details.
* You may distribute and modify this code under the terms of the GNU General
* Public License Version 2, which you should have received a copy of along with
* this program. If not, please go to <https://www.gnu.org/licenses/>.
* Created: 2024-07-25
* Author: Aryadev Chavali
* Description: Entrypoint
*/
#include <cstdint>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define MAX(A, B) ((A) > (B) ? (A) : (B))
typedef uint64_t word_t;
word_t gcd(word_t a, word_t b)
{
if (a == b)
return a;
else if (a <= 1 || b <= 1)
return 1;
for (word_t r = b % a; r != 0; b = a, a = r, r = b % a)
continue;
return a;
}
struct Fraction
{
word_t numerator, denominator;
bool is_simplified;
Fraction(word_t numerator = 0, word_t denominator = 1)
: numerator{numerator}, denominator{denominator}, is_simplified{false}
{
// TODO: Figure out if this is a good idea, or simplifying afterwards
simplify();
}
bool operator<(const Fraction other)
{
if (other.denominator == denominator)
return numerator < other.numerator;
// TODO: Is it better to use the GCD?
return (numerator * other.denominator) < (other.numerator * denominator);
}
bool operator==(const Fraction &other)
{
return numerator == other.numerator && denominator == other.denominator;
}
void simplify(void)
{
// No-Op if already simplified
if (is_simplified)
return;
word_t hcf = gcd(MIN(numerator, denominator), MAX(numerator, denominator));
numerator /= hcf;
denominator /= hcf;
// Ensure this is a noop after this
is_simplified = true;
}
};
std::string to_string(const Fraction &f)
{
std::stringstream ss;
ss << f.numerator << "/" << f.denominator;
return ss.str();
}
struct Node
{
Fraction value;
int64_t left, right;
Node(Fraction val, int64_t left = -1, int64_t right = -1)
: value{val}, left{left}, right{right}
{
}
};
std::vector<Node> nodes;
word_t alloc_node(Node n)
{
nodes.push_back(n);
return nodes.size() - 1;
}
void indent_depth(int depth, std::stringstream &ss)
{
for (int i = 0; i < depth; ++i)
ss << " ";
}
std::string to_string(Node n, int depth = 1)
{
std::stringstream ss;
ss << "(" << to_string(n.value) << "\n";
indent_depth(depth, ss);
if (n.left == -1)
ss << "NIL";
else
ss << to_string(nodes[n.left], depth + 1);
ss << "\n";
indent_depth(depth, ss);
if (n.right == -1)
ss << "NIL";
else
ss << to_string(nodes[n.right], depth + 1);
ss << ")";
return ss.str();
}
std::queue<word_t> to_iterate;
void iterate(void)
{
if (to_iterate.empty())
return;
word_t index = to_iterate.front();
if (nodes[index].left == -1)
{
nodes[index].left = alloc_node(Fraction{
nodes[index].value.numerator,
nodes[index].value.numerator + nodes[index].value.denominator});
}
if (nodes[index].right == -1)
{
nodes[index].right = alloc_node(
Fraction{nodes[index].value.numerator + nodes[index].value.denominator,
nodes[index].value.denominator});
}
to_iterate.pop();
to_iterate.push(nodes[index].left);
to_iterate.push(nodes[index].right);
}
int main(void)
{
word_t root = alloc_node(Fraction{2, 4});
to_iterate.push(root);
for (int i = 0; i < 10; ++i)
{
iterate();
printf("step[%d]:\n%s\n\n", i, to_string(nodes[root]).c_str());
}
return 0;
}
|
