dlist.rs

#[crate_type = "rlib"];
#[comment = "A doubly-linked list implementation using Rc and Weak"];

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

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

/// An immutable, doubly-linked list. Use RefCell to store mutable values.
pub struct List<T> {
    priv head: Option<Rc<RcN<T>>>
}

/// Explicit impl because T need not be clonable
impl<T> Clone for List<T> {
    fn clone(&self) -> List<T> {
        List { head: self.head.clone() }
    }
}

struct Node<T> {
    val: T,
    next: Option<Rc<Node<T>>>,
    prev: Option<Weak<RcN<T>>>,
}

impl<T> List<T> {
    pub fn new() -> List<T> {
        List { head: None }
    }

    fn from_node(node: Option<Rc<RcN<T>>>) -> List<T> {
        List { head: node }
    }

    /// Return the last element in a list
    pub fn last(&self) -> List<T> {
        let mut node = &self.head;
        loop {
            match node {
                // does only one refcount bump :)
                &None => return List::from_node(node.clone()),
                n     => node = n,
            }
        }
    }

    /// Get a reference to the value at the head of this list. Returns None if
    /// the empty list.
    pub fn get<'a>(&'a self) -> Option<&'a T> {
        match self.head {
            // dat pointer sugar
            // dat rvalue lifetime
            Some(ref n) => {
                let cell = n.borrow();
                // poo, ref_ has the wrong lifetime. ask niko what's up, how
                // to thread lifetime through.
                let ref_ = cell.borrow();
                Some(&ref_.get().val)
            },
            None    => None
        }
    }

    fn append(&mut self, item: T) {
        let mut n = self.last();
        let mut new_n = Node { val: item, next: None, prev: None };
        match n.head {
            Some(ref mut n) => {
                new_n.prev = Some(n.downgrade());
                let new_n = Rc::new(new_n);
                n.borrow().borrow_mut().get().next = Some(new_n);
            },
            None => self.head = Some(Rc::new(RefCell::new(new_n)))
        }
    }
}