11
メモ帳などのエディタの実装に使用されるデータ構造。このデータ構造は拡張可能であり、編集、削除、スクロール、テキスト範囲の選択などのさまざまな機能をサポートする必要がありますか？メモ帳のようなエディタを実装するのに最適なデータ構造は何ですか？
A
答えて
1
メモ帳++の実装をチェックし、あなたがをチェックSourceForge
5
上のソースを表示することができます。文字列の挿入/削除/編集を高速に処理します。通常、Ropeの実装では範囲がサポートされており、スクロールは逆のインデックスで行えます。
-1
普通のことは、文字の配列のリストまたは配列のようなものを持つことです。これには長年にわたって多くのことが行われています。this google searchをご覧ください。
8
私たちは古いマシンのエディタを書いています（これはもうちょっと前のことです、1986年頃ですので、これは記憶からのものであり、当時の状態はやや進歩しているかもしれません）自己管理型プールからの固定メモリブロックを使用することで、パフォーマンスを向上させることができます。
各プールには、固定サイズの特定サイズのブロック（1つはプール構造、もう1つはラインセグメント構造）が含まれています。それは基本的にリンクリストのリンクリストでした。
メモリは、 'malloc()'のような呼び出しから事前に割り当てられ、65,535ブロック（0〜65,534を含む。ブロック番号65,535はヌルブロックとみなされ、リストの終わりのインジケータ）。
これは、それぞれ65,535行（パッド付きバージョンでは384Kまたは512K）と約1.6Gのファイルサイズ（2Gの割り当てスペースを取る）で許容されていました。それは理論的にはのファイルサイズの制限でした。私たちは実際にはそれほど近づいていないと思います。
メモリブロックごとにmalloc()を呼び出す必要はありません。特に、固定サイズブロック用に独自のメモリ割り当てルーチンを最適化することができます（最適化された最終バージョンの呼び出しをインライン化するなど）。
次の2つのプール内の構造は、各ラインは単一バイトであることであった）：
Line structure (6/8 bytes) Line-segment structure (32 bytes)
+--------+ +--------+
|NNNNNNNN| |nnnnnnnn|
|NNNNNNNN| |nnnnnnnn|
|PPPPPPPP| |pppppppp|
|PPPPPPPP| |pppppppp|
|bbbbbbbb| |LLLLLLLL|
|bbbbbbbb| |LLLLLLLL|
|........| |xxxxxxxx|
|........| :25 more :
+--------+ : x lines:
+--------+
：線分プールにx点以外
- 小文字のアルファベット。
- 大文字は、行プールを指します。
Nは、次の行のブロック番号（nullはファイルの最後の行であることを意味します）です。P前の行のブロック番号（nullはファイル内の最初の行であることを意味します）。bは、その行の最初の行セグメントのブロック番号です（nullは行が空であることを意味します）。.は、（8バイトに構造をバンプするために）予約されたパディングです。nは、次の行セグメントのブロック番号（nullが行の最後のセグメントであることを意味します）です。pは、前の線分（これは線の最初の線分を意味するnull）のブロック番号です。Lは、セグメントのラインブロックのブロック番号でした。xは、その行セグメントの26文字でした。
ブロック構造体をパディングする理由は、ブロック番号の実際のメモリ位置への変換を高速化することでした（3ビット左シフトは、その特定アーキテクチャで6を掛けるよりもずっと速く、 、使用されている総記憶容量と比較して最小）、私たちはメモリをもっと気にしていた人のためにより遅いバージョンを提供しました。
また、約16％の値の配列を持っていました。その値はおよそそのパーセンテージになりました（配列[7]は大雑把にファイルに7％）と各プールの空きリストを維持するための2つのフリー・ポインタ（これは非常に単純な一方向リストで、構造内のNまたはnは次の空きブロックが示され、空きブロックが割り当てられ、 、これらのリストの先頭）。
ファイル内で0バイトが有効でないため、各行セグメントの文字の数を維持する必要はありませんでした。各線分は、無視された最後の0バイトを持つことができました。線が修正されたときには、線が圧縮された（すなわち、線分が結合された）。これはブロックの使用率を低く抑え（まれでガーベージ・コレクションが少ない）、検索と置換の操作を大幅に高速化しました。
これらの構造を使用すると、テキストの編集、挿入、削除、検索、ナビゲーションが簡単に行えます。これは、単純なテキストエディタでパフォーマンスの問題が発生する可能性が高い場所です。
選択の使用{line#/block, char-pos}タプルを持つことで実現することができた（それは6つの文字を削除するには、3線や6xを削除するには、viのようなコマンドなど3dとして使用されるテキストモードエディタだったので、我々はこれを実装していませんでした）テキスト内の位置をマークし、それらのタプルのうちの2つを選択範囲に使用します。
3
多くの編集者はGap Bufferを使用しています。これは、基本的に、途中に未使用スペースがある配列です。カーソルはギャップの直前に位置しているので、カーソルの削除と挿入はO（1）です。実装するのはかなり簡単です。
メモ帳++のソースコード（Chris Ballanceがこのスレッドで提案したようにhere）はギャップバッファも使用していることを示しています。あなたはそれからいくつかの実装のアイデアを得ることができます。
3
HexEditの著者James Brownによると、Piece Chainsに関する素晴らしい記事があります。
簡単に言えば、ピースチェーンを使用すると、テキストに加えられた変更を記録できます。ロード後、テキスト全体にまたがるピースチェーンがあります。今はどこかに挿入します。
新しいバッファを割り当てたり、テキストをコピーしたりする代わりに、2つの新しい部分を作成して既存の部分を修正します。既存の部分には挿入ポイントまでのテキストが含まれます。あなたはちょうどその部分の長さを変えています）、新しいテキストの部分があり、その後に挿入後のすべてのテキストを含む新しい部分があります。元のテキストは変更されません。
元に戻す/やり直しを行うには、追加/削除/変更した部分を簡単に思い出してください。
ピースチェーンを使用するときに最も複雑な領域は、可視テキスト内のオフセットとメモリ構造の間に1対1のマッピングが存在しないことです。チェーンを検索するか、何らかの種類のバイナリツリー構造を維持する必要があります。
Emacsもこれをウィキペディア –