From: malcolm.arthur.mclean@gmail.com
On Tuesday, 5 April 2022 at 02:25:43 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean 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
#include
#include
#include
template 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 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(); }
};
.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
