3 ms·

Not sure it is off-topic or not, but I wonder what resources it would contain to help design a software with undo/redo feature.

by lolive 4y ago

MaxLeiter 4y ago
Am I missing something or would it just need to be a doubly linked list? It really depends on your program state being… stateful (so you can navigate forwards and back consistently)
- blt 4y ago
  If you store the total application state for each step then it's simple, but consumes lots of memory. If you want to store something more like a diff, there are choices. For example, you could have code to undo each operation, but you can also implement undo by going back to some checkpoint and then recomputing all operations between the checkpoint and now. Latter consumes more CPU, but comparable memory and a lot less code surface for bugs.
  - neilparikh 4y ago
    If you use persistent data structures, you can store the total state, and you'll get deduplication of the common parts, which brings down the memory usage to a more reasonable amount. This is what git does essentially, which gets you O(1) checkout to arbitrary steps in the future/past. This also means you don't need to design/pick a diffing algorithm, which you would be locked into (since changing the diffing algorithm would mean you couldn't consume old diffs).
    - account42 4y ago
      Git does store deltas when packing objects because storing all distinct objects as-is would be too inefficient for large repos. This isn't the same text diffs as shown to the user but there is still a diffing algorithm that all future git versions need to support (well, at least the patch counterpart).
deleted 4y ago
[deleted]
vivegi 4y ago
A Merkle-tree data structure + an append only log with checkpoints + a command processor would provide a basic foundation. Your data can be represented in a Merkle-tree. You provide operations add-node, delete-node, move-node etc., on the Merkle-tree and build a command processor that takes as input a checkpointed Merkle-tree snapshot (could be empty when you start) and a log of operations (essentially an sequence of operations). The command processor then applies the series of tree operations in the log to build the final state of the tree. The special checkpoint operation saves a snapshot of the Merkle-tree. This basic set of operations should allow you to do unlimited undo/redo/transaction playback capabilities. Also see: Command Pattern, https://en.wikipedia.org/wiki/Command_pattern https://en.wikipedia.org/wiki/Command_pattern
amelius 4y ago
Simple. For every operation performed by the user, you push a function to the end of a list that undoes that operation. When the user presses undo, you pop the function from the end of the list and call it.
medo-bear 4y ago
check out emacs' undo-tree for a cool implementation https://www.dr-qubit.org/undo-tree/undo-tree.txt https://www.dr-qubit.org/undo-tree/undo-tree.txt
- JHonaker 4y ago
  Emacs’s undo system is quite frankly amazing. Not only can you recover any state through an arbitrary number of undo and redo operations, but you can also localize the undo/redo operations to a selected region of the buffer. It’s the number one feature I miss when I’m using another editor.

Not sure it is off-topic or not, but I wonder what resources it would contain to help design a software with undo/redo feature.

by lolive 4y ago

Not sure it is off-topic or not, but I wonder what resources it would contain to help design a software with undo/redo feature.

MaxLeiter 4y ago

Am I missing something or would it just need to be a doubly linked list? It really depends on your program state being… stateful (so you can navigate forwards and back consistently)

blt 4y ago
If you store the total application state for each step then it's simple, but consumes lots of memory. If you want to store something more like a diff, there are choices. For example, you could have code to undo each operation, but you can also implement undo by going back to some checkpoint and then recomputing all operations between the checkpoint and now. Latter consumes more CPU, but comparable memory and a lot less code surface for bugs.
- neilparikh 4y ago
  If you use persistent data structures, you can store the total state, and you'll get deduplication of the common parts, which brings down the memory usage to a more reasonable amount. This is what git does essentially, which gets you O(1) checkout to arbitrary steps in the future/past. This also means you don't need to design/pick a diffing algorithm, which you would be locked into (since changing the diffing algorithm would mean you couldn't consume old diffs).
  - account42 4y ago
    Git does store deltas when packing objects because storing all distinct objects as-is would be too inefficient for large repos. This isn't the same text diffs as shown to the user but there is still a diffing algorithm that all future git versions need to support (well, at least the patch counterpart).

deleted 4y ago

[deleted]

vivegi 4y ago

A Merkle-tree data structure + an append only log with checkpoints + a command processor would provide a basic foundation. Your data can be represented in a Merkle-tree. You provide operations add-node, delete-node, move-node etc., on the Merkle-tree and build a command processor that takes as input a checkpointed Merkle-tree snapshot (could be empty when you start) and a log of operations (essentially an sequence of operations). The command processor then applies the series of tree operations in the log to build the final state of the tree. The special checkpoint operation saves a snapshot of the Merkle-tree. This basic set of operations should allow you to do unlimited undo/redo/transaction playback capabilities. Also see: Command Pattern, https://en.wikipedia.org/wiki/Command_pattern https://en.wikipedia.org/wiki/Command_pattern

amelius 4y ago

Simple. For every operation performed by the user, you push a function to the end of a list that undoes that operation. When the user presses undo, you pop the function from the end of the list and call it.

medo-bear 4y ago

check out emacs' undo-tree for a cool implementation https://www.dr-qubit.org/undo-tree/undo-tree.txt https://www.dr-qubit.org/undo-tree/undo-tree.txt

JHonaker 4y ago
Emacs’s undo system is quite frankly amazing. Not only can you recover any state through an arbitrary number of undo and redo operations, but you can also localize the undo/redo operations to a selected region of the buffer. It’s the number one feature I miss when I’m using another editor.