Skip to content

Instantly share code, notes, and snippets.

@zaki-joho

zaki-joho/single.rs

Created Jun 20, 2020
Embed
What would you like to do?
single linked list
struct Node<T> {
elem: T,
next: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct List<T> {
head: Link<T>,
size: u32,
}
struct IntoIter<T>(List<T>);
struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<T> List<T> {
fn new() -> Self {
List {
head: None,
size: 0,
}
}
fn push(&mut self, elem: T) {
self.size += 1;
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
fn pop(&mut self) -> Option<T> {
match self.head.take() {
None => None,
Some(node) => {
self.size -= 1;
self.head = node.next;
Some(node.elem)
}
}
}
fn top(&self) -> Option<&T> {
match &self.head {
None => None,
Some(node) => Some(&node.elem),
}
}
fn top_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| &mut node.elem)
}
fn is_empty(&self) -> bool {
match &self.head {
None => true,
Some(_) => false,
}
}
fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter {
next: self.head.as_ref().map(|node| &**node),
}
}
fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
IterMut {
next: self.head.as_mut().map(|node| &mut **node),
}
}
fn len(&self) -> u32 {
self.size
}
fn clear(&mut self) {
self.size = 0;
self.head = None;
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.pop()
}
}
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
})
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_mut().map(|node| &mut **node);
&mut node.elem
})
}
}
fn make_list(x: u32) -> List<i32> {
let mut list = List::new();
for i in 1..x + 1 {
list.push(i as i32);
}
list
}
#[test]
fn top() {
let list = make_list(3);
assert_eq!(list.top(), Some(&3));
}
#[test]
fn top_mut() {
let mut list = make_list(3);
assert_eq!(list.top(), Some(&3));
let x = list.top_mut();
match x {
None => {}
Some(n) => *n += 1,
}
assert_eq!(list.top(), Some(&4));
}
#[test]
fn is_empty() {
let mut list = List::new();
assert_eq!(list.is_empty(), true);
list.push(1);
assert_eq!(list.is_empty(), false);
}
#[test]
fn into_iter() {
let list = make_list(3);
let mut iter = list.into_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 iter() {
let list = make_list(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
}
#[test]
fn iter_mut() {
let mut list = make_list(3);
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 3));
assert_eq!(iter.next(), Some(&mut 2));
assert_eq!(iter.next(), Some(&mut 1));
}
#[test]
fn len() {
let mut list = make_list(3);
assert_eq!(list.len(), 3);
list.pop();
assert_eq!(list.len(), 2);
}
#[test]
fn clear() {
let mut list = make_list(3);
assert_eq!(list.len(), 3);
list.clear();
assert_eq!(list.len(), 0);
}
@zaki-joho

This comment has been minimized.

Copy link
Owner Author

@zaki-joho zaki-joho commented Oct 29, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment