1
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.