Print a tree in rust with termtree

Question

I am trying to use the crate termtree to print a tree which needs to use the custom rust idiom of using Rc adn RefCel for its children. Currently the code looks like:

#[derive(Debug, Clone)]
pub struct NodeData {
    pub base_path: String,
    pub file_path: String
}

impl fmt::Display for NodeData {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.file_path)
    }
}

pub type WrappedTreeNode<> = Rc<RefCell<TreeNode>>;

#[derive(Debug, Clone)]
pub struct TreeNode {
    pub node_data: NodeData,
    pub children: Vec<WrappedTreeNode>,
}

I just cannot figure out what needs to be done in order to to conform to the tree structure 'termtree' needs: Tree:

pub struct Tree<D: Display> {
    pub root: D,
    pub leaves: Vec<Tree<D>>,
    /* private fields */
}

If I need to implement Display for my struct then there is not much benefit any more in using 'termtree'.

Of course I can create a new tree out of TreeNode which looks like:

pub struct Tree<String> {
    pub root: String,
    pub leaves: Vec<Tree<String>>,
}

Then 'termtree' does its nice formatting. However, translating my tree TreeNode into Tree<String> turned out to be way more complex than expected. I was able to find a simple recursive way to do so:

pub fn transform_tree_recursive(node: &WrappedTreeNode) -> Tree<String> {
    let mut new_node = Tree::new(format!("{}", node.borrow().node_data.file_path));

    for child in &node.borrow().children {
        new_node.leaves.push(transform_tree_recursive(child));
    }

    new_node
}

But to challenge myself I was trying to find a non-recursive way and I gave up after drowning in the Rust tree rabbithole.

Bottom line: How to simply use 'termtree' crate which arbitrary Trees? Any hint or example would be much appreciated (the example which is coming with 'termtree' is good for filesystems, but nothing else').

Answer 1

I found a potential solution which uses a DFS together with a stack and maps to store visited nodes:

pub fn convert_to_termtree<T: Display + Clone>(root: &Rc<RefCell<TreeNode<T>>>) -> Tree<String> {
    let mut stack: Vec<Rc<RefCell<TreeNode<T>>>> = vec![root.clone()];
    // Using a raw pointer (*const TreeNode<T>) as an identifier ensures that each node
    // has a unique key because memory addresses are unique.
    // using them as keys and not dereferencing them, so it's relatively safe
    let mut visited: HashMap<*const TreeNode<T>, bool> = HashMap::new();
    // map of corresponding nodes
    let mut map: HashMap<*const TreeNode<T>, Tree<String>> = HashMap::new();

    while !stack.is_empty() {
        let current = stack.last().unwrap().clone();

        if visited.get(&(&*current.borrow() as *const _)).is_some() {
            stack.pop();  // 2nd pass: now we consume it and rm from stack (its already in 'current')
            let mut leaves = Vec::new();

            // creates the corresponding termtree children list
            for child in &current.borrow().children {
                // remove corresponding termtree child from map and add it
                if let Some(tree) = map.remove(&(&*child.borrow() as *const _)) {
                    leaves.push(tree);
                }
            }

            // create node, add children and push it onto map as corresponding node
            if leaves.len() == current.borrow().children.len() {
                let mut tree = Tree::new(current.borrow().data.to_string());
                tree.leaves = leaves; // Assuming leaves is public or has a method to set them
                map.insert(&*current.borrow() as *const _, tree);
            } else { unreachable!() }
        } else {
            // if node is not visited yet, mark as visited and push all children onto stack
            visited.insert(&*current.borrow() as *const _, true);
            for child in &current.borrow().children {
                if !visited.contains_key(&(&*child.borrow() as *const _)) {
                    stack.push(child.clone());
                }
            }
        }
    }

    map.remove(&(&*root.borrow() as *const _)).unwrap()
}

However, the recursive approach is way simpler and easier to understand.