How to build TOC tree from titles

help
#1

I want to build table of contents tree form titles.

I want to achieve a transformation similar to this:

Vec<Title {level:usize,detail:String}> -> TOC {detail:String, children: Vec<TOC>}

I thought of such an algorithm, compare the current level and decide whether to push or move to the parent node.

But I encountered some problems when expressing mutable nodes.

Here is my implementation:

#[derive(Debug,Clone)]
pub struct TOC {
    level: usize,
    parent: Option<Box<TOC>>,
    detail: String,
    children: Vec<TOC>,
}

fn build_toc(ts: &[(usize, String)]) -> TOC {
    let mut out = TOC { level: 0, parent: None, detail: "ROOT".to_string(), children: vec![] };
    for (level, detail) in ts {
        out = append_toc(*level, &mut out, detail.to_owned())
    }
    return out;
}

fn append_toc(this: usize, last: &mut TOC, detail: String) -> TOC {
    if this > last.level {
        let new = TOC { level: this, parent: Some(Box::new(last)), detail, children: vec![] };
        last.children.push(new);
        new
    }
    else {
        let out = *last.parent.unwrap();
        append_toc(this, out, detail)
    }
}


fn main() {
    let titles = vec![
        (1, "title1".to_string()),
        (2, "title2".to_string()),
        (3, "title3".to_string()),
        (3, "title4".to_string()),
        (2, "title5".to_string()),
        (3, "title6".to_string()),
        (1, "title6".to_string()),
    ];

    println!("{:#?}", build_toc(&titles))
}

How can I fix my implementation?

#2

Because of technical details of Rust’s ownership system, parent pointers are usually more trouble than they’re worth. The easiest way to make this work is to search from the root node every time:

#[derive(Debug,Clone)]
pub struct TOC {
    level: usize,
    detail: String,
    children: Vec<TOC>,
}

impl TOC {
    fn last_at_level(&mut self, depth: usize)->&mut TOC {
        if depth == 0 { self }
        else { self.children.last_mut().unwrap().last_at_level(depth - 1) }
    }
}

(Playground)

If you really need/want parent pointers, one way to do it is with Rc/Weak. A direct adaptation of your algorithm along these lines is here.

#3

Thanks for your help, I tested it in the project, and the efficiency of search from the root is acceptable.