cartesian_tree/tree/
traits.rs

1/// Defines the parent trait.
2pub trait HasParent {
3    type Node: Clone;
4
5    /// Returns the parent of this node, if it exists.
6    fn parent(&self) -> Option<Self::Node>;
7}
8
9/// Defines the equality trait.
10pub trait NodeEquality {
11    /// Whether this node is the same as another.
12    fn is_same(&self, other: &Self) -> bool;
13}
14
15/// Defines the child trait.
16pub trait HasChildren {
17    type Node: Clone;
18
19    /// Returns all children.
20    fn children(&self) -> Vec<Self::Node>;
21}
22
23///Defines the walking trait of tree-like structure.
24pub trait Walking: HasParent<Node = Self> + NodeEquality + Clone {
25    /// Gets the depth of this node in comparison to the root.
26    ///
27    /// # Returns
28    ///
29    /// The depth of this node in comparison to the root.
30    fn depth(&self) -> usize {
31        let mut depth = 0;
32        let mut current = self.clone();
33        while let Some(parent) = current.parent() {
34            depth += 1;
35            current = parent;
36        }
37        depth
38    }
39
40    /// Walks up the tree by a given number of steps.
41    ///
42    /// # Arguments
43    ///
44    /// * `steps` - The number of steps to traverse upward.
45    ///
46    /// # Returns
47    ///
48    /// The ancestor Node or `None` if it does not exist (root reached before).
49    fn walk_up(&self, steps: usize) -> Option<Self> {
50        let mut current = self.clone();
51        for _ in 0..steps {
52            current = current.parent()?;
53        }
54        Some(current)
55    }
56
57    /// Finds the root of this node.
58    ///
59    /// # Returns
60    ///
61    /// The root Node.
62    #[must_use]
63    fn root(&self) -> Self {
64        self.walk_up(self.depth()).unwrap_or_else(|| self.clone())
65    }
66
67    /// Finds the lowest common ancestor with another Node.
68    ///
69    /// # Arguments.
70    ///
71    /// - `other`: The other Node to find the lca with.
72    ///
73    /// # Returns
74    ///
75    /// The lowest common ancestor Node or `None` if it does not exist.
76    fn lca_with(&self, other: &Self) -> Option<Self> {
77        let mut own = self.clone();
78        let mut other = other.clone();
79
80        let own_depth = self.depth();
81        let other_depth = other.depth();
82
83        // Equalize depths
84        if own_depth > other_depth {
85            own = own.walk_up(own_depth - other_depth)?;
86        } else if other_depth > own_depth {
87            other = other.walk_up(other_depth - own_depth)?;
88        }
89
90        // Walk up together
91        while !own.is_same(&other) {
92            own = own.parent()?;
93            other = other.parent()?;
94        }
95        Some(own)
96    }
97}
98
99impl<T> Walking for T where T: HasParent<Node = T> + NodeEquality + Clone {}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104    use crate::frame::Frame;
105    use nalgebra::{UnitQuaternion, Vector3};
106
107    #[test]
108    fn test_depth() {
109        let root = Frame::new_origin("root");
110        assert_eq!(root.depth(), 0);
111
112        let child = root
113            .add_child("child", Vector3::zeros(), UnitQuaternion::identity())
114            .unwrap();
115        assert_eq!(child.depth(), 1);
116
117        let grandchild = child
118            .add_child("grandchild", Vector3::zeros(), UnitQuaternion::identity())
119            .unwrap();
120        assert_eq!(grandchild.depth(), 2);
121    }
122
123    #[test]
124    fn test_walk_up() {
125        let root = Frame::new_origin("root");
126        let child = root
127            .add_child("child", Vector3::zeros(), UnitQuaternion::identity())
128            .unwrap();
129        let grandchild = child
130            .add_child("grandchild", Vector3::zeros(), UnitQuaternion::identity())
131            .unwrap();
132
133        assert!(grandchild.walk_up(0).unwrap().is_same(&grandchild));
134        assert!(grandchild.walk_up(1).unwrap().is_same(&child));
135        assert!(grandchild.walk_up(2).unwrap().is_same(&root));
136        assert!(grandchild.walk_up(3).is_none());
137    }
138
139    #[test]
140    fn test_root() {
141        let root = Frame::new_origin("root");
142        let child = root
143            .add_child("child", Vector3::zeros(), UnitQuaternion::identity())
144            .unwrap();
145        let grandchild = child
146            .add_child("grandchild", Vector3::zeros(), UnitQuaternion::identity())
147            .unwrap();
148
149        assert!(root.root().is_same(&root));
150        assert!(child.root().is_same(&root));
151        assert!(grandchild.root().is_same(&root));
152    }
153
154    #[test]
155    fn test_lca_with() {
156        let root = Frame::new_origin("root");
157        let child1 = root
158            .add_child("child1", Vector3::zeros(), UnitQuaternion::identity())
159            .unwrap();
160        let child2 = root
161            .add_child("child2", Vector3::zeros(), UnitQuaternion::identity())
162            .unwrap();
163        let grandchild1 = child1
164            .add_child("grandchild1", Vector3::zeros(), UnitQuaternion::identity())
165            .unwrap();
166        let grandchild2 = child2
167            .add_child("grandchild2", Vector3::zeros(), UnitQuaternion::identity())
168            .unwrap();
169
170        // LCA of a node with itself is itself
171        assert!(child1.lca_with(&child1).unwrap().is_same(&child1));
172        // LCA of sibling nodes is their parent
173        assert!(child1.lca_with(&child2).unwrap().is_same(&root));
174        // LCA of grandchild and parent is the parent
175        assert!(grandchild1.lca_with(&child1).unwrap().is_same(&child1));
176        // LCA of two grandchildren with different parents is root
177        assert!(grandchild1.lca_with(&grandchild2).unwrap().is_same(&root));
178    }
179}
cartesian_tree/tree/traits.rs

cartesian_tree/tree/
traits.rs
