Boring Combinatorics
Boring Combinatorics
好了，回到我们的常规链接列表！
首先，让我们来解决 Drop 的问题：
impl<T> Drop for LinkedList<T> {
fn drop(&mut self) {
// Pop until we have to stop
while let Some(_) = self.pop_front() { }
}
}我们必须填写一堆非常无聊的组合实现，如 front、front_mut、back、back_mut、iter、iter_mut、into_iter......
我已经精心设计了之前的 push/pop 实现，因此我们只需前后对调，代码就能做正确的事情！痛苦的经验万岁！(对于节点来说，使用 "prev和next "是很有诱惑力的，但我发现，为了避免错误，尽量使用 "front "和 "back"才是真正对的）。
首先是 front:
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)
}
}我会把所有的 back 版本放到文章最终的代码中。
接下来是迭代器。与之前的所有列表不同，我们终于解锁了双端迭代器（DoubleEndedIterator）的功能，而且如果要达到生产质量，我们还要支持精确大小迭代器（ ExactSizeIterator）。
因此，除了 next 和 size_hint，我们还将支持 next_back 和 len。
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
}
}...这只是 .iter()...
我们将在最后粘贴 IterMut，它在很多地方与 mut 的代码完全相同，让我们先敲掉 into_iter。我们仍然可以使用我们屡试不爽的解决方案，即让它包裹我们的集合，并在下一步中使用 pop：
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
}
}仍然是一大堆模板，但至少是令人满意的模板。
好了，这是我们所有的代码，其中包含了所有的组合：
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);
}
}链接到当前文件 1