Insert cursor into the buffer, maintaining sorted order efficiently The algorithm models cursor coverage as an "array with holes" that get filled over time: ```text Positions: [0][1][2][3][4][5][6] Initial: [ ][ ][ ][ ][ ][ ][ ] committed_position = 0 Add cursor_4: [ ][ ][ ][ ][4][ ][ ] buffer: [4], nothing emitted Add cursor_0: [0][ ][ ][ ][4][ ][ ] emit [0], committed_position = 1
(&mut self, cursor: Cursor)
| 61 | // |
| 62 | // Once a contiguous section from `committed_position` is complete, it's emitted immediately. |
| 63 | fn append(&mut self, cursor: Cursor) { |
| 64 | #[cfg(debug_assertions)] |
| 65 | { |
| 66 | debug_assert!(!self.seen_eof, "Received cursor after EOF: {:?}", cursor); |
| 67 | if cursor == Kind::Eof { |
| 68 | self.seen_eof = true; |
| 69 | } |
| 70 | } |
| 71 | let cursor_start = cursor.span().start(); |
| 72 | if self.buffer.is_empty() || cursor_start.0 >= self.buffer.last().unwrap().span().start().0 { |
| 73 | self.buffer.push(cursor); |
| 74 | } else if cursor_start == self.committed_position { |
| 75 | // This cursor is the next in order |
| 76 | self.sink.append(cursor); |
| 77 | self.committed_position = cursor.end_offset(); |
| 78 | } else { |
| 79 | // The cursor needs to be buffered. |
| 80 | // TODO: binary_search_by_key is giving BTreeMap which would be O(log n) instead of O(n), but |
| 81 | // for small enough numbers that's fine? Investigate more. |
| 82 | let insert_pos = |
| 83 | self.buffer.binary_search_by_key(&cursor_start, |c| c.span().start()).unwrap_or_else(|pos| pos); |
| 84 | self.buffer.insert(insert_pos, cursor); |
| 85 | } |
| 86 | |
| 87 | // Check if a contiguous section from committed_position exists, and emit it if so |
| 88 | while !self.buffer.is_empty() { |
| 89 | // Remove any overlapping cursors first (those that start before committed_position) |
| 90 | let mut overlapping_count = 0; |
| 91 | for cursor in self.buffer.iter() { |
| 92 | if cursor.span().start().0 < self.committed_position.0 { |
| 93 | overlapping_count += 1; |
| 94 | } else { |
| 95 | break; |
| 96 | } |
| 97 | } |
| 98 | if overlapping_count > 0 { |
| 99 | self.buffer.drain(0..overlapping_count); |
| 100 | } |
| 101 | |
| 102 | if self.buffer.is_empty() { |
| 103 | break; |
| 104 | } |
| 105 | |
| 106 | // Find how many contiguous cursors can be emitted from the front |
| 107 | let mut current_pos = self.committed_position; |
| 108 | let mut emit_count = 0; |
| 109 | |
| 110 | for cursor in self.buffer.iter() { |
| 111 | let cursor_start = cursor.span().start(); |
| 112 | |
| 113 | if cursor_start == current_pos { |
| 114 | current_pos = cursor.end_offset(); |
| 115 | emit_count += 1; |
| 116 | } else { |
| 117 | // If this cursor starts after current_pos, stop, as there is a gap |
| 118 | break; |
| 119 | } |
| 120 | } |