やっとremove
の実装にとりかかれた。
成果物
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); }
テストが通った。完璧!
この調子でほかのメソッドも実装していきたい。
対象環境
- 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