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
|
/* 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 "./numerics.hpp"
#include <cmath>
#include <cstdio>
#include <iostream>
#include <sstream>
#include <stack>
#include <tuple>
#include <raylib.h>
#define WIDTH 1024
#define HEIGHT 1024
#define FONT_SIZE 20
#define CIRCLE_SIZE 2
#define LINE_TOP (7 * HEIGHT / 16)
#define LINE_BOTTOM (9 * HEIGHT / 16)
Node rightmost_node(const NodeAllocator &allocator)
{
auto node = allocator.getVal(0);
while (node.right.has_value())
node = allocator.getVal(node.right.value());
return node;
}
Node leftmost_node(const NodeAllocator &allocator)
{
auto node = allocator.getVal(0);
while (node.left.has_value())
node = allocator.getVal(node.left.value());
return node;
}
constexpr word_t clamp_to_width(long double value, long double min,
long double max)
{
// translate v in [min, max] -> v' in [0, WIDTH]
// [min, max] -> [0, max-min] -> [0, WIDTH]
return WIDTH / (max - min) * (value - min);
}
void draw_fraction(Fraction f, word_t x, word_t y)
{
std::string s{to_string(f)};
// Centered at (x, y)
int width = MeasureText(s.c_str(), FONT_SIZE);
DrawText(s.c_str(), x - width / 2, y - FONT_SIZE, FONT_SIZE, WHITE);
}
void draw_node_number_line(const NodeAllocator &allocator, long double lower,
long double upper)
{
std::stack<Node> stack;
stack.push(allocator.getVal(0));
while (!stack.empty())
{
Node n = stack.top();
stack.pop();
word_t x = clamp_to_width(n.value.norm, 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()));
}
}
void draw_number_line(const NodeAllocator &allocator)
{
// Draw a general guide number line
DrawLine(0, HEIGHT / 2, WIDTH, HEIGHT / 2, WHITE);
// Figure out the leftmost and rightmost nodes for bounds
const auto right = rightmost_node(allocator);
const auto left = leftmost_node(allocator);
const auto upper_bound = std::ceill(right.value.norm);
const auto lower_bound = std::floorl(left.value.norm);
// Draw all the nodes
draw_node_number_line(allocator, lower_bound, upper_bound);
// Draw the bounds, with their values, in white
word_t lower_x = clamp_to_width(left.value.norm, lower_bound, upper_bound);
word_t upper_x = clamp_to_width(right.value.norm, lower_bound, upper_bound);
draw_fraction(left.value, lower_x, 3 * HEIGHT / 8);
draw_fraction(right.value, upper_x, 3 * HEIGHT / 8);
DrawLine(lower_x, LINE_TOP, lower_x, LINE_BOTTOM, WHITE);
DrawLine(upper_x, LINE_TOP, upper_x, LINE_BOTTOM, WHITE);
}
int main(void)
{
// Setup CW tree
NodeAllocator allocator{0};
std::queue<word_t> to_iterate;
Fraction best_frac{1, 2};
word_t root = allocator.alloc({best_frac});
to_iterate.push(root);
// Setup meta text (counter, iterations, etc)
word_t count = 1, prev_count = 0;
std::stringstream format_stream;
std::string format_str;
word_t format_str_width = 0;
InitWindow(WIDTH, HEIGHT, "Calkin-Wilf Tree");
while (!WindowShouldClose())
{
if (IsKeyPressed(KEY_SPACE))
{
iterate(to_iterate, allocator);
count += 2;
}
if (prev_count != count)
{
prev_count = count;
format_stream << "Count=" << count << "\n\n";
format_stream << "Iterations=" << (count - 1) / 2;
format_str = format_stream.str();
format_stream.str("");
format_str_width = MeasureText(format_str.c_str(), FONT_SIZE * 2);
}
ClearBackground(BLACK);
BeginDrawing();
draw_number_line(allocator);
DrawText(format_str.c_str(), WIDTH / 2 - format_str_width / 2,
LINE_TOP - HEIGHT / 4, FONT_SIZE * 2, WHITE);
EndDrawing();
}
CloseWindow();
return 0;
}
|
