# Rust - insert into piecetable

I'm writing a piece table library in Rust with the structures:

#[derive(Default)]
struct Piece {
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,
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 {
offset: into.offset,
length: offset - into.offset,
};
let insert = Piece {
length: text.len(),
};
let next = Piece {
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.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!

Keep in mind that there already exist rope structure implementations in Rust, which support utf8, for example an_rope, where your PieceTable::insert is Rope::insert_str: https://docs.rs/an-rope/0.3.1/an_rope/struct.Rope.html#method.insert_str

Your code is really good for someone who just started learning, and nothing stands out as a misuse of language.

Why is index + 1 passed to piece_at, not simply index?

Using VecDeque does give a little potential for speedup in random insertion and removal. Although if I was doing a program like this, my choice of the data structure would be different - I'd use BTreeSet<Piece> instead, and order the Pieces by piece.offset.

You may write a removal and an insert at the same index as a single [] = instead.

About Copy/Clone:

• if your Piece derived Copy, the & in &self.table[index] could be omitted. Did you try compiling this code? Can it compile without errors? I doubt it since the immutable borrow with & will prevent you from removal and insertion later on.
• the .clone() in piece_at can be omitted, because piece: usize is Plain Old Data that is copied around with zero overhead (in syntax and in performance as well).

There are two tiny misspellings

• text: &string instead of text: &str
• (usize,usize>, instead of (usize,usize)>,

I'd change the Err(-1) return to carry the unit value instead as we don't need the i32 to signal anything. We return Err(()) there.