UNDO実装の定石ってあるんですか？

世の中には色々なエディタがありますが、UNDOって大体どんな感じて
実装されてるんでしょうか？
一回の操作ごとにバッファを全部記憶していたらメモリが大変なことに
なるし、かといって差分（一回ごとの操作でやったこと）だけを
保存してUNDO実行時にその逆の操作をするとすると、
不可逆操作のときはどうすんだ、とか、考えてみると不思議です。
両方を使い分けているのかな。

どなたかお詳しい方教えていただけませんか？

速度を気にしなければdiff＠｀patchを使えば出来そうだ。。。

editを中間言語通してやるようにして「何行目にxxxを追加した」とか
「何行目からyyyをどけた」とかを記憶しとけばできそうな。

エディタでマクロが使えるのが多いのはそういう理由か？

>>1
UNDOするってことはREDOも行なうんですか？
他の人も言ってますが、内部でコマンドみたいなのを作るのが楽だと思います。
それをスタックに持ちます。
コマンドにはREDO/UNDOの情報（一つにまとまるならそれで、）が
くっつくわけですが、エディタの場合、ユーザの操作に合わせて差分情報を
作っていく事になります。
例えば、’あ’という文字を入力したら、共通的な情報としてテキスト／カーソル
の位置、REDO情報には'あ'という文字、UNDO情報には削除、という具合です。
これらの情報は一緒に持っておきます。
もしこの入力の時にREDOバッファが存在するなら、もう必要が無いので削除します。
この辺の煩雑な処理を、うまくまとめられれば、あとはコマンドを作っていく
だけです。
データ構造(参考までに)
REDO/UNDOスタック
|--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+//--+
|　　　　　　　　　　　↑
|　　　　　　　　　　　Redo/Undoポインタ（現在のエディタの状態）
|　　　　　　　　　　　｜
|これ以前はREDO｜これ以降はUNDO
|　　　　　　　　　　　｜
最新の更新←　　　　　　　　　　　→オリジナル

いちお、デザインパターンのcommandパターンが定石にはなるかと。

>>5
デザインパターンの本は、わかりにくい気がしませんか？
言いたいことはわかるんですが。訳者が駄目なのかなあ。
著者の寝言聞いてるみたいで気持ち悪いですね。

あー、俺もまともに読んでないっす、あの本。
概略さえつかめればそれでオーケーなんじゃない？

無限UNDOって・・・

>>8
ん? 人生やり直したいとか思うことない??

>6.7

それ以前に、斜め読み程度でだいたいのイメージがつかめる
くらいの知識と経験を身に付けなさい。
それ以前の段階で、あれだけ読んでも無駄です。

>>4
ありがとうございます。やはり差分情報を逐一記憶している
ということですね。そしてUNDO情報とREDO情報を両方記憶する
ことで不可逆操作も戻せるということでしょうか。
ということは、Photoshop等のグラフィックエディタでは
「ぼかし」などの不可逆操作が多数ありますが、
全体に対してこのような操作を何度も行うと、毎回ぼかす前の
画像を例えばUNDO情報に保存しているということでしょうか。
でもあのソフトはREDOしたときも一瞬で戻るから、ぼかし後の
画像も記憶しているのかな。メモリの消費は莫大ですね。

描画動作の情報を最初から全部記憶しておくのじゃ駄目かなー。
どっかのアルゴリズムでそういうの見たことあるんだが。
俺その辺詳しくないから自信ないスマソ

適当にアプリ作ってて、そういえばＵＮＤＯどうしようって考えるんだよな。

>11
操作ごとに1フレームの動画として保存するとか(藁
MPEG4なんかの動画像向けの圧縮アルゴリズムが利用できて幸せだと思うぞ。

>>11
グラフィックエディタで変更の大きな操作の場合、
前回の画像を全部覚えてるんじゃない？
そしてUNDOすると今の情報がUNDOバッファに入って
UNDOを繰り返すといったり来たりする。
俺はそう作ったぞ。

ところで実装って英語でimplementでいいの？

>>16
駄目レス。

なして俺にもつっかかるかなあ。まあ、場所が場所だけに仕方ないけど。

>18
ここは単なる煽りはいっぱいいても良いと思うけど、
外でもあんなこと言ってたら頭にくるから一言。
気にしないで自分の感じた通りに時々読んで下さい。

GoFやBushmannとかが業界全体の再利用性の向上のために
汗水垂らして本にしてるのに、あんなこと言われると台無しだよね。
# 因みにデザパタ専門だけどあの本は訳してないです。

>11
何のソフトかによるけど、操作とデータ全体のどちらでも
保存しておけるようにしとくと良いですよ。
15さんが言ってるように、操作の実行に時間がかかる場合は
前のデータをそのまま表示すれば良いし、時間がかからなければ
操作を覚えておくように実装すれば良いです。

他のファクターとして操作を記憶するだけでUndo/Redoを
実装するのは整合性を取るのが難しい場合がある。その場合は
商用製品だと実装+テスト時間とのトレードオフで決めます。
Observerパターンがきちんと出来てる方が整合性が取り易い。

というか、俺「も」貴方同様に6が過激だと思ったので、
まあまあってなだめるっていうか、流すつもりで書いたんですがね。
10は真面目な話、かなりグサッと来ましたよ。

まあ、もういいです。俺が言葉足らずだったのが悪いんで。鬱だ氏のう

運動？

そういう事は２で書かなきゃ…

時々しかみない＆時差もあるし...すまソ。

あと、GoFでもGrandでも誰のカタログにも共通してることだけど、
Undo/Redoを実装する時に作るCommandの実行メソッド
# excute()とかdoIt()とかissue()とか
に引数がないけど、ここにコンテキストディクショナリのような形で
コマンド実行の瞬間の世界の情報を渡してあげると良いです。
単にObserver(大抵はView)を渡すだけでも、データを取り出すことに
関してCommandの独立性を上げるのに効果あります。

シングルウィンドウのうちはSingletonとかグローバル
データを使ってObserverのSubjectを取り出せるから良いけど、
MDIやフローティングツールパレットを使い始めると動的な
メニューの切り替えとかまで管理しなければならなくなる。

あるいはカタログ通りに引数無しで実行するようにして、
Command作成時にViewやSubjectをセットする方法もあります。
これはCommandの生成時の契約が一つのインタフェースに
し難いのが難点。

どちらを選ぶかはGUIライブラリの制約によります。

>1
viviというエディタのドキュメントが参考になるよ!!

内容は、4が言っているアイデアと大体同じで、UNDOオブジェクトを
溜めていくというもの。

　ttp://hp.vector.co.jp/authors/VA007799/viviProg/doc3.htm