最終コード
はい.これがRustで100%安全な双方向リストを実装するということです.悪夢のような体験でしたし, できたリストは実装の詳細を晒している上いくつか基礎的な機能をがありません.
でも,確かにここに存在します.
あ,それとRc
とRefCell
で大量の「不要な」ランタイムチェックを行っています.不要な
をカッコに入れたのは,実際には本当に安全であることを保証するために必要だからです.
実際いくつかのところでは必要でした.双方向リストはエイリアスと所有権がおそろしく
複雑に絡み合ったなにかでした!
でも私達はある程度やり遂げました.特に内部のデータ構造を晒すことを気にしないなら 上出来といえるでしょう.
ここからは,コインの裏側を見ていきたいと思います.不安全な実装によってあらゆるものの 制御を再び取り戻すのです.
# #![allow(unused_variables)] #fn main() { use std::rc::Rc; use std::cell::{Ref, RefMut, RefCell}; pub struct List<T> { head: Link<T>, tail: Link<T>, } type Link<T> = Option<Rc<RefCell<Node<T>>>>; struct Node<T> { elem: T, next: Link<T>, prev: Link<T>, } impl<T> Node<T> { fn new(elem: T) -> Rc<RefCell<Self>> { Rc::new(RefCell::new(Node { elem: elem, prev: None, next: None, })) } } impl<T> List<T> { pub fn new() -> Self { List { head: None, tail: None } } pub fn push_front(&mut self, elem: T) { let new_head = Node::new(elem); match self.head.take() { Some(old_head) => { old_head.borrow_mut().prev = Some(new_head.clone()); new_head.borrow_mut().next = Some(old_head); self.head = Some(new_head); } None => { self.tail = Some(new_head.clone()); self.head = Some(new_head); } } } pub fn push_back(&mut self, elem: T) { let new_tail = Node::new(elem); match self.tail.take() { Some(old_tail) => { old_tail.borrow_mut().next = Some(new_tail.clone()); new_tail.borrow_mut().prev = Some(old_tail); self.tail = Some(new_tail); } None => { self.head = Some(new_tail.clone()); self.tail = Some(new_tail); } } } pub fn pop_back(&mut self) -> Option<T> { self.tail.take().map(|old_tail| { match old_tail.borrow_mut().prev.take() { Some(new_tail) => { new_tail.borrow_mut().next.take(); self.tail = Some(new_tail); } None => { self.head.take(); } } Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem }) } pub fn pop_front(&mut self) -> Option<T> { self.head.take().map(|old_head| { match old_head.borrow_mut().next.take() { Some(new_head) => { new_head.borrow_mut().prev.take(); self.head = Some(new_head); } None => { self.tail.take(); } } Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem }) } pub fn peek_front(&self) -> Option<Ref<T>> { self.head.as_ref().map(|node| { Ref::map(node.borrow(), |node| &node.elem) }) } pub fn peek_back(&self) -> Option<Ref<T>> { self.tail.as_ref().map(|node| { Ref::map(node.borrow(), |node| &node.elem) }) } pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> { self.tail.as_ref().map(|node| { RefMut::map(node.borrow_mut(), |node| &mut node.elem) }) } pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> { self.head.as_ref().map(|node| { RefMut::map(node.borrow_mut(), |node| &mut node.elem) }) } pub fn into_iter(self) -> IntoIter<T> { IntoIter(self) } } impl<T> Drop for List<T> { fn drop(&mut self) { while self.pop_front().is_some() {} } } pub struct IntoIter<T>(List<T>); impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<T> { self.0.pop_front() } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<T> { self.0.pop_back() } } #[cfg(test)] mod test { use super::List; #[test] fn basics() { let mut list = List::new(); // 空のリストが動くことを確認 assert_eq!(list.pop_front(), None); // リストの要素をつめる list.push_front(1); list.push_front(2); list.push_front(3); // 普通に要素を削除してみる assert_eq!(list.pop_front(), Some(3)); assert_eq!(list.pop_front(), Some(2)); // 何も壊れてないことを確認するためにもう一回push list.push_front(4); list.push_front(5); // 普通に要素を削除してみる assert_eq!(list.pop_front(), Some(5)); assert_eq!(list.pop_front(), Some(4)); // リストを出し切ったとき assert_eq!(list.pop_front(), Some(1)); assert_eq!(list.pop_front(), None); // ---- 逆順 ----- // 空のリストが動くことを確認 assert_eq!(list.pop_back(), None); // リストの要素をつめる list.push_back(1); list.push_back(2); list.push_back(3); // 普通に要素を削除してみる assert_eq!(list.pop_back(), Some(3)); assert_eq!(list.pop_back(), Some(2)); // 何も壊れてないことを確認するためにもう一回push list.push_back(4); list.push_back(5); // 普通に要素を削除してみる assert_eq!(list.pop_back(), Some(5)); assert_eq!(list.pop_back(), Some(4)); // リストを出し切ったとき assert_eq!(list.pop_back(), Some(1)); assert_eq!(list.pop_back(), None); } #[test] fn peek() { let mut list = List::new(); assert!(list.peek_front().is_none()); assert!(list.peek_back().is_none()); assert!(list.peek_front_mut().is_none()); assert!(list.peek_back_mut().is_none()); list.push_front(1); list.push_front(2); list.push_front(3); assert_eq!(&*list.peek_front().unwrap(), &3); assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3); assert_eq!(&*list.peek_back().unwrap(), &1); assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1); } #[test] fn into_iter() { let mut list = List::new(); list.push_front(1); list.push_front(2); list.push_front(3); let mut iter = list.into_iter(); assert_eq!(iter.next(), Some(3)); assert_eq!(iter.next_back(), Some(1)); assert_eq!(iter.next(), Some(2)); assert_eq!(iter.next_back(), None); assert_eq!(iter.next(), None); } } #}