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

Benchmarking Bowtie2 Threading

I've been using Bowtie2 to align reads to genomes, and one of it's many settings is the number of threads. While sometimes people advise using about as many threads as your machine has cores, but if I'm running on a big machine are there diminishing retur…

via Jeff Kaufman's Writing December 01, 2023

Control - how to make a game enjoyable for casual audiences

I’ve decided to intentionally take more time to play video games this year, since it’s a relatively healthy way to escape from the real world once in a while. A friend recommended one game in particular: Control: Ultimate Edition. During the Steam summer s…

via ./techtipsy December 01, 2023

clang now makes binaries an original Pi B+ can't run

I have a bunch of Raspberry Pi systems all over the place, goofy things that they are. They do dumb and annoying jobs in strange locations. I even have one of the older models, which is called just the B+. You can think of it as the "1B+" but apparen…

via Writing - rachelbythebay December 01, 2023

Generated by openring-rs