Hacker News new | past | comments | ask | show | jobs | submit login

A piece table[0] solves this rather elegantly. Since it is a persistent data structure, a mark can be represented as a pointer into an underlying buffer. If the corresponding text is deleted, marks are updated automatically, since the pointer is no longer reachable from the piece chain. Lookup is linear[1] (or logarithmic if you store pieces in a balanced search tree) in the number of pieces i.e. non-consecutive editing operations.

[0] https://github.com/martanne/vis#text-management-using-a-piec...

[1] https://github.com/martanne/vis/blob/master/text.c#L1152




I used an editor in 1980 that was implemented as piece tables! That was a 64K HP2000. It worked great!




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: