Advertisement
Savior

Primitive LinkedList that works with Iterators

Feb 22nd, 2020
689
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Rust 4.23 KB | None | 0 0
  1. // Heavily based on https://rust-unofficial.github.io/too-many-lists
  2. use std::fmt;
  3. use std::iter::{FromIterator, IntoIterator};
  4.  
  5. #[derive(Debug)]
  6. struct LinkedList<T> {
  7.     head: Option<Box<Node<T>>>,
  8. }
  9.  
  10. #[derive(Debug)]
  11. struct Node<T> {
  12.     data: T,
  13.     next: Option<Box<Node<T>>>,
  14. }
  15.  
  16. struct LinkedListIterator<'a, T> {
  17.    next: Option<&'a Node<T>>,
  18. }
  19.  
  20. struct LinkedListMutIterator<'a, T> {
  21.    next: Option<&'a mut Node<T>>,
  22. }
  23.  
  24. struct LinkedListIntoIter<T>(LinkedList<T>);
  25.  
  26. impl<T> LinkedList<T> {
  27.     fn pop(&mut self) -> Option<T> {
  28.         self.head.take().map(|node| {
  29.             self.head = node.next;
  30.             node.data
  31.         })
  32.     }
  33.  
  34.     fn iter(&self) -> LinkedListIterator<T> {
  35.         LinkedListIterator {
  36.             next: self.head.as_ref().map::<&Node<T>, _>(|node| &node),
  37.         }
  38.     }
  39.  
  40.     fn iter_mut(&mut self) -> LinkedListMutIterator<T> {
  41.         LinkedListMutIterator {
  42.             // How to use the "turbofish" here?
  43.             next: self.head.as_mut().map(|node| &mut **node),
  44.         }
  45.     }
  46. }
  47.  
  48. impl<T> Drop for LinkedList<T> {
  49.     fn drop(&mut self) {
  50.         let mut cursor = self.head.take();
  51.         while let Some(mut node) = cursor {
  52.             cursor = node.next.take();
  53.         }
  54.     }
  55. }
  56.  
  57. impl<T> IntoIterator for LinkedList<T> {
  58.     type Item = T;
  59.     type IntoIter = LinkedListIntoIter<Self::Item>;
  60.  
  61.     fn into_iter(self) -> Self::IntoIter {
  62.         LinkedListIntoIter(self)
  63.     }
  64. }
  65.  
  66. impl<'a, T> Iterator for LinkedListIterator<'a, T> {
  67.     type Item = &'a T;
  68.  
  69.    fn next(&mut self) -> Option<Self::Item> {
  70.        self.next.take().map(|node| {
  71.            self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);
  72.            &node.data
  73.        })
  74.    }
  75. }
  76.  
  77. impl<'a, T> Iterator for LinkedListMutIterator<'a, T> {
  78.    type Item = &'a mut T;
  79.  
  80.     fn next(&mut self) -> Option<Self::Item> {
  81.         self.next.take().map(|node| {
  82.             self.next = node.next.as_mut().map(|node| &mut **node);
  83.             &mut node.data
  84.         })
  85.     }
  86. }
  87.  
  88. impl<T> Iterator for LinkedListIntoIter<T> {
  89.     type Item = T;
  90.  
  91.     #[inline(always)]
  92.     fn next(&mut self) -> Option<Self::Item> {
  93.         self.0.pop()
  94.     }
  95. }
  96.  
  97. impl<T> FromIterator<T> for LinkedList<T>
  98. where
  99.     T: Copy,
  100. {
  101.     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
  102.         // Is there a non-ugly way to do this?
  103.  
  104.         let mut list = LinkedList { head: None };
  105.         let mut prev: &mut Option<Box<Node<T>>> = &mut None;
  106.  
  107.         for item in iter {
  108.             let current = Some(Box::new(Node {
  109.                 data: item,
  110.                 next: None,
  111.             }));
  112.  
  113.             match *prev {
  114.                 None => {
  115.                     list.head = current;
  116.                     prev = &mut list.head;
  117.                 }
  118.                 Some(ref mut v) => {
  119.                     v.next = current;
  120.                     prev = &mut v.next;
  121.                 }
  122.             }
  123.         }
  124.  
  125.         list
  126.     }
  127. }
  128.  
  129. impl<T> fmt::Display for LinkedList<T>
  130. where
  131.     T: fmt::Display,
  132. {
  133.     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  134.        write!(f, "[")?;
  135.        for (i, v) in self.iter().enumerate() {
  136.            if i != 0 {
  137.                write!(f, ", ")?;
  138.            }
  139.            write!(f, "{}", v)?;
  140.        }
  141.        write!(f, "]")
  142.    }
  143. }
  144.  
  145. fn main() {
  146.    // let list = LinkedList {
  147.    //     head: Some(Box::new(Node {
  148.    //         data: 1u8,
  149.    //         next: Some(Box::new(Node {
  150.    //             data: 2u8,
  151.    //             next: Some(Box::new(Node {
  152.    //                 data: 3u8,
  153.    //                 next: None,
  154.    //             })),
  155.    //         })),
  156.    //     })),
  157.    // };
  158.  
  159.    // for elem in list.iter() {
  160.    //     println!("{}", elem);
  161.    // }
  162.  
  163.    // FromIter:
  164.    let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9].iter().copied().collect();
  165.  
  166.    println!("{}\n", list);
  167.  
  168.    // Iter:
  169.    for elem in list.iter().step_by(2).take(3).map(|&v| v * v * v) {
  170.        println!("{}", elem);
  171.    }
  172.  
  173.    // IterMut:
  174.    for elem in list.iter_mut() {
  175.        *elem *= 5;
  176.    }
  177.  
  178.    println!();
  179.    // IntoIter:
  180.    for elem in list {
  181.        println!("{}", elem);
  182.    }
  183. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement