Aryadev Chavali
925c5e0372
This way you won't need to install raylib as a dependency in order to use it. You'll still need its dependencies, like glfw, but this should remove one layer of indirection.
Calkin-Wilf trees
A graphical visualisation of Calkin-Wilf trees.
Currently visualises it using a self adjusting number line, from the smallest fraction to the largest fraction generated. Both are always positive.
The bound fractions are drawn in white, while all other fractions are in red. On any one iteration (taking any one fraction and generating its two children fractions), the generated fractions are in blue while the generator fraction is in green.
This was done just for fun really, but it's quite fun to see it generate a dense number line over many iterations.
TODOs
TODO Tree visualisation
Instead of a number line, how about visualising the actual tree at work as a graph of nodes? Maybe colouring nodes based on where it is on the number line.
TODO Don't walk the tree everytime we compute_bounds
We already have the latest bound nodes so we're part-way through the tree. Just keep going down what we have so far surely? Even better, don't use nodes at all. Run with an index!
DONE Fix weird issue at past 100K nodes
std::vector seems to crap itself past 100K nodes - we keep getting heap-use-after-free issues when trying to access the allocator nodes at that point. Seemingly random. What's going on?
Solution: everytime we want to access the allocator for nontrivial (like memory reads) we need to lock the mutex. No two ways about it. All draw functions were causing the issue.
DONE Prettify code base
It's a big blob of code currently in the graphics portion. Not very pretty but it gets the job done. Try modularisation.
DONE Multithreading
Currently single threaded. A multithreaded implementation could have multiple nodes generated at once, which would speed up the implementation.
Might need to study my current implementation to see if it could be done better.
DONE Formalise state structure (separate drawing functions)
Make a dedicated header and fit the necessary functions to our state structure: state structure.
We need this in order so that we can get multithreading (using mutexes on the actual state itself) working.
A good working name would be cw_state.
We could then have a separate structure for the drawing context
(cw_draw) which can update itself by reading the cw_state.
DONE Setup a queue and allocator mutex on state
We need one for the queue so we can make clean pushes and pops, and one for the allocator to ensure we're not messing up our indices in the nodes.
We could just set these up in the state structure itself to make lookup easier.
DONE Make iterate use the state structure and mutexes
[[file:src/numerics.cpp::std::tuple<Fraction, Fraction, Fraction> iterate(std::queue<word_t> &queue,]]
-
Locking scheme could be:
- Lock queue when popping a value as root, then unlock.
- Leave queue and allocator unlocked while getting root/left/right values (readonly) and computing (but not setting/allocating) the left and right node values
- Allocator Lock when allocating the left/right values, setting the root's left and right, then unlock.
- Queue lock when pushing the left and right fractions for further processing, then unlock
- Unlock all when returning relevant values
I think this scheme minimises the any mutex is locked to just the bare minimum, ensuring other threads can get in on the action.