Design and Implementation of a Win32 Text Editor (2005)
I don&#x27;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&#x27;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&#x27;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 &quot;expensive&quot; operations (like beginning to edit at a random point in the text, or cutting&#x2F;pasting a huge chunk of text) and O(1) for &quot;cheap&quot; operations (like insertion&#x2F;deletion of a character after you&#x27;ve started editing).<p>It&#x27;s based on a finger tree containing densely packed byte or UTF arrays (strictly speaking, this isn&#x27;t necessary, but gives an appreciable constant time&#x2F;memory speedup), and tree nodes are tagged with the length of all text underneath them. Here&#x27;s an implementation specialized to byte arrays (not UTF-8). <a href="https:&#x2F;&#x2F;hackage.haskell.org&#x2F;package&#x2F;rope" rel="nofollow">https:&#x2F;&#x2F;hackage.haskell.org&#x2F;package&#x2F;rope</a>