【C++】テキストエディタのバッファデータ構造・アルゴリズム【第5回】

Undo/Redo

現実世界の行動に Undo は効かないが、多くのアプリケーションには Undo 機能があり、行った操作を取り消すことができる。
手が滑って大事なテキストの一部を消してしまったとき、アプリの Undo 機能に救われた人も少なくないと思う。
さらに Undo で取り消した操作を再実行することもできる。それが Redo 機能だ。
もし、人生の Undo ができるとしたら、読者はどこまで Undo したいと思うだろうか？
それはともかく、本章ではどうやってテキストバッファの Undo/Redo 機能を実装するのかを解説する。

ちなみに、筆者が Undo 機能を初めて実装したのは、某社に入社したときの新人研修だ。
あるソフトを作るというお題だったのだが、早く出来すぎて暇だったので、お題にはない Undo/Redo まで実装してしまった。
Undo/Redo の実装方法は勉強したこともなく知らなかったので、社内をふらふら30分ほど散歩しながら実装方法を考えついたのだ。

挿入と削除処理のみを考えた場合（実際には、置換やインデント処理なども必要）の、Undo処理を行うクラス UndoMgr のクラス図を以下に示す。

【C++】テキストエディタのバッファデータ構造・アルゴリズム【第5回】_01

m_stack は Undo情報オブジェクトへのポインタを保持する FILO（First In Last Out）コンテナだ。
挿入・削除を行った場合は、その情報を持った UndoActionInsert・UndoActionDelete オブジェクトを作成し、それへのポインタをスタックに積む。
m_cur はスタックに積まれた位置を示す。
m_delText は削除された文字列を保存しておくためのもの。どこかに保存しておかないと削除処理を Undo できないからだ。
m_insText は挿入された文字列を保存しておくためのもの。挿入された文字列はバッファにあるので、保存しておく必要はないのでは？と思った人は洞察力がするどい。が、この m_insText は挿入処理を Undo され、そのあとに Redo されたときのものだ。なので、挿入直後はテキストを保存しないが、undo されたときに削除されたテキストをここに保存しておく。

挿入処理を行った場合の処理を以下に示す。

bool UndoMgr::push_back_insText(pos_t pos, int sz)
{
    UndoActionInsert *act = new UndoActionInsert();
    act->m_pos = pos;   //  挿入位置
    act->m_size = sz;   //  挿入文字サイズ
    m_stack.resize(m_cur);      //  Redo のためのオブジェクトを削除
    m_stack.push_back(act);     //  UndoAction オブジェクトをスタックに積む
    ++m_cur;                    //  スタックインデックスをインクリメント
    return true;
}

undo が実行されると、スタック上の情報を元に、編集処理を取り消す処理を行う。
挿入であれば文字を削除し、削除であれば削除された文字を挿入するわけだ。
また、m_cur をデクリメントし、さらにさかのぼって undo が可能なようにする。
undo を行っても、m_cur 以降のオブジェクトの消去は行わない。これは redo を可能にするためだ。
なので、編集処理が実行された場合は、m_cur 以降のオブジェクトを削除してから、スタックにオブジェクトアドレスを追加するようにする。

次に、undo 処理のコードを以下に示す。

void UndoMgr::undo()
{
    if( !m_cur ) return false;      //  undo オブジェクトが無い場合
    UndoAction *ptr = m_stack[--m_cur];     //  undo オブジェクトへのポインタを取り出す
    switch( ptr->m_type ) {         //  編集処理ごとに場合分け
    case UndoAction::ACT_INSERT:
        undoInsert(ptr);    //  挿入の Undo 処理
        break;
    case UndoAction::ACT_DELETE:
        undoDelete(ptr);    //  削除の Undo 処理
        break;
    }
}

スタックに UndoItem が存在する場合は、そのアイテムの処理を undo する。
実際の処理、挿入・削除などの処理ごとに分かれる。

挿入処理の undo 処理を以下に示す

int UndoMgr::undoInsert(UndoActionInsert *p)
{
    auto pos = p->m_pos;    //  挿入位置
    const int ix = p->m_ix = m_insText.size();      //  挿入されたテキストを保存する位置
    m_insText.resize(ix + p->m_size);               //  保存テキスト分だけ保存領域を確保
    m_buffer->getText(p->m_pos, &m_insText[ix], p->m_size);     //  挿入されたテキストを保存
    m_buffer->basicDeleteText(p->m_pos, p->m_size);     //  挿入されたテキストを削除
}

挿入処理の Undo では、UndoActionInsert オブジェクトが保持する、挿入位置・文字数情報を元に、挿入されたテキストを削除する。
ただし、挿入→Undo→Redo が行われた場合は、Undo で削除されたテキストを復活する必要があるので、挿入テキストを保存しておく m_insText に保存する。

挿入処理の Redo のコードを以下にしめす。

int RedoMgr::undoInsert(UndoActionInsert *p)
{
    //  挿入されていたテキストをバッファに挿入
    m_buffer->basicInsertText(p->m_pos, &m_insText[p->m_ix], p->m_size);
    m_insText.resize(p->m_ix);      //  m_insText から挿入テキストを削除
}

挿入されていたテキストは m_insText の p->m_ix から p->m_size 文字に存在するので、
そのテキストをバッファに挿入する。
挿入されていたテキスト情報はバッファに移動し m_insText にはもう必要ないので、削除する。

以上が、Undo/Redo 処理の説明だ。
要は、Undo/Redo に必要な情報をオブジェクトとしてスタック上に保存しておき、その情報を利用して処理を行うという仕組みだ。

おわりに

テキストエディタのバッファデータ構造について数種類を解説した。
個人的には、１Gバイト以下の非巨大ファイルを取り扱う場合においては gap_buffer が最強だと考えている。
１Gバイト超の巨大ファイルにも対応する場合、テキストバッファデータ構造は、なんらかの階層的データ構造にせざると得ないのだが、具体的に何が最適なのかは筆者にはよくわかっていない。今後の課題である。