Implementing a double-linked structure is not straight-forward in Rust for several reasons. @segeljakt has a WIP (#24) with an implementation. His thoughts on design follows:
I think there should be one or more chunked array queue implementations floating around on https://crates.io/. The solution I had in mind before was to use:
- a
std::collections::LinkedList for connecting the chunks
- a
std::vec::Vec (or array [T;N]) for storing each chunk.
- a
std::collections::linked_list::CursorMut for traversing between chunks.
- a higher-level Cursor, building on top of
CursorMut for traversing between elements of chunks.
A cursor is like an iterator but does not consume the thing it is iterating over. With DoubleEndedIterator, it might be a problem because you cannot iterate over the same element twice:
let numbers = vec![1, 2, 3, 4, 5, 6];
let mut iter = numbers.iter();
assert_eq!(Some(&1), iter.next());
assert_eq!(Some(&6), iter.next_back());
assert_eq!(Some(&5), iter.next_back());
assert_eq!(Some(&2), iter.next());
assert_eq!(Some(&3), iter.next());
assert_eq!(Some(&4), iter.next());
assert_eq!(None, iter.next());
assert_eq!(None, iter.next_back());
If you need multiple cursors, you might have to create them using an unsafe pointer. I think it is not possible to use a std::cell::RefCell + std::rc::Rc because the cursors must mutably borrow the linked list which they are traversing for their whole lifetime. With RefCell, Rust would panic if two cursors exist simultaneously. There should hopefully be no problem as long as you ensure that the cursors do not point to something which is deallocated.
fn main() {
use std::collections::LinkedList;
let mut l: LinkedList<[i32; 5]> = LinkedList::new();
let (mut c0, mut c1, mut c2) = unsafe {
let l = &mut l;
let l = l as *mut LinkedList<[i32; 5]>;
let c0 = l.as_mut().unwrap().cursor_back_mut();
let c1 = l.as_mut().unwrap().cursor_back_mut();
let c2 = l.as_mut().unwrap().cursor_back_mut();
(c0, c1, c2)
};
l.push_back([0,1,2,3,4]);
l.push_back([5,6,7,8,9]);
c0.move_next();
c1.move_next();
c2.move_next();
c2.move_next();
l.push_front([4,3,2,1,0]);
c0.move_prev();
println!("{:?}", l);
assert_eq!(c0.current(), Some(&mut [4,3,2,1,0]));
assert_eq!(c1.current(), Some(&mut [0,1,2,3,4]));
assert_eq!(c2.current(), Some(&mut [5,6,7,8,9]));
}
Implementing a double-linked structure is not straight-forward in Rust for several reasons. @segeljakt has a WIP (#24) with an implementation. His thoughts on design follows:
And,