Savior

Primitive LinkedList that works with Iterators

Feb 22nd, 2020
620
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×