From 727dd03e5e9d2fd62d00fab36c7d277a75849f9b Mon Sep 17 00:00:00 2001
From: Federico Igne <git@federicoigne.com>
Date: Thu, 24 Dec 2020 11:17:02 +0000
Subject: [rust] Simple Linked List

---
 simple-linked-list/src/lib.rs | 109 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 109 insertions(+)
 create mode 100644 simple-linked-list/src/lib.rs

(limited to 'simple-linked-list/src/lib.rs')

diff --git a/simple-linked-list/src/lib.rs b/simple-linked-list/src/lib.rs
new file mode 100644
index 0000000..75e82f5
--- /dev/null
+++ b/simple-linked-list/src/lib.rs
@@ -0,0 +1,109 @@
+use std::iter::FromIterator;
+
+#[derive(Debug)]
+struct Node<T> {
+    data: T,
+    next: Option<Box<Node<T>>>,
+}
+
+impl<T> Node<T> {
+    pub fn new(data: T, next: Option<Box<Node<T>>>) -> Self {
+        Node { data, next }
+    }
+
+    pub fn len(&self) -> usize {
+        1 + self.next.as_ref().map(|n| n.len()).unwrap_or(0)
+    }
+}
+
+#[derive(Debug)]
+pub struct SimpleLinkedList<T> {
+    head: Option<Box<Node<T>>>,
+}
+
+impl<T> SimpleLinkedList<T> {
+    pub fn new() -> Self {
+        SimpleLinkedList { head: None }
+    }
+
+    // You may be wondering why it's necessary to have is_empty()
+    // when it can easily be determined from len().
+    // It's good custom to have both because len() can be expensive for some types,
+    // whereas is_empty() is almost always cheap.
+    // (Also ask yourself whether len() is expensive for SimpleLinkedList)
+    pub fn is_empty(&self) -> bool {
+        self.head.is_none()
+    }
+
+    pub fn len(&self) -> usize {
+        self.head.as_ref().map(|n| n.len()).unwrap_or(0)
+    }
+
+    pub fn push(&mut self, _element: T) {
+        // let node = Box::new(Node::new(_element, self.head.take()));
+        // self.head.replace(node);
+        self.head = Some(Box::new(Node::new(_element, self.head.take())));
+    }
+
+    pub fn pop(&mut self) -> Option<T> {
+        self.head.take().map(|n| {
+            // n.next.map(|n1| self.head.replace(n1));
+            self.head = n.next;
+            n.data
+        })
+    }
+
+    pub fn peek(&self) -> Option<&T> {
+        self.head.as_ref().map(|n| &n.data)
+    }
+
+    pub fn rev(self) -> SimpleLinkedList<T> {
+        self.rev_aux(SimpleLinkedList::new())
+    }
+
+    pub fn rev_aux(mut self, mut acc: SimpleLinkedList<T>) -> SimpleLinkedList<T> {
+        if let Some(e) = self.pop() {
+            acc.push(e);
+            self.rev_aux(acc)
+        } else {
+            acc
+        }
+    }
+
+    fn into_aux(mut self, mut acc: Vec<T>) -> Vec<T> {
+        if let Some(e) = self.pop() {
+            acc.push(e);
+            self.into_aux(acc)
+        } else {
+            acc
+        }
+    }
+}
+
+impl<T> FromIterator<T> for SimpleLinkedList<T> {
+    fn from_iter<I: IntoIterator<Item = T>>(_iter: I) -> Self {
+        _iter
+            .into_iter()
+            .fold(SimpleLinkedList::new(), |mut acc, n| {
+                acc.push(n);
+                acc
+            })
+    }
+}
+
+// In general, it would be preferable to implement IntoIterator for SimpleLinkedList<T>
+// instead of implementing an explicit conversion to a vector. This is because, together,
+// FromIterator and IntoIterator enable conversion between arbitrary collections.
+// Given that implementation, converting to a vector is trivial:
+//
+// let vec: Vec<_> = simple_linked_list.into_iter().collect();
+//
+// The reason this exercise's API includes an explicit conversion to Vec<T> instead
+// of IntoIterator is that implementing that interface is fairly complicated, and
+// demands more of the student than we expect at this point in the track.
+
+impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
+    fn into(self) -> Vec<T> {
+        self.rev().into_aux(Vec::new())
+    }
+}
-- 
cgit v1.2.3