Gap buffer

Gap buffer

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.

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.

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.

Example

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.

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.

This is the way the world [ ] started out.

User adds text filling the gap; system creates new g

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

ee also

* Dynamic array, the special case of a gap buffer where the gap is always at the end
* Linked list
* Circular buffer

External references

* [http://www.codeproject.com/csharp/GenericGapBuffer.asp Overview and implementation in .NET/C#]
* [http://www.lazyhacker.com/gapbuffer/gapbuffer.htm Brief overview and sample C++ code]
* [http://www.codeproject.com/useritems/SplitArrayDictionary.asp Implementation of a cyclic sorted gap buffer in .NET/C#]
* [http://history.dcs.ed.ac.uk/archive/apps/ecce/hmd/e915.imp.html Use of gap buffer in early editor.] (First written somewhere between 1969 and 1971)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Buffer underrun — In computing, buffer underrun or buffer underflow is a state occurring when a buffer used to communicate between two devices or processes is fed with data at a lower speed than the data is being read from it. This requires the program or device… …   Wikipedia

  • Anion gap — The anion gap is used to aid in the differential diagnosis of metabolic acidosis.CalculationIt is calculated by subtracting the serum concentrations of chloride and bicarbonate (anions) from the concentrations of sodium plus potassium (cations) …   Wikipedia

  • Dynamic array — Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast (constant time), while some are slow due to the need for reallocation (Θ(n) time,… …   Wikipedia

  • Model–view–adapter — (MVA) or mediating controller MVC is an architectural pattern and multitier architecture, used in software engineering. In complex computer applications that present large amounts of data to users, developers often wish to separate data (model)… …   Wikipedia

  • Metabolic acidosis — Classification and external resources Davenport diagram ICD 10 E …   Wikipedia

  • Life Sciences — ▪ 2009 Introduction Zoology       In 2008 several zoological studies provided new insights into how species life history traits (such as the timing of reproduction or the length of life of adult individuals) are derived in part as responses to… …   Universalium

  • India — /in dee euh/, n. 1. Hindi, Bharat. a republic in S Asia: a union comprising 25 states and 7 union territories; formerly a British colony; gained independence Aug. 15, 1947; became a republic within the Commonwealth of Nations Jan. 26, 1950.… …   Universalium

  • HISTORICAL SURVEY: THE STATE AND ITS ANTECEDENTS (1880–2006) — Introduction It took the new Jewish nation about 70 years to emerge as the State of Israel. The immediate stimulus that initiated the modern return to Zion was the disappointment, in the last quarter of the 19th century, of the expectation that… …   Encyclopedia of Judaism

  • Optical disc recording technologies — Optical discs Optical disc Optical disc drive Optical disc authoring Authoring software Recording technologies Recording modes Packet writing Optical media types …   Wikipedia

  • Agriculture and Food Supplies — ▪ 2007 Introduction Bird flu reached Europe and Africa, and concerns over BSE continued to disrupt trade in beef. An international vault for seeds was under construction on an Arctic island. Stocks of important food fish species were reported… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”