3 ms·

I see a bunch of editors using ropes. Are they in any way superior to RRB trees? My gut tells me no, but ai might be missing something.

• cschmidt 5y ago
  Pragmatically, there is a nice rust crate that implements a rope [1]. I think that has a lot to do with it. And it is a nice data structure for editors. [1] https://docs.rs/ropey/latest/ropey/ https://docs.rs/ropey/latest/ropey/
  • bjoli 5y ago
    Of course. The rrb tree implementation in im.rs handles inserts in a way that might lead to the same problems of ropes, but without doing any rebalancing. That would make it unsuitable for text editor usage.
• aledue 5y ago
  Are there any accessible explanations of RRB trees? I tried implementing them a while ago but all I could find was a something-hundred pages thesis and a paper with some Scala code that I didn't fully grasp ;)
  • bjoli 5y ago
    The simple explanation is "take the bit partitioned immutable vectors and relax the leftwise dense requirement" and then sprinkle some magic implementation dust in between that and the finished implementation. On a more serious note: the only complex piece of code to write is the merge and split operations, but since the structure of the tree is given it isn't theoretically hard. It is just a pain in the ass. There are two high quality implementations. One for c++ (immer) and the one in scala. Bagwell did a talk about it on YouTube as well.