今回は「片方向連結リスト (singly linked list)」を実装してみましょう。連結リストは基本的なデータ構造です。他のプログラミング言語、特にガベージコレクションがある言語では、とても簡単にプログラムを作ることができます。ところが、Rust には所有権や借用チェックがあるので、他の言語のように簡単ではありません。他の言語と同じように作ろうとすると、必ずといっていいほど借用チェッカーにひっかかるのではないでしょうか。
案の定、M.Hiroi も借用チェッカーの壁を越えられず途方に暮れていたのですが、Learning Rust With Entirely Too Many Linked Lists という参考文献を見つけたので、Rust における連結リストの基本的な作り方を勉強しているところです。作者様に感謝いたします。
Rust は再帰的なデータ構造の扱いが難しいようで、Rust の制約を回避するため、unsafe な処理が必要になることもあるようです。まあ、必要なものはたいてい標準ライブラリに揃っているので、それらを使えばよいのですが、連結リストのような基本的なデータ構造を素直にプログラムできないのは、M.Hiroi の好みとはちょっと違うなあ、と思っています。リストの操作は Lisp / Scheme や関数型言語のほうが簡単ですね。
今回は上記文献を参考にして、連結リストを使ってスタックを実装してみましょう。プログラムは次のようになります。
リスト : 連結リストによるスタックの実装 (list1.rs)
// ノードの定義
enum Node<T> {
Nil,
Cons(T, Box<Node<T>>)
}
use Node::*;
// スタックの定義
struct Stack<T> {
head: Node<T>
}
// メソッド
impl<T> Stack<T> {
// スタックの生成
fn new() -> Stack<T> {
Stack { head: Nil }
}
// データの追加
fn push(&mut self, x: T) {
let new_node = Cons(x, Box::new(std::mem::replace(&mut self.head, Nil)));
self.head = new_node;
//self.head = Cons(x, Box::new(self.head));
}
// データの取り出し
fn pop(&mut self) -> Option<T> {
match std::mem::replace(&mut self.head, Nil) {
Nil => None,
Cons(x, node) => {
let node = *node; // Box から移動
self.head = node;
Some(x)
}
}
}
// 先頭データの参照
fn peek(&self) -> Option<&T> {
match self.head {
Nil => None,
Cons(ref x, _) => Some(x)
}
}
// スタックは空か？
fn is_empty(&self) -> bool {
match self.head {
Nil => true,
_ => false
}
}
}
fn main() {
let mut a: Stack<i32> = Stack::new();
for i in 0 .. 8 {
a.push(i);
}
println!("{}", a.peek().unwrap());
while !a.is_empty() {
println!("{}", a.pop().unwrap());
}
}
7 7 6 5 4 3 2 1 0
プログラムのポイントはメソッド push() と pop() で Stack の head を書き換えるところです。たとえば、push() を次のようにプログラムするとコンパイルエラーになります。
リスト : 間違った push()
fn push(&mut self, x: T) {
self.head = Cons(x, Box::new(self.head));
}
$ rustc -O list1.rs
error[E0507]: cannot move out of `self.head` which is behind a mutable reference
--> list1.rs:25:38
|
25 | self.head = Cons(x, Box::new(self.head));
| ^^^^^^^^^ move occurs because `self.head` has type `Node<T>`,
which does not implement the `Copy` trait
error: aborting due to previous error
For more information about this error, try `rustc --explain E0507`.
self.head の値を書き換えるためには、push() の第 1 引数を &mut self にしなければいけないのですが、そうすると所有権を移動することができなくなってしまうのです。これを回避するためには、std::mem モジュールにある関数 replace() を使います。
fn replace<T>(dest: &mut T, src: T) -> T
replace() は dest の値を src に書き換えて、dest の元の値を返します。std::mem にはメモリを操作する特別な関数が定義されています。その中では unsafe な処理を行うことにより、Rust の制約を緩和しているようです。単純な連結リスト (スタック) を作るのに、このような処理が必要になるとは驚きました。
push() は Cons(x, Box::new(std::mem::replace(&mut self.head, Nil))) で新しいコンスセルを作ります。replace() により self.head の値がコンスセルの Box に移され、self.head の値は Nil に書き換えられます。あとは新しいセルを self.head にセットするだけです。
pop() は replace() で self.head を Nil に書き換えて、その返り値を match でパターンマッチします。Nil であれば None を返します。そうでなければ、Cons(x, node) とマッチングします。コンスセルは Box に格納されているので、let node = *node; で Box から取り出します。あとは self.head の値を Box から取り出した node に書き換え、値 x を Some に包んで返すだけです。
ところで、Option には replace() と同様のメソッド take() があるので、Option を使って連結リスト (スタック) を作ることも可能です。次のリストを見てください。
リスト : 連結リストによるスタックの実装 (Option 版)
// ノードの定義
struct Node<T> {
car: T,
cdr: Option<Box<Node<T>>>
}
// スタックの定義
struct Stack<T> {
head: Option<Box<Node<T>>>
}
構造体 Node がコンスセルを表します。フィールド car にデータを、cdr に次のコンスセルを格納します。car と cdr は Lisp から拝借しました。cdr のデータ型は Option<Box<Node<T>>> で、終端を None で表します。末尾のコンスセルは cdr が None になります。Stack の head は連結リストを保持するので、cdr と同じデータ型になります。そして、head が None であれば空のスタックになります。
次はスタックのメソッドを定義します。
リスト : スタックのメソッド
impl<T> Stack<T> {
// スタックの生成
fn new() -> Stack<T> {
Stack { head: None }
}
// データの追加
fn push(&mut self, x: T) {
let new_node = Node { car: x, cdr: self.head.take() };
self.head = Some(Box::new(new_node));
}
// データの取り出し
fn pop(&mut self) -> Option<T> {
self.head.take().map(|xs| {
let xs = *xs;
self.head = xs.cdr;
xs.car
})
}
// 先頭データの参照
fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|xs| {
&xs.car
})
}
// スタックは空か？
fn is_empty(&self) -> bool {
self.head.is_none()
}
}
fn main() {
let mut a: Stack<i32> = Stack::new();
for i in 0 .. 8 {
a.push(i);
}
println!("{}", a.peek().unwrap());
while !a.is_empty() {
println!("{}", a.pop().unwrap());
}
}
push() は新しいリスト new_node を生成するとき、self.head.take() で cdr に self.head の値をセットします。このとき、self.head の値は None に書き換えられます。あとは、new_node を Box に包み、さらに Some に包んで self.head にセットするだけです。
pop() は self.head.take() で self.head の値 (Option 型) を取り出し、それを map() に渡して処理します。ラムダの引数 xs は Box 型なので、let xs = *xs; でリストを Box から取り出します。あとは、self.head に xs.cdr をセットして xs.car を返すだけです。
peek() は as_ref() と map() を使うと簡単です。as_ref() で Option<T> を Option<&T> に変換してから map() に渡します。ラムダの引数 xs は Box の参照になりますが、自動的にデリファレンスが行われるので、&xs.car で値の参照を返すことができます。
実行結果は同じなので省略します。
次は n 番目の要素の参照 (immutable と mutable) を返すメソッド get() と get_mut() を作りましょう。プログラムは最初に作った基本的な連結リストの定義を使います。それから、構造体 Stack の名前を List に変更します。
get() は簡単に定義することができます。次のリストを見てください。
リスト : immutable な参照を返す
fn get(&self, n: usize) -> Option<&T> {
let mut i = 0;
let mut node = &self.head;
while i < n {
match *node {
Nil => break,
Cons(_, ref node1) => {
node = &node1; // &**node1 のこと (自動デリファレンスされる)
i += 1;
}
}
}
match *node {
Nil => None,
Cons(ref x, _) => Some(x)
}
}
コンスセルを順番にたどるだけなので、とくに難しいところはないと思います。ところが、get_mut() の場合、次のように get() と同じようにプログラムすると借用チェックでコンパイルエラーになります。
リスト : mutable な参照を返す (コンパイルエラー版)
fn get_mut(&mut self, n: usize) -> Option<&mut T> {
let mut i = 0;
let mut node = &mut self.head;
while i < n {
match *node {
Nil => break,
Cons(_, ref mut node1) => {
node = &mut node1;
i += 1;
}
}
}
match *node {
Nil => None,
Cons(ref mut x, _) => Some(x)
}
}
Rust の場合、mutable な借用は一つしか作成することができません。node に node1 を代入するところで、同じデータを指す mutable な参照が 2 つできるので、コンパイルエラーになるようです。ここで、またしても M.Hiroi は途方に暮れたのですが、tkyk0317 さんの rustで単方向リスト＋単体テスト を参考にして解決することができました。tkyk0317 さんに感謝いたします。
具体的には、次のように局所関数 iter() を再帰呼び出しで定義することで、mutable な参照でもコンスセルをたどることができました。
リスト : mutable な参照を返す
fn get_mut(&mut self, n: usize) -> Option<&mut T> {
fn iter<T>(i: usize, n: usize, node: &mut Node<T>) -> Option<&mut T> {
if i == n {
match *node {
Nil => None,
Cons(ref mut x, _) => Some(x)
}
} else {
match *node {
Nil => None,
Cons(_, ref mut node1) => iter(i + 1, n, node1)
}
}
}
iter(0, n, &mut self.head)
}
この方法だと、引数 node と変数 node1 が指し示すデータの参照 (mutable) が別々になるので、借用チェッカーに引っかかることなくコンパイルすることができます。
プログラムと簡単な実行例を示します。
リスト : 連結リストの実装
// ノード (コンスセル) の定義
enum Node<T> {
Nil,
Cons(T, Box<Node<T>>)
}
use Node::*;
// 連結リストの定義
struct List<T> {
head: Node<T>
}
// メソッドの定義
impl<T> List<T> {
// 連結リストの生成
fn new() -> List<T> {
List { head: Nil }
}
// データの追加
fn push(&mut self, x: T) {
let new_node = Cons(x, Box::new(std::mem::replace(&mut self.head, Nil)));
self.head = new_node;
//self.head = Cons(x, Box::new(self.head));
}
// データの取り出し
fn pop(&mut self) -> Option<T> {
match std::mem::replace(&mut self.head, Nil) {
Nil => None,
Cons(x, node) => {
let node = *node; // Box から移動
self.head = node;
Some(x)
}
}
}
// 先頭データの参照
fn peek(&self) -> Option<&T> {
match self.head {
Nil => None,
Cons(ref x, _) => Some(x)
}
}
// 連結リストは空か？
fn is_empty(&self) -> bool {
match self.head {
Nil => true,
_ => false
}
}
// n 番目の要素の参照 (immutable) を返す
fn get(&self, n: usize) -> Option<&T> {
let mut i = 0;
let mut node = &self.head;
while i < n {
match *node {
Nil => break,
Cons(_, ref node1) => {
node = &node1; // &**node1 のこと (自動デリファレンスされるlist1)
i += 1;
}
}
}
match *node {
Nil => None,
Cons(ref x, _) => Some(x)
}
}
// n 番目の要素の参照 (mutable) を返す
fn get_mut(&mut self, n: usize) -> Option<&mut T> {
fn iter<T>(i: usize, n: usize, node: &mut Node<T>) -> Option<&mut T> {
if i == n {
match *node {
Nil => None,
Cons(ref mut x, _) => Some(x)
}
} else {
match *node {
Nil => None,
Cons(_, ref mut node1) => iter(i + 1, n, node1)
}
}
}
iter(0, n, &mut self.head)
}
}
fn main() {
let mut a: List<i32> = List::new();
for i in 0 .. 8 {
a.push(i);
}
println!("{}", a.peek().unwrap());
for i in 0 .. 9 {
println!("{:?}", a.get(i));
}
*a.get_mut(7).unwrap() += 10;
while !a.is_empty() {
println!("{}", a.pop().unwrap());
}
}
7 Some(7) Some(6) Some(5) Some(4) Some(3) Some(2) Some(1) Some(0) None 7 6 5 4 3 2 1 10
次は連結リストにイテレータを実装してみましょう。イテレータにはメソッド nth() があるので、get() や get_mut() を作らなくても要素の参照を取得することができます。ところが、mutable なイテレータの実装でつまづいてしまいました。ライフタイム関連でコンパイルエラーが発生し、それを解決することができませんでした。まだまだ修行が足りないようです。
そこで、Option を使った連結リストにイテレータを実装することにしました。このプログラムは参考文献 Learning Rust With Entirely Too Many Linked Lists とほとんど同じです。詳しい説明は参考文献をお読みいただくとして、ここでは概要を簡単に説明することにします。
プログラムは次のようになります。
リスト : イテレータの実装
// ノードの定義
struct Node<T> {
car: T,
cdr: Option<Box<Node<T>>>
}
// 連結リストの定義
struct List<T> {
head: Option<Box<Node<T>>>
}
// イテレータの定義
struct IterList<'a, T: 'a> {
next: Option<&'a Node<T>>
}
struct IterMutList<'a, T: 'a> {
next: Option<&'a mut Node<T>>
}
struct IterIntoList<T> {
head: List<T>
}
impl<'a, T> Iterator for IterList<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
self.next.map(|node| {
self.next = node.cdr.as_ref().map(|node| { &**node });
&node.car
})
}
}
impl<'a, T> Iterator for IterMutList<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<&'a mut T> {
self.next.take().map(|node| {
self.next = node.cdr.as_mut().map(|node| { &mut **node });
&mut node.car
})
}
}
impl<T> Iterator for IterIntoList<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.head.pop()
}
}
// メソッドの定義
impl<T> List<T> {
// リストの生成
fn new() -> List<T> {
List { head: None }
}
// データの追加
fn push(&mut self, x: T) {
let new_node = Node { car: x, cdr: self.head.take() };
self.head = Some(Box::new(new_node));
}
// データの取り出し
fn pop(&mut self) -> Option<T> {
self.head.take().map(|xs| {
let xs = *xs;
self.head = xs.cdr;
xs.car
})
}
// 先頭データへの参照
fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|xs| {
&xs.car
})
}
// リストは空か？
fn is_empty(&self) -> bool {
self.head.is_none()
}
// イテレータの生成
fn iter(&self) -> IterList<T> {
IterList { next: self.head.as_ref().map(|node| &**node )}
}
fn iter_mut(&mut self) -> IterMutList<T> {
IterMutList { next: self.head.as_mut().map(|node| &mut **node )}
}
fn into_iter(self) -> IterIntoList<T> {
IterIntoList { head: self }
}
}
// 簡単なテスト
fn main() {
let mut a: List<i32> = List::new();
for i in 0 .. 8 {
a.push(i);
}
println!("{}", a.peek().unwrap());
for x in a.iter() {
print!("{} ", x)
}
println!("");
for x in a.iter_mut() {
*x += 10;
}
println!("{}", a.iter().nth(7).unwrap());
*a.iter_mut().nth(7).unwrap() += 100;
println!("{}", a.iter().nth(7).unwrap());
while !a.is_empty() {
println!("{}", a.pop().unwrap());
}
for i in 0 .. 8 {
a.push(i)
}
let b: Vec<i32> = a.into_iter().collect();
println!("{:?}", b);
}
イテレータは次の 3 つのメソッドで生成します。
3 番目の into_iter() が一番簡単で、連結リスト self をイテレータの head に move し、あとは pop() を使って要素を順番に返していくだけです。immutable なイテレータは map() でノード node を取り出し、その cdr を as_ref() で Option の型を参照に変換し、map() で次のノードを取り出していきます。
mutable なイテレータも map() でノード (node) を取り出しますが、take() でイテレータのフィールド self.next を None に書き換えないと、借用チェッカーに引っかかるので注意してください。あとは、node.cdr を as_mut() で Option の型を mutable な参照に変換し、map() で次のセルを取りだします。
単純な連結リストのはずなのですが、Rust ではけっこう複雑な処理になりますね。もしかしたら、もっと簡単な方法があるのかもしれません。今後の課題にしたいと思います。それでは実行結果を示します。
7 7 6 5 4 3 2 1 0 10 110 17 16 15 14 13 12 11 110 [7, 6, 5, 4, 3, 2, 1, 0]
正常に動作していますね。
今回は Rust で「二分木 (binary tree)」を作ってみましょう。Rust のライブラリには B-tree という平衡木を使った BTreeMap, BTreeSet が用意されているので、わざわざ二分木を作る必要はないのですが、Rust のお勉強ということで単純な二分木を作ってみましょう。なお、二分木のアルゴリズムは拙作のページで詳しく説明しています。よろしければ参考にしてください。
まずは最初にデータ構造を定義しましょう。連結リストと同様に、列挙型で二分木の節を定義する方法と、Option 型を使う方法があります。次のリストを見てください。
リスト : 二分木の定義１ (列挙型を使う方法)
// 節の定義
enum Node<T: Ord> {
Nil,
Cons(T, Box<Node<T>>, Box<Node<T>>)
}
// 二分木
struct Tree<T: Ord> {
root: Node<T>
}
リスト : 二分木の定義２ (Option 型を使う方法)
// 節の定義
struct Node<T : Ord> {
item: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>
}
// 二分木
struct Tree<T: Ord> {
root: Option<Box<Node<T>>>
}
二分木の基本的な操作であるデータの挿入と探索はどちらの方法でも簡単にプログラムできます。ところが、データの削除が超絶に難しいのです。改訂前 (2017/09/10) のプログラムは、Binary Tree Implementation in Rust を参考にして、ようやく完成したのですが、現在のバージョン (Rust 1.62.1) ではコンパイルエラーになってしまいます。参考にしたプログラムもコンパイルエラーです。ここで M.Hiroi の心が折れてしまいました。
大変申し訳ありませんが、データの削除処理は今回の改定版では作成しないことにします。データの削除処理は今後の課題とさせていただきます。Rust 初心者 (M.Hiroi) にとって再帰的なデータ構造は鬼門ですね。Rust は本当に難しいプログラミング言語だと改めて痛感しました。
データの挿入は再帰定義を使えば簡単です。他の言語の場合、部分木を保持するフィールド変数に関数の返り値を代入する方法をよく使いますが、Rust ではデータを挿入する場所を探して、そこに新しい節を挿入する方法になります。次のリストを見てください。
リスト : データの挿入 (定義１)
impl<T: Ord> Node<T> {
// データの挿入
fn insert(&mut self, x: T) {
match *self {
Nil => *self = Cons(x, Box::new(Nil), Box::new(Nil)),
Cons(ref y, ref mut left, ref mut right) => {
if x < *y {
left.insert(x);
} else if x > *y {
right.insert(x)
}
}
}
}
}
// メソッドの定義
impl<T: Ord> Tree<T> {
// 二分木の生成
fn new() -> Tree<T> {
Tree { root: Nil }
}
// データの挿入
fn insert(&mut self, x: T) {
self.root.insert(x);
}
}
リスト : データの挿入 (定義２)
// 節のメソッド
impl<T: Ord> Node<T> {
// 節の生成
fn new(x: T) -> Node<T> {
Node { item: x, left: None, right: None }
}
// データの挿入
fn insert(&mut self, x: T) {
if x == self.item { return; }
let node = if x < self.item { &mut self.left } else { &mut self.right };
match node {
&mut Some(ref mut node1) => node1.insert(x),
&mut None => {
*node = Some(Box::new(Node::new(x)))
}
}
}
}
// 二分木のメソッド
impl<T: Ord> Tree<T> {
// 二分木の生成
fn new() -> Tree<T>{
Tree { root: None }
}
// データの挿入
fn insert(&mut self, x: T) {
if self.root.is_none() {
self.root = Some(Box::new(Node::new(x)));
} else {
self.root.as_mut().map(|node| node.insert(x));
}
}
}
どちらの方法でも Node のメソッド insert() でデータを挿入します。第 1 引数 &mut self の値が空の木 (Nil, None) の場合、そこに新しい節を挿入します。それ以外の場合は、値を比較して二分木の節をたどります。
次はデータを探索するメソッド contains(), min(), max() と二分木を巡回するメソッド foreach() を作ります。contains() はデータを比較して左右の部分木をたどります。min() は一番左側にある節のデータの参照を、max() が一番右側にある節のデータの参照を返します。それから、foreach() にはクロージャではなくトレイトオブジェクトを渡すことに注意してください。詳細はプログラムリストをお読みくださいませ。
リスト : データの探索と巡回 (定義１)
impl<T: Ord> Node<T> {
// データの探索
fn contains(&self, x: T) -> bool {
match *self {
Nil => false,
Cons(ref y, ref left, ref right) => {
if x == *y {
true
} else if x < *y {
left.contains(x)
} else {
right.contains(x)
}
}
}
}
// 最小値
fn min(&self) -> Option<&T> {
match *self {
Nil => None,
Cons(ref x, ref left, _) => {
match **left {
Nil => Some(x),
_ => left.min()
}
}
}
}
// 最大値
fn max(&self) -> Option<&T> {
match *self {
Nil => None,
Cons(ref x, _, ref right) => {
match **right {
Nil => Some(x),
_ => right.max()
}
}
}
}
// 巡回
fn foreach(&self, func: &dyn Fn(&T) -> ()) {
match *self {
Nil => (),
Cons(ref x, ref left, ref right) => {
left.foreach(func);
func(x);
right.foreach(func);
}
}
}
}
// 二分木のメソッド
impl<T: Ord> Tree<T> {
fn new() -> Tree<T> {
Tree { root: Nil }
}
fn contains(&self, x: T) -> bool {
self.root.contains(x)
}
fn min(&self) -> Option<&T> {
self.root.min()
}
fn max(&self) -> Option<&T> {
self.root.max()
}
fn foreach(&self, func: &dyn Fn(&T) -> ()) {
self.root.foreach(func);
}
fn is_empty(&self) -> bool {
match self.root {
Nil => true,
_ => false
}
}
}
リスト : 簡単なテスト
fn main() {
let mut a: Tree<i32> = Tree::new();
println!("{}", a.is_empty());
for x in vec![5, 3, 1, 4, 2, 7, 6, 8, 9] {
a.insert(x);
}
println!("{}", a.is_empty());
for x in 0 .. 11 {
println!("{}, {}", x, a.contains(x));
}
a.foreach(&|x| print!("{} ", x));
println!("");
println!("{:?}", a.min());
println!("{:?}", a.max());
}
true false 0, false 1, true 2, true 3, true 4, true 5, true 6, true 7, true 8, true 9, true 10, false 1 2 3 4 5 6 7 8 9 Some(1) Some(9)
リスト : データの探索と巡回 (定義２)
// 節のメソッド
impl<T: Ord> Node<T> {
// データの探索
fn contains(&self, x: T) -> bool {
if x == self.item { return true; }
let node = if x < self.item { &self.left } else { &self.right };
match node {
&Some(ref node1) => node1.contains(x),
&None => false
}
}
// 最小値
fn min(&self) -> &T {
match self.left {
None => &self.item,
Some(ref node) => node.min()
}
}
// 最大値
fn max(&self) -> &T {
match self.right {
None => &self.item,
Some(ref node) => node.max()
}
}
// 巡回
fn foreach(&self, func: &dyn Fn(&T) -> ()) {
self.left.as_ref().map(|node| node.foreach(func));
func(&self.item);
self.right.as_ref().map(|node| node.foreach(func));
}
}
impl<T: Ord> Tree<T> {
fn contains(&self, x: T) -> bool {
self.root.as_ref().map_or_else(|| false, |node| node.contains(x))
}
fn min(&self) -> Option<&T> {
self.root.as_ref().map(|node| node.min())
}
fn max(&self) -> Option<&T> {
self.root.as_ref().map(|node| node.max())
}
fn foreach(&self, func: &dyn Fn(&T) ->()) {
self.root.as_ref().map(|node| node.foreach(func));
}
fn is_empty(&self) -> bool {
self.root.is_none()
}
}
テストプログラムと結果は同じなので省略します。
次は二分木 Tree<T> にイテレータを実装しましょう。値を書き換えることを許すと、大小関係が崩れる場合があるので、mutable な参照を返す iter_mut() は実装しません。immutable な参照を返す iter() だけを実装します。次のリストを見てください。
リスト : イテレータの実装
struct IterTree<'a, T: 'a + Ord> {
next: Vec<&'a Node<T>>
}
fn next_node<'a, T: Ord>(node: &'a Node<T>, buff: &mut Vec<&'a Node<T>>) {
buff.push(node);
node.left.as_ref().map(|node| next_node(node, buff));
}
impl<'a, T: Ord> Iterator for IterTree<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
if self.next.len() == 0 {
None
} else {
let node = self.next.pop().unwrap();
node.right.as_ref().map(|node| {
next_node(node, &mut self.next);
});
&node.item
}
}
}
イテレータは Node のメソッド foreach() をループに展開することで実現することができます。この場合、自分でスタックを管理する必要があります。スタック (Vec 型) は IntoIterTree のフィールド変数 next に用意します。
考え方は簡単です。左部分木をたどるとき、その節をスタックに積んでいきます。左部分木が空の木であれば処理を終了します。このとき、スタックトップの節が、イテレータが指し示す節になります。この処理を関数 next_node() で行っています。
次の節に移動するとき、スタックから節を取り出して、その節の右部分木を同様にたどればいいわけです。右部分木が空の場合は、一つ前の節に戻ることになります。これをイテレータのメソッド next() で行います。
next() の処理は簡単です。スタック next が空の場合は None を返します。そうでなければ、pop() で節を取り出して変数 node にセットします。そして、右部分木をたどるため、node.right に as_ref() と map() を適用して節の参照を取り出し、それとスタックを next_node() に渡して実行します。あとは &node.item を返すだけです。
最後にイテレータを生成するメソッドを作ります。
リスト : イテレータの生成
impl<T: Ord> Tree<T> {
fn iter(&self) -> IterTree<T> {
let mut buff: Vec<&Node<T>> = vec![];
self.root.as_ref().map(|node| next_node(node, &mut buff));
IterTree { next: buff }
}
}
iter() はスタック buff を用意して、next_node() で一番左側の節 (先頭のデータ) までたどり、それを IntoTree の next にセットします。
プログラムはこれで完成です。それでは実行してみましょう。
リスト : 簡単なテスト
fn main() {
let mut a: Tree<i32> = Tree::new();
println!("{}", a.is_empty());
for x in vec![5, 3, 2, 4, 1, 7, 6, 8, 9] {
a.insert(x);
}
println!("{}", a.is_empty());
for x in 0 .. 11 {
println!("{}, {}", x, a.contains(x));
}
a.foreach(&|x| print!("{} ", x));
println!("");
for x in a.iter() {
print!("{}", x);
}
println!("");
println!("{:?}", a.min());
println!("{:?}", a.max());
}
true false 0, false 1, true 2, true 3, true 4, true 5, true 6, true 7, true 8, true 9, true 10, false 1 2 3 4 5 6 7 8 9 123456789 Some(1) Some(9)
正常に動作しているようです。興味のある方はいろいろ試してみてください。
//
// tree.rs : 単純な二分木
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// ノードの定義
enum Node<T: Ord> {
Nil,
Cons(T, Box<Node<T>>, Box<Node<T>>)
}
impl<T: Ord> Node<T> {
// データの探索
fn contains(&self, x: T) -> bool {
match *self {
Nil => false,
Cons(ref y, ref left, ref right) => {
if x == *y {
true
} else if x < *y {
left.contains(x)
} else {
right.contains(x)
}
}
}
}
// データの挿入
fn insert(&mut self, x: T) {
match *self {
Nil => *self = Cons(x, Box::new(Nil), Box::new(Nil)),
Cons(ref y, ref mut left, ref mut right) => {
if x < *y {
left.insert(x);
} else if x > *y {
right.insert(x)
}
}
}
}
// 最小値の探索
fn min(&self) -> Option<&T> {
match *self {
Nil => None,
Cons(ref x, ref left, _) => {
match **left {
Nil => Some(x),
_ => left.min()
}
}
}
}
// 最大値の探索
fn max(&self) -> Option<&T> {
match *self {
Nil => None,
Cons(ref x, _, ref right) => {
match **right {
Nil => Some(x),
_ => right.max()
}
}
}
}
// 巡回
fn foreach(&self, func: &dyn Fn(&T) -> ()) {
match *self {
Nil => (),
Cons(ref x, ref left, ref right) => {
left.foreach(func);
func(x);
right.foreach(func);
}
}
}
}
use Node::*;
// 二分木
struct Tree<T: Ord> {
root: Node<T>
}
// メソッドの定義
impl<T: Ord> Tree<T> {
fn new() -> Tree<T> {
Tree { root: Nil }
}
fn contains(&self, x: T) -> bool {
self.root.contains(x)
}
fn insert(&mut self, x: T) {
self.root.insert(x);
}
fn min(&self) -> Option<&T> {
self.root.min()
}
fn max(&self) -> Option<&T> {
self.root.max()
}
fn foreach(&self, func: &dyn Fn(&T) -> ()) {
self.root.foreach(func);
}
fn is_empty(&self) -> bool {
match self.root {
Nil => true,
_ => false
}
}
}
// 簡単なテスト
fn main() {
let mut a: Tree<i32> = Tree::new();
println!("{}", a.is_empty());
for x in vec![5, 3, 1, 4, 2, 7, 6, 8, 9] {
a.insert(x);
}
println!("{}", a.is_empty());
for x in 0 .. 11 {
println!("{}, {}", x, a.contains(x));
}
a.foreach(&|x| print!("{} ", x));
println!("");
println!("{:?}", a.min());
println!("{:?}", a.max());
}
//
// tree2.rs: 単純な二分木 (Option 版)
//
// Copyright (C) 2017-2022 Makoto Hiroi
//
// 節
#[derive(Debug)]
struct Node<T : Ord> {
item: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>
}
// 節のメソッド
impl<T: Ord> Node<T> {
fn new(x: T) -> Node<T> {
Node { item: x, left: None, right: None }
}
// データの挿入
fn insert(&mut self, x: T) {
if x == self.item { return; }
let node = if x < self.item { &mut self.left } else { &mut self.right };
match node {
&mut Some(ref mut node1) => node1.insert(x),
&mut None => {
*node = Some(Box::new(Node::new(x)))
}
}
}
// データの探索
fn contains(&self, x: T) -> bool {
if x == self.item { return true; }
let node = if x < self.item { &self.left } else { &self.right };
match node {
&Some(ref node1) => node1.contains(x),
&None => false
}
}
// 最小値を求める
fn min(&self) -> &T {
match self.left {
None => &self.item,
Some(ref node) => node.min()
}
}
// 最大値を求める
fn max(&self) -> &T {
match self.right {
None => &self.item,
Some(ref node) => node.max()
}
}
// 巡回
fn foreach(&self, func: &dyn Fn(&T) -> ()) {
self.left.as_ref().map(|node| node.foreach(func));
func(&self.item);
self.right.as_ref().map(|node| node.foreach(func));
}
}
// 二分木
#[derive(Debug)]
struct Tree<T: Ord> {
root: Option<Box<Node<T>>>
}
// イテレータ
struct IterTree<'a, T: 'a + Ord> {
next: Vec<&'a Node<T>>
}
fn next_node<'a, T: Ord>(node: &'a Node<T>, buff: &mut Vec<&'a Node<T>>) {
buff.push(node);
node.left.as_ref().map(|node| next_node(node, buff));
}
impl<'a, T: Ord> Iterator for IterTree<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
if self.next.len() == 0 {
None
} else {
let node = self.next.pop().unwrap();
node.right.as_ref().map(|node| {
next_node(node, &mut self.next);
})
&node.item
}
}
}
// 二分木のメソッド
impl<T: Ord> Tree<T> {
fn new() -> Tree<T>{
Tree { root: None }
}
fn insert(&mut self, x: T) {
if self.root.is_none() {
self.root = Some(Box::new(Node::new(x)));
} else {
self.root.as_mut().map(|node| node.insert(x));
}
}
fn contains(&self, x: T) -> bool {
self.root.as_ref().map_or_else(|| false, |node| node.contains(x))
}
fn min(&self) -> Option<&T> {
self.root.as_ref().map(|node| node.min())
}
fn max(&self) -> Option<&T> {
self.root.as_ref().map(|node| node.max())
}
fn foreach(&self, func: &dyn Fn(&T) ->()) {
self.root.as_ref().map(|node| node.foreach(func));
}
fn is_empty(&self) -> bool {
self.root.is_none()
}
fn iter(&self) -> IterTree<T> {
let mut buff: Vec<&Node<T>> = vec![];
self.root.as_ref().map(|node| next_node(node, &mut buff));
IterTree { next: buff }
}
}
// 簡単なテスト
fn main() {
let mut a: Tree<i32> = Tree::new();
println!("{}", a.is_empty());
for x in vec![5, 3, 2, 4, 1, 7, 6, 8, 9] {
a.insert(x);
}
println!("{}", a.is_empty());
for x in 0 .. 11 {
println!("{}, {}", x, a.contains(x));
}
a.foreach(&|x| print!("{} ", x));
println!("");
for x in a.iter() {
print!("{}", x);
}
println!("");
println!("{:?}", a.min());
println!("{:?}", a.max());
}