How to implement fmt::Display on a recursive data structure in Rust

Question

I tried to provide an implementation of the Display trait on the recursive data structure Tree as defined below.

#[derive(Debug)]
struct Tree <'a> {
    node: (&'a str, Vec<Tree<'a>>)
}

impl <'a> Tree<'a> {
   fn new(str: &'a str) -> Tree<'a> {
    Tree {node: (str, Vec::new())}
   }

   pub fn merge_sub (&mut self, sub: Tree<'a>) {
    self.node.1.push(sub); 
   }
}

fn main(){
 
    let ta = Tree::new("a");
    let mut tb = Tree::new("b");
    tb.merge_sub(ta);

    let tc = Tree::new("c");
    let mut td = Tree::new("d");
    td.merge_sub(tc);

    let te = Tree::new("e");
    let mut tf = Tree::new("f");
    tf.merge_sub(te);


    let mut tg = Tree::new("g");
    tg.merge_sub(tb);
    tg.merge_sub(td);
    tg.merge_sub(tf);
    println!("sub tree g: {:#?}.", tg);
    println!("Display: {}.", tg);
}

Hopefully, the println!("Display: {}.", tg); would render in the format like this below :

   |--b--a
   |
g--|--d--c
   |
   |--f--e

The challenge here is that the fmt function and write! macro may not be the best fit for my requirements. Because I need to manipulate the string representation of inductive cases specifically, while these tools provide more general, high-level functionalities.

impl<'a> fmt::Display for Tree<'a>{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
        let length = self.node.1.len();
        if length == 0{
            return write!(f, "{}", self.node.0)
        }else{
            for (i,t) in self.node.1.iter().enumerate(){ 
                // How to get recursive show instance of Tree ?
            } 
        }
    }
}

This is a bit of a broad question when you take into account that the core of it is "how do I automatically generate a horizontal ASCII graph from a tree structure." The answer is non-trivial. — cdhowie
– cdhowie, Commented May 27, 2023 at 2:21
Certainly the standard formatting traits aren't doing you any favors. The most sensible solution would likely construct the visual layout as a String, Vec<String>, or whatever is most convenient, and then printing that. — kmdreko
– kmdreko, Commented May 27, 2023 at 4:40

cafce25 · Accepted Answer · 2023-05-27 11:45:53Z

You can use format! and ToString::to_string to convert something that implements Display into a String you can work with, that gives us this simplistic implementation:

        } else {
            let mut sub_nodes = self
                .node
                .1
                .iter()
                .map(ToString::to_string)
                .intersperse("\n\n".into())
                .collect::<String>()
                .split('\n')
                .map(ToString::to_string)
                .collect::<Vec<_>>();
            let len = sub_nodes.len();
            if len == 1 {
                return write!(f, "{}--{}", self.node.0, sub_nodes[0]);
            }
            for (i, sn) in sub_nodes.iter_mut().enumerate() {
                if len / 2 == i {
                    *sn = format!("{}--|--{}", self.node.0, sn);
                } else {
                    if sn == "" {
                        *sn = format!("   |   ");
                    } else {
                        *sn = format!("   |--{}", sn);
                    }
                }
            }
            write!(f, "{}", sub_nodes.join("\n"))
        }

Note: This code assumes all node identifiers are 1 character wide and that any subtree only contains a linked list, to make this work properly with any trees you have to output the corresponding amount of spaces or dashes and further special case the different possibilities of sn.

Collectives™ on Stack Overflow

How to implement fmt::Display on a recursive data structure in Rust

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related