はじめに
rustでグラフアルゴリズムを実装しようと思いましたがふと、rustで単方向リストを実装してみようと思い、実装してみました。
また単体テストも書いてみることにより、rustの理解を深めていこうと思います。
（初心者で理解が浅いので、間違っている部分があればご指摘頂ければと思います）
単方向リストとは？
単方向リストとは、順序をもったデータを表すデータ構造であり、任意の位置へデータを挿入したり、削除を行ったりすることができます。
次の要素への参照をポインタとして持ち、ポインタで連結されるデータ構造です（要素が存在しない場合は、ポインタ＝NULL）。
特徴しては、
- 要素の挿入・削除が簡単（ポインタをつなぎ合わせるだけ）
- 要素の挿入・削除が$O(1)$で実行可能
- 但し、検索時間は$O(n)$
等があります。
詳しくは、wikipediaを参照してください。
環境
- MacBook Pro (Sierra 10.12.6 Retina)
- 2.3GHz IntelCore i7
- Memory 16GB
- NVIDIA GeForce GT 750M 2048MB Intel Iris Pro 1536MB
- rustc v.1.19.0
実装
nodeを構造体で表現し、その構造体に「挿入・検索処理」を実装していきます。
末尾へ要素を挿入する処理で、whileループで実装しようとするとビルドすら通らなかったのですが、
末尾再帰をループにできないRustプログラムの例を参考にさせて頂き、無事ビルドが通るようになりました（探索部分は自力で実装してみたつもりです）。
記事を読むとどうやら、「各ノードのライフタイムがネストしており、次のノードに進むと前のノードの生存期間が異なる為、同じ変数で管理できない。よって、ビルドエラー」となっているらしい。
正確に把握できていないので、間違っているかもしれません。このあたり再度確認し、理解を深めていきたいです。
以下、実装になります。
// 単方向リスト構造体.
struct List<T> {
root: Option<Box<Node<T>>>,
}
struct Node<T> {
value: T,
next: Option<Box<Node<T>>>,
}
impl <T: Eq> List<T> {
// 先頭へ要素を挿入.
fn push_front(&mut self, value: T) {
self.root = Some(Box::new(Node {
value: value,
next: ::std::mem::replace(&mut self.root, None), // 中身を取り出す(所有権問題を回避).
}));
}
// 最後に要素を挿入.
fn push_back(&mut self, value: T) {
// 最終要素探索関数.
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 _node = last_node(&mut self.root);
*_node = Some(Box::new(Node { value: value, next: None, }));
}
// 要素検索.
fn search(&self, value: T) -> Result<&Option<Box<Node<T>>>, &'static str> {
// 要素探索関数.
fn search_elem<'a, T: Eq>(node: &'a Option<Box<Node<T>>>, value: T) -> Result<&'a Option<Box<Node<T>>>, &'static str> {
if let Some(ref _n) = *node {
// 要素が等しいかチェック.
if _n.value == value {
return Ok(node);
}
else {
// 次の要素へ.
return search_elem(&_n.next, value);
}
}
else {
// ノードが存在しない.
return Err("Not found");
}
}
// 指定された要素を探索.
return search_elem(&self.root, value);
}
}
ユニットテスト
rustでは、ユニットテストを実装ファイル内にコーディングすることができます。
#testアトリビュートや#[cfg(test)]アトリビュートを使用する事によって、テストを実行するときのみビルドを実施するといったことができるようになります。
以下、今回の単方向リストのユニットテストコードです。
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn search_test() {
let mut node = List { root: None };
node.push_front(1);
node.push_front(2);
// 1要素目検索.
match node.search(1) {
Ok(i) => {
if let Some(ref e) = *i { assert_eq!(e.value, 1); }
else { assert!(false); }
},
Err(_) => assert!(false)
}
// 2要素目検索.
match node.search(2) {
Ok(i) => {
if let Some(ref e) = *i { assert_eq!(e.value, 2); }
else { assert!(false); }
},
Err(_) => assert!(false)
}
// 存在しない要素検索.
match node.search(3) {
Ok(_) => assert!(false),
Err(e) => assert_eq!("Not found", e)
}
}
#[test]
fn push_front_test() {
let mut node = List { root: None };
node.push_front(1);
assert_eq!(node.root.unwrap().value, 1);
}
#[test]
fn push_front_two_items_test() {
let mut node = List { root: None };
node.push_front(1);
node.push_front(2);
assert_eq!(node.root.unwrap().value, 2);
}
#[test]
fn push_back_test() {
let mut node = List { root: None };
node.push_back(1);
assert_eq!(node.root.unwrap().value, 1);
}
#[test]
fn push_back_two_test() {
let mut node = List { root: None };
node.push_back(1);
node.push_back(2);
assert_eq!(node.root.unwrap().next.unwrap().value, 2);
}
}
一つのテスト関数の中で、assert!を連続して実行すると、エラーが出てしまいます。
例えば、
#[test]
fn push_back_two_test() {
let mut node = List { root: None };
node.push_back(1);
node.push_back(2);
assert_eq!(node.root.unwrap().next.unwrap().value, 2);
assert_eq!(node.root.unwrap().value, 1); // ここで「move occurs because `node.root` has type `std::option::Option<std::boxed::Box<Node<i32>>>`, which does not implement the `Copy` trait」
}
ということなので、今後は「Copy trait」も実装してみたいと思います。
まとめ
ビルドエラーを解消するのにかなりの時間が掛かってしまい、やはり「ライフタイム、所有権と参照・借用の理解が出来ていない」と思いました（難しい。基本的なことが理解できていない。）
公式ドキュメントを再度、読み込もうかと思います。。。
ただ、テストに関しては言語自体に組み込まれており、また同じファイルに書けるのは実装とテストコードが離れていないのでメリットだなと感じました。
(C/C++で実装していた頃は、cppunitなどを使ってユニットテストを実施していたので、環境設定等など色々面倒でした)
Programming Rustでも予約しておこうかな。。。