如何使用递归迭代器展平递归结构? [英] How do I flatten a recursive structure using recursive iterators?
问题描述
我正在尝试扁平化一个递归结构，但是在使用递归迭代器时遇到了麻烦.
I'm trying to flatten a recursive structure but I'm having trouble with recursive iterators.
结构如下:
#[derive(Debug, Clone)]
pub struct C {
name: String,
vb: Option<Vec<B>>,
}
#[derive(Debug, Clone)]
pub struct B {
c: Option<C>,
}
#[derive(Debug, Clone)]
pub struct A {
vb: Option<Vec<B>>,
flat_c: Option<Vec<C>>,
}
我的计划是遍历vb向量并将其展平为flat_c.我希望它看起来像这样，或者至少是Vec<String>:
My plan is to traverse the vb vector and flatten it into flat_c. I want it to look like this, or at least, be a Vec<String>:
Some([
C {
name: "foo",
vb: None,
},
C {
name: "bar",
vb: None,
},
C {
name: "fizz",
vb: None,
},
C {
name: "buzz",
vb: None,
},
])
这是我设法做的事情，虽然没有实现递归，但是使结构稍微平坦了，但仅适用于最后一个元素.
Here what I managed to do, somewhat flattening the struct, but only for the last element, as the recursion is not implemented.
impl A {
fn flat_c(self) -> Self {
let fc: Vec<C> = self
.vb
.clone()
.unwrap()
.iter()
.flat_map(|x| x.c.as_ref().unwrap().vb.as_ref().unwrap().iter())
.cloned()
.map(|x| x.c.unwrap())
.collect();
Self {
flat_c: Some(fc),
..self
}
}
}
fn main() {
let a = A {
vb: Some(vec![
B {
c: Some(C {
name: "foo".to_string(),
vb: Some(vec![B {
c: Some(C {
name: "bar".to_string(),
vb: None,
}),
}]),
}),
},
B {
c: Some(C {
name: "fiz".to_string(),
vb: Some(vec![B {
c: Some(C {
name: "buzz".to_string(),
vb: None,
}),
}]),
}),
},
]),
flat_c: None,
};
let a = a.flat_c();
println!("a: {:#?}", a);
}
flat_c的输出:
Some([
C {
name: "bar",
vb: None,
},
C {
name: "buzz",
vb: None,
},
])
我还没有深入研究此问题可能需要的Iterator特征实施.
I haven't dived into the Iterator trait implementation that might be required for this problem.
我将如何解决这个问题?也许使用fold?也许甚至不需要递归方法?我很茫然.
How would I tackle this problem? Maybe using a fold? Perhaps a recursive approach is not even needed? I'm at loss.
推荐答案
熟悉常见的数据结构是一个好主意.您有树，并且
It's a good idea to be familiar with common data structures. You have a tree, and there are several ways to traverse a tree. You haven't precisely specified which method to use, so I chose one arbitrarily that's easy to implement.
这里的关键是实现一个跟踪某些状态的迭代器:所有尚未访问的节点.在每次调用Iterator::next时，我们都会获取下一个值，将要访问的任何新节点保留在一边，然后返回该值.
The key here is to implement an iterator that keeps track of some state: all of the nodes yet to be visited. On each call to Iterator::next, we take the next value, save aside any new nodes to visit, and return the value.
一旦有了迭代器，就可以将其collect转换为Vec.
Once you have the iterator, you can collect it into a Vec.
use std::collections::VecDeque;
impl IntoIterator for A {
type IntoIter = IntoIter;
type Item = String;
fn into_iter(self) -> Self::IntoIter {
IntoIter {
remaining: self.vb.into_iter().flatten().collect(),
}
}
}
struct IntoIter {
remaining: VecDeque<B>,
}
impl Iterator for IntoIter {
type Item = String;
fn next(&mut self) -> Option<Self::Item> {
self.remaining.pop_front().and_then(|b| {
b.c.map(|C { name, vb }| {
self.remaining.extend(vb.into_iter().flatten());
name
})
})
}
}
fn to_strings(a: A) -> Vec<String> {
a.into_iter().collect()
}
#[derive(Debug, Clone)]
struct A {
vb: Option<Vec<B>>,
}
#[derive(Debug, Clone)]
struct B {
c: Option<C>,
}
#[derive(Debug, Clone)]
struct C {
name: String,
vb: Option<Vec<B>>,
}
fn main() {
let example: A = A {
vb: Some(vec![
B {
c: Some(C {
name: "Hello ".to_string(),
vb: None,
}),
},
B {
c: Some(C {
name: "World!".to_string(),
vb: None,
}),
},
]),
};
println!("The example struct: {:?}", example);
//clone a copy for a second example, because to_strings() takes ownership of the example A struct
let receipt: A = example.clone();
println!("Iterated: {:?}", to_strings(example));
// another example of using to_strings()
println!(
"As a string: {:?}",
to_strings(receipt).into_iter().collect::<String>()
);
}
如果需要的话，从这里直接创建B的迭代器应该很简单.拥有所有None值似乎很愚蠢，因此我将它们省略，直接返回了String s.
From here, it should be straight-forward to create an iterator of B if that's what you need. Having all of the None values seemed silly, so I left them out and directly returned Strings.
我也使它成为一个按值迭代器.您可以按照相同的模式创建一个迭代器，该迭代器返回对B/String的引用，并仅在需要时将其克隆.
I also made this a by-value iterator. You could follow the same pattern to create an iterator that returned references to the B / String and only clone them as needed.
另请参阅:
- How to implement Iterator and IntoIterator for a simple struct?
- Implement IntoIterator for binary tree
- Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time
- Recursive inorder traversal of a binary search tree
这篇关于如何使用递归迭代器展平递归结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
