Design and Implementation of a Win32 Text Editor (2005)
I don't see it mentioned in the text, but essentially the best-known data structure for representing large amounts of random-location-editable text is called the Rope. It's based on my favorite data structure, the Finger Tree, which has very impressive asymptotic performance characteristics over a huge range of intuitively (but not actually) expensive operations.<p>It doesn't require you to break the text up into lines and hope for short lines or anything; you can insert, split, cut, paste, delete, whatever, with at worst O(log(n)) for "expensive" operations (like beginning to edit at a random point in the text, or cutting/pasting a huge chunk of text) and O(1) for "cheap" operations (like insertion/deletion of a character after you've started editing).<p>It's based on a finger tree containing densely packed byte or UTF arrays (strictly speaking, this isn't necessary, but gives an appreciable constant time/memory speedup), and tree nodes are tagged with the length of all text underneath them. Here's an implementation specialized to byte arrays (not UTF-8). <a href="https://hackage.haskell.org/package/rope" rel="nofollow">https://hackage.haskell.org/package/rope</a>