Pasted

mod x_c3db81ec94bf231b721ef483f58deb35 {
    //! A doubly-linked list in 50 LOCs of stable and safe Rust.
    use std::cell::RefCell;
    use std::rc::{Rc, Weak};
    use std::fmt::Display;
 
    // The node type stores the data and two pointers.
    //
    // It uses Option to represent nullability in safe Rust. It has zero overhead
    // over a null pointer due to the NonZero optimization.
    //
    // It uses an Rc (Reference Counted) pointer to give ownership of the next node
    // to the current node. And a Weak (weak Reference Counted) pointer to reference
    // the previous node without owning it.
    //
    // It uses RefCell for interior mutability. It allows mutation through
    // shared references.
    struct Node<T> {
        pub data: T,
        pub prev: Option<Weak<RefCell<Node<T>>>>,
        pub next: Option<Rc<RefCell<Node<T>>>>,
    }
 
    impl<T> Node<T> {
        // Constructs a node with some `data` initializing prev and next to null.
        pub fn new(data: T) -> Self {
            Self { data, prev: None, next: None }
        }
 
        // Appends `data` to the chain of nodes. The implementation is recursive
        // but one could rewrite it to use a while-let imperative loop instead
        // without too much effort.
        pub fn append(node: &mut Rc<RefCell<Node<T>>>, data: T) -> Option<Rc<RefCell<Node<T>>>> {
            let is_last = node.borrow().next.is_none();
            if is_last {
                // If the current node is the last one, create a new node,
                // set its prev pointer to the current node, and store it as
                // the node after the current one.
                let mut new_node = Node::new(data);
                new_node.prev = Some(Rc::downgrade(&node));
                let rc = Rc::new(RefCell::new(new_node));
                node.borrow_mut().next = Some(rc.clone());
                Some(rc)
            } else {
                // Not the last node, just continue traversing the list:
                if let Some(ref mut next) = node.borrow_mut().next {
                    Self::append(next, data)
                } else { None }
            }
        }
    }
 
    // The doubly-linked list with pointers to the first and last nodes in the list.
    struct List<T> {
        first: Option<Rc<RefCell<Node<T>>>>,
        last: Option<Rc<RefCell<Node<T>>>>,
    }
 
    impl<T> List<T> {
        // Constructs an empty list.
        pub fn new() -> Self {
            Self { first: None, last: None }
        }
        // Appends a new node to the list, handling the case where the list is empty.
        pub fn append(&mut self, data: T) {
            if let Some(ref mut next) = self.first {
                self.last = Node::append(next, data);
            } else {
                let f = Rc::new(RefCell::new(Node::new(data)));
                self.first = Some(f.clone());
                self.last = Some(f);
            }
        }
    }
 
    // Pretty-printing
    impl<T: Display> Display for List<T> {
        fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
            write!(w, "[")?;
            let mut node = self.first.clone();
            while let Some(n) = node {
                write!(w, "{}", n.borrow().data)?;
                node = n.borrow().next.clone();
                if node.is_some() {
                    write!(w, ", ")?;
                }
            }
            write!(w, "]")
        }
    }
 
    fn main() {
        let mut list = List::new();
        println!("{}", list);
        for i in 0..5 {
            list.append(i);
        }
        println!("{}", list);
    }
}
 
mod x_71c6bc45ff92452d5a4397ddb2dbb3de {
    //! A doubly-linked list in 50 LOCs of stable and safe Rust.
    use std::cell::RefCell;
    use std::rc::{Rc, Weak};
    use std::fmt::Display;
 
    // The node type stores the data and two pointers.
    //
    // It uses Option to represent nullability in safe Rust. It has zero overhead
    // over a null pointer due to the NonZero optimization.
    //
    // It uses an Rc (Reference Counted) pointer to give ownership of the next node
    // to the current node. And a Weak (weak Reference Counted) pointer to reference
    // the previous node without owning it.
    //
    // It uses RefCell for interior mutability. It allows mutation through
    // shared references.
    struct Node<T> {
        pub data: T,
        pub prev: Option<Weak<RefCell<Node<T>>>>,
        pub next: Option<Rc<RefCell<Node<T>>>>,
    }
 
    impl<T> Node<T> {
        // Constructs a node with some `data` initializing prev and next to null.
        pub fn new(data: T) -> Self {
            Self { data, prev: None, next: None }
        }
        // Appends `data` to the chain of nodes. The implementation is recursive
        // but one could rewrite it to use a while-let imperative loop instead
        // without too much effort.
        pub fn append(node: &mut Rc<RefCell<Node<T>>>, data: T) {
            let is_last = node.borrow().next.is_none();
            if is_last {
                // If the current node is the last one, create a new node,
                // set its prev pointer to the current node, and store it as
                // the node after the current one.
                let mut new_node = Node::new(data);
                new_node.prev = Some(Rc::downgrade(&node));
                node.borrow_mut().next = Some(Rc::new(RefCell::new(new_node)));
            } else {
                // Not the last node, just continue traversing the list:
                if let Some(ref mut next) = node.borrow_mut().next {
                    Self::append(next, data);
                }
            }
        }
    }
 
    // The doubly-linked list with pointers to the first and last nodes in the list.
    struct List<T> {
        first: Option<Rc<RefCell<Node<T>>>>,
        last: Option<Rc<RefCell<Node<T>>>>,
    }
 
    impl<T> List<T> {
        // Constructs an empty list.
        pub fn new() -> Self {
            Self { first: None, last: None }
        }
        // Appends a new node to the list, handling the case where the list is empty.
        pub fn append(&mut self, data: T) {
            if let Some(ref mut next) = self.first {
                Node::append(next, data);
                let v = self.last.as_ref().unwrap().borrow().next
                    .as_ref().unwrap().clone();
                self.last = Some(v);
            } else {
                let f = Rc::new(RefCell::new(Node::new(data)));
                self.first = Some(f.clone());
                self.last = Some(f);
            }
        }
    }
 
    // Pretty-printing
    impl<T: Display> Display for List<T> {
        fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
            write!(w, "[")?;
            let mut node = self.first.clone();
            while let Some(n) = node {
                write!(w, "{}", n.borrow().data)?;
                node = n.borrow().next.clone();
                if node.is_some() {
                    write!(w, ", ")?;
                }
            }
            write!(w, "]")
        }
    }
 
    fn main() {
        let mut list = List::new();
        println!("{}", list);
        for i in 0..5 {
            list.append(i);
        }
        println!("{}", list);
    }
}