I have a particular algorithm which I want to implement using doubly linked lists. I need to do this because the algorithm requires some linked list operations like (i) deleting an element inside the list or (ii) moving an element from one linked list to another.
I thought that the best way to do this may be to allocate an arena which holds all the elements, and has all the forward and backward links. And then, a linked list would constitute of a reference to an arena, and a pointer to the head of the specific linked list. The arenas would be implemented using a vector.
However, I am not able to figure out the correct lifetime parameter tricks to make the get function below to typecheck. Any help is appreciated. Also, if the code can be more idiomatic and less awkward somehow, please suggest how I can do so.
use std::cell::RefCell;
use std::rc::Rc;
struct VllPool<T> {
mem : Vec<T>,
freehead : Option<usize>,
next : Vec<Option<usize>>,
prev : Vec<Option<usize>>,
}
struct Vll<T> {
pool : Rc<RefCell<VllPool<T>>>,
head : Option<usize>,
}
struct VllPointer<T> {
ptr : usize,
vll : Rc<RefCell<Vll<T>>>,
}
impl<T> VllPool<T>{
fn new(size : usize) -> VllPool<T> {
assert!(size > 0);
let mut mem : Vec<T> = Vec::with_capacity(size);
unsafe {
mem.set_len(size);
}
let freehead : Option<usize> = Some(0);
// next = [Some(1), Some(2), ..., Some(size-1), None]
let mut next : Vec<Option<usize>> = (0..size).map(|i| Some(i + 1)).collect();
next.push(None);
let prev : Vec<Option<usize>> = vec![None; size];
VllPool { mem, freehead, next, prev }
}
fn new_vll(self_ : Rc<RefCell<VllPool<T>>>) -> Vll<T> {
Vll { pool : self_.clone(), head : None }
}
fn has_space(&self) -> bool {
self.freehead.is_some()
}
// creates a new node with content x
// which is positioned after after, and before before,
// i.e, after -> new -> before
fn insert_new(&mut self, x : T, after : Option<usize>, before : Option<usize>) -> usize {
assert!(self.has_space());
let tmp = self.freehead.unwrap();
self.freehead = self.next[tmp];
self.next[tmp] = before;
self.prev[tmp] = after;
if let Some(b) = before {
self.prev[b] = Some(tmp);
}
if let Some(a) = after {
self.next[a] = Some(tmp);
}
self.mem[tmp] = x;
tmp
}
// deletes the node at position p
// p is the new head of the free list
// if we previously had after -> p -> before
// now we have after -> before
fn delete(&mut self, p : usize) {
let after = self.prev[p];
let before = self.next[p];
if let Some(b) = before {
self.prev[b] = after;
}
if let Some(a) = after {
self.next[a] = before;
}
self.next[p] = self.freehead;
self.freehead = Some(p);
}
// moves p to a new singleton list
fn move_to_singleton(&mut self, p : usize){
// previously we had after -> p -> before
// now we have after -> before
let after = self.prev[p];
let before = self.next[p];
if let Some(b) = before {
self.prev[b] = after;
}
if let Some(a) = after {
self.next[a] = before;
}
// now we have p -> None
self.next[p] = None;
self.prev[p] = None;
}
fn get<'b>(&'b self, p : usize) -> &'b T {
&self.mem[p]
}
}
impl<T> Vll<T> {
fn is_empty(&self) -> bool {
self.head.is_none()
}
fn push(self_ : Rc<RefCell<Vll<T>>>, x : T) -> VllPointer<T> {
let mut self1 = self_.borrow_mut();
let tmp = {
let mut pool = self1.pool.borrow_mut();
pool.insert_new(x, None, self1.head)
};
self1.head = Some(tmp);
VllPointer { ptr : tmp, vll : self_.clone() }
}
fn delete(p : VllPointer<T>) {
let mut self1 = p.vll.borrow_mut();
let headnext = self1.pool.borrow().next[p.ptr];
if self1.head == Some(p.ptr) {
self1.head = headnext;
}
let mut pool = self1.pool.borrow_mut();
pool.delete(p.ptr);
}
// move current node to a new list
fn move_to_singleton(p : VllPointer<T>) -> Vll<T>{
let self1 = p.vll.borrow();
let mut pool = self1.pool.borrow_mut();
pool.move_to_singleton(p.ptr);
Vll { pool : self1.pool.clone(), head : Some(p.ptr) }
}
// fn get(&self, p : VllPointer<T>) -> &T {
// let pool = self.pool.borrow();
// &pool.get(p.ptr)
// }
}
fn main(){
let pool : VllPool<u64> = VllPool::new(10);
let poolref = Rc::new(RefCell::new(pool));
let vll1 = VllPool::new_vll(poolref.clone());
let vll2 = VllPool::new_vll(poolref.clone());
let vll1ref = Rc::new(RefCell::new(vll1));
let vll2ref = Rc::new(RefCell::new(vll2));
let p11 = Vll::push(vll1ref.clone(), 1);
let p12 = Vll::push(vll1ref.clone(), 2);
let p21 = Vll::push(vll2ref.clone(), 1);
let p22 = Vll::push(vll2ref.clone(), 2);
let p23 = Vll::push(vll2ref.clone(), 3);
Vll::delete(p21);
Vll::delete(p11);
let vll3 = Vll::move_to_singleton(p22);
}
To be clear, Vll (vector linked list) is the linked list type, and it is meant to be accessed via the VllPointer type
