Skip to content

Instantly share code, notes, and snippets.

@reu
Created March 24, 2022 12:25
Show Gist options
  • Save reu/e2c63db31c7494aa39a534b3264d7065 to your computer and use it in GitHub Desktop.
Save reu/e2c63db31c7494aa39a534b3264d7065 to your computer and use it in GitHub Desktop.
Bad Rust linked cons list
use std::mem;
#[derive(Debug, PartialEq)]
pub enum List<T> {
Empty,
Cons(T, Box<List<T>>),
}
impl<T> List<T> {
pub fn new() -> Self {
List::Empty
}
pub fn push(&mut self, item: T) {
let current = mem::replace(&mut *self, List::Empty);
*self = List::Cons(item, Box::new(current));
}
pub fn pop(&mut self) -> Option<T> {
match mem::replace(&mut *self, List::Empty) {
List::Empty => None,
List::Cons(elem, rest) => {
*self = *rest;
Some(elem)
}
}
}
pub fn iter(&self) -> Iter<T> {
Iter(self)
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut(Some(self))
}
}
impl<T: PartialEq> List<T> {
pub fn contains(&self, item: &T) -> bool {
match self {
List::Cons(i, rest) => i == item || rest.contains(item),
List::Empty => false,
}
}
}
impl<T> FromIterator<T> for List<T> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
iter.into_iter()
.fold(List::Empty, |list, item| List::Cons(item, Box::new(list)))
}
}
impl<T> IntoIterator for List<T> {
type Item = T;
type IntoIter = ListIterator<T>;
fn into_iter(self) -> Self::IntoIter {
ListIterator(self)
}
}
pub struct ListIterator<T>(List<T>);
impl<T> Iterator for ListIterator<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.pop()
}
}
pub struct Iter<'a, T>(&'a List<T>);
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
match self.0 {
List::Empty => None,
List::Cons(item, list) => {
self.0 = list;
Some(item)
}
}
}
}
pub struct IterMut<'a, T>(Option<&'a mut List<T>>);
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().and_then(|list| match list {
List::Empty => None,
List::Cons(item, list) => {
self.0 = Some(list);
Some(item)
}
})
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn push() {
let mut list1 = List::new();
list1.push(10);
list1.push(20);
assert_eq!(list1, List::from_iter([10, 20]));
}
#[test]
fn pop() {
let mut list: List<u8> = List::new();
assert_eq!(list.pop(), None);
let mut list = List::new();
list.push(10);
list.push(20);
assert_eq!(list.pop(), Some(20));
assert_eq!(list.pop(), Some(10));
assert_eq!(list.pop(), None);
list.push(30);
assert_eq!(list.pop(), Some(30));
assert_eq!(list.pop(), None);
}
#[test]
fn contains() {
let list = List::from_iter([10, 20]);
assert!(list.contains(&10));
assert!(list.contains(&20));
assert!(!list.contains(&30));
}
#[test]
fn into_iter() {
let list = List::from_iter([10, 20, 30]);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(30));
assert_eq!(iter.next(), Some(20));
assert_eq!(iter.next(), Some(10));
assert_eq!(iter.next(), None);
}
#[test]
fn iter() {
let list = List::from_iter([10, 20, 30]);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&30));
assert_eq!(iter.next(), Some(&20));
assert_eq!(iter.next(), Some(&10));
assert_eq!(iter.next(), None);
}
#[test]
fn iter_mut() {
let mut list = List::from_iter([10, 20, 30]);
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 30));
assert_eq!(iter.next(), Some(&mut 20));
assert_eq!(iter.next(), Some(&mut 10));
assert_eq!(iter.next(), None);
let mut list = List::from_iter([10]);
let mut iter = list.iter_mut();
*iter.next().unwrap() = 20;
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 20));
assert_eq!(iter.next(), None);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment