テキストエディタ実装技術

[ index | 前のドキュメント | 次のドキュメント | このドキュメントのソース ]

■ 行単位双方向リンク

　テキストエディタ（以下、エディタと略す）は文字の1次元的な並びを管理しなくてはいけない。エディタには様々な機能が要求されるが、エディタであるためには、文字列情報の保持、表示、修正が出来なくてはいけない。そのための機構を バッファ と呼ぶことがある。

　バッファの設計・実装にはいくつかの方法がある。最も単純なものはバッファ全体をひとつの文字列とする方法だ。MFC であれば CString を使うと良い。これでも部分文字列の参照や修正が出来るが、バッファのサイズが大きくなると、修正のたびに大量のデータを移動する必要があるので、明らかに効率が悪い。

　効率的な実装方法として、筆者が最初に学んだのは Brian Kernighan and P.J. Plauger, "Software Tools", 1976, にある行単位双方向リンクによる実装だ。行単位双方向リンクとは次の行と前の行に対するポインタにより、行の集合を管理する機構のことだ（図1参照）。


図1 双方向リンクによる行管理

    ┌──┐  ┌──────┐
    │    ↓  │            │
    │  ┌─┬┼┬──┐    │
    │  │●│●│text│    │      ダミー行
    │  └┼┴─┴──┘    │
    │    ↓  ↑            │
    │  ┌─┬┼┬──┐    │
    │  │●│●│text│    │      1行目
    │  └┼┴─┴──┘    │
    │    ↓  ↑            │
    │  ┌─┬┼┬──┐    │
    │  │●│●│text│    │      2行目
    │  └┼┴─┴──┘    │
    │    │  ↑            │
    ：    ：  ：            ：
    │    ↓  │            │
    │  ┌─┬┼┬──┐    │
    │  │●│●│text│    │      N行目
    │  └┼┴─┴──┘    │
    │    │  ↑            │
    └──┘  └──────┘

　行単位の双方向リンクは管理できる行数に制限がなく、行単位の挿入、削除が容易であるという長所を持つ。たとえば、1行のためのデータ構造を SNode とし、


    struct SNode {
        SNode   *m_next;        //  次の行へのポインタ
        SNode   *m_prev;        //  前の行へのポインタ
        CString m_text;         //  行に含まれる文字列
    public:
        SNode() {};
        SNode(const CString&text) : m_text(text) {};

        void link(SNode *next)       //  next を次のノードに設定する
        {
            m_next = next;
            next->m_prev = this;
        };
    };

と定義すれば、SNode *node1 の直後に SNode *node2 を挿入するのは、


    node2->link(node1->m_next);
    node1->link(node2);

とするとよい。SNode *node をリンクから外すのはもっと簡単で、


    node->m_prev->link(node->m_next);

とするだけだ。

　図1には1行目の前にダミー行というのが存在する。これは行が1行も存在しない場合でも、先の挿入、削除アルゴリズムを使用可能にするためのものだ。ダミー行からすべての行に行き着くことが出来るので、すべての行を管理するためにはダミー行へのポインタを保持していればよい。また、最初の行と最後の行はダミー行をはさんで循環している。このようなデータ構造は循環リストと呼ばれる。

　行単位双方向リンクは目的の行を取得するのに、リンクをだどる必要があり、これに時間を要するという短所がある。行数が N であれば平均して N/2 回リンクをたどる（次の行へのリンクだけをたどる場合）必要があるが、これについては後でもう少し詳しく述べる。

　バッファは上記の双方向にリンクされた行の集合を管理するクラスとして定義できる。クラス名を CLineMgr とすると、


    class CLineMgr {
        SNode   *m_ptr;         //  ダミー行へのポインタ
        uint    m_lineCount;    //  バッファに含まれる行数（ダミー行は含まない）
    public:
        CLineMgr();         //  コンストラクタ
        ~CLineMgr();        //  デストラクタ

        .....               //  参照、修正メソッド
    };

    CLineMgr::CLineMgr()
    {
        m_ptr = new SNode;      //  ダミー行を作成
        m_ptr->link(m_ptr);     //  双方向にリンクを張る
        m_lineCount = 0;        //  行数は０
    }

    CLineMgr::~CLineMgr()
    {
        //  バッファ内の全ての行をデリート
        SNode *p = m_ptr;
        do {
            SNode *q = p->m_next;
            delete p;
            p = q;
        } while( p != m_ptr );
    }

のようにするとよい。

　メンバ変数としては、双方向リンクのダミー行へのポインタと行数を持つ。行数は必須ではないが、行の参照などで利用できるので、持っていた方が効率が良い。メソッドとしてはコンストラクタとデストラクタは必須である。コンストラクタはダミー行を作成し、SNode の link メソッドを使って双方向リンクを張る。デストラクタは双方向リンクに含まれる行を全てデリートする。この他に行を参照、修正するメソッドを定義する必要があるが、それについては後で述べる。

　CLineMgr の実装では双方向リンクのひとつのノードが1行に対応しているので、行単位の挿入、削除は非常に効率が良い。行内の一部を変更する場合は文字列クラスの機能を使用するが、1行の長さが極端に長いことは極めて稀なので、その処理時間はあまり大きくはならない。極端に長い場合でも高速な処理を行うために、双方向リンクのノードを1文字単位にすることも出来る。しかし、これではポインタのために余分なメモリを大量に消費するし、文字の表示も1文字ずつ取り出さねばならないので、トータルのオーバーヘッドが大きくなる。

　バッファ全体をひとつの文字列にする方法と、1文字をひとつのノードにするという方法は、それぞれ両極端なデータ構造である。それに対し、行単位のノードというのは中庸でほどよいバランスであると考える。

[ index | 前のドキュメント | 次のドキュメント | このドキュメントのソース ]