Rustによる単方向リスト

list.rs

use std::fmt;
#[derive(Debug)]
pub struct List<T: Eq> {
    head: Option<Box<Node<T>>>,
}
#[derive(Debug)]
pub struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}
impl<T: Eq> List<T> {
    pub fn new() -> Self {
        Self { head: None }
    }
    pub fn push_front(&mut self, value: T) {
        self.head = Some(Box::new(Node {
            value: value,
            next: std::mem::replace(&mut self.head, None),
            // 一度self.headはNoneになるが再代入される。
        }))
    }
    pub fn push_back(&mut self, value: T) {
        fn get_last<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
            match *node {
                Some(ref mut node_) => get_last(&mut node_.next),
                None => node, // Noneとなるnodeの&mutを返す
            }
        }
        let last_node = get_last(&mut self.head);
        *last_node = Some(Box::new(Node {
            value: value,
            next: None,
        }));
    }
    pub fn search(&self, value: T) -> Result<&Option<Box<Node<T>>>, &'static str> {
        fn search_elem<'a, T: Eq>(
            node: &'a Option<Box<Node<T>>>,
            value: T,
        ) -> Result<&'a Option<Box<Node<T>>>, &'static str> {
            match *node {
                None => Err("Not found"),
                Some(ref node_) => {
                    if node_.value == value {
                        Ok(node)
                    } else {
                        search_elem(&node_.next, value)
                    }
                }
            }
        }
        search_elem(&self.head, value)
    }
}

impl<T: Eq + fmt::Display> fmt::Display for List<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut node = match self.head {
            None => return write!(f, "has no nodes"),
            Some(ref b) => {
                let _ = write!(f, "{} ", &b.value);
                b.as_ref()
            }
        };
        while let Some(ref b) = node.next {
            let _ = write!(f, "{} ", &b.value);
            node = b.as_ref();
        }
        write!(f, "")
    }
}
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn push_front_one_item_test() {
        let mut list = List::new();
        list.push_front(1);
        assert_eq!(list.head.unwrap().value, 1);
    }
    #[test]
    fn push_front_two_items_test() {
        let mut list = List::new();
        list.push_front(1);
        list.push_front(2);
        assert_eq!(list.head.unwrap().value, 2);
    }
    #[test]
    fn push_back_one_item_test() {
        let mut list = List::new();
        list.push_back(1);
        assert_eq!(list.head.unwrap().value, 1);
    }
    #[test]
    fn push_back_two_items_test() {
        let mut list = List::new();
        list.push_back(1);
        list.push_back(2);
        assert_eq!(list.head.unwrap().next.unwrap().value, 2);
    }
    #[test]
    fn search_test() {
        let mut list = List::new();
        list.push_front(2);
        list.push_front(1);
        list.push_back(3);
        // vec![1, 2, 3].iter().map(|i| match list.search(*i)...)
        for i in 1..4 {
            match list.search(i) {
                Ok(node) => match *node {
                    Some(ref e) => assert_eq!(e.value, i),
                    None => assert!(false),
                },
                Err(_) => assert!(false),
            }
        }
        if let Err(_) = list.search(-1) {
            assert!(true);
        } else {
            assert!(false);
        }
    }
}

main.rs

extern crate introduction;
use introduction::list::List;
fn main() {
    let mut list = List::new();
    println!("{}", list);
    for i in vec![1, 2, 3] {
        list.push_back(i);
    }
    println!("{}", list);
}