Lab notes #010 4th time's the charm to rewrite append

Lab notes #010 4th time's the charm to rewrite append
A writer writing at a desk with pencil and paper next to a trashcan overflowing with a giant pile of crumpled paper in a verdant park with gnarled trees. Natural lighting, unreal engine, anime rendering, digital art, close-up view, trending on artstation HQ

Most of this week has been spent rewriting `append()`. This stemmed from mostly following the pseudocode from the L'Orange paper too closely. Excited about ChatGPT, I used it to convert the pseudocode to Rust code and tried to go from there. However, in the end, I found that it was much better to just understand the intent of the pseudocode and rewrite it in Rust given its nature.

  1. Most of the problem stemmed from the pseudocode from C or C++, where the new branch as a result  append() is built from the root on down. This is more problematic because you end up having to create nodes and then mutate them. Given that I'm a new Rust programmer, that invokes a lot of problems from the borrow checker that I'm not always quite sure how to solve.
  2. The other issue is that you need to do a look-ahead to find the deepest vacant rightmost node to do an insertion. And for us to find that node first, we first have to do a single traversal down the right side to find that node.
  3. To build from the bottom up, the nodes have to be first traversed and then processed in reverse order. In order to do that, I tried writing an iterator, and a traversal method that yielded a closure. It turns out it's hard to write a recursive function with a closure that mutates its closure. At the end of the day, I opted for an iterative solution with a stack. The traversal down filled the stack, and then the closure is called as the stack is popped.

At the end of the day, the pre-traversal isn't as big of a deal since the height of the tree is limited to about 7 levels in an RRBT.

On to splitAt() soon.