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

A Baseball Startup with Paul Freedman and Bryan Carmel

Bryan, Adam, Steve, and the Oxide Friends are joined by the founders of the Oakland Ballers, the continuation of a long history of baseball in Oakland. There turns out to be a plenty in common between founding a computer company and founding a baseball tea…

via Oxide and Friends April 17, 2024

Platform Support

Supporting multiple platforms can be a repetitive and boring problem, or a fun challenge.

via Stay SaaSy April 17, 2024

Day 2: Cold email results

After sending a batch of cold emails to WooCommerce agencies who might be interested in Dashify, there’s been two visible results! One is that visitors to the website spiked to 9 people, myself excluded, whereas previously it might have received 1 or 2 in …

via John Jago April 16, 2024

Generated by openring-rs from my blogroll.