Dev Blog #17: Fun with sub-trees.
This week's big push is to add functionality to the Doctree system so I'll have something to put in the video I've already announced.
One thing I knew I wanted to do was to be able to display a sub-tree consisting of the changes relating to one specific note, and that turned out to be an enjoyable head-scratcher.
Drawing the full tree is reasonably straightforward. You can't do a recursive depth-first traversal because a) these trees could get large and that's asking for a stack overflow, and b) until you know how many nodes are in each horizontal 'layer' of the tree you can't position them. So I use a standard breadth-first traversal:
Add the root to a queue with a layer value of 0, then:
1) Pop the first node off the start of the queue
2) Append all its children to the end of the queue with a layer value of (this node layer + 1)
3) If there's anything in the queue, go back to 1
This ensures I encounter all the nodes in left-right breadth-first order, so whenever I encounter a new layer I know how many were in the previous layer and can position them accordingly.
Picking out a subtree proved rather harder. Here's an example of what I'm talking about:
The green nodes are actions (edits) affecting one specific note. I want to end up with a tree diagram that only includes those nodes, but which still correctly represents the parent/child relationship between the actions (so F and L should be children of D, and D should be a child of A). Not only that, but I want to process the green nodes in strictly left-to-right breadth-first order so that I can line them up nicely, and I want to do that while touching each node only once.
A / H D / O J L F / M
Assuming you're not bored already, I won't bore you now with the two hours I spent coming up with wrong answers and will instead skip to a right answer, which was pleasingly neat:
Add the root to the queue, then:
1 Pop the first node off the start of the queue
2.a If it's a node we want (green), add it to the current visible row and then add all its children to the BACK of the queue.
2.b If it isn't a node we want (not green), throw it away and add all its children to the FRONT of the queue.
3 If there's still something in the queue, go back to 1
Applying those rules to the tree above, the queue looks like this after each step:
A *
B
HC *
CNI
DNI *
NIE
OIE *
IE
JE *
E
KF
PLF
LF *
FQ *
QG
G
M *
The steps with an asterisk are the ones where a green node is encountered at the head of the queue, and as you can see we encounter them in the correct order.
I think this is one of my favourite solutions of all time, because it always looks like it's going to go wrong and then somehow doesn't.
One thing I knew I wanted to do was to be able to display a sub-tree consisting of the changes relating to one specific note, and that turned out to be an enjoyable head-scratcher.
Drawing the full tree is reasonably straightforward. You can't do a recursive depth-first traversal because a) these trees could get large and that's asking for a stack overflow, and b) until you know how many nodes are in each horizontal 'layer' of the tree you can't position them. So I use a standard breadth-first traversal:
Add the root to a queue with a layer value of 0, then:
1) Pop the first node off the start of the queue
2) Append all its children to the end of the queue with a layer value of (this node layer + 1)
3) If there's anything in the queue, go back to 1
This ensures I encounter all the nodes in left-right breadth-first order, so whenever I encounter a new layer I know how many were in the previous layer and can position them accordingly.
Picking out a subtree proved rather harder. Here's an example of what I'm talking about:
The green nodes are actions (edits) affecting one specific note. I want to end up with a tree diagram that only includes those nodes, but which still correctly represents the parent/child relationship between the actions (so F and L should be children of D, and D should be a child of A). Not only that, but I want to process the green nodes in strictly left-to-right breadth-first order so that I can line them up nicely, and I want to do that while touching each node only once.
A / H D / O J L F / M
Assuming you're not bored already, I won't bore you now with the two hours I spent coming up with wrong answers and will instead skip to a right answer, which was pleasingly neat:
Add the root to the queue, then:
1 Pop the first node off the start of the queue
2.a If it's a node we want (green), add it to the current visible row and then add all its children to the BACK of the queue.
2.b If it isn't a node we want (not green), throw it away and add all its children to the FRONT of the queue.
3 If there's still something in the queue, go back to 1
Applying those rules to the tree above, the queue looks like this after each step:
A *
B
HC *
CNI
DNI *
NIE
OIE *
IE
JE *
E
KF
PLF
LF *
FQ *
QG
G
M *
The steps with an asterisk are the ones where a green node is encountered at the head of the queue, and as you can see we encounter them in the correct order.
I think this is one of my favourite solutions of all time, because it always looks like it's going to go wrong and then somehow doesn't.
Comments
Post a Comment