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

Air Skoog

One of basketball's early jump shooters and my next dunk goal

via Vertically Challenged July 17, 2024

Put Up Or Shut Up

I feel like the tech industry is currently in the midst of the most bizarre cognitive dissonance I've ever seen — more so than the metaverse, even — as company after company simply lies about their intentions and the power of AI. I get it. Everybody wants

via Ed Zitron's Where's Your Ed At July 16, 2024

Turning Your Back On Traffic

We do a lot of walking around the neighborhood with kids, which usually involves some people getting to intersections a while before others. I'm not worried about even the youngest going into the street on their own—Nora's been street trained for abou…

via Jeff Kaufman's Writing July 16, 2024

Generated by openring-rs from my blogroll.