Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #14772 > unrolled thread

Undo / Redo design pattern.

Back to article view | Back to comp.programming

Contents

  Undo / Redo design pattern. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-03 04:16 -0700
    Re: Undo / Redo design pattern. Öö Tiib <ootiib@hot.ee> - 2022-04-03 06:26 -0700
      Re: Undo / Redo design pattern. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-03 13:32 -0700
    Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 01:03 -0700
      Re: Undo / Redo design pattern. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-04 01:49 -0700
        Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 05:23 -0700
          Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 06:02 -0700
            Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 06:14 -0700
              Re: Undo / Redo design pattern. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-04 06:38 -0700
                Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 18:02 -0700
                  Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 18:08 -0700
            Re: Undo / Redo design pattern. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-04 06:46 -0700
              Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 17:59 -0700
        Re: Undo / Redo design pattern. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-04-05 02:25 +0100
          Re: Undo / Redo design pattern. Julio Di Egidio <julio@diegidio.name> - 2022-04-04 18:53 -0700
          Re: Undo / Redo design pattern. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-04-05 02:03 -0700
    Re: Undo / Redo design pattern. Kristjan Robam <ya3891921@gmail.com> - 2022-04-04 04:04 -0700

#14772 — Undo / Redo design pattern.

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.

However this is memory greedy. So it is better to use the following pattern, on stack push, take the difference between stack top and the object being pushed. Then delete stack top, and replace with the difference between the pushed object and stack top, then push. To pop the stack, apply the difference to stack top, and set it as new stack top.

This could be made generic, but it involves a user-supplied delta codec which could be hard to write. Another way of doing it is to feed everything through a tostring / fromstring representation.

The problem is now reduced to writing the delta codec for two strings. The proper way to do this is to use a string alignment algorithm, but that is likely to be overkill. The majority of changes will be either one character or one indel. If we've got more than few changes, we can simply resort to storing the entire string.
 

[toc] | [next] | [standalone]

#14773

On Sunday, 3 April 2022 at 14:16:14 UTC+3, 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. 
> 
> However this is memory greedy. So it is better to use the following pattern, on stack push, take the difference between stack top and the object being pushed. Then delete stack top, and replace with the difference between the pushed object and stack top, then push. To pop the stack, apply the difference to stack top, and set it as new stack top. 
> 
> This could be made generic, but it involves a user-supplied delta codec which could be hard to write. Another way of doing it is to feed everything through a tostring / fromstring representation. 
> 
> The problem is now reduced to writing the delta codec for two strings. The proper way to do this is to use a string alignment algorithm, but that is likely to be overkill. The majority of changes will be either one character or one indel. If we've got more than few changes, we can simply resort to storing the entire string.

Storing whole program state is pointlessly memory consuming and diffing whole program state is pointlessly expensive. 
More usual is to make all actions to be required to record their reverse actions.
 
So when action is done then reverse action is stored to undo stack and redo stack is cleaned.
Undo then means that reverse action is done and removed from undo stack and action is stored to redo stack.
Redo then means that action is done and removed from redo stack and reverse action is stored to undo stack.

That takes designing (and testing) your commands/actions/operations more carefully.
But that is anyway not bad at all in the long run.  

[toc] | [prev] | [next] | [standalone]

#14774

On Sunday, 3 April 2022 at 14:26:22 UTC+1, oot...@hot.ee wrote:
> 
> Storing whole program state is pointlessly memory consuming and diffing whole program state is pointlessly expensive. 
> More usual is to make all actions to be required to record their reverse actions. 
> 
> So when action is done then reverse action is stored to undo stack and redo stack is cleaned. 
> Undo then means that reverse action is done and removed from undo stack and action is stored to redo stack. 
> Redo then means that action is done and removed from redo stack and reverse action is stored to undo stack. 
> 
> That takes designing (and testing) your commands/actions/operations more carefully. 
> But that is anyway not bad at all in the long run.
>
I decided to knock something up anyway.
I just diff by finding the changed section. It will be inefficient if the user makes an edit which moves
an item from the start of the string to the end, which is the most likely bad-case scenario. But it's
O(N) in text size.
The other question is whether there will be many applications which can cheaply stringify their
state. This approach makes sense for Crossword Designer, because the program state is just
a crossword, which is 15x15 bytes for the grid and up to about a hundred short strings for the clues.
But how many other programs have those characteristics I don't know.

[toc] | [prev] | [next] | [standalone]

#14778

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.

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...

Julio

[toc] | [prev] | [next] | [standalone]

#14779

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.
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,
then user operations are expressed as operation on that graph, and you store the operation
in the undo system.

That is how a lot of programs work. But it means the undo/redo system dominates the design
of the program. 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. 

[toc] | [prev] | [next] | [standalone]

#14781

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<T> implements IList<T>, 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

[toc] | [prev] | [next] | [standalone]

#14782

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<T> implements IList<T>, 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 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

[toc] | [prev] | [next] | [standalone]

#14783

On Monday, 4 April 2022 at 15:02:24 UTC+2, Julio Di Egidio wrote:
> 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: 
<snip>
> > > 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.

In fact, "again use the key to, viceversa, know which -- property value to change/restore", no need to now about actions at all, this is all about property values.  The only reason I can think of to, a this point, also record the name of the action with every entry in the stack, is to be able to show it it to the user or similar...

Anyway, details apart, I'd think that's pretty much it: the only open question on my side is what you mean by "program state" and why...

BTW, sorry for being a bit messy.

Julio

[toc] | [prev] | [next] | [standalone]

#14784

On Monday, 4 April 2022 at 14:14:38 UTC+1, ju...@diegidio.name wrote:
> 
> In fact, "again use the key to, viceversa, know which -- property value to change/restore", no need to now about actions at all, this is all about property values.
> The only reason I can think of to, a this point, also record the name of the action with every entry in the stack, is to be able to show it it to the user or similar... 
>
That's a good point. Some programs show "undo paste", "undo clear" and so on, rather than just "undo".
> 
> Anyway, details apart, I'd think that's pretty much it: the only open question on my side is what you mean by "program state" and why... 
> 
In Crossword Designer, which is my currently active hobby project, the program state is the crossword. So a W x H grid of characters
representing the current gird, and a list of clues. As the user uses the program, he can add or delete letters, or turn black grid squares
into letter ones or vice versa. The can also edit the clues. And if he changes the grid so as to change the relationship of the clues
to the numbers, the program will update the clues for him.
So just a small amount of data. I have an undo/redo system, so he can undo or redo an action. But currently it just saves the entire
crossword. Most edits change only one letter, so this seems a bit wasteful, I wondered if I could do better.

Strictly speaking, the position of the cursor on the grid is also part of the program state. But users don't expect moving the cursor
to create an undoable action, and I doubt they care whether the cursor is restored after an undo.

[toc] | [prev] | [next] | [standalone]

#14788

On Monday, 4 April 2022 at 15:38:25 UTC+2, Malcolm McLean wrote:

> Most edits change only one letter, so this seems a bit wasteful, I wondered if I could do better. 

Either you do it or you don't.

And you haven't engage with my observation that this is *not* about "program state".  Talking of how to approach the whole thing "canonically"...

> Strictly speaking, the position of the cursor on the grid is also part of the program state. But users don't expect moving the cursor 
> to create an undoable action, and I doubt they care whether the cursor is restored after an undo.

I dislike it but most more advanced editor do have it, usually optional.

Anyway, just my 2c: have fun.

Julio

[toc] | [prev] | [next] | [standalone]

#14789

On Tuesday, 5 April 2022 at 03:02:11 UTC+2, Julio Di Egidio wrote:
> On Monday, 4 April 2022 at 15:38:25 UTC+2, Malcolm McLean wrote: 
> 
> > Most edits change only one letter, so this seems a bit wasteful, I wondered if I could do better.

And that's anyway inaccurate: most editors will compound changes in between movements of the cursor.

Anyway, enough said.

> Either you do it or you don't. 
> 
> And you haven't engage with my observation that this is *not* about "program state". Talking of how to approach the whole thing "canonically"...
> > Strictly speaking, the position of the cursor on the grid is also part of the program state. But users don't expect moving the cursor 
> > to create an undoable action, and I doubt they care whether the cursor is restored after an undo.
> I dislike it but most more advanced editor do have it, usually optional. 
> 
> Anyway, just my 2c: have fun. 

Julio

[toc] | [prev] | [next] | [standalone]

#14785

On Monday, 4 April 2022 at 14:02:24 UTC+1, ju...@diegidio.name wrote:
>
> In fact, a stack that does not implement access by index just wouldn't cut it.
> 
You can only undo the item on top of the stack. So if you just have undo, a stack is
fine. If you have redo, you can only redo the last operation that was undone. So
one way is to use a stack with an index indicating the current undo position.
The other way is to have two stacks, and push to the redo stack on every undo.

If you have two stacks, they can be true stacks, with only the top accessible.
and that has the advantage that we don't need to store whole objects in the stacks.
We can store the top object, then the delta from the top to the next, and so
on. When we push the stack, we calculate the delta, and replace stack top with
the delta, then place the new object on the top.  When we pop the stack,
stack top is the object we return, and we apply the delta to create the new
stack top.

[toc] | [prev] | [next] | [standalone]

#14787

On Monday, 4 April 2022 at 15:46:12 UTC+2, Malcolm McLean wrote:
> On Monday, 4 April 2022 at 14:02:24 UTC+1, ju...@diegidio.name wrote: 
> > 
> > In fact, a stack that does not implement access by index just wouldn't cut it. 
> >
> You can only undo the item on top of the stack.

At that point I had explained exactly how to do it with one stack: indeed you just need a stack pointer and what you can do with that.

> If you have two stacks, they can be true stacks

There is no such thing as a "true stack", there is the basic stack from programming course #1 and then there is more.

Julio

[toc] | [prev] | [next] | [standalone]

#14790

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> You need two stacks because after a series of undos, you have a series
> of redos.

This is just a random observation that might trigger something useful in
more complex situations...

Emacs has what I find to be a very useful refinement of undo/redo: it
can be limited to a region of the text.

Say I delete most of the quoted material in a reply (Emacs is my Usenet
client), and then make a few remarks at the end of the post, maybe doing
some undo or redo operations.  If I now realise I need some of the stuff
I delete for context, I can highlight the top of my reply and undo in
the selected region only.  The big delete will be undone, and I can then
do the more selective editing I now know I need.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#14791

On Tuesday, 5 April 2022 at 03:25:43 UTC+2, Ben Bacarisse wrote:

> This is just a random observation that might trigger something useful in 
> more complex situations... 
> 
> Emacs has what I find to be a very useful refinement of undo/redo: it 
> can be limited to a region of the text.

Maybe worth noticing in this context (see the original question) is that those are already applicative details: a generic undo/redo engine just handles opaque path/value pairs, what's encoded in those paths and values is application specific.  Then of course one might think of abstracting a little bit on the cases for the paths and values in various scenarios (from a text editor to a database manager to a designer and what not: whether they have something in common), but this would be a different and further layer of abstraction, and I haven't yet thought about it at all, but my guess is that this isn't worth it, as there isn't much here in terms of actual generality and shared logic.  That's also an example of what in real production rather comes out incrementally, as long as the architecture is at every step rational...

Julio

[toc] | [prev] | [next] | [standalone]

#14792

On Tuesday, 5 April 2022 at 02:25:43 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > You need two stacks because after a series of undos, you have a series 
> > of redos.
> This is just a random observation that might trigger something useful in 
> more complex situations... 
> 
> Emacs has what I find to be a very useful refinement of undo/redo: it 
> can be limited to a region of the text. 
> 
> Say I delete most of the quoted material in a reply (Emacs is my Usenet 
> client), and then make a few remarks at the end of the post, maybe doing 
> some undo or redo operations. If I now realise I need some of the stuff 
> I delete for context, I can highlight the top of my reply and undo in 
> the selected region only. The big delete will be undone, and I can then 
> do the more selective editing I now know I need. 
> 

I knocked it up. Unfortunately Google groups will wreck the formatting.
The DeltaString class is the crucial part. How to encode the edit distance 
between two strings efficiently in space and time, bearing in mind that
most edits will be small.
I just take the changed region. This will not work well if the edit is a move
from the start of the representation to the end.

I chose C++, though the basic pattern is language-agnostic.

The system should work well for Crossword Designer. If it will generalise to
other programs I don't know.
/*
* UndoRedo stack, by Malcolm McLean.
* Draft version, do not use
* Free for any use
*/
#pragma once

#include <deque>
#include <vector>
#include <string>
#include <cassert>

template<typename T, typename ToString, typename FromString> class UndoRedo
{
	class DeltaString
	{
		struct Diff
		{
			int original_index;
			int original_length;
			std::string replacement;
		};
		Diff mDiff;

		static Diff getGreedyDiff(std::string const& a, std::string const& b)
		{
			int starti, endia, endib;
			Diff diff;

			for (starti = 0; starti < a.length() && starti < b.length(); starti++)
				if (a[starti] != b[starti])
					break;
			if (starti == a.length() && a.length() == b.length())
			{
				diff.original_index = 0;
				diff.original_length = 0;
				diff.replacement = std::string();
			}
			endia = (int)a.length() - 1;
			endib = (int)b.length() - 1;
			while (endia >= starti && endib >= starti)
			{
				if (a[endia] != b[endib])
					break;
				endia--;
				endib--;
			}
			endia++;
			endib++;
			
			diff.original_index = starti;
			diff.original_length = endia - starti;
			diff.replacement = b.substr(starti, endib - starti);

			return diff;
		}
		static std::string applyDiff(std::string const& a, Diff const& diff)
		{
			std::string start = a.substr(0, diff.original_index);
			std::string end = a.substr(diff.original_index + diff.original_length,
				a.length() - diff.original_index - diff.original_length);
			return start + diff.replacement + end;
		}
	public:
		DeltaString(std::string const& a, std::string const& b)
		{
			mDiff = getGreedyDiff(a, b);
		}
		std::string apply(std::string const& a)
		{
			return applyDiff(a, mDiff);
		}
	};
	class StringStack
	{
		std::string mTop;
		std::deque<DeltaString> mDeltas;
		bool mHasData;
		int mCapacity;
	public:
		StringStack(int capacity) : mCapacity(capacity), mHasData(false) {};
		void push(std::string const& str)
		{
			if (!mHasData)
			{
				mTop = str;
				mHasData = true;
			}
			else
			{
				DeltaString delta(str, mTop);
				mDeltas.push_back(delta);
				mTop = str;
				if (mDeltas.size() > mCapacity - 1)
					mDeltas.pop_front();
			}
		}
		std::string pop(void)
		{
			assert(mHasData);
			std::string answer = mTop;
			if (mDeltas.empty())
			{
				mTop = std::string();
				mHasData = false;
			}
			else
			{
				mTop = mDeltas.back().apply(mTop);
				mDeltas.pop_back();
			}
			return answer;
		}
		bool empty(void) const { return !mHasData; }
		void clear(void)
		{
			mTop = std::string();
			mDeltas.clear();
			mHasData = false;
		}
	};

	StringStack mUndoStack;
	StringStack mRedoStack;
	std::string mCurrent;
	ToString mToString;
	FromString mFromString;
public:
	UndoRedo(ToString tostring, FromString fromstring, int NMaxUndos) :
		mToString(tostring),
		mFromString(fromstring),
		mUndoStack(NMaxUndos),
		mRedoStack(NMaxUndos)
	{

	}
	void push(T const& obj)
	{
		std::string str = mToString(obj);
		mUndoStack.push(str);
		mRedoStack.clear();
	}
	T undo(T const &redoobj)
	{
		assert(hasundos());
	    mCurrent = mUndoStack.pop();
		std::string redostr = mToString(redoobj);
		mRedoStack.push(redostr);
		return mFromString(mCurrent);
	}
	T redo(void)
	{
		assert(hasredos());
		mUndoStack.push(mCurrent);
		mCurrent = mRedoStack.pop();
		return mFromString(mCurrent);
	}
	void clear(void)
	{
		mUndoStack.clear();
		mRedoStack.clear();
	}

	bool hasundos(void) const { return !mUndoStack.empty(); }
	bool hasredos(void) const { return !mRedoStack.empty(); }
};
.

[toc] | [prev] | [next] | [standalone]

#14780

Something for You.

Can You help me out with 2100 euros ?

I want to buy a new Iphone.



Kristjan Robam

Malcolm McLean kirjutas Pühapäev, 3. aprill 2022 kl 14:16:14 UTC+3:
> 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. 
> 
> However this is memory greedy. So it is better to use the following pattern, on stack push, take the difference between stack top and the object being pushed. Then delete stack top, and replace with the difference between the pushed object and stack top, then push. To pop the stack, apply the difference to stack top, and set it as new stack top. 
> 
> This could be made generic, but it involves a user-supplied delta codec which could be hard to write. Another way of doing it is to feed everything through a tostring / fromstring representation. 
> 
> The problem is now reduced to writing the delta codec for two strings. The proper way to do this is to use a string alignment algorithm, but that is likely to be overkill. The majority of changes will be either one character or one indel. If we've got more than few changes, we can simply resort to storing the entire string.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web