Rust中n叉带权树Iterator实现是否符合惯用风格？冗余优化问询

背景与需求 #

• 已实现泛型N叉带权树结构，节点类型为N、边类型为E
• 需要为该树实现Iterator trait，支持三种遍历方式：前序(preorder)、后序(postorder)、中序(inorder)
• 每种遍历需提供不可变引用(&) 和可变引用(&mut) 两种迭代器，总计6个，仅可变性存在差异
• 希望尽量不使用宏，但当前实现存在较多代码重复

当前实现方案 #

节点结构体提供两个核心方法，用于返回对应迭代器：

pub fn traverse_ref(&self, traverse: Traverse) -> Box<dyn Iterator<Item = &Self> + '_>

pub fn traverse_mut(&mut self, traverse: Traverse) -> Box<dyn Iterator<Item = &mut Self> + '_>

其中Traverse是枚举类型，包含三种遍历方式；方法返回装箱后的迭代器结构体Traversal<'t, N, E, M>（不可变）和TraversalMut<'t, N, E, M>（可变），泛型参数M是用于标记遍历类型的空结构体。

尝试通过自定义Traveller trait封装遍历逻辑，减少Iterator实现中的重复，但仍存在大量冗余代码。

代码示例 #

main.rs #

mod tree;

fn main() {
    use std::num::NonZeroU8;
    use tree::Node;

    let mut tree = Node::new(NonZeroU8::new(1));

    tree.add_children(NonZeroU8::new(2), true);
    tree.add_children(NonZeroU8::new(3), false);

    tree.get_children_mut()[0]
        .0
        .add_children(NonZeroU8::new(4), true);
    tree.get_children_mut()[0]
        .0
        .add_children(NonZeroU8::new(5), false);

    for node in tree.traverse_ref(tree::Traverse::PreOrder) {}
}

tree.rs #

注：为提升可读性，遍历算法的具体实现已省略，用todo!()替代

use std::marker::PhantomData;

mod internal {
    pub trait Sealed {}
}

#[derive(Debug)]
pub struct Node<N, E> {
    value: N,
    children: Vec<(Node<N, E>, E)>,
}

impl<N, E> Node<N, E> {
    pub fn new(value: N) -> Self {
        Self {
            value,
            children: vec![],
        }
    }

    pub fn add_children(&mut self, value: N, edge: E) {
        self.children.push((Node::new(value), edge));
    }

    pub fn get_children_mut(&mut self) -> &mut Vec<(Self, E)> {
        &mut self.children
    }

    pub fn get_value_mut(&mut self) -> &mut N {
        &mut self.value
    }

    pub fn set_value(&mut self, new_value: N) {
        self.value = new_value;
    }

    pub fn traverse_ref(&self, traverse: Traverse) -> Box<dyn Iterator<Item = &Self> + '_> {
        match traverse {
            Traverse::InOrder => Box::new(Traversal::<N, E, InOrder>::new(self)),
            Traverse::PostOrder => Box::new(Traversal::<N, E, PostOrder>::new(self)),
            Traverse::PreOrder => Box::new(Traversal::<N, E, PreOrder>::new(self)),
        }
    }

    pub fn traverse_mut(&mut self, traverse: Traverse) -> Box<dyn Iterator<Item = &mut Self> + '_> {
        match traverse {
            Traverse::InOrder => Box::new(TraversalMut::<N, E, InOrder>::new(self)),
            Traverse::PostOrder => Box::new(TraversalMut::<N, E, PostOrder>::new(self)),
            Traverse::PreOrder => Box::new(TraversalMut::<N, E, PreOrder>::new(self)),
        }
    }
}

#[derive(Debug)]
pub enum Traverse {
    PreOrder,
    PostOrder,
    InOrder,
}

pub trait TraverseMethod: internal::Sealed {}

#[derive(Debug)]
struct PreOrder {}
impl internal::Sealed for PreOrder {}
impl TraverseMethod for PreOrder {}

#[derive(Debug)]
struct InOrder {}
impl internal::Sealed for InOrder {}
impl TraverseMethod for InOrder {}

#[derive(Debug)]
struct PostOrder {}
impl internal::Sealed for PostOrder {}
impl TraverseMethod for PostOrder {}

#[derive(Debug)]
pub struct Traversal<'t, N, E, M>
where
    M: TraverseMethod,
{
    tree: &'t Node<N, E>,
    _marker: PhantomData<M>,
}

impl<'t, N, E, M> Traversal<'t, N, E, M>
where
    M: TraverseMethod,
{
    fn new(tree: &'t Node<N, E>) -> Self {
        Self {
            tree,
            _marker: PhantomData {},
        }
    }
}

#[derive(Debug)]
pub struct TraversalMut<'t, N, E, M>
where
    M: TraverseMethod,
{
    tree: &'t mut Node<N, E>,
    _marker: PhantomData<M>,
}

impl<'t, N, E, M> TraversalMut<'t, N, E, M>
where
    M: TraverseMethod,
{
    fn new(tree: &'t mut Node<N, E>) -> Self {
        Self {
            tree,
            _marker: PhantomData {},
        }
    }
}

trait Traveller {
    type Item;

    fn travel_preorder(&mut self) -> Option<Self::Item> {
        todo!()
    }

    fn travel_postorder(&mut self) -> Option<Self::Item> {
        todo!()
    }

    fn travel_inorder(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, PreOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, PreOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_preorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, PreOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, PreOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_preorder()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, PostOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, PostOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_postorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, PostOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, PostOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_postorder()
    }
}

impl<'t, N, E> Traveller for Traversal<'t, N, E, InOrder> {
    type Item = &'t Node<N, E>;
}

impl<'t, N, E> Iterator for Traversal<'t, N, E, InOrder> {
    type Item = &'t Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_inorder()
    }
}

impl<'t, N, E> Traveller for TraversalMut<'t, N, E, InOrder> {
    type Item = &'t mut Node<N, E>;
}

impl<'t, N, E> Iterator for TraversalMut<'t, N, E, InOrder> {
    type Item = &'t mut Node<N, E>;

    fn next(&mut self) -> Option<Self::Item> {
        self.travel_inorder()
    }
}

问题 #

1. 该N叉带权树的实现是否符合Rust惯用风格？
2. 如何在不使用宏的前提下进一步减少代码冗余？

内容的提问来源于stack exchange，提问作者JosRs