singlely_linked_list.rs

use std::cell::RefCell;
use std::rc::Rc;

type Link<T> = Rc<RefCell<Node<T>>>;

pub struct Node<T: Copy> {
    value: T,
    next: Option<Link<T>>,
}

pub struct SinglyLinkedList<T: Copy> {
    head: Option<Link<T>>,
}

impl<T: Copy> SinglyLinkedList<T> {
    pub fn new() -> Self {
        Self { head: None }
    }

    fn get_head(&self) -> Option<Link<T>> {
        match self.head {
            Some(ref h) => Some(Rc::clone(h)),
            None => return None,
        }
    }

    pub fn get_node(&self, index: usize) -> Option<Link<T>> {
        let head = self.get_head();
        let mut node = match head {
            Some(h) => h,
            None => return None,
        };

        for _ in 0..index {
            node = match Rc::clone(&node).borrow().next {
                Some(ref next) => Rc::clone(next),
                None => return None,
            };
        }
        Some(node)
    }

    pub fn insert(&mut self, index: usize, value: T) -> Result<(), ()> {
        if index == 0 {
            self.head = Some(Rc::new(RefCell::new(Node {
                value,
                next: self.get_head(),
            })));
            return Ok(());
        }

        let c = match self.get_node(index - 1) {
            Some(ref p) => Rc::clone(p),
            None => return Err(()),
        };
        let mut previous = c.borrow_mut();
        let new_node = Node {
            value,
            next: previous.next.as_ref().map(|x| Rc::clone(x)),
        };
        previous.next = Some(Rc::new(RefCell::new(new_node)));

        Ok(())
    }

    pub fn to_vec(&self) -> Vec<T> {
        let mut v = vec![];
        let head = self.get_head();
        let mut node = match head {
            Some(h) => {
                v.push(h.borrow().value);
                h
            }
            None => return v,
        };

        loop {
            node = match Rc::clone(&node).borrow().next {
                Some(ref n) => {
                    v.push(n.borrow().value);
                    Rc::clone(n)
                }
                None => return v,
            };
        }
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn test() {
        let mut list = super::SinglyLinkedList::new();

        assert!(list.insert(0, "Hello").is_ok());
        assert_eq!(list.to_vec(), vec!["Hello"]);

        assert!(list.insert(1, "World").is_ok());
        assert_eq!(list.to_vec(), vec!["Hello", "World"]);

        assert!(list.insert(1, "Rust").is_ok());
        assert_eq!(list.to_vec(), vec!["Hello", "Rust", "World"]);
    }
}