I'm writing a piece table library in Rust with the structures:
#[derive(Default)]
struct Piece {
additional: bool,
offset: usize,
length: usize,
}
and
/// PieceTable contains the additional, original buffers and a vector of pieces.
/// It also maintains a length variable.
pub struct PieceTable {
table: VecDeque<Piece>,
orig_buffer: String,
add_buffer: String,
length: usize,
}
I'm fairly confident that I didn't mess anything up here, though I'm not sure if VecDeque is the best structure to hold the pieces. My insert method is:
impl PieceTable {
...
pub fn insert(&mut self, index: usize, text: &string) {
match self.piece_at(index + 1) {
Ok((index, offset)) => {
// isolate piece being inserted into
let into = &self.table[index];
// create necessary Pieces to enter
let previous = Piece {
additional: into.additional,
offset: into.offset,
length: offset - into.offset,
};
let insert = Piece {
additional: true,
offset: self.add_buffer.len(),
length: text.len(),
};
let next = Piece {
additional: into.additional,
offset: offset,
length: into.length - (offset - into.offset),
};
// remove index, add in previous, insert, next
self.table.remove(index);
self.table.insert(index, previous);
self.table.insert(index + 1, insert);
self.table.insert(index + 2, next);
// update buffer, length vars
self.add_buffer.push_str(text);
self.length += text.len();
}
Err(_) => self.push_str(text),
}
}
}
Which refers to the piece_at
method:
fn piece_at(&self, index: usize) -> Result<(usize, usize>, i32> {
if index > self.length {
return Err(-1);
}
let mut remaining = index.clone();
for (i, piece) in self.table.iter().enumerate() {
if remaining <= piece.length {
return Ok((i, remaining));
}
remaining -= piece.length;
}
return Err(-1);
}
It also relies on the push_str method, which is just appends a piece with the proper parameters to the end of self.table
.
This algorithm is stolen basically verbatim from the python implementation at https://github.com/saiguy3/piece_table, so hopefully there's nothing terribly wrong with it that I missed. Rust is hard and I started learning it yesterday, so I'm fully expecting I horribly misused some language feature.
Thanks!