On Wed, Jul 13, 2011 at 02:33, Ghadi Shayban <gshay...@gmail.com> wrote: > > I put up a simple demo that implements a piece table data structure in > Clojure > > (This is totally an excuse to use finger trees, which Chris Houser > implemented and excellently presented at the first conj) > > A piece table is good for buffer management in a text editor, as it > gets around making changes in place. All changes are made to a > separate append-only buffer. > > I'll spare you the details but if you look at the code you'll see why > a finger tree is a good base structure... > Each piece in the table has a different "weight" (the length of the > piece), and you need to find a point without traversing the whole > sequence. > > https://github.com/ghadishayban/piece-table/blob/master/src/piecetable/core.clj
That's a nice use of finger trees. I'll take it along this morning to read on the subway. > More about piece-tables > http://www.cs.unm.edu/~crowley/papers/sds.pdf Ah, the memories! :-) Wirth and Gutknecht's Oberon System used this technique (under the name 'piece chain') for the built-in text editing facility. In their case the pieces also carried attribute (font, size, style, color) information for the run of text being described. The raw text backing the chain remained on disk. Newly entered text was appended to a separate on disk file. So, on disk text files had the property of being immutable or append only while you were editing. Saving the current document replaced the old version atomically in the disk directory. This always struck me as a tiny bit FP, though one would never confuse Oberon with FP or a lisp. The implementation is described here: http://www.ethoberon.ethz.ch/WirthPubl/ProjectOberon.pdf (~ 5MB!) Starting at page 83. There are figures on pp 84-86. // Ben -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
