Datastructure / algorithm for replacing subrange of sequence

1 
We have:

T: type of some Node
Seq: could be Vec, LinkedList, ... some type of _Ordered_ List

impl Seq {
  fn foo(&mut self, left: usize, right: usize, other_seq: Seq) {
    delete elements [left, right) from self;
    insert other_seq
  }
}

This is fairly straight forward to do in O(n) time.

I think there is a O(log n) solution involving immutable::Vec / rrb vectors.

This is also an operation that turns up frequently in editors (delete this region, insert this other block).

I am wondering if there is an idiomatic solution for this.

2

Are you looking for a rope?

1 Like
3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.