treesome 0.7.0

A library for tree creation, manipulation, traversal and visualization.
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

use std::ops::Index;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

use crate::sized::structs::Array;

pub const LEAF_NODE: isize = -1;
pub const ROOT_NODE: isize = 0;

/// Statically sized n-ary tree, using an array representation of nodes and edges internally. Suitable for dense graphs
/// and fast serialization/deserialization.
#[derive(Eq, PartialEq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Tree<T, const M: usize, const N: usize> {
    nodes: Array<Array<isize, N>, M>,
    values: Array<T, N>,
}

impl<T, const M: usize, const N: usize> Tree<T, M, N> {
    pub fn from_arrays(nodes: Array<Array<isize, N>, M>, values: Array<T, N>) -> Self {
        Self { nodes, values }
    }
    pub fn new(nodes: [[isize; N]; M], values: [T; N]) -> Self {
        let node_indices: Vec<Array<isize, N>> = nodes
            .into_iter()
            .map(|node| {
                let arr: Array<isize, N> = node.into();
                arr
            })
            .collect();
        let node_indices_array: [Array<isize, N>; M] =
            node_indices.try_into().unwrap_or_else(|_| {
                unreachable!("Input size is guaranteed by constant generic args <M,N>")
            });
        let array_of_nodes: Array<Array<isize, N>, M> = node_indices_array.into();
        Self {
            nodes: array_of_nodes,
            values: values.into(),
        }
    }

    /// True if given `node_id` is a leaf node (no children), false otherwise.
    ///
    ///
    ///
    /// # Examples
    ///
    /// ```
    ///         use treesome::sized::Tree;
    ///         let left = [1, 4, 7, 10, -1, -1, -1, -1, -1, -1, -1, -1];
    ///         let mid = [2, 5, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1];
    ///         let right = [3, 6, 9, 12, -1, -1, -1, -1, -1, -1, -1, -1];
    ///         let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
    ///         let tree = Tree::new([left, mid, right], values);
    ///         assert!(!tree.is_leaf_node(0));
    ///         assert!(tree.is_leaf_node(4));
    /// ```
    pub fn is_leaf_node(&self, node_id: usize) -> bool {
        self.nodes
            .iter()
            .enumerate()
            .all(|(m, _)| self.nodes[m][node_id] == LEAF_NODE)
    }

    /// Returns an array of size [M] with node's children indices, or [LEAF_NODE] as a placeholder for every missing child.
    ///
    /// # Examples
    ///
    /// ```
    ///         use treesome::sized::Tree;
    ///         let left = [1, 4, 7, 10, -1, -1, -1, -1, -1, -1, -1, -1];
    ///         let mid = [2, 5, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1];
    ///         let right = [3, 6, 9, 12, -1, -1, -1, -1, -1, -1, -1, -1];
    ///         let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
    ///         let tree = Tree::new([left, mid, right], values);
    ///         assert_eq!(tree.children(0), [1, 2, 3]);
    ///         assert_eq!(tree.children(2), [7, 8, 9]);
    ///         assert_eq!(tree.children(6), [-1, -1, -1]); // Leaf node, no children
    /// ```
    pub fn children(&self, node_id: usize) -> [isize; M] {
        let mut children = [0_isize; M];
        for (m, _) in self.nodes.iter().enumerate() {
            children[m] = self.nodes[m][node_id];
        }
        children
    }

    /// Returns index of a node's parent, if the node has a parent. `None` otherwise.
    /// E.g. root nodes don't have a parent.
    ///
    ///
    /// # Examples
    ///
    /// ```
    ///        use treesome::sized::{ROOT_NODE, Tree};
    ///        let left = [1, 4, 7, 10, -1, -1, -1, -1, -1, -1, -1, -1];
    ///        let mid = [2, 5, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1];
    ///        let right = [3, 6, 9, 12, -1, -1, -1, -1, -1, -1, -1, -1];
    ///        let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
    ///        let tree = Tree::new([left, mid, right], values);
    ///
    ///        ///Root's parent
    ///        assert_eq!(tree.parent(0), None);
    ///
    ///         // Overflow - nonexistent node
    ///         assert_eq!(tree.parent(values.len() as isize), None);
    ///
    ///         // Valid use cases
    ///         assert_eq!(tree.parent(1).unwrap(), ROOT_NODE);
    ///         assert_eq!(tree.parent(3).unwrap(), ROOT_NODE);
    ///         assert_eq!(tree.parent(4).unwrap(), 1);
    ///         assert_eq!(tree.parent(7).unwrap(), 2);
    ///         assert_eq!(tree.parent(9).unwrap(), 2);
    ///         assert_eq!(tree.parent(10).unwrap(), 3);
    /// ```
    pub fn parent(&self, node_id: isize) -> Option<isize> {
        if node_id <= ROOT_NODE || node_id as usize >= self.values.len() {
            return None; // Root node doesn't have a parent.
        };

        Some((node_id - 1) / M as isize)
    }
}

impl<T, const M: usize, const N: usize> Index<usize> for Tree<T, M, N> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        &self.values[index]
    }
}

#[cfg(test)]
mod tests {
    use crate::sized::Tree;

    #[test]
    fn index() {
        let left = [1, 4, 7, 10, -1, -1, -1, -1, -1, -1, -1, -1];
        let mid = [2, 5, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1];
        let right = [3, 6, 9, 12, -1, -1, -1, -1, -1, -1, -1, -1];
        let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
        let tree = Tree::new([left, mid, right], values);
        assert_eq!(tree[0], 1);
        assert_eq!(tree[3], 4);
    }

    #[cfg(feature = "serde")]
    #[test]
    fn serde() {
        let left = [1, 4, 7, 10, -1, -1, -1, -1, -1, -1, -1, -1];
        let mid = [2, 5, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1];
        let right = [3, 6, 9, 12, -1, -1, -1, -1, -1, -1, -1, -1];
        let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
        let tree = Tree::new([left, mid, right], values);
        let string_repr = serde_json::to_string(&tree).unwrap();
        let deserialized_tree = serde_json::from_str::<Tree<i32, 3, 12>>(&string_repr).unwrap();
        assert_eq!(tree, deserialized_tree);
    }
}