Day 30: Branching out

A quick in the weeds update today. Unlike previous sessions, most of my work was spent thinking through how to construct trees on pen and paper. I think this has lead to a good strategy, but I have not yet had the chance to implement it. I have a work-in-progress test that exercises the code, which fulfills my “write code” obligations, but the rest of this will be theory.

Family dynamics

Consider the following tree diagram:

a
├── b
│   ├── c
│   │   ╰── d
│   ╰── e
╰── f

I first started by imagining what it would take to draw the line containing the “d” label above. Here’s that section pulled out on its own:

│   │   ╰── d

Note that doing this correctly requires knowing a considerable amount about the rest of the structure of the tree. Because we need to connect node b to node e later on, we need a bar character that will form this connection. We likewise need another bar in the first column to represent the further off connection to f.

This dependency isn’t too complex. In short we need to know if there is a following relative node at each of the intermediary levels. There are some complexities here though. Consider this tree:

1
├── 2
│   ╰── 3
│       ╰── 4
╰── 5
    ╰── 6

Here we have a later relative at level 3, but we don’t need to render a pipe, because it is preceded by a relative at a higher level (5).

I was in the process of formalizing this relationship when I realized there’s actually a simpler way to go about it.

You didn’t learn this in school

I started my approach by considering what it would take to construct a single line of the tree diagram in isolation. I think I was lead into this pattern of thought because of distant memories of early learning-programming exercises, which would have you do things like print a triangle of asterisks of a given size, line by line. However, we don’t actually need to do that! In Ratatui widgets you have write access to the entire output at once.

Given this, a simpler way to construct the tree is to create the new branches all in one go, retroactively modifying the previous rows. For example, this is how the initial diagram would look after drawing node d:

a
╰── b
    ╰── c
        ╰── d

When moving on to e we modify the previous structure with a new branch:

a
╰── b
    ├── c
    │   ╰── d
    ╰── e

We set pipe characters on each row between the previous junction and that of the newly introduced node. Importantly, we also modify the previous junction, changing it from a L into a T junction. Of course, sometimes you don’t have a previous sibling, in which case you skip this step, creating only the bottom L junction.

Tomorrow I plan to implement this algorithm, and hope that it will be as straightforward in practice as I imagine.