Memory lane, geek edition...

Memory lane, geek edition...  I stumbled across this 1999 paper on data structures for representing text sequences in editors.  I love the idea of using a simulator to rank the data structure approaches! 

All of the data structures it discusses are far older than that paper, and I've implemented many of them.  In the late '70s I wrote a Basic interpreter that used a buffer for each line of the program.  In the early '80s I wrote a text editor (in Pascal!) that used what the paper's author calls a “piece table” data structure that included a snapshot feature (not discussed in the paper, but an obvious enhancement). 

I got the idea for that last by reverse-engineering a '70s program by MicroPro called WordMaster (manual) – a general purpose WYSIWYG text editor I used for programming.  I was amazed by its ability to handle large text files, and I wanted to know how it worked.  I reverse engineered enough of it to understand that it kept something like a piece table data structure, and that gave me the ideas I needed to write my own with the snapshot capability.  The “gap” approach discussed in the paper is new to me, and I'm surprised its performance was as good as it was...