I was assuming the use of an auxillary data tructure, essentially a doubly-linked list of integers (or some faster hybrid data structure) to track, in order, which index or index+element have been removed or added. Since iteration for Seq always proceeds in the same linear order, this would be sufficient for all Seqs.
If the removed/added elements are not many, it’s better than creating a new collection from scratch. Probably also better for GC, as we’d only generate short-lived garbage and keep the original presumably-long-lived data structure alive.
Oh, right, sorry–I forgot that slow ops has everything, not just the slow stuff.
I guess that works out okay. It’s a bit of extra plumbing to set everything up right (every leaf type needs to actually have two leaf types, e.g. ListBufferCursor and ListBufferCursorWithSlowOps) but maybe the usage is friendlier than with an implicit gating on a per-method basis. If there were multiple things to gate, implicits would be good for handling the combinatorial complexity, but here I think there’s only one thing to gate.
1 Like
I have created a repo for exploring Cursor designs over at NthPortal/cursor-exploration. Feel free to have a look or contribute, and I am happy to give some more people write access if it gets attention
6 Likes