利用者:Atirow/ギャップバッファ

en:Gap buffer (15:16, 5 August 2009 UTC)

In computer science, a gap buffer is a dynamic array that allows efficient insertion and deletion operations clustered near the same location. Gap buffers are especially common in text editors, where most changes to the text occur at or near the current location of the cursor. The text is stored in a large buffer in two contiguous segments, with a gap between them for inserting new text. Moving the cursor involves copying text from one side of the gap to the other (sometimes copying is delayed until the next operation that changes the text). Insertion adds new text at the end of the first segment. Deletion increases the size of the gap.

計算機科学では、ギャップバッファ(英: gap buffer)は、同じ場所付近に集中する挿入操作と削除操作が効率的良く行なえる動的配列である。ギャップバッファはテキストエディタで特に一般的である。テキストエディタでは、テキストへの大部分の変更がカーソルの現在位置付近で起こる。__テキストは2つの連続したセグメント内の大きなバッファに保存される。新しいテキストを挿入するそれらの間のギャップ__カーソルを移動することはテキストをギャップの片側から反対側へテキストをコピーすることを含んでいる(時々コピーはテキストを変更する次の動作まで遅延される)。挿入は新しいテキストを最初のセグメントの末尾に追加する。削除はギャップのサイズを増やす。

The advantage of using a gap buffer over more sophisticated data structures (such as linked lists) is that the text is represented simply as two literal strings, which take very little extra space and which can be searched and displayed very quickly.

(連結リストのような)より洗練されたデータ構造よりもギャップバッファを使うことの利点は、テキストが2つのliteral stringとして単純に表現されるからである。これは余分な空間を非常に少ししかとらず、非常に高速に検索や表示ができる。

The disadvantage is that operations at different locations in the text and ones that fill the gap (requiring a new gap to be created) require re-copying most of the text, which is especially inefficient for large files. The use of gap buffers is based on the assumption that such recopying occurs rarely enough that its cost can be amortized over the more common cheap operations.

A gap buffer is used in most Emacs editors.

ギャップバッファは大部分のEmacs系エディタで使われている。

例

Below are some examples of operations with buffer gaps. The gap is represented pictorially by the empty space between the square brackets. This representation is a bit misleading: in a typical implementation, the endpoints of the gap are tracked using pointers or array indices, and the contents of the gap are ignored; this allows, for example, deletions to be done by adjusting a pointer without changing the text in the buffer. It is a common programming practice to use a semi-open interval for the gap pointers, i.e. the start-of-gap points to the invalid character following the last character in the first buffer, and the end-of-gap points to the first valid character in the second buffer (or equivalently, the pointers are considered to point "between" characters).

Initial state:

初期状態。

This is the way [                    ]out.

User inserts some new text:

ユーザはいくつかの新しいテキストを挿入する。

This is the way the world started [   ]out.

User moves the cursor before "started"; system moves "started " from the first buffer to the second buffer.

ユーザはカーソルを「started」の前に移動する。システムは「started」を1番目のバッファから2番目のバッファへ移動する。

This is the way the world [   ]started out.

User adds text filling the gap; system creates new gap:

ユーザがテキストを追加してギャップを埋める。システムは新しいギャップを作成する。

This is the way the world as we know it [                   ]started out.

See also

• Dynamic array, the special case of a gap buffer where the gap is always at the end
• Linked list
• Circular buffer
• Rope (computer science)

関連項目

• 動的配列はギャップが常に終端にあるようなギャップバッファの特殊な場合
• 連結リスト
• リングバッファ
• ロープ (計算機科学)

外部参考文献

• Overview and implementation in .NET/C#
• Brief overview and sample C++ code
• Implementation of a cyclic sorted gap buffer in .NET/C#
• Use of gap buffer in early editor. (First written somewhere between 1969 and 1971)