Doubly Linked List in purely safe rust

doubly_linked_list.rs

/// doubly linked list in purely safe rust

use std::rc::{Rc, Weak};
use std::cell::RefCell;
use std::fmt::Debug;

type Node<T> = RefCell<Option<T>>;

#[derive(Debug)]
pub struct ListNode<T> {
    pub v: T,
    prev: Node<Weak<ListNode<T>>>,
    next: Node<Rc<ListNode<T>>>,
}

impl<T> ListNode<T> {
    fn new(v: T) -> Self {
        ListNode { v, prev: RefCell::new(None), next: RefCell::new(None) }
    }
}

#[derive(Debug)]
struct LinkedList<T> {
    head: RefCell<Rc<ListNode<T>>>,
    last: RefCell<Rc<ListNode<T>>>,
}

impl<T: Debug> LinkedList<T> {
    pub fn singleton(t: T) -> Self {
        let node = Rc::new(ListNode::new(t));

        LinkedList {
            head: RefCell::new(Rc::clone(&node)),
            last: RefCell::new(Rc::clone(&node)),
        }
    }

    pub fn prepend(&mut self, v: T) -> &mut Self {
        let ref head = self.head;
        let new_head = Rc::new(
            ListNode {
                v,
                prev: RefCell::new(None),
                next: RefCell::new(Some(Rc::clone(&head.borrow()))),
            });

        *head.borrow().prev.borrow_mut() = Some(Rc::downgrade(&new_head));
        *head.borrow_mut() = new_head;

        self
    }

    pub fn append(&mut self, v: T) -> &mut Self {
        let ref last = self.last;

        let new_last = Rc::new(
            ListNode {
                v,
                prev: RefCell::new(Some(Rc::downgrade(&last.borrow()))),
                next: RefCell::new(None),
            });

        *last.borrow().next.borrow_mut() = Some(Rc::clone(&new_last));
        *last.borrow_mut() = new_last;

        self
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_singleton() {
        let list: LinkedList<u32> = LinkedList::singleton(1u32);

        let head = list.head.borrow();
        eprintln!("head = {:?}", head);
        assert_eq!(head.v, 1u32);

        // singleton list's head and last should point to the same node
        assert_eq!(head.v, list.last.borrow().v);
    }

    #[test]
    fn test_prepend1() {
        let mut list = LinkedList::singleton(1u32);
        list.prepend(0);

        eprintln!("new-list = {:#?}", &list);
        assert_eq!(0, list.head.borrow().v);
    }

    #[test]
    fn test_append1() {
        let mut xs = LinkedList::singleton(1);

        xs.prepend(0)
            .append(2)
            .append(3)
            .append(4);

        // head and last should have 2 strong count
        assert_eq!(2, Rc::strong_count(&xs.last.borrow()));

        eprintln!("xs = {:#?}", xs);
        assert_eq!(xs.last.borrow().v, 4);
        let head = xs.head.borrow();
        assert_eq!(head.v, 0);

        let second_node = head.next.borrow();
        let second_node_ref = second_node.as_ref().unwrap();

        assert_eq!(second_node_ref.v, 1);
        eprintln!("original_value1_node strong vs weak = {:?} vs {:?}",
                  Rc::strong_count(second_node_ref),
                  Rc::weak_count(second_node_ref));

        assert_eq!(1, Rc::strong_count(second_node_ref));
        assert_eq!(1, Rc::weak_count(second_node_ref));
    }
}