Re:Rope Science – Computer science concepts behind the Xi ed...
by asrp on Monday April 17, 2017 @11:23AM
(#14131560)
This write up is really good! Are there similar write-ups for things other than text editors?
I wonder if only wanted a printable character ASCII editor would simplify things a lot or only a little. And I guess no tabs.
> Part 2 Line breaking
I don't really understand the problem here. Can't we count the line breaks like anything else? Is it because that's not the values we want in the end?
> Part 4: Again, making this into a monoid is pretty easy. You store two copies of the (t, m) pair - one for the simple case, and one for the case where the beginning of the string is in a comment. You also keep two bits to keep track of whether the string ends or begins a comment. In principle, you have to do the computation twice for both cases, whether the first line is a comment or not, but in practice it doesn’t make the computation any more expensive: you compute (t, m) for the first line and for the rest of the string, and just store both the first value and the monoid sum.
What if a node of the rope contains an "end comment" and (later) a "("? What should the two pairs of (t, m) be? Now that substring might be entirely inside, outside or partially outside and inside a comment.
Although I do understand the general idea of computing the result for all possible initial/input state to achieve paralellism.
I wonder if only wanted a printable character ASCII editor would simplify things a lot or only a little. And I guess no tabs.
> Part 2 Line breaking
I don't really understand the problem here. Can't we count the line breaks like anything else? Is it because that's not the values we want in the end?
> Part 4: Again, making this into a monoid is pretty easy. You store two copies of the (t, m) pair - one for the simple case, and one for the case where the beginning of the string is in a comment. You also keep two bits to keep track of whether the string ends or begins a comment. In principle, you have to do the computation twice for both cases, whether the first line is a comment or not, but in practice it doesn’t make the computation any more expensive: you compute (t, m) for the first line and for the rest of the string, and just store both the first value and the monoid sum.
What if a node of the rope contains an "end comment" and (later) a "("? What should the two pairs of (t, m) be? Now that substring might be entirely inside, outside or partially outside and inside a comment.
Although I do understand the general idea of computing the result for all possible initial/input state to achieve paralellism.