行管理 - ViVi version 5.0 Free Wiki - ViVi version 5.0 Free

■ 背景

• 画面表示も、垂直スクロールも行単位で処理を行う。
• したがって行情報を管理し、行番号とバッファオフセットを高速に相互変換できる様にする必要がある。
• もっとも単純なデータ構造は、各行先頭文字オフセットを配列で保持するものである。
  

    ┏━┓←┐┌───┐
    ┃  ┃  └┼─●  │
    ┃  ┃    ├───┤
    ┠─┨←─┼─●  │
    ┠─┨←┐├───┤
    ┃  ┃  └┼─●  │
    ┃  ┃    ├───┤
    ┠─┨←─┼─●  │
    ┃  ┃    ├───┤
    ┠─┨←─┼─●  │
    ┃：┃    └───┘
    ┃：┃        ：
    ┠─┨        ：
    ┗━┛
  

  • 行番号→オフセット変換は O(1)、オフセット→行番号変換は O(logN) だが、
  • 編集時の行情報更新に O(N) の処理時間を要する。（※ 処理時間として許容できるのは O(logN) までである）
• 行情報として各行の文字数を保持する方法もある。
  

    ┏━┓    ┌───┐
    ┃  ┃    │ 行長 │
    ┃  ┃    ├───┤
    ┠─┨    │ 行長 │
    ┠─┨    ├───┤
    ┃  ┃    │ 行長 │
    ┃  ┃    ├───┤
    ┠─┨    │ 行長 │
    ┃  ┃    ├───┤
    ┠─┨    │ 行長 │
    ┃：┃    └───┘
    ┃：┃        ：
    ┠─┨        ：
    ┗━┛
  

  • 編集時の行情報更新処理は O(1) になるが、
  • 行番号→オフセット変換、オフセット→行番号変換はともに O(N) となる。
• 行情報を平衡２分木類で保持すれば、全ての処理時間は O(logN) となる。
  • しかし、配列に比べるとプログラムは複雑になり、全体的に重くなる。

■ ViVi 5.0 行管理

• ViVi 5.0 では以下の理由で、行長情報配列＋キャッシュ を採用することにした。

    ┏━┓                  ┌───┐
    ┃  ┃                  │ 行長 │
    ┃  ┃                  ├───┤
    ┠─┨                  │ 行長 │
    ┠─┨                  ├───┤
    ┃  ┃←─カレント行─→│ 行長 │
    ┃  ┃                  ├───┤
    ┠─┨                  │ 行長 │
    ┃  ┃                  ├───┤
    ┠─┨                  │ 行長 │
    ┃：┃                  └───┘
    ┃：┃                      ：
    ┠─┨                      ：
    ┗━┛
  
  

  • 平衡２分木類は処理オーダは logN と高速だが、処理自体は重く、配列を用いる場合に比べプログラムは複雑である。
  • オフセットを配列で保持する場合、編集時の処理時間が O(N) になる。
    これは広範囲に渡るデータの更新が必須であり、メモリスワップが発生する確率を高めるので好ましくない。
  • テキストエディタ操作においては参照される場所は局所化されており、
    キャッシュを使えば オフセット←→行番号 変換処理時間を O(1) にすることができる。
  • 「行長情報配列」と記述したが、正確には gap_vector を用いる。行の挿入・削除処理時間は場所が局所化されていれば O(1) となる。
• キャッシュ法は大変優れた方法なのだが、キャッシュの更新に誤りがあっても、それが直ぐにプログラム誤動作につながらず、
  バグを発見しづらいという問題がある。
  • 細心の注意を払ったコーディングと、入念な単体・総合テストが必要である。

■ 関連項目

• バッファ
• テキストカーソル

---

:

• mac でも　chrome で見れば経線ずれてないお
  -- vivisuke (2011-04-17)
• mac のサファリで見ると経線図形がずれてるお
  -- vivisuke (2011-04-17)