　やっとremoveの実装にとりかかれた。

成果物

github
- 7/one_way_list

`remove`

インタフェース

　removeはリストの要素を削除するメソッド。インタフェースはいくつか考えられる。

    pub fn clear(&mut self) {}
    pub fn remove_head(&mut self) {}
    pub fn remove_tail(&mut self) {}
    pub fn remove_from_index(&mut self, index: u32) {}

    pub fn remove(&mut self, item: T) {} // 指定要素に一致するノードを検索する必要がある
    // 指定要素に一致するノードを検索する
    fn search(&self, item: T) -> Result<&Option<Box<Node<T>>>, &'static str> { Err("Not found") }

　単方向リストとしては、headかtailの一方向から1ノードだけ削除できればいい気がする。あるいは全部消すclear()のみ実装する。もしくは、別に削除なんていらない。今回は学習目的なので、色々実装してみたい。

　要素の追加においても以下のようなインタフェースが考えられる。これは別の機会に。

    pub fn push_head(&mut self, item: T) {}
    pub fn push_tail(&mut self, item: T) {}

    pub fn insert(&mut self, item: T, index: i32) {}

    pub fn concat(&mut self, list: Self) {}

`remove_head`

　先頭の要素を削除する。おそらく最も簡単。

    pub fn remove_head(&mut self) {
        match self.head {
            Some(ref mut node) => {
                let first = std::mem::replace(&mut self.head, None);
                let first = std::mem::replace(&mut self.head, first.unwrap().next);
            },
            _ => (),
        }
    }

　これをif let文で書くと以下。

    pub fn remove_head(&mut self) {
        if let Some(ref mut node) = self.head {
            let first = std::mem::replace(&mut self.head, None);
            let first = std::mem::replace(&mut self.head, first.unwrap().next);
        };
    }

コードを意味を考えてみる

　先頭ノードの削除とは、2番目のノードをheadにセットすることである。

　remove_headメソッドは2つのstd::mem::replace文で成り立っている。1つ目はself.headを取り出している。その後、使わない値Noneを代入している。これは所有権ムーブエラーを回避するために行っている。

　取り出された値は変数firstに代入している。所有権を奪っているため、このスコープが抜けたらdropするはず。

　2つ目はself.headにself.head.nextをセットしている。これで最初のノードとして2番目のノードが参照されるようになった。このとき、2番目のノードの所有権を1番目のノードのnextフィールドから奪い、OnewayList.headにセットしている。

　2つ目replaceの戻り値は、1つ目replaceでセットしたNoneである。また、2回目let first = ...として1回目のfirstがシャドーイングされている。これでもう最初のノードにはアクセスできなくなり、スコープを抜けてdropされるのを待つだけ。

　最後にスコープを抜けて最初のノードはdropされる。ついでにNoneも。削除完了。

テストコード

　ノードがないときにremoveしても、panic!しないことを確認する。

    #[test]
    fn OnewayList_remove_head_0() {
        let mut list: OnewayList<i32> = OnewayList::new();
        list.remove_head();
        assert_eq!(list.head, None);
    }

　ノードが1個あるときにremoveしたら、OnewayList.headがNoneになること。

    #[test]
    fn OnewayList_remove_head_1() {
        let mut list: OnewayList<i32> = OnewayList::new();
        list.push(0);
        assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None })));
        list.remove_head();
        assert_eq!(list.head, None);
    }

　ノードが2個あるときにremoveしたら、最初にセットしたノードが消えること。

    #[test]
    fn OnewayList_remove_head_2() {
        let mut list: OnewayList<i32> = OnewayList::new();
        list.push(0);
        list.push(1);
        assert_eq!(list.head, Some(Box::new(Node { item: 0, next: 
            Some(Box::new(Node { item: 1, next: None }))
        })));
        list.remove_head();
        assert_eq!(list.head, Some(Box::new(Node { item: 1, next: None })));
        list.remove_head();
        assert_eq!(list.head, None);
    }

　ノードが3個あるときに1回ずつremoveしていったら、最初にセットした順にノードが消えていくこと。

    #[test]
    fn OnewayList_remove_head_3() {
        let mut list: OnewayList<i32> = OnewayList::new();
        list.push(0);
        list.push(1);
        list.push(2);
        assert_eq!(list.head, Some(Box::new(Node { item: 0, next: 
            Some(Box::new(Node { item: 1, next: 
                Some(Box::new(Node { item: 2, next: None }))
            }))
        })));
        list.remove_head();
        assert_eq!(list.head, Some(Box::new(Node { item: 1, next: 
            Some(Box::new(Node { item: 2, next: None }))
        })));
        list.remove_head();
        assert_eq!(list.head, Some(Box::new(Node { item: 2, next: None })));
        list.remove_head();
        assert_eq!(list.head, None);
    }

　テストが通った。完璧！

　この調子でほかのメソッドも実装していきたい。

対象環境

2019-07-13
Raspbierry pi 3 Model B+
Raspbian stretch 9.0 2018-11-13
bash 4.4.12(1)-release
rustc 1.34.2 (6c2484dc3 2019-05-13)
cargo 1.34.0 (6789d8a0a 2019-04-01)

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1219 SMP Tue May 14 21:20:58 BST 2019 armv7l GNU/Linux

やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

Rust自習（単方向リスト5）

成果物