- Inserting/deleting text before a range moves it.
- Inserting/deleting text after a range leaves it unchanged.
- Inserting/deleting text within a range grows/shrinks it.
- Deleting text at a boundary shrinks the range, and deletes it when it becomes empty.
- Inserting text at boundaries can't disambiguate whether I want the text within or outside the boundaries. But I can grab some handles on the range to adjust.
The final complexity cost was 200 lines but it was a non-linear path getting there. I started out with the notion of pivots from my doodle app. There, pivots live inside the data structure for a single line of text. Since ranges now need two pivots that could be on different lines, I had to move them out. I started tracking pivots in a separate data structure, maintaining bidirectional mappings between pivots and their locations, and then tracking ranges as combinations of pivots. This quickly blew up the implementation to 500 lines, and I was juggling 27 manual tests of which half were failing.
The next day I started from scratch and threw out the notion of pivots entirely. Now I just maintain 2 locations directly inside each range, and linearly scan through them all for any book-keeping. The implementation dropped to 200 lines and the tests passed fairly quickly.
Earlier this year I threw out an implementation after suffering with it for 2+ years. It feels like I'm getting the hang of this programming thing that I threw out an implementation now after just 2 days. I'm setting a higher bar for elegance. At the same time, it's interesting that my instinct remains as poor as ever for the right approach in even a slightly new problem. Here I spent a lot of time trying to squeeze my ranges into lines so that deleting a line would transparently delete ranges within it. But I blindly assumed a fully normalized design with a first-class notion of a pivot must be a good idea.
As I linked to in the previous post, this app was inspired by this comment by Alex Kladov about how Emacs maps ranges of text to attributes.
This post is part of my Freewheeling Apps Devlog.
Comments gratefully appreciated. Please send them to me by any method of your choice and I'll include them here.