stevelauc / blog Goto Github PK

//! A single linked list implementation using safe Rust.

use std::fmt::{Debug, Display, Formatter};

type Link<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Link<T>,
}

impl<T> Node<T> {
    fn new(data: T) -> Self {
        Self { data, next: None }
    }
}

#[derive(Debug)]
pub struct List<T> {
    head: Link<T>,
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop_front()
    }
}

impl<T> IntoIterator for List<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}

impl<'node, T> IntoIterator for &'node List<T> {
    type Item = &'node T;
    type IntoIter = Iter<'node, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'node, T> IntoIterator for &'node mut List<T> {
    type Item = &'node mut T;
    type IntoIter = IterMut<'node, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T> List<T> {
    /// Returns an empty List
    pub fn new() -> Self {
        List::default()
    }

    /// Returns an iterator over the list.
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            cursor: self.head.as_deref(),
        }
    }

    /// Returns an iterator that allows modifying each value.
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            cursor: self.head.as_deref_mut(),
        }
    }

    /// Pushes an item to the end of the list.
    pub fn push_back(&mut self, value: T) {
        if let Some(ref mut head) = self.head {
            let mut last_node = head;
            while let Some(ref mut new_node) = last_node.next {
                last_node = new_node;
            }

            last_node.next = Some(Box::new(Node::new(value)));
        } else {
            self.head = Some(Box::new(Node::new(value)));
        }
    }

    /// Pushes an item to the front of the list.
    pub fn push_front(&mut self, value: T) {
        if self.head.is_some() {
            let old_head = self.head.take();
            let mut new_head = Node::new(value);
            new_head.next = old_head;
            self.head = Some(Box::new(new_head));
        } else {
            self.head = Some(Box::new(Node::new(value)));
        }
    }

    /// Removes the last element from the list and returns it, or None if it is empty.
    // The implementation of `pop_back()` depends on the situation of list and
    // can be divided into three cases:
    // 1. List is empty
    // 2. List has 1 node
    // 3. List has more than 1 node
    pub fn pop_back(&mut self) -> Option<T> {
        // case 3: List has more than 1 node
        if self.head.is_some() && self.head.as_ref().unwrap().next.is_some() {
            let mut node_before_last_node = self.head.as_deref_mut().unwrap();
            // The impl in this branch is a bit awkward
            // See this question for more detail
            // https://stackoverflow.com/q/73789723/14092446
            while node_before_last_node.next.is_some() {
                if node_before_last_node.next.as_ref().unwrap().next.is_none() {
                    break;
                }

                node_before_last_node =
                    node_before_last_node.next.as_deref_mut().unwrap();
            }
            let last_node = node_before_last_node.next.take().unwrap();
            Some(last_node.data)
        }
        // case 2: List has 1 node
        else if self.head.is_some()
            && self.head.as_ref().unwrap().next.is_none()
        {
            Some(self.head.take().unwrap().data)
        }
        // case 1: List is empty
        else {
            None
        }
    }

    /// Removes the first element from the list and returns it, or `None` if it is empty.
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|head| {
            self.head = head.next;
            head.data
        })
    }

    /// Returns a reference to the first element in the List, or `None` if it is empty.
    pub fn peek_front(&self) -> Option<&T> {
        self.head.as_ref().map(|head| &head.data)
    }

    /// Returns a reference to the last element in the List, or `None` if it is empty.
    pub fn peek_back(&self) -> Option<&T> {
        if let Some(ref head) = self.head {
            let mut last_node = head;
            while let Some(ref next) = last_node.next {
                last_node = next;
            }

            Some(&last_node.data)
        } else {
            None
        }
    }

    /// Returns a mutable reference to the first element in the List, or `None` if
    /// it is empty.
    pub fn peek_mut_front(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|head| &mut head.data)
    }

    /// Returns a mutable reference to the last element in the List, or `None` if
    /// it is empty.
    pub fn peek_mut_back(&mut self) -> Option<&mut T> {
        if let Some(ref mut head) = self.head {
            let mut last_node = head;
            while let Some(ref mut next) = last_node.next {
                last_node = next;
            }

            Some(&mut last_node.data)
        } else {
            None
        }
    }

    /// Returns the length of the List.
    pub fn len(&self) -> usize {
        let mut len = 0;
        let mut p = self.head.as_ref();
        while let Some(p_non_null) = p {
            len += 1;
            p = p_non_null.next.as_ref();
        }
        len
    }

    /// Returns `true` if the list is empty. Otherwise, returns `false`.
    pub fn is_empty(&self) -> bool {
        self.len().eq(&0)
    }

    /// Sort the list.
    pub fn sort(&mut self) {
        unimplemented!()
    }
}

/// An iterator over the references of the elements in a [`List`]
pub struct Iter<'node_lifetime, T> {
    cursor: Option<&'node_lifetime Node<T>>,
}

impl<'node_lifetime, T> Iterator for Iter<'node_lifetime, T> {
    type Item = &'node_lifetime T;
    fn next(&mut self) -> Option<Self::Item> {
        self.cursor.map(|node| {
            self.cursor = node.next.as_deref();
            &node.data
        })
    }
}

/// An iterator over the mutable references of the elements in a [`List`]
pub struct IterMut<'lifetime_of_node, T> {
    cursor: Option<&'lifetime_of_node mut Node<T>>,
}

impl<'node_lifetime, T> Iterator for IterMut<'node_lifetime, T> {
    type Item = &'node_lifetime mut T;

    fn next(&mut self) -> Option<Self::Item> {
        // ```rust
        // self.cursor.map(|node| {
        //     self.cursor = node.next.as_deref_mut();
        //     &mut node.data
        // })
        // ```
        // `self.cursor` is of type `Option<&mut Node<T>>`, which is not `Copy`.
        // `.map()` will move `self.cursor`, which is not allowed because `self.cursor`
        // is behind a shared reference `&mut self`.
        //
        // What if we call `.as_mut()` on `self.cursor` first
        //
        // ```rust
        // self.cursor.as_mut().map(|node| {
        //     // tries to update `self.cursor` in this closure
        //     self.cursor = node.next.as_deref_mut();
        //     &mut node.data
        // })
        // ```
        // `.as_mut()` exclusively borrows `self.cursor` in this closure, and we
        // are trying to write to `self.cursor` in this closure, which is obviously
        // not safe, so Rust rejects this code.
        //
        // The accepted solution is to call `.take()` on `self.cursor` to takes its
        // value out of option. By doing this, we will have two separate objects in
        // the memory, one is `self.cursor`, which has the value `None`, another one
        // is a new object constructed by `.take()`, then we write to `self.cursor`
        // using the value from that new object, this is totally safe.
        self.cursor.take().map(|node| {
            self.cursor = node.next.as_deref_mut();
            &mut node.data
        })
    }
}

impl<T> Default for List<T> {
    fn default() -> Self {
        Self { head: None }
    }
}

impl<T: Debug> Display for List<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "List: ")?;
        let mut p = self.head.as_ref();
        while let Some(p_not_null) = p {
            write!(f, "{:?} ", p_not_null.data)?;
            p = p_not_null.next.as_ref();
        }
        Ok(())
    }
}

impl<T> FromIterator<T> for List<T> {
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = Self::new();

        iter.into_iter().for_each(|value| list.push_back(value));
        list
    }
}

impl<T> Extend<T> for List<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        iter.into_iter().for_each(|value| self.push_back(value));
    }
}

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

    #[test]
    fn test_from_iter() {
        let list = List::from_iter([1, 2, 3]);
        list.into_iter().eq([1, 2, 3]);
    }

    #[test]
    fn test_extend() {
        let mut list = List::new();
        list.extend([1, 2, 3]);
        list.into_iter().eq([1, 2, 3]);

        let mut list = List::from_iter([1, 2, 3]);
        list.extend([4, 5, 6]);
        list.into_iter().eq([1, 2, 3, 4, 5, 6]);
    }

    #[test]
    fn test_iter() {
        let list = List::from_iter([1, 2, 3]);
        list.iter().eq([&1, &2, &3]);
    }

    #[test]
    fn test_iter_mut() {
        let mut list = List::from_iter([1, 2, 3]);
        list.iter_mut().eq([&mut 1, &mut 2, &mut 3]);
    }

    #[test]
    fn test_into_iter() {
        let list = List::from_iter([1, 2, 3]);
        list.into_iter().eq([1, 2, 3]);
    }

    #[test]
    fn test_push_back() {
        let mut list = List::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        list.into_iter().eq([1, 2, 3]);
    }

    #[test]
    fn test_push_front() {
        let mut list = List::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        list.into_iter().eq([3, 2, 1]);
    }

    #[test]
    fn test_pop_back() {
        let mut list = List::from_iter([1, 2, 3]);
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn test_pop_front() {
        let mut list = List::from_iter([1, 2, 3]);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), None);
    }

    #[test]
    fn test_peek_front() {
        let mut list = List::new();
        assert_eq!(list.peek_front(), None);

        list.push_front(1);
        assert_eq!(list.peek_front(), Some(&1));
    }

    #[test]
    fn test_peek_back() {
        let mut list = List::new();
        assert_eq!(list.peek_back(), None);

        list.push_back(1);
        assert_eq!(list.peek_back(), Some(&1));

        list.push_front(0);
        assert_eq!(list.peek_back(), Some(&1));

        list.push_back(2);
        assert_eq!(list.peek_back(), Some(&2));
    }

    #[test]
    fn test_peek_mut_front() {
        let mut list = List::new();
        assert_eq!(list.peek_mut_front(), None);

        list.push_front(1);
        assert_eq!(list.peek_mut_front(), Some(&mut 1));
    }

    #[test]
    fn test_peek_mut_back() {
        let mut list = List::new();
        assert_eq!(list.peek_back(), None);

        list.push_back(1);
        assert_eq!(list.peek_mut_back(), Some(&mut 1));

        list.push_front(0);
        assert_eq!(list.peek_mut_back(), Some(&mut 1));

        list.push_back(2);
        assert_eq!(list.peek_mut_back(), Some(&mut 2));
    }

    #[test]
    fn test_len() {
        let mut list = List::new();
        assert_eq!(list.len(), 0);

        list.push_back(0);
        assert_eq!(list.len(), 1);

        list.extend([1, 2, 3]);
        assert_eq!(list.len(), 4);

        list.pop_back();
        assert_eq!(list.len(), 3);
    }
}