Created
January 7, 2021 21:18
-
-
Save richard-gibson/b21016acef37bf9ddcaf75f80d3a0f49 to your computer and use it in GitHub Desktop.
Persistent List in rust
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::{iter::FromIterator, rc::Rc}; | |
#[derive(Eq, PartialEq, Debug, Ord, PartialOrd, Clone)] | |
struct Node<T> { | |
elem: T, | |
next: Link<T>, | |
} | |
#[derive(Eq, PartialEq, Debug, Ord, PartialOrd, Clone)] | |
pub struct List<T> { | |
head: Link<T>, | |
} | |
type Link<T> = Option<Rc<Node<T>>>; | |
pub struct Iter<'a, T> { | |
next: Option<&'a Node<T>>, | |
} | |
impl<T> List<T> { | |
pub fn new() -> Self { | |
List { head: None } | |
} | |
pub fn append(&self, elem: T) -> Self { | |
List { | |
head: Some(Rc::new(Node { | |
elem: elem, | |
next: self.head.clone(), | |
})), | |
} | |
} | |
pub fn head(&self) -> Option<&T> { | |
self.head.as_ref().map(|node| &node.elem) | |
} | |
pub fn tail(&self) -> Self { | |
List { | |
head: self.head.as_ref().and_then(|node| node.next.clone()), | |
} | |
} | |
pub fn iter(&self) -> Iter<'_, T> { | |
Iter { | |
next: self.head.as_ref().map(|node| &**node), | |
} | |
} | |
} | |
// allow Iterator functions for List Iter | |
impl<'a, T> Iterator for Iter<'a, T> { | |
type Item = &'a T; | |
fn next(&mut self) -> Option<Self::Item> { | |
self.next.map(|node| { | |
self.next = node.next.as_ref().map(|node| &**node); | |
&node.elem | |
}) | |
} | |
} | |
// Collect from Iterator to List | |
impl<T: Copy> FromIterator<T> for List<T> { | |
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { | |
// cheating, meh. | |
// Could make a DoubleEndedIterator TC instance and call iter.rev() instead | |
// but much slower than vec.reverse | |
let mut vec = Vec::new(); | |
iter.into_iter().for_each(|e| vec.push(e)); | |
vec.reverse(); | |
vec.iter().fold(List::new(), |acc, elem| acc.append(*elem)) | |
} | |
} | |
//Destructor | |
impl<T> Drop for List<T> { | |
fn drop(&mut self) { | |
let mut link = self.head.take(); | |
while let Some(rc_node) = link { | |
if let Ok(mut node) = Rc::try_unwrap(rc_node) { | |
link = node.next.take(); | |
} else { | |
break; | |
} | |
} | |
} | |
} | |
#[cfg(test)] | |
mod test { | |
use super::List; | |
#[test] | |
fn append_tail() { | |
let empty_list = List::new(); | |
assert_eq!(empty_list.head(), None); | |
let list = empty_list.append(1).append(2).append(3); | |
assert_eq!(list.head(), Some(&3)); | |
assert_eq!(list.tail().head(), Some(&2)); | |
assert_eq!(list.tail().tail().head(), Some(&1)); | |
assert_eq!(list.tail().tail().tail().head(), None); | |
assert_eq!(list.tail().tail().tail().tail().head(), None); | |
} | |
#[test] | |
fn rc_tail() { | |
let list = List::new().append(1).append(2); | |
assert_eq!(list.append(0).tail(), list.append(9).tail()); | |
} | |
#[test] | |
fn iter() { | |
let list = List::new().append(1).append(2).append(3); | |
let mut iter = list.iter(); | |
assert_eq!(iter.next(), Some(&3)); | |
assert_eq!(iter.next(), Some(&2)); | |
assert_eq!(iter.next(), Some(&1)); | |
assert_eq!(iter.next(), None); | |
} | |
#[test] | |
fn map() { | |
let list = List::new().append(1).append(2).append(3); | |
let list_inc = List::new().append(2).append(3).append(4); | |
assert_eq!(list.iter().map(|i| i + 1).collect::<List<_>>(), list_inc); | |
} | |
#[test] | |
fn find() { | |
let list = List::new().append(1).append(2).append(3); | |
assert_eq!( | |
list.iter().find(|i| *i == &2), | |
Some(&2) | |
); | |
} | |
#[test] | |
fn fold() { | |
let list = List::new().append(1).append(2).append(3); | |
assert_eq!(list.iter().fold(0, |acc, elem| acc + elem), 6) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Could have used the enum below but head can end up on the stack rather than heap | |
pub enum List<T> { | |
Nil, | |
Cons(T, Rc<List<T>>) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment