5 ms·

Data Structures for Text Sequences (1998) [pdf]

103 points by fabriceleal 12y ago

jjangsangy 12y ago
I don't think I ever really understood what a descriptor was until reading this, and now I feel really stupid but at the same time grateful!
cjensen 12y ago
Is the typo in the first sentence (the letters in "to" are reversed) a joking reference to the the topic "text SEQUENCE"?
- gavinpc 12y ago
  Good question. It was asked (but never answered) last time this was posted: https://news.ycombinator.com/item?id=8828207 https://news.ycombinator.com/item?id=8828207 Personally, I think it must be a joke. Besides the fact that it would have been noticed and corrected by now, it's just not a "typo" kind of error (i.e. a common transposition).
deleted 12y ago
[deleted]
visarga 12y ago
I invented the "piece table" data structure independently, while writing a DOS text editor in 1990s, presented it at a symposium in my faculty and got laughed off. 20 years later I stumble into this PDF describing it as a worthwhile data structure. LOL
- martanne 12y ago
  Since I've recently implemented a text editor based on a piece table myself, I spent some time researching where the concept was first used. One of the first references (1974) I found was to the Bravo text editor for the Alto from Xerox PARC. "Alto User’s Handbook" http://research.microsoft.com/en-us/um/people/blampson/15a-AltoHandbook/15a-AltoHandbookAbstract.html http://research.microsoft.com/en-us/um/people/blampson/15a-A... Then in 1985 a text editor called Lara by J. Gutknecht who in the following years joined Wirth to build Project Oberon whose text management system is also based on a piece table. "Concepts of the text editor Lara" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.8966&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.... If somebody as other, in particular earlier references, that would be interesting. My recent implementation: https://github.com/martanne/vis/blob/master/text.c https://github.com/martanne/vis/blob/master/text.c
rsuelzer 12y ago
My alma mater.
liugiul 12y ago
This is very interesting for someone who dreams about making a text editor!

103 points by fabriceleal 12y ago

I don't think I ever really understood what a descriptor was until reading this, and now I feel really stupid but at the same time grateful!

cjensen 12y ago

Is the typo in the first sentence (the letters in "to" are reversed) a joking reference to the the topic "text SEQUENCE"?

gavinpc 12y ago
Good question. It was asked (but never answered) last time this was posted: https://news.ycombinator.com/item?id=8828207 https://news.ycombinator.com/item?id=8828207 Personally, I think it must be a joke. Besides the fact that it would have been noticed and corrected by now, it's just not a "typo" kind of error (i.e. a common transposition).

deleted 12y ago

[deleted]

visarga 12y ago

I invented the "piece table" data structure independently, while writing a DOS text editor in 1990s, presented it at a symposium in my faculty and got laughed off. 20 years later I stumble into this PDF describing it as a worthwhile data structure. LOL

martanne 12y ago
Since I've recently implemented a text editor based on a piece table myself, I spent some time researching where the concept was first used. One of the first references (1974) I found was to the Bravo text editor for the Alto from Xerox PARC. "Alto User’s Handbook" http://research.microsoft.com/en-us/um/people/blampson/15a-AltoHandbook/15a-AltoHandbookAbstract.html http://research.microsoft.com/en-us/um/people/blampson/15a-A... Then in 1985 a text editor called Lara by J. Gutknecht who in the following years joined Wirth to build Project Oberon whose text management system is also based on a piece table. "Concepts of the text editor Lara" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.8966&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.... If somebody as other, in particular earlier references, that would be interesting. My recent implementation: https://github.com/martanne/vis/blob/master/text.c https://github.com/martanne/vis/blob/master/text.c

rsuelzer 12y ago

My alma mater.

liugiul 12y ago

This is very interesting for someone who dreams about making a text editor!