Comment by rawnlq

9 years ago

Do you mean https://en.wikipedia.org/wiki/Persistent_data_structure or something more specific for this case? It's known how to only incur an O(1) cost in time and space for making a data structure persistent. So then you just need to keep a reference to all past versions of the data structure you might ever want to undo back to.

EDIT: actually reading the wiki more carefully, I think they were talking about making a BST persistent specifically rather than any data structure. In that case looking at implementations such as rrb-vectors might be more interesting: https://github.com/clojure/core.rrb-vector

That wikipedia article looks interesting. I guess the only thing more specific I'm wondering about is persistent data structures for undo/redo systems. But just knowing the name 'persistent data structure' is useful.

You need a reference to each state, but because the components are themselves immutable you can share objects. For example a Document may contain many Blocks which contain many Lines. Changing a Line means replacing that object, its parent Block and its parent Document, but references to everything else can be copied over.