grapes 0.3.0

Persistent graph data structures: Tree, Graph, Arena & more
Documentation 
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

#[cfg(test)]
mod tests {
    use graph_test::{verify_correctness, Location, TreeManipulation, TreeTraversal};

    use crate::tree::{NodeId, Tree};

    impl From<graph_test::Location<NodeId>> for crate::tree::Location {
        fn from(location: Location<NodeId>) -> Self {
            match location {
                Location::FirstChildOf(parent) => Self::FirstChildOf(parent),
                Location::NextSiblingOf(sibling) => Self::AfterSibling(sibling),
            }
        }
    }

    impl<T: Clone> TreeTraversal<T> for Tree<T> {
        type NodeId = NodeId;

        fn root(&self) -> Self::NodeId {
            self.root().id()
        }

        fn node<'a>(
            &'a self,
            node: Self::NodeId,
        ) -> (&'a T, Box<dyn Iterator<Item = Self::NodeId> + 'a>) {
            let node = self.get(node).expect("no such node");

            let b = Box::new(node.children().map(|node| node.id()));

            (node.data(), b)
        }
    }

    impl<T: Clone> TreeManipulation<T> for Tree<T> {
        type Key = NodeId;

        fn new_with_root(value: T) -> (Self::Key, Self) {
            let tree = Self::new_with_root(value);

            (tree.root().id(), tree)
        }

        fn insert_node(&mut self, value: T, location: Location<Self::Key>) -> Self::Key {
            let id = match location {
                Location::FirstChildOf(id) => self
                    .get_mut(id)
                    .expect("no such node")
                    .push_front_child(value)
                    .id(),
                Location::NextSiblingOf(id) => self
                    .get_mut(id)
                    .expect("no such node")
                    .push_next_sibling(value)
                    .expect("cannot add sibling")
                    .id(),
            };
            self.validate();
            id
        }

        fn move_node(&mut self, id: &Self::Key, new_location: Location<Self::Key>) {
            self.get_mut(*id)
                .expect("no such node")
                .move_to(new_location.into())
                .expect("could not move");

            self.validate();
        }

        fn remove(&mut self, id: &Self::Key) {
            self.get_mut(*id)
                .expect("no such node")
                .remove()
                .expect("cannot remove");

            self.validate();
        }
    }

    #[test]
    fn fuzz_test() {
        verify_correctness::<Tree<i64>>()
    }
}