rust - 重新排列id_tree Rust中的同级节点

Question

我想重新排列id_tree中的 sibling 。我看到id_tree包括使节点成为子组中第一个或最后一个同级节点的方法，分别是make_first_sibling()和make_last_sibling()，但是id_tree的move_node()似乎仅对将节点移动到根节点或新父节点有用，而不会重新排列 sibling 索引。
如果您想将节点移动到同级数组中的任意索引，您该怎么做？
id_tree Tree docs

use id_tree::*;

struct MyTree{
    pub tree: Tree<i32>
}

impl MyTree{
    pub fn insert_node(&mut self, node: &NodeId, pos: u32){
        //inserts node as some pos within the array of its parents children (siblings) 
        //        Z
        //     / / \ \
        //    A  B  C  D
        //insert_node(A, 2)
        //        Z
        //     / / \ \
        //    B  C  A  D
        
    }
}

fn main() {
    use id_tree::InsertBehavior::*;

        MyTree{
            tree: Tree<i32> = TreeBuilder::new()
            .with_node_capacity(5)
            .build();
        }

    let root_id: NodeId = my_tree.tree.insert(Node::new(0), AsRoot).unwrap();
    let child_id: NodeId = my_tree.tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
    my_tree.tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
    my_tree.tree.tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
    my_tree.tree.insert(Node::new(4), UnderNode(&root_id)).unwrap();

}

也许 make_first_sibling()函数的源代码会有所帮助？

pub fn make_first_sibling(&mut self, node_id: &NodeId) -> Result<bool, NodeIdError> {
    let (is_valid, error) = self.is_valid_node_id(node_id);
    if !is_valid {
        return Err(error.expect(
            "Tree::make_first_sibling: Missing an error value but found an invalid NodeId.",
        ));
    }

    let mut moved = false;
    if let Some(parent_id) = self.get(node_id)?.parent().cloned() {
        let parent = self
            .get_mut(&parent_id)
            .expect("Tree::make_first_sibling: invalid parent id");
        let mut position = parent.children.iter().position(|id| id == node_id).unwrap();
        moved = position > 0;
        while position > 0 {
            parent.children.swap(position - 1, position);
            position -= 1;
        }
    }
    Ok(moved)
}

Answer 1

您可以使用 swap_nodes 将节点从其当前位置随机拖移到所需位置。
例如:

use id_tree::*;

trait TreeExt {
    fn move_node_to_pos(&mut self, node: &NodeId, pos: usize) -> Result<(), NodeIdError>;
}
 
impl TreeExt for Tree<i32> {

    /// Move the indicated child so that it has position `pos` under its parent
    ///        Z
    ///     / / \ \
    ///    A  B  C  D
    ///
    /// move_node_to_pos(A, 2)
    ///        Z
    ///     / / \ \
    ///    B  C  A  D
    fn move_node_to_pos(&mut self, node: &NodeId, pos: usize) -> Result<(), NodeIdError> {

        let parent = self.get(node)?.parent()
            .ok_or(NodeIdError::NodeIdNoLongerValid)?
            .clone();

        let num_children = self.children_ids(&parent)?.count();
        if pos >= num_children {
            return Err(NodeIdError::NodeIdNoLongerValid);
        }
        
        // First determine the current index that the node has
        // unwrap should not be reachable, since we are searching under node's
        // own parent, barring bugs in id_tree
        let mut current_pos = self.children_ids(&parent)?
            .enumerate()
            .find_map(|(i, n) | if n==node { Some(i) } else { None })
            .unwrap();
        
        while current_pos != pos {
            let pos_to_swap = if current_pos < pos {
                current_pos+1
            } else if current_pos > pos {
                current_pos-1
            } else {
                break;
            };
            let node_to_swap = self.children_ids(&parent)?.nth(pos_to_swap).unwrap().clone();
            self.swap_nodes(node, &node_to_swap, SwapBehavior::TakeChildren)?;
            current_pos = pos_to_swap;
        }

        Ok(())
    }
}

在这里，我定义了一个扩展特性，将方法 move_node_to_pos添加到 Tree。
为了避免生命周期问题，我们在循环内克隆了我与之交换的节点的父 &NodeId和 &NodeId。否则，您在树上获取节点的不可变借位将阻止您调用 swap_node。
在此示例实现中，错误处理并不是真正正确的-您真的不希望将 NodeIdError返回为错误类型，因为还会发生其他一些错误情况，例如请求位置大于父节点下当前节点的数量，或尝试对没有父节点的节点执行此操作。
用法示例:

fn main() {
    use id_tree::InsertBehavior::*;

    let mut my_tree = TreeBuilder::<i32>::new()
            .with_node_capacity(5)
            .build();

    let root_id: NodeId = my_tree.insert(Node::new(0), AsRoot).unwrap();
    let c1: NodeId = my_tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
    let _c2 = my_tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
    let _c3 = my_tree.insert(Node::new(3), UnderNode(&root_id)).unwrap();
    let _c4 = my_tree.insert(Node::new(4), UnderNode(&root_id)).unwrap();

    for (i,n) in my_tree.children(&root_id).unwrap().enumerate() {
        println!("i={} n={:?}", i, n.data());
    }
    
    my_tree.move_node_to_pos(&c1, 3).unwrap();

    for (i,n) in my_tree.children(&root_id).unwrap().enumerate() {
        println!("i={} n={:?}", i, n.data());
    }

}