描述
Broken out from https://github.com/google/xi-editor/pull/575#pullrequestreview-107817261: there are two optimizations missing from the current rope impl:
For the purpose of institutional memory, the old rope implementation has a couple of optimizations that the new one lacks:
It is more aggressive about editing in-place when a unique reference exists
The RopeBuilder is O(n) in the number of blocks, using a height-sorted stack, while the newer TreeBuilder just does pairwise concat, each of which is O(log n), so O(n log n) total.
Neither of these things is going to make a measurable difference for ordinary text editing tasks, but if xi-rope is to be considered a "gold-plated" rope library they should probably get some attention.
I think the best thing at this point is to have an open issue for the potential improvements, pointing at the deleted code as a possible inspiration.
the code in question is here.
This is not especially high priority, but could be fun for someone interested in the rope data structure.