So I'm working on a "Rope" data structure, which is a "chunked" vector that allows (relatively) quick inserts and deletes.
It looks like this:
#[derive(Clone, Debug)]
struct RopeChunk<T: Copy> {
idx: usize,
content: Vec<T>,
}
#[derive(Clone, Debug)]
pub struct Rope<T: Copy> {
len: usize,
chunks: Vec<RopeChunk<T>>,
}
Easy peasy.
I need a method with this signature:
pub fn get_mut<U: RangeBounds<usize>>(&mut self, range: U) -> Vec<&mut [T]>
Many of you can now imagine my suffering.
Here is what I came up with:
pub fn get_mut<U: RangeBounds<usize>>(&mut self, range: U) -> Vec<&mut [T]> {
let (start, end) = range_helper(range, self.len);
if start == end {
Vec::new()
} else {
let mut result = Vec::new();
let chunks = self.get_chunks(start, end);
let (_, main_split) = self.chunks.split_at_mut(chunks[0].0);
let mut len = main_split.len();
let mut remaining_slices = main_split.as_mut_ptr();
for (ch_idx, ch_start, ch_end) in chunks {
let cur;
let next;
unsafe {
cur = slice::from_raw_parts_mut(remaining_slices, 1)
.get_mut(0)
.unwrap();
next = slice::from_raw_parts_mut(remaining_slices.offset(1), len);
}
len += 1;
remaining_slices = next.as_mut_ptr();
result.push(&mut cur.content[ch_start..ch_end]);
}
result
}
}
The self.getChunks(...) method figures out which RopeChunks we need, along with what sub-ranges within them.
I tried doing this with slice::split_at_mut(), but I kept getting all kinds of borrow errors, since I needed to split it repeatedly in a loop. The borrow checker didn't like that, not at all. Anyhow, I gave up and used pointers.
I've tested this a fair bit, even at the boundaries. It seems to work.
But still...
But still...
Can this be done in safe Rust?