Bufor luki - Gap buffer

Bufor luka w informatyce jest dynamiczna tablica , która umożliwia wydajne operacje wstawiania i usuwania skupione w pobliżu tej samej lokalizacji. Bufory odstępów są szczególnie powszechne w edytorach tekstu , w których większość zmian w tekście ma miejsce w bieżącym położeniu kursora lub w jego pobliżu . Tekst jest przechowywany w dużym buforze w dwóch sąsiadujących segmentach, z przerwą między nimi na wstawienie nowego tekstu. Przesuwanie kursora wiąże się z kopiowaniem tekstu z jednej strony luki na drugą (czasami kopiowanie jest opóźnione do następnej operacji zmieniającej tekst). Wstawienie dodaje nowy tekst na końcu pierwszego segmentu; usunięcie usuwa go.

Tekst w buforze luk jest reprezentowany jako dwa ciągi , które zajmują bardzo mało dodatkowego miejsca i które można przeszukiwać i wyświetlać bardzo szybko, w porównaniu z bardziej wyrafinowanymi strukturami danych, takimi jak listy połączone . Jednak operacje w różnych miejscach w tekście i te, które wypełniają lukę (wymagające utworzenia nowej przerwy) mogą wymagać skopiowania większości tekstu, co jest szczególnie nieefektywne w przypadku dużych plików. Stosowanie buforów luk opiera się na założeniu, że takie ponowne kopiowanie występuje na tyle rzadko, że jego koszt można zamortyzować w stosunku do bardziej powszechnych tanich operacji. To sprawia, że ​​bufor luki jest prostszą alternatywą dla liny do użytku w edytorach tekstu, takich jak Emacs .

Przykład

Poniżej znajduje się kilka przykładów operacji z lukami w buforze. Luka jest reprezentowana przez pustą przestrzeń między nawiasami kwadratowymi. Ta reprezentacja jest nieco myląca: w typowej implementacji punkty końcowe luki są śledzone za pomocą wskaźników lub indeksów tablicowych, a zawartość luki jest ignorowana; pozwala to, na przykład, na usuwanie poprzez dostosowywanie wskaźnika bez zmiany tekstu w buforze. Powszechną praktyką programowania jest stosowanie półotwartego przedziału dla wskaźników przerwy, tj. Początek przerwy wskazuje na nieprawidłowy znak następujący po ostatnim znaku w pierwszym buforze, a koniec przerwy wskazuje na pierwszy ważny znak w drugim buforze (lub równoważnie, wskaźniki są uważane za wskazujące "pomiędzy" znakami).

Stan początkowy: 

This is the way [                     ]out.

Użytkownik wstawia nowy tekst: 

This is the way the world started [   ]out.

Użytkownik przesuwa kursor przed „rozpoczęte”; system przenosi „uruchomiony” z pierwszego bufora do drugiego bufora. 

This is the way the world [   ]started out.

Użytkownik dodaje tekst wypełniając lukę; system tworzy nową lukę: 

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

Zobacz też

Bibliografia

Zewnętrzne linki