Per VognsenSince I was doing something the other day which is related to this: sometimes, instead of implementing features like undo/rollback for a higher-level data structure, you can implement it at the level of the data structure's backing memory. While you can do it for a lower level, byte-oriented memory, it can be faster and simpler if the backing memory is more structured, e.g. an arena of typed nodes, where node fields provide a natural granularity for updates.
Ultimately it's not that different from how disk-based database systems tend to be page-oriented for their transaction layer but it works just as well for in-memory data structures and if the backing memory is strongly typed. I remember there was an academic paper (using Ocaml as the implementation language) that can basically be summarized as "persistent union-find = imperative union-find + persistent array a la Baker" but you can replicate that formula ad nauseam.
mistymntncop@blackeggs That looks right. There's also a more recent one I can't find right now.
@blackeggs Here's an example: https://cambium.inria.fr/~fpottier/unionFind/doc/unionFind/#stores
@pervognsen Thanks. Don't know OCaml so it's a bit of a struggle for me. Trying to use Gemini to help me understand ha.
@blackeggs I don't think there is anything deep going on here with the code; I just linked it because you asked. It should be self-explanatory just at the idea level, especially given that we've talked about closely related issues before.
@pervognsen mmm, i think it's starting to make more sense now. With figures 1 and 2 of the version tree. And then they do pointer reversal from the current version to the target version to rollback to a particular version state.
@blackeggs Oh, that rerooting trick is ancient history from 1978: https://www.plover.com/misc/hbaker-archive/ShallowBinding.html. It's very neat!
@pervognsen It's a cool trick. I hope this is correct. I don't bother with having the current version node point to the actual values array, it just makes things more complicated. Uses stackless traversal using pointer reversal for reroot, no recursion needed.
https://gist.github.com/mistymntncop/d2b54ef13911f5ef203f4160bfd06102
