Rust自習（単方向リスト3）
removeメソッドを実装したかった。それ以前の段階で精一杯。
成果物
removeメソッド
要素を削除したい。以下のようなコードになるだろう。
impl<T> Node<T> { // ... fn remove(&mut self) { // 末尾なら if self.next == None { self.prev.next = None } // 先頭なら else if self.next.prev == None { } else { self.next.prev.next = self.next; } } }
だが、prevフィールドなど実装していない。とりあえず前の要素を参照するものとして仮に表現した。
順に追ってみうよう。
要素を削除するときはnextの付け替えをする必要がある。このとき、削除対象が末尾か否かで処理が変わる。
たとえば以下のようなリストのとき。
Node0 Node1 Node2 +-+------+ +-+------+ +-+----+ |0|&Node1|->|1|&Node2|->|2|None| +-+------+ +-+------+ +-+----+
先頭を削除するなら以下。nextの付け替えは不要。
Delete!! Node0 Node1 Node2 +-+------+ +-+------+ +-+----+ |0|&Node1|->|1|&Node2|->|2|None| +-+------+ +-+------+ +-+----+ Node1 Node2 +-+------+ +-+----+ |1|&Node2|->|2|None| +-+------+ +-+----+
末尾を削除するなら以下。nextの付け替えが必要。selfの前の要素のnextをNoneにすべき。
Delete!! Node0 Node1 Node2 +-+------+ +-+------+ +-+----+ |0|&Node1|->|1|&Node2|->|2|None| +-+------+ +-+------+ +-+----+ Node0 Node1 +-+------+ +-+----+ |0|&Node1|->|1|None| +-+------+ +-+----+
先頭でも末尾でもないなら以下。nextの付け替えが必要。selfの前の要素のnextを、selfの後の要素にすべき。
Delete!! Node0 Node1 Node2 +-+------+ +-+------+ +-+----+ |0|&Node1|->|1|&Node2|->|2|None| +-+------+ +-+------+ +-+----+ Node0 Node2 +-+------+ +-+----+ |0|&Node2|->|2|None| +-+------+ +-+----+
課題
いずれにせよ、selfの前の要素を知る必要がある。ところが、Node構造体にはnextしかない。単方向リストなのだから。
では、一体どうやって前の要素を知れるのか。
最初の要素
nextがあるので最初の要素さえ知っていれば全要素を辿れる。逆にいえば、next以外ないので、前の要素を知るには最初の要素からnextを辿っていくしかない。
そこで、最初の要素を記憶する構造体を作る。満を持してOnewayList構造体の登場。
struct OnewayList<T> { head: Option<Box<Node<T>>>, }
OnewayListはNodeの親になる。NodeのインタフェースもほぼOnewayListに移動する。そしてアルゴリズムも大きく変わる。
struct Node<T> { item: T, next: Option<Box<Node<T>>>, } impl<T> Node<T> { fn new(item: T) -> Self { Self { item: item, next: None } } } impl<T> OnewayList<T> { fn new() -> Self { Self { head: None } } fn push(&mut self, item: T) { if self.head.is_none() { self.head = Some(Box::new(Node::new(item))); } else { // 1. 最後の要素を取得する // 2. 最後の要素の`next`に新要素へのポインタをセットする } } }
push
こいつの実装方法がさっぱりわからなかった。
新規生成
impl<T> OnewayList<T> { fn new() -> Self { Self { head: None } } fn push(&mut self, item: T) { if self.head.is_none() { self.head = Some(Box::new(Node::new(item))); } // ...
最初はheadに新しいNodeのポインタをセットする。
リストの呼出は以下。
let list: OnewayList<i32> = OnewayList::new()` list.push(0); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None })));
ここまではわかる。
2件目以降
ここからがわからない。大筋は以下で合っているはずだが、借用チェッカーに怒られまくる。
} else { // 1. 最後の要素を取得する // 2. 最後の要素の`next`に新要素へのポインタをセットする }
最後の要素を取得する
方法1。for。
impl<T> OnewayList<T> { fn push(&mut self, item: T) { // ... } else { // 1. 最後の要素を取得する let last = self.head.next; for node in last { if last.next.is_some() { last = last.next; } else { break; } }
方法2。while。
impl<T> OnewayList<T> { fn push(&mut self, item: T) { // ... } else { // 1. 最後の要素を取得する let last = self.head.as_mut().unwrap().next; while last.is_some() { last = last.as_mut().unwrap().next; }
問題は、ここで検索したlastのnextに新要素へのポインタをセットできないこと。
impl<T> OnewayList<T> { fn push(&mut self, item: T) { if self.head.is_none() { self.head = Some(Box::new(Node::new(item))); } else { // 1. 最後の要素を取得する let mut last = self.head.as_ref().unwrap().next.as_ref(); while last.is_some() { last = last.as_ref().unwrap().next.as_ref(); } // 2. 最後の要素の`next`に新要素へのポインタをセットする std::mem::replace(last.unwrap().next.as_mut(), Some(Box::new(Node::new(item)))); } }
error[E0308]: mismatched types
--> src/lib.rs:59:31
|
59 | std::mem::replace(last.unwrap().next.as_mut(), Some(Box::new(Node::new(item))));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^
| |
| expected &mut _, found enum `std::option::Option`
| help: consider mutably borrowing here: `&mut last.unwrap().next.as_mut()`
|
= note: expected type `&mut _`
found type `std::option::Option<&mut std::boxed::Box<Node<T>>>`
impl<T> OnewayList<T> { fn push(&mut self, item: T) { if self.head.is_none() { self.head = Some(Box::new(Node::new(item))); } else { // 1. 最後の要素を取得する let last = self.head.as_mut().unwrap().next; while last.is_some() { last = last.as_mut().unwrap().next; } // 2. 最後の要素の`next`に新要素へのポインタをセットする last.unwrap().next = Some(Box::new(Node::new(item))); } }
error[E0507]: cannot move out of borrowed content --> src/lib.rs:44:24 | 44 | let last = self.head.as_mut().unwrap().next; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | | | cannot move out of borrowed content | help: consider borrowing here: `&self.head.as_mut().unwrap().next`
どうすればいいか思いつかない。禁断のGoogle先生に委ねた。自力で解きたかったがギブアップ……。
impl<T> OnewayList<T> { fn new() -> Self { Self { head: None } } fn push(&mut self, item: T) { if self.head.is_none() { self.head = Some(Box::new(Node::new(item))); } else { // 1. 最後の要素を取得する fn last_node<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { if let Some(ref mut _n) = *node { last_node(&mut _n.next) } else { node } } let last = last_node(&mut self.head); // 2. 最後の要素の`next`に新要素へのポインタをセットする *last = Some(Box::new(Node::new(item))); } } }
キモはlast_node内部関数。let last = last_node(&mut self.head);で呼び出している。最初の要素を引数に渡して、最後の要素を戻り値として受け取る。
もし引数nodeの参照外しした値がSome(ref mut _n)なら、再帰実行する（last_node引数にnextを与えて）。もし引数nodeの参照外しした値がそれ以外（None）なら、そのまま返す。
初回はself.headがNoneである。よってelseを通る。self.headがそのまま返る。つまりself.head = Some(Box::new(Node::new(item)));となる。
2回目はself.headがSomeである。よってifを通る。再帰の引数にnextを渡す。この値はNoneである。よって再帰したらelseを通る。引数をそのまま返す。つまりself.head.next = Some(Box::new(Node::new(item)));となる。
あれ、1件目のnextに新たな要素へのポインタをセットしてないような？
でも、以下のテストは成功する。なぜ？
#[test] fn OnewayList_push_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 })) })) })) ); }
ちょっとわからん。次回、ゆっくり解いてみる。
対象環境
- 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
