如何使用递归迭代器展平递归结构?

问题描述

我正在尝试扁平化一个递归结构，但是在使用递归迭代器时遇到了麻烦.

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.

另请参阅:

• 如何为简单结构实现Iterator和IntoIterator?
• 为二进制树实现IntoIterator
• 迭代递归结构时无法获得可变引用:一次不能多次借用可变变量
• 二叉搜索树的递归有序遍历

• 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

这篇关于如何使用递归迭代器展平递归结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！