Gap buffert

En gap-buffert inom datavetenskap är en dynamisk array som möjliggör effektiva insättnings- och raderingsoperationer klustrade nära samma plats. Mellanrumsbuffertar är särskilt vanliga i textredigerare , där de flesta ändringar av texten sker vid eller nära markörens aktuella plats . Texten lagras i en stor buffert i två sammanhängande segment, med ett mellanrum mellan dem för att infoga ny text. Att flytta markören innebär att text kopieras från den ena sidan av gapet till den andra (ibland fördröjs kopieringen till nästa operation som ändrar texten). Infogning lägger till ny text i slutet av det första segmentet; radering tar bort det.

Text i en gapbuffert representeras som två strängar , som tar väldigt lite extra utrymme och som kan sökas och visas mycket snabbt, jämfört med mer sofistikerade datastrukturer som länkade listor . Men operationer på olika platser i texten och sådana som fyller luckan (kräver att en ny lucka skapas) kan kräva att det mesta av texten kopieras, vilket är särskilt ineffektivt för stora filer. Användningen av gapbuffertar bygger på antagandet att sådan omkopiering sker sällan så mycket att kostnaden kan amorteras över de vanligare billiga operationerna. Detta gör gapbufferten till ett enklare alternativ till repet för användning i textredigerare som Emacs .

Exempel

Nedan följer några exempel på verksamheter med buffertluckor. Gapet representeras av det tomma utrymmet mellan hakparenteserna. Denna representation är lite missvisande: i en typisk implementering spåras slutpunkterna för gapet med hjälp av pekare eller arrayindex, och innehållet i gapet ignoreras; detta gör att till exempel raderingar kan göras genom att justera en pekare utan att ändra texten i bufferten. Det är en vanlig programmeringspraxis att använda ett halvöppet intervall för gap-pekarna, dvs. start-of-gap pekar på det ogiltiga tecknet efter det sista tecknet i den första bufferten, och slutet av gapet pekar på det första giltigt tecken i den andra bufferten (eller motsvarande, pekarna anses peka "mellan" tecken).

Initialtillstånd:

Det här är vägen [ ]ut.

Användaren infogar lite ny text:

Det var så här världen började [ ].

Användaren flyttar markören innan "startade"; systemet flyttar "startat" från den första bufferten till den andra bufferten.

Det var så världen [ ] började.

Användaren lägger till text som fyller tomrummet; systemet skapar ny lucka:

Så här började världen som vi känner den [ ].

Se även

• Dynamic array , specialfallet med en gapbuffert där gapet alltid är i slutet
• Zipper (datastruktur) , konceptuellt en generalisering av gapbufferten.
• Länkad lista
• Cirkulär buffert
• Rep (datavetenskap)
• Bittabell - datastruktur som används av Bravo och Microsoft Word

externa länkar

• Implementering i C
• Översikt och implementering i .NET/C#
• Kort översikt och exempel på C++-kod
• Implementering av en cyklisk sorterad gapbuffert i .NET/C#
• Användning av gap buffert i tidig editor. (Skrivs först någonstans mellan 1969 och 1971)
• emacs gap buffer info (Emacs gap buffer referens)
• Flexichain: En redigerbar sekvens och dess gap-buffertimplementering