A gap buffer stores text as two contiguous regions separated by a "gap" at the cursor. Insertions cost O(1); cursor movement costs O(distance).
pub struct GapBuffer {
data: Vec<u8>,
gap_start: usize,
gap_end: usize,
}
impl GapBuffer {
pub fn new(capacity: usize) -> Self {
Self {
data: vec![0u8; capacity],
gap_start: 0,
gap_end: capacity,
}
}
pub fn from_str(s: &str) -> Self {
let gap = 64;
let mut data = vec![0u8; s.len() + gap];
data[gap..].copy_from_slice(s.as_bytes());
Self { data, gap_start: 0, gap_end: gap }
}
#[inline]
pub fn gap_len(&self) -> usize {
self.gap_end - self.gap_start
}
pub fn len(&self) -> usize {
self.data.len() - self.gap_len()
}
pub fn insert(&mut self, ch: char) {
let mut buf = [0u8; 4];
let encoded = ch.encode_utf8(&mut buf);
for &byte in encoded.as_bytes() {
if self.gap_start == self.gap_end {
self.grow();
}
self.data[self.gap_start] = byte;
self.gap_start += 1;
}
}
pub fn delete_back(&mut self) {
if self.gap_start > 0 {
self.gap_start -= 1;
}
}
pub fn move_right(&mut self, n: usize) {
for _ in 0..n {
if self.gap_end < self.data.len() {
self.data[self.gap_start] = self.data[self.gap_end];
self.gap_start += 1;
self.gap_end += 1;
}
}
}
pub fn move_left(&mut self, n: usize) {
for _ in 0..n {
if self.gap_start > 0 {
self.gap_start -= 1;
self.gap_end -= 1;
self.data[self.gap_end] = self.data[self.gap_start];
}
}
}
pub fn as_string(&self) -> String {
let mut s = Vec::with_capacity(self.len());
s.extend_from_slice(&self.data[..self.gap_start]);
s.extend_from_slice(&self.data[self.gap_end..]);
String::from_utf8(s).unwrap_or_default()
}
fn grow(&mut self) {
let new_gap = self.data.len().max(8);
let mut new_data = vec![0u8; self.data.len() + new_gap];
new_data[..self.gap_start].copy_from_slice(&self.data[..self.gap_start]);
let tail = self.data.len() - self.gap_end;
let new_end = new_data.len() - tail;
new_data[new_end..].copy_from_slice(&self.data[self.gap_end..]);
self.gap_end = new_end;
self.data = new_data;
}
}