退屈な組み合わせ論

さて、通常進行の linked list に戻りましょう！

まずは、pop があれば些細な Drop を片付けましょう。

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        // 停止するまで pop する
        while let Some(_) = self.pop_front() { }
    }
}

front、front_mut、back、back_mut、iter、iter_mut、into_iter、… といった、本当に退屈な組み合わせ的な実装をたくさん埋める必要があります。

マクロか何かでやってもいいですが、正直なところ、それはコピー＆ペーストより悪い運命です。ここでは大量のコピー＆ペーストをするだけにします。これまでの push/pop 実装は、front と back を文字通り入れ替えるだけでコードが正しく動き、正しいことを表すように、私は非常に注意深く作ってきました！ 苦い経験に万歳！ （ノードについて “prev and next” と言いたくなる誘惑は強いですが、ミスを避けるためには、できるだけ一貫して “front” と “back” と言い続けることに本当に価値があると私は思います。）

ではまず、front です。

pub fn front(&self) -> Option<&T> {
    unsafe {
        self.front.map(|node| &(*node.as_ptr()).elem)
    }
}

ところで実は、この本はかなり古く、その後 ? 演算子のような素敵な新機能がいくつか追加されました。これは Option::None で早期 return するものですが、これでコードはより良くなるでしょうか？

pub fn front(&self) -> Option<&T> {
    unsafe {
        Some(&(*self.front?.as_ptr()).elem)
    }
}

たぶん？ これくらい単純なものだとどちらとも言えませんし、前のセクションでは早期 return が私たちにとってちょっと不気味だという話を散々したので、ここではもう少し明示的な方を好むべきかもしれません（私は map の実装のままでいきます）。次は front_mut です。

pub fn front_mut(&mut self) -> Option<&mut T> {
    unsafe {
        self.front.map(|node| &mut (*node.as_ptr()).elem)
    }
}

back 版は最後にまとめて載せます。

次は iterator です。これまでのすべての list と違って、私たちはついに DoubleEndedIterator を使う能力を解禁しました。さらに本番品質を目指すなら ExactSizeIterator も実装します。

つまり、next と size_hint に加えて、next_back と len もサポートします。

注意深い読者は、IterMut が両端 iterator だとかなり怪しく見えることに気づくかもしれませんが、実際にはそれでも健全です！

… これは大量のボイラープレートになりそうです。やっぱりマクロを書くべきかも… いや、いや、それでもそっちの方が悪い運命です。

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> {
        // ここで self.front == self.back を条件としてチェックしたくなるが、
        // 最後の要素を yield するときに正しく動かない！ その手の
        // ことが配列でだけ機能するのは、"one-past-the-end" ポインタがあるから。
        if self.len > 0 {
            // front を unwrap することもできるが、こちらの方が安全で簡単
            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 を片付けましょう。ありがたいことに、コレクションをラップして next で 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
    }
}

まだ大量のボイラープレートですが、少なくとも満足感のあるボイラープレートです。

さて、組み合わせ的な部分をすべて埋めたコード全体がこちらです。

```rust
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: これは連結リストです、他にどうしろと？
        unsafe {
            let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node {
                front: None,
                back: None,
                elem,
            })));
            if let Some(old) = self.front {
                // 新しい front を古いものの前に置く
                (*old.as_ptr()).front = Some(new);
                (*new.as_ptr()).back = Some(old);
            } else {
                // front がない場合、このリストは空なので back も
                // 設定する必要がある。
                self.back = Some(new);
            }
            // これらは常に行われる！
            self.front = Some(new);
            self.len += 1;
        }
    }

    pub fn push_back(&mut self, elem: T) {
        // SAFETY: これは連結リストです、他にどうしろと？
        unsafe {
            let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node {
                back: None,
                front: None,
                elem,
            })));
            if let Some(old) = self.back {
                // 新しい back を古いものの前に置く
                (*old.as_ptr()).back = Some(new);
                (*new.as_ptr()).front = Some(old);
            } else {
                // back がない場合、このリストは空なので front も
                // 設定する必要がある。
                self.front = Some(new);
            }
            // これらは常に行われる！
            self.back = Some(new);
            self.len += 1;
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        unsafe {
            // pop する front ノードがある場合にだけ処理すればよい。
            self.front.map(|node| {
                // Box を蘇らせて、その値を取り出し、
                // それを Drop できるようにする（Box は引き続き魔法のようにこれを理解してくれる）。
                let boxed_node = Box::from_raw(node.as_ptr());
                let result = boxed_node.elem;

                // 次のノードを新しい front にする。
                self.front = boxed_node.back;
                if let Some(new) = self.front {
                    // 削除されたノードへの参照を掃除する
                    (*new.as_ptr()).front = None;
                } else {
                    // front が null になったなら、このリストは空になった！
                    self.back = None;
                }

                self.len -= 1;
                result
                // Box はここで暗黙に解放され、T が存在しないことを理解している。
            })
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        unsafe {
            // pop する back ノードがある場合にだけ処理すればよい。
            self.back.map(|node| {
                // Box の front を蘇らせて、その値を取り出し、
                // それを Drop できるようにする（Box は引き続き魔法のようにこれを理解してくれる）。
                let boxed_node = Box::from_raw(node.as_ptr());
                let result = boxed_node.elem;

                // 次のノードを新しい back にする。
                self.back = boxed_node.front;
                if let Some(new) = self.back {
                    // 削除されたノードへの参照を掃除する
                    (*new.as_ptr()).back = None;
                } else {
                    // back が null になったなら、このリストは空になった！
                    self.front = None;
                }

                self.len -= 1;
                result
                // Box はここで暗黙に解放され、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 する
        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> {
        // self.front == self.back はここで確認したくなる条件だが、
        // 最後の要素を yield するには正しく動作しない！ その種のことは
        // "one-past-the-end" ポインタがあるため配列でのみ機能する。
        if self.len > 0 {
            // front を unwrap することもできるが、こちらの方が安全で簡単
            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> {
        // self.front == self.back はここで確認したくなる条件だが、
        // 最後の要素を yield するには正しく動作しない！ その種のことは
        // "one-past-the-end" ポインタがあるため配列でのみ機能する。
        if self.len > 0 {
            // front を unwrap することもできるが、こちらの方が安全で簡単
            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();

        // 空のリストを壊してみる
        assert_eq!(list.len(), 0);
        assert_eq!(list.pop_front(), None);
        assert_eq!(list.len(), 0);

        // 1 要素のリストを壊してみる
        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);

        // いじくり回す
        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);
    }
}