spyne_text/buffer/gap_buffer.rs
1use crate::buffer::TextBuffer;
2
3/// A gap buffer structure.
4///
5/// Useful for small and frequent insertions and deletions.
6/// O(1) insertions and deletions on average.
7/// O(n) gap repositioning on edit location change.
8///
9/// Example use case: Shell
10pub struct GapBuffer {
11 buffer: Vec<char>,
12 gap_start: usize,
13 gap_end: usize
14}
15
16impl TextBuffer for GapBuffer {
17 /// Creates a gap buffer according to gap size.
18 ///
19 /// Start is at first insertable location.
20 /// End is at first character after last insertable location.
21 ///
22 /// Buffer is initialized to designated gap size.
23 fn create_buffer(init_size: usize) -> Self where Self: Sized {
24 Self { buffer: vec![char::default(); init_size], gap_start: 0, gap_end: init_size }
25 }
26
27 /// Inserts into a gap buffer.
28 ///
29 /// 1. Moves gap
30 /// 2. Checks if gap is empty (if so, resize by doubling existing buffer length)
31 /// 3. Insert at `gap_start` and increment gap_start by 1 (slot filled)
32 ///
33 /// # Panics
34 /// Panics if `pos` is out of bounds.
35 fn insert(&mut self, pos: usize, char: char) {
36 if pos >= self.len() {
37 panic!("GapBuffer: Insert range out of bounds ({} >= {})", pos, self.len());
38 }
39 self.move_gap(pos);
40
41 if self.gap_start == self.gap_end {
42 let old_len = self.buffer.len();
43 self.buffer.resize(old_len * 2, char::default());
44 let new_len = self.buffer.len();
45 let range_size = old_len - self.gap_start;
46 self.buffer.copy_within(self.gap_start..old_len, new_len - range_size);
47 self.gap_end = new_len - range_size;
48 }
49
50 self.buffer[self.gap_start] = char;
51 self.gap_start += 1;
52 }
53
54 /// Deletes from a gap buffer.
55 ///
56 /// 1. Moves gap
57 /// 2. Extends gap by `len` by adding to `gap_end`
58 ///
59 /// # Panics
60 /// Panics if `gap_end` + `len` is out of bounds.
61 fn delete(&mut self, start: usize, len: usize) {
62 self.move_gap(start);
63 if self.gap_end + len > self.buffer.len() {
64 panic!("GapBuffer: Delete range out of bounds.");
65 }
66 self.gap_end += len;
67 }
68
69 /// Reads from a gap buffer.
70 ///
71 /// Reads from the left and right of the buffer, skipping over the gap.
72 ///
73 /// # Panics
74 /// Panics if `start` is out of bounds.
75 /// Panics if `end` is out of bounds.
76 /// Panics if `start` is greater than `end`.
77 fn read(&self, start: usize, end: usize) -> impl DoubleEndedIterator<Item = &char> {
78 let len = self.buffer.len();
79 if start >= len {
80 panic!("GapBuffer: Read range out of bounds ({} >= {}).", start, len);
81 }
82 else if end > len {
83 panic!("GapBuffer: Read range out of bounds ({} > {}).", end, len)
84 }
85 else if start > end {
86 panic!("GapBuffer: Read range invalid ({} > {}).", start, end);
87 }
88
89 let left = &self.buffer[start..self.gap_start];
90 let right = &self.buffer[self.gap_end..end];
91
92 left.iter().chain(right.iter())
93 }
94
95 /// Calculates the length of a gap buffer.
96 ///
97 /// Length = Length of buffer - size of gap
98 fn len(&self) -> usize {
99 self.buffer.len() - (self.gap_end - self.gap_start)
100 }
101}
102
103impl GapBuffer {
104 /// Helper method to move the gap.
105 ///
106 /// First determine direction to move in.
107 ///
108 /// LEFT:
109 /// 1. Determine distance between `pos` and `gap_start`.
110 /// 2. Copy all characters between `pos` and `gap_start` inclusive to the other side of the gap.
111 /// 3. Move gap to the left by subtracting `dist` from gap bounds.
112 ///
113 /// LEFT EXAMPLE:
114 /// [H, E (pos), L, _ (gap_start), _, _, _, _, L (gap_end), O], `pos` = 1, `gap_start` = 3, `gap_end` = 8
115 ///
116 /// 1. dist = 2
117 ///
118 /// 2. Characters between `pos` and `gap_start`: E, L
119 /// [H, E (pos), L, _ (gap_start), _, _, E, L, L (gap_end), O]
120 ///
121 /// 3. "Retrieve" consumed gap spaces:
122 /// [H, E (gap_start/pos), L, _, _, _, E, L, L (gap_end), O]
123 ///
124 /// "Final" buffer: [H, _ (gap_start), _, _, _, _, E (gap_end), L, L, O]
125 ///
126 /// RIGHT:
127 /// 1. Determine "real position" because the user of the API doesn't account for gap indices
128 /// 2. Determine distance between `pos` and `gap_start` to calculate the distance the gap has to move
129 /// 3. Copy all characters between `gap_end` and the "real position" to the other side of the gap.
130 /// 4. Move gap to the right by adding `dist` to gap bounds.
131 ///
132 /// RIGHT EXAMPLE:
133 /// [H, _ (gap_start), _, _, _, _, E (gap_end), L, L (pos), O], `pos` = 3, `gap_start` = 1, `gap_end` = 6
134 ///
135 /// 1. real_pos = 8
136 ///
137 /// 2. dist = 2
138 ///
139 /// 3. Characters between `gap_end` and `real_pos`: E, L
140 /// [H, E (gap_start), L, _, _, _, E (gap_end), L, L (pos), O]
141 ///
142 /// 4. "Retrieve" consumed gap spaces:
143 /// [H, E, L, _ (gap_start), _, _, E, L, L (gap_end/pos), O]
144 ///
145 /// "Final" buffer: [H, E, L, _ (gap_start), _, _, _, _, L (gap_end/pos), O]
146 fn move_gap(&mut self, pos: usize) {
147 if self.gap_start > pos {
148 let dist = self.gap_start - pos;
149 self.buffer.copy_within(pos..self.gap_start, self.gap_end - dist);
150 self.gap_start -= dist;
151 self.gap_end -= dist;
152 }
153 else if self.gap_start < pos {
154 let real_pos = pos + self.gap_end - self.gap_start;
155 let dist = pos - self.gap_start;
156 self.buffer.copy_within(self.gap_end..real_pos, self.gap_start);
157 self.gap_start += dist;
158 self.gap_end += dist;
159 }
160 }
161}