Understanding the GURQ Algorithm

Just wanted to make some notes on “Resolving the Great Undo-Redo Quandary”. It was high on HackerNews, but I missed the window to post.

Here’s my attempt to visualize what the author described. This is what the undo/redo stacks would look like in the standard case (and, I believe what emacs does).

| iter | undo               | redo  | display | action  |
|------|--------------------|-------|---------|---------|
| 1    | A                  |       | A       | Add 'A' |
| 2    | AB                 |       | AB      | Add 'B' |
| 3    | ABC                |       | ABC     | Add 'C' |
| 4    | AB                 | C     | AB      | Undo    |
| 5    | A                  | CB    | A       | Undo    |
| 6    | ABC(-C)(-B)D       |       | AD      | Add 'D' |
| 8    | ABC(-C)(-B)        | D     | A       | Undo    |
| 9    | ABC(-C)            | D(-B) | AB      | Undo    |
| 10   | ABC(-C)(-B)D(-D)BE |       | ABE     | Add 'E' |

Then, there is this optimization.

Third, although it isn’t strictly necessary, we can add a slight shortcut because of redundancies. In the A-B-C example above, B) is redundant with A), because one is just the other in reverse. When the butterfly is squashed and we create B, we mark its beginning and end as “instant”; whenever we later traverse onto either end of B), we proceed to the opposite end in one fell swoop to save the user some traversal time. All edit states are recoverable from A & C alone. Again, it’s strictly optional, but less cumbersome.

After confirming with the author (thanks, Troy!) I now understand the behavior described would be like this:

| iter | undo                   | redo       | display | action  |
|------|------------------------|------------|---------|---------|
| 1    | A                      |            | A       | Add 'A' |
| 2    | AB                     |            | AB      | Add 'B' |
| 3    | ABC                    |            | ABC     | Add 'C' |
| 4    | AB                     | C          | AB      | Undo    |
| 5    | A                      | CB         | A       | Undo    |
| 6    | ABC(-C)(-B)D           |            | AD      | Add 'D' |
| 8    | ABC(-C)(-B)            | D          | A       | Undo    |
| 9    | ABC                    | D(-B)(-C)  | ABC     | Undo    |
| 10   | AB                     | D(-B)(-C)C | AB      | Undo    |
| 11   | ABC(-C)(-B)D(-D)BC(-C) |            | ABE     | Add 'E' |

Note the “fast forward” in step 9, where we rewind through both (-B)(-C).

Posts from blogs I follow

Little Helpers

Yesterday I couldn't help but feel a sense of awe at all the conveniences modern life has to offer. A lot of the chores in our household are taken care of by little helpers: The dishwasher washes the dishes, the washing machine washes the clothes, and the …

via Matthias Endler January 05, 2023

Caro, a New Static Site Generator

I'm building safer, healthier online spaces.

via atthis.link January 02, 2023

We need to talk about Dropout

Let's talk about big TV and movie studios. About the life and death of CollegeHumor, about what makes Dropout interesting, and how their video platform could be improved! 00:00 Big TV and movie studios 01:38 Internet and the attention economy 02:32 The lif…

via fasterthanli.me December 31, 2022

Generated by openring-rs