Gap buffer là gì?

Gap buffer là một cấu trúc dữ liệu (data structure) được triển khai phổ biến trong các trình soạn thảo văn bản (editor) có thể di chuyển con trỏ (cursor) một cách hiệu quả, cũng như thêm và xóa các ký tự.

Ý tưởng rất đơn giản: nội dung của trình soạn thảo được biểu diễn dưới dạng một mảng ký tự a có độ dài n, có một khoảng trống (gap) của các mục (entry) không sử dụng a [l], ..., a [r −1], đối với hai chỉ số (index) l ≤ r. Dữ liệu mà nó biểu diễn bao gồm a [0], ..., a [l −1], a [r], ..., a [n − 1].

Vị trí con trỏ hiện tại nằm ở bên trái chỉ số l, và nếu chúng ta nhập một ký tự, ký tự đó sẽ được ghi vào a[l] và l được tăng lên. Khi khoảng trống trở nên trống (empty), mảng được mở rộng và dữ liệu từ r được dịch chuyển sang phải.