From: julio@diegidio.name   
      
   On Monday, 4 April 2022 at 14:23:58 UTC+2, Julio Di Egidio wrote:   
   > On Monday, 4 April 2022 at 10:49:05 UTC+2, Malcolm McLean wrote:    
   > > On Monday, 4 April 2022 at 09:03:31 UTC+1, ju...@diegidio.name wrote:    
   > > > On Sunday, 3 April 2022 at 13:16:14 UTC+2, Malcolm McLean wrote:    
   > > > > To implement a simple undo redo, you need two stacks, and a copyable   
   representation of the program state. You then push to the undo stack, with   
   straight forwards extensions for redo.    
   > >    
   > > > Why two stacks? I just see the need for one. And why "program state",   
   this is usually about a specific set of properties along some tree hierarchy   
   so that each property is identified by a unique path... and then, in a basic   
   implementation, at any    
   change you just record the path together with the value before change.    
   >    
   > > You need two stacks because after a series of undos, you have a series of   
   redos.   
   > Ah, right, I forgot the redo part. But this can still be done with one   
   stack, plus a "stack pointer", that is you need to maintain an index to point   
   at the currently "active entry": that index would be equal to the stack count,   
   meaning it's past the    
   end of the stack, when there is no redo. Then undo/redo is simply walking up   
   and down the stack and restoring whichever value is recorded there (the "value   
   before change"), while adding a new entry becomes 1) drop all entries starting   
   starting from the    
   pointer index (there will be none if there is no redo), 2) add the new entry   
   at the pointer position (this will always be an append to the stack at this   
   point, aka a push), and 3) increment the pointer index.    
   >    
   > BTW, you haven't said what language you are using, but e.g. in .Net Stack   
   implements IList, which makes manipulations easier. Indeed, in case your   
   language does not provide something like that, I'd directly use a List,   
   otherwise, for one thing,    
   dropping trailing entries as in step 1 becomes a series of individual pops...   
      
   In fact, a stack that does not implement access by index just wouldn't cut it.   
      
   > > These can be in the same contiguous region of memory in a simple   
   implementation, but you still    
   > > have two stacks, one growing up and one growing down.    
   > > In my system, you need two actual stacks, because we only store the   
   deltas, except for at stack    
   > > top, where we store the entire object.    
   > >    
   > > > That said, it's hardly the case that any diffing logic can do better   
   than just recording the old value in the case of "primitive" types: you can do   
   better for composite objects/arrays, by checking what properties have actually   
   changed (and    
   extending a little bit on the notion of changed property path). Anyway this is   
   a further step...    
   > >    
   > > I don't quite follow, but I think what you are saying is that program   
   state is held as a graph,   
   >    
   > No, I am saying why would you track "program state"? It's at best a subset   
   of program state, no? Speaking generally, I'd say there is a set of actions   
   that need to be "tracked", which are typically actions on "data", not general   
   program actions.   
   >    
   > > then user operations are expressed as operation on that graph, and you   
   store the operation    
   > > in the undo system.   
   >    
   > I am just thinking about it as hierarchically structured data, but I may   
   very well be missing part of the picture here: I am "reconstructing" this with   
   you, I do not have a ready model I am just describing to you.   
   >    
   > > That is how a lot of programs work. But it means the undo/redo system   
   dominates the design    
   > > of the program.   
   >    
   > No no, I would certainly expect the whole thing to be orthogonal to normal   
   operations: don't we just need a "definition file" where we say what maps to   
   what, plus hooks wherever relevant actions happen? And then again, this (what   
   needs to be tracked)    
   is not usually "just everything".   
      
   To be clearer, I mean mapping property values within the program to keys   
   ("paths") for tracking: then you'd use the key to add to the undo stack (where   
   you'd know which key you need because this "derives" from the specific action   
   that is originating it),    
   and when restoring state from the stack, you'd again use the key to,   
   viceversa, know which action it refers to whence which property value to   
   change/restore...  That's what I end up with.   
      
   > > And it means it needs to be bespoke. Te idea is to have a generic system,   
   which    
   > > relies on just converting the state to and from a universal    
   epresentation. Strings are the    
   > > obvious example of a universal representation.   
   >    
   > What I have been describing so far is (on the way to) totally generic,   
   rather maybe I am still missing part of the requirements: see my comment   
   above.    
   >    
   > On another note (and still relative to my "hierarchical data"), one thing   
   one might want to add is a data type along with the property path/name, but   
   even there, considering that client code and library code are most probably   
   written in the same    
   language, so they already share a same type system, in a simple implementation   
   for internal use I'd most probably not even bother about that: although this   
   is the one main extension point I see, up to custom comparers and what not.    
      
   Julio   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)