/// Link is a type alias for `enum Option<Box<Node<T>>>`. /// It represents two possibilities for a link: /// either `Some(Box<Node<T>>)` a boxed Node (representing a cons) /// or a `None` (representing a nill) type Link<T> = Option<Box<Node<T>>>; /// `struct List` represents a list itself. It has a `head` filed /// which points to first node in the actual list. The field `len` /// contains the size of the list. #[derive(Debug)] pub struct List<T> { pub head: Link<T>, pub len: usize, } /// `struct Node` represents a list's node with a `payload` field /// and a `next` field that points to the next node (or null). #[derive(Debug)] pub struct Node<T> { pub payload: T, pub next: Link<T> } impl<T> List<T> { /// Makes a new empty list. pub fn new() -> Self { List { head: None, len: 0, } } /// Get list size pub fn size(&self) -> i32 { // list size is usize, but cast it as i32 *&self.len as i32 } /// Check if the list is empty. pub fn is_empty(&self) -> bool { self.head.is_none() } /// Removes all elements from the list. pub fn clear(&mut self) { *self = Self::new(); } /// Removes the first node, returns its payload pub fn pop(&mut self) -> Option<T> { self.head .take() .map(|boxed_node| { let node = *boxed_node; self.head = node.next; self.len -= 1; node.payload }) } /// Prepend node onto the list. pub fn push(&mut self, payload: T) { let new_node = Box::new(Node { payload, next: self.head.take(), }); self.head = Some(new_node); self.len += 1; } /// Returns a reference to the payload of the list's head node pub fn peek(&self) -> Option<&T> { self.head.as_ref().map(|node| &node.payload) } /// Returns a mutable reference to the payload of the list's head node pub fn peek_mut(&mut self) -> Option<&mut T> { self.head.as_mut().map(|node| &mut node.payload) } /// Puts a payload in a new node and appends it onto the list. pub fn append(&mut self, payload: T) { if self.is_empty() { self.push(payload); return; } let mut link = self.head.as_mut(); while let Some(mut_boxed_node) = link { if let None = mut_boxed_node.next { let new_node = Some(Box::new(Node { payload, next: None })); mut_boxed_node.next = new_node; self.len += 1; break; } link = mut_boxed_node.next.as_mut(); } } } //impl // Drop // impl<T> Drop for List<T> { /// Drops the list recursively by node. fn drop(&mut self) { let mut cur_link = self.head.take(); while let Some(mut boxed_node) = cur_link { cur_link = boxed_node.next.take(); } } } // IntoIter // pub struct IntoIter<T>(List<T>); impl<T> List<T> { pub fn into_iter(self) -> IntoIter<T> { IntoIter(self) } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.0.pop() } } // impl IntoIter // Display // use std::fmt::{self, Display}; impl<T> Display for List<T> where T: fmt::Display { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { let mut cur_link = &self.head; write!(f, "List: ")?; while let &Some(ref boxed_node) = cur_link { write!(f, "[{}] -> ", boxed_node.payload)?; cur_link = &boxed_node.next; } write!(f, "nil") } } // impl Display // Default // impl<T> Default for List<T> { /// Creates an empty list. fn default() -> Self { Self::new() } } // impl Default