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

gap_buffer<char> + 行管理

gap_buffer<char> は1次元的で、文字位置を0オリジンの数値で指定するが、テキストエディタではテキストを行単位で表示するので、行番号と行先頭位置の高速な相互変換を可能にする必要がある。
特に、スクロールバーをぐりぐりドラッグされた場合を考えると、各行先頭位置を高速に取り出せるようにする必要がある。
そのための最も自然な解決方法は、各行の先頭位置をテーブルで管理する方法だ（下図参照）。

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

この方法であれば、行番号→行先頭位置変換はテーブルを参照するだけなので、O(1) と高速になる。
また、文字位置→行番号変換もテーブルをバイナリサーチすれば可能なので、O(logN) で計算可能だ。
しかし、この方法には欠点がある。それは、行の長さが変化した場合、当該行～末尾までの位置を更新する必要があり、その処理時間は O(N) となるという点だ。
一括置換などではこの処理を複数回繰り返すので、トータル処理時間が O(N^2) となり、パフォーマンス的に好ましくないのだ。

編集時の更新処理を最小化する解決方法として、各行先頭位置ではなく、各行の長さを保持しておくというものがある（下図参照）。

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

このようにすれば編集時の更新処理は O(1) で済む。
しかし、行の先頭位置を取り出すには、1～L-1 までの行長の総和を求める必要があり O(N) の処理時間を要してしまう。
つまり、行先頭位置・行長テーブル方式は相補的で、どっちもどっちというデータ構造だ。

本連載に何度も出てきた話であるが、テキストエディタにおいては、ほとんどの場合において参照・編集箇所は局所化されているという性質がある。
この性質をうまく利用することで、前者のデータ構造における各行頭位置配列の更新を O(1) に高速化できる。
以下、その具体的アルゴリズムについて解説する。

行先頭位置管理を行うクラスを LineMgr という名前とする。下図にそのクラス図を示す。

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

list<string>+キャッシュの時と同じように、最後に編集された行を m_stepIndex で覚えておき、line == m_stepIndex 行以降（m_stepIndex行も含む）に m_stepSize の差分があるものとする。
つまり、編集箇所が以前の編集箇所と同じ行であれば、m_stepSize を変更するだけで、行先頭位置テーブルの値はいっさい変更しない。
編集を行った行に m_stepIndex があるものとする。なので、m_stepIndex が編集行でない場合は、m_stepIndex を移動し、その間の行先頭位置のみを更新する。
したがって、編集箇所が局所的であれば、その更新処理は少ない行についてのみなので、処理時間は O(1) となる。
このようなアルゴリズムは「遅延評価」と呼ばれる。
行先頭位置情報の更新処理が必要になるまで処理を遅延することで、無駄な処理をはぶき高速化するという手法だ。

以下に、ステップがある場合の、行番号 → 行先頭位置取得処理のコードを示す。

    int lineStartPosition(int line) {
        return m_startPos(line) + (line > m_stepIndex ? m_stepSize : 0);
    }

処理は単純で、行先頭位置をテーブルでひいて、引数で指定された行番号が m_stepIndex より大きければ m_stepSize を加えるだけだ。

次に line 行を編集（挿入・削除）した場合の処理を以下に示す。

    void textInserted(int line, int delta)  //  line 行にdelta文字のテキストが挿入された時の処理
    {
        if( !m_stepSize ) {     //  ステップが0の場合
            m_stepIndex = line;     //  ステップ位置を設定
            m_stepSize = delta;     //  ステップを設定
        } else {                //  ステップが0でない場合
            if( line != m_stepIndex ) {     //  ステップ位置と異なる場合
                setStepIndex(line);         //  ステップ位置を line に移動
            }
            m_stepSize += delta;    //  ステップサイズ更新
        }
    }

ステップが0の場合は、なにも処理する必要がなく、m_stepIndex・m_stepSize を引数で渡された値に設定するだけ。
そうでなければ、setStepIndex(line) をコールし、m_stepIndex を line に設定し、m_stepSize を更新する。

以下に setStepIndex(int line) の実装を示す

    void setStepIndex(int line)     //  m_stepIndex を line に設定し、先頭位置テーブルを更新
    {
        if( line == m_stepIndex ) return;       //  変化なしの場合
        if( !m_stepSize ) return;               //  ステップが0の場合は何もする必要がない
        if( line > m_stepIndex ) {              //  ステップ位置より後方に移動する場合
            while( line > m_stepIndex ) {
                m_startPos[++m_stepIndex] += m_stepSize;    //  その間の行先頭位置を更新
            }
        } else {                                //  ステップ位置より前方に移動する場合
            while( line < m_stepIndex ) {
                m_startPos[m_stepIndex--] -= m_stepSize;    //  その間の行先頭位置を更新
            }
        }
    }

m_stepIndex を移動する場合は、その行と新しい行までの間の行先頭位置を更新する。

この方法であれば、編集処理毎に行先頭位置情報を最終行まで更新する必要が無く、m_stepIndex を移動する処理は編集箇所が局所的であれば O(1) なので、全体の処理時間は O(N) → O(1) と高速化される。