4 ms·
Do you mean https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure or something more specific for this
by rawnlq 9y ago
Do you mean https://en.wikipedia.org/wiki/Persistent_data_structure 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 https://github.com/clojure/core.rrb-vector
- westoncb 9y agoThat 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.
- underwater 9y agoYou 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.