Lab notes #012 Taking right and left and the case of the weird iterator

After the iteration over values was done, it was quick work to write tests for concatenation and make sure that it was working correctly. Then the time thereafter was some cleanup and moving stuff out to their own files.

The work this week to implement take_right and take_left, which is essentially taking one side of the RRBT and discarding the other side. In order to do this, I ended up writing another iterator, this time over the internal nodes. It ended up being a little odd since I needed to traverse the height of the trie and push them onto a stack when the iterator is created. Then when next() is called, it just pops the nodes off of the stack.

This seems a little weird because all the work is being done upfront when the iterator is created, which kinda defeats the purpose of an iterator, where the work is spread out with each call to next(). However, I figured:

1. The height of the trie is constrained to about 7 levels in practice for a 32-bit key. So doing the work upfront on iterator creation doesn't seem too bad.
2. And if I wrote the internal node walker recursively, I'd just be storing the node path on the call stack instead of in an actual stack in the iterator.

The reason why this weird iterator exists is that:

• And in every operation, you need to start at the root, because that's the only thing you have reference to at the start of every operation.
• It's a lot easier to build tries without having to fight the borrow checker if the trie is built from the bottom up. Every child is actually an Rc<> to a node, so mutating it is out of the question.
• However, there are no references to the parent at each node, so once you find a leaf node, you can't follow parent references back up to the top. The only way to trace a path bottom up is if you remembered the path on the way down.

Time will tell if this is a bad idea. But headway was made. With concat, append, and take_right, take_left, insert_at was fairly easy to write, as promised. There's a last weird bug with it that remains to investigate, but hopefully, it won't blow everything else up for this next week.

Took to tweeting more this week, and thought the following threads had the beginnings of a thought.