From: julio@diegidio.name   
      
   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...   
      
   > 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".   
      
   > 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 representation.   
   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)