mull 0.16.0

Organize your knowledge.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

use crate::wiki::{HOME_TITLE, Link, Wiki};
use std::collections::VecDeque;

// Populate minimum text-link distances from the home node using breadth-first traversal.
pub fn populate_depths(wiki: &mut Wiki) {
    // Reset depths before recalculating them.
    for node in wiki.text_nodes.values_mut() {
        node.depth = None;
    }

    // Preserve the invariant that queued nodes have assigned depths [tag:queued_node_depths].
    let mut pending_titles = VecDeque::<String>::new();
    if let Some(home) = wiki.text_nodes.get_mut(HOME_TITLE) {
        home.depth = Some(0);
        pending_titles.push_back(HOME_TITLE.to_owned());
    }

    // Score each newly reached node and queue it for traversal.
    while let Some(title) = pending_titles.pop_front() {
        // Every title enters the queue only after its depth is assigned [ref:queued_node_depths].
        let depth = wiki.text_nodes[&title]
            .depth
            .expect("queued nodes should have a depth");
        let text_links = wiki.text_nodes[&title]
            .links
            .iter()
            .filter_map(|link| match link {
                Link::Text { title, .. } => Some(title.clone()),
                Link::File { .. } | Link::Directory { .. } => None,
            })
            .collect::<Vec<_>>();
        for text_link in text_links {
            if let Some(target) = wiki.text_nodes.get_mut(&text_link)
                && target.depth.is_none()
            {
                target.depth = Some(depth + 1);
                pending_titles.push_back(text_link);
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::populate_depths;
    use crate::parser::parse;
    use std::path::Path;

    // Populate depths for nodes reached through multiple levels of text links.
    #[test]
    fn transitive_text_links() {
        let mut wiki = parse(
            Some(Path::new("test.mull")),
            "# Home\nSee [Middle].\n# Middle\nSee [End].\n# End",
        )
        .unwrap();

        populate_depths(&mut wiki);

        assert_eq!(wiki.text_nodes["Home"].depth, Some(0));
        assert_eq!(wiki.text_nodes["Middle"].depth, Some(1));
        assert_eq!(wiki.text_nodes["End"].depth, Some(2));
    }

    // Choose the shortest distance when a node is reachable through multiple paths.
    #[test]
    fn minimum_depth() {
        let mut wiki = parse(
            Some(Path::new("test.mull")),
            concat!(
                "# Home\nSee [Left] and [Target].\n",
                "# Left\nSee [Middle].\n",
                "# Middle\nSee [Target].\n",
                "# Target",
            ),
        )
        .unwrap();

        populate_depths(&mut wiki);

        assert_eq!(wiki.text_nodes["Left"].depth, Some(1));
        assert_eq!(wiki.text_nodes["Middle"].depth, Some(2));
        assert_eq!(wiki.text_nodes["Target"].depth, Some(1));
    }
}