Boring Combinatorics
Ok, back to our regularly scheduled linked lists!
First let's knock out Drop which is trivial with pop:
impl<T> Drop for LinkedList<T> {
fn drop(&mut self) {
// Pop until we have to stop
while let Some(_) = self.pop_front() { }
}
}
We've got to fill in a bunch of really boring combinatoric implementations like front, front_mut, back, back_mut, iter, iter_mut, into_iter, ...
You could do them with macros or whatever but honestly, that's a worse fate than copy-pasting. We're just going to do a lot of copy-pasting. I have very carefully crafted the previous push/pop implementations so that we should be able to literally just swap front and back and the code does/says the right thing! Hooray for painful experience! (It's so tempting to talk about "prev and next" for nodes, but I find it's really worth it to just consistently talk about "front" and "back" as much as possible to avoid mistakes.)
Alright, first up, front:
pub fn front(&self) -> Option<&T> {
unsafe {
self.front.map(|node| &(*node.as_ptr()).elem)
}
}
Hey actually, this book is really old and some nice new things have been added like the ? operator which does an early return on Option::None, does that make our code nicer?
pub fn front(&self) -> Option<&T> {
unsafe {
Some(&(*self.front?.as_ptr()).elem)
}
}
Maybe? It's kind of a wash for something this simple, and the previous section was all about how early returns are kinda spooky for us, so maybe we should prefer being a bit more explicit here (I'm sticking to the map implementation). On to front_mut:
pub fn front_mut(&mut self) -> Option<&mut T> {
unsafe {
self.front.map(|node| &mut (*node.as_ptr()).elem)
}
}
I'll just dump all the back versions at the end.
Next up, iterators. Unlike all of our previous lists we've finally unlocked the ability to do DoubleEndedIterator, and if we're going for production quality we're gonna do ExactSizeIterator too.
So in addition to next and size_hint, we're going to support next_back and len.
The vigilant among you might notice that IterMut seems a lot more sketchy with double-ended iteration, but it's actually still sound!
... god this is gonna be a lot of boilerplate. Maybe I should really write a macro... no, no, that's still a worse fate.
pub struct Iter<'a, T> {
front: Link<T>,
back: Link<T>,
len: usize,
_boo: PhantomData<&'a T>,
}
impl<T> LinkedList<T> {
pub fn iter(&self) -> Iter<T> {
Iter {
front: self.front,
back: self.back,
len: self.len,
_boo: PhantomData,
}
}
}
impl<'a, T> IntoIterator for &'a LinkedList<T> {
type IntoIter = Iter<'a, T>;
type Item = &'a T;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
// While self.front == self.back is a tempting condition to check here,
// it won't do the right for yielding the last element! That sort of
// thing only works for arrays because of "one-past-the-end" pointers.
if self.len > 0 {
// We could unwrap front, but this is safer and easier
self.front.map(|node| unsafe {
self.len -= 1;
self.front = (*node.as_ptr()).back;
&(*node.as_ptr()).elem
})
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len, Some(self.len))
}
}
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.len > 0 {
self.back.map(|node| unsafe {
self.len -= 1;
self.back = (*node.as_ptr()).front;
&(*node.as_ptr()).elem
})
} else {
None
}
}
}
impl<'a, T> ExactSizeIterator for Iter<'a, T> {
fn len(&self) -> usize {
self.len
}
}
...that's just .iter()...
we'll paste IterMut at the end, it's literally the exact same code with mut in a lot of places, let's just knock out into_iter first. We can mercifully still lean on our tried-and-true solution of just making it wrap our collection and using pop for next:
pub struct IntoIter<T> {
list: LinkedList<T>,
}
impl<T> LinkedList<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter {
list: self
}
}
}
impl<T> IntoIterator for LinkedList<T> {
type IntoIter = IntoIter<T>;
type Item = T;
fn into_iter(self) -> Self::IntoIter {
self.into_iter()
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.list.pop_front()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.list.len, Some(self.list.len))
}
}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<Self::Item> {
self.list.pop_back()
}
}
impl<T> ExactSizeIterator for IntoIter<T> {
fn len(&self) -> usize {
self.list.len
}
}
Still a crapload of boiler plate, but at least it's satisfying boilerplate.
Alright, here's all of our code with all the combinatorics filled in:
#![allow(unused)] fn main() { use std::ptr::NonNull; use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<T>, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, } pub struct Iter<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a T>, } pub struct IterMut<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a mut T>, } pub struct IntoIter<T> { list: LinkedList<T>, } impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } pub fn push_front(&mut self, elem: T) { // SAFETY: it's a linked-list, what do you want? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Put the new front before the old one (*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old); } else { // If there's no front, then we're the empty list and need // to set the back too. self.back = Some(new); } // These things always happen! self.front = Some(new); self.len += 1; } } pub fn push_back(&mut self, elem: T) { // SAFETY: it's a linked-list, what do you want? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { back: None, front: None, elem, }))); if let Some(old) = self.back { // Put the new back before the old one (*old.as_ptr()).back = Some(new); (*new.as_ptr()).front = Some(old); } else { // If there's no back, then we're the empty list and need // to set the front too. self.front = Some(new); } // These things always happen! self.back = Some(new); self.len += 1; } } pub fn pop_front(&mut self) -> Option<T> { unsafe { // Only have to do stuff if there is a front node to pop. self.front.map(|node| { // Bring the Box back to life so we can move out its value and // Drop it (Box continues to magically understand this for us). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Make the next node into the new front. self.front = boxed_node.back; if let Some(new) = self.front { // Cleanup its reference to the removed node (*new.as_ptr()).front = None; } else { // If the front is now null, then this list is now empty! self.back = None; } self.len -= 1; result // Box gets implicitly freed here, knows there is no T. }) } } pub fn pop_back(&mut self) -> Option<T> { unsafe { // Only have to do stuff if there is a back node to pop. self.back.map(|node| { // Bring the Box front to life so we can move out its value and // Drop it (Box continues to magically understand this for us). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Make the next node into the new back. self.back = boxed_node.front; if let Some(new) = self.back { // Cleanup its reference to the removed node (*new.as_ptr()).back = None; } else { // If the back is now null, then this list is now empty! self.front = None; } self.len -= 1; result // Box gets implicitly freed here, knows there is no T. }) } } pub fn front(&self) -> Option<&T> { unsafe { self.front.map(|node| &(*node.as_ptr()).elem) } } pub fn front_mut(&mut self) -> Option<&mut T> { unsafe { self.front.map(|node| &mut (*node.as_ptr()).elem) } } pub fn back(&self) -> Option<&T> { unsafe { self.back.map(|node| &(*node.as_ptr()).elem) } } pub fn back_mut(&mut self) -> Option<&mut T> { unsafe { self.back.map(|node| &mut (*node.as_ptr()).elem) } } pub fn len(&self) -> usize { self.len } pub fn iter(&self) -> Iter<T> { Iter { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn iter_mut(&mut self) -> IterMut<T> { IterMut { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn into_iter(self) -> IntoIter<T> { IntoIter { list: self } } } impl<T> Drop for LinkedList<T> { fn drop(&mut self) { // Pop until we have to stop while let Some(_) = self.pop_front() { } } } impl<'a, T> IntoIterator for &'a LinkedList<T> { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { // While self.front == self.back is a tempting condition to check here, // it won't do the right for yielding the last element! That sort of // thing only works for arrays because of "one-past-the-end" pointers. if self.len > 0 { // We could unwrap front, but this is safer and easier self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &(*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &(*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for Iter<'a, T> { fn len(&self) -> usize { self.len } } impl<'a, T> IntoIterator for &'a mut LinkedList<T> { type IntoIter = IterMut<'a, T>; type Item = &'a mut T; fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { // While self.front == self.back is a tempting condition to check here, // it won't do the right for yielding the last element! That sort of // thing only works for arrays because of "one-past-the-end" pointers. if self.len > 0 { // We could unwrap front, but this is safer and easier self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &mut (*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &mut (*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for IterMut<'a, T> { fn len(&self) -> usize { self.len } } impl<T> IntoIterator for LinkedList<T> { type IntoIter = IntoIter<T>; type Item = T; fn into_iter(self) -> Self::IntoIter { self.into_iter() } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.list.pop_front() } fn size_hint(&self) -> (usize, Option<usize>) { (self.list.len, Some(self.list.len)) } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<Self::Item> { self.list.pop_back() } } impl<T> ExactSizeIterator for IntoIter<T> { fn len(&self) -> usize { self.list.len } } #[cfg(test)] mod test { use super::LinkedList; #[test] fn test_basic_front() { let mut list = LinkedList::new(); // Try to break an empty list assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Try to break a one item list list.push_front(10); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Mess around list.push_front(10); assert_eq!(list.len(), 1); list.push_front(20); assert_eq!(list.len(), 2); list.push_front(30); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(30)); assert_eq!(list.len(), 2); list.push_front(40); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(40)); assert_eq!(list.len(), 2); assert_eq!(list.pop_front(), Some(20)); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); } } }