push_from_indexメソッドを実装する。
成果物
インタフェース
そもそもpush_from_indexメソッドのインタフェースを用意し忘れていた。
pub fn push_from_index(&mut self, item: T, index: u32) {}
実装
まずは指定インデックスのポインタを返す内部メソッドを実装する。
ここで苦労した。NoneなLinkedList.headやNode.nextも含めているのがポイント。ただしNodeインスタンスが存在しないインデックスならパニックする。
fn search_from_index_ptr(&mut self, index: u32) -> &mut Option<Box<Node<T>>> { fn node_of_index<T>(node: &mut Option<Box<Node<T>>>, index: u32, count: u32) -> &mut Option<Box<Node<T>>> { if index == count { node } else { if let None = node { panic!("Out of index. index値が大きすぎます。index: {}, 許容範囲: 0...{}", index, count) } else { node_of_index(&mut node.as_mut().unwrap().next, index, count+1) } } } node_of_index(&mut self.head, index, 0) }
指定インデックスのポインタが帰ってきたら、あとは今までどおりインスタンスの入替。
pub fn push_from_index(&mut self, item: T, index: u32) { let index_ptr = self.search_from_index_ptr(index); let mut new_node = Some(Box::new(Node::new(item))); let old_idx_node = std::mem::replace(index_ptr, None); std::mem::replace(&mut new_node.as_mut().unwrap().next, old_idx_node); std::mem::replace(index_ptr, new_node); }
テスト
インデックス値が超過していたらパニックするか。
#[test] #[should_panic] fn LikedList_push_from_index_out_of_index() { let mut list: LinkedList<i32> = LinkedList::new(); list.push_from_index(0, 1); }
先頭に追加できるか。
#[test] fn LikedList_push_from_index_3_head() { let mut list: LinkedList<i32> = LinkedList::new(); list.push_from_index(0, 0); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None, prev: None }))); list.push_from_index(1, 0); assert_eq!(list.head, Some(Box::new(Node { item: 1, next: Some(Box::new(Node { item: 0, next: None, prev: None })) , prev: None })) ); list.push_from_index(2, 0); assert_eq!(list.head, Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 1, next: Some(Box::new(Node { item:0, next: None, prev: None })) , prev: None })) , prev: None })) ); }
末尾に追加できるか。
#[test] fn LikedList_push_from_index_3_tail() { let mut list: LinkedList<i32> = LinkedList::new(); list.push_from_index(0, 0); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None, prev: None }))); list.push_from_index(1, 1); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: None, prev: None })) , prev: None })) ); list.push_from_index(2, 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, prev: None })) , prev: None })) , prev: None })) ); }
中間に追加できるか。今回のキモであり、これこそがpush_from_indexメソッドの真髄。
#[test] fn LikedList_push_from_index_4_middle() { let mut list: LinkedList<i32> = LinkedList::new(); list.push_from_index(0, 0); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None, prev: None }))); list.push_from_index(1, 1); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: None, prev: None })) , prev: None })) ); list.push_from_index(2, 1); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item:1, next: None, prev: None })) , prev: None })) , prev: None })) ); list.push_from_index(3, 0); assert_eq!(list.head, Some(Box::new(Node { item: 3, next: Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 1, next: None, prev: None })) , prev: None })) , prev: None })) , prev: None })) ); }
課題
- インデックスに負数を受け付けるようにする（
-1なら末尾など）
こういう細かい点はべつにいいか。それよりremove_from_itemとかnextのほうが優先すべき。でもネタとして記録しておく。
所感
作っておいて何だが、私ならこんなメソッド使いたくない。実行するたび位置を検索するとかクソすぎる。別リストとしてOrderedListを作り、内部でインデックスを保持したほうが効率よく処理できそう。
でも、今回はRustの学習が目的。実用性は最初から考えてない。だからこれでいい。むしろOrderedListという新たなリストを作れるキッカケになったよ、やったね。
あと、LinkedListは思いつくメソッド全部乗せしていくつもり。たとえ非効率であったとしても。学習のために。飽きるまで。目をつぶってでも書けるようになるまで。
対象環境
- 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
