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    fn root(&self) -> Self {
63        self.walk_up(self.depth()).unwrap_or_else(|| self.clone())
64    }
65
66    /// Finds the lowest common ancestor with another Node.
67    ///
68    /// # Arguments.
69    ///
70    /// - `other`: The other Node to find the lca with.
71    ///
72    /// # Returns
73    ///
74    /// The lowest common ancestor Node or `None` if it does not exist.
75    fn lca_with(&self, other: &Self) -> Option<Self> {
76        let mut own = self.clone();
77        let mut other = other.clone();
78
79        let own_depth = self.depth();
80        let other_depth = other.depth();
81
82        // Equalize depths
83        if own_depth > other_depth {
84            own = own.walk_up(own_depth - other_depth)?;
85        } else if other_depth > own_depth {
86            other = other.walk_up(other_depth - own_depth)?;
87        }
88
89        // Walk up together
90        while !own.is_same(&other) {
91            own = own.parent()?;
92            other = other.parent()?;
93        }
94        Some(own)
95    }
96}
97
98impl<T> Walking for T where T: HasParent<Node = T> + NodeEquality + Clone {}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103    use crate::frame::Frame;
104    use nalgebra::{UnitQuaternion, Vector3};
105
106    #[test]
107    fn test_depth() {
108        let root = Frame::new_origin("root");
109        assert_eq!(root.depth(), 0);
110
111        let child = root
112            .add_child("child", Vector3::zeros(), UnitQuaternion::identity())
113            .unwrap();
114        assert_eq!(child.depth(), 1);
115
116        let grandchild = child
117            .add_child("grandchild", Vector3::zeros(), UnitQuaternion::identity())
118            .unwrap();
119        assert_eq!(grandchild.depth(), 2);
120    }
121
122    #[test]
123    fn test_walk_up() {
124        let root = Frame::new_origin("root");
125        let child = root
126            .add_child("child", Vector3::zeros(), UnitQuaternion::identity())
127            .unwrap();
128        let grandchild = child
129            .add_child("grandchild", Vector3::zeros(), UnitQuaternion::identity())
130            .unwrap();
131
132        assert!(grandchild.walk_up(0).unwrap().is_same(&grandchild));
133        assert!(grandchild.walk_up(1).unwrap().is_same(&child));
134        assert!(grandchild.walk_up(2).unwrap().is_same(&root));
135        assert!(grandchild.walk_up(3).is_none());
136    }
137
138    #[test]
139    fn test_root() {
140        let root = Frame::new_origin("root");
141        let child = root
142            .add_child("child", Vector3::zeros(), UnitQuaternion::identity())
143            .unwrap();
144        let grandchild = child
145            .add_child("grandchild", Vector3::zeros(), UnitQuaternion::identity())
146            .unwrap();
147
148        assert!(root.root().is_same(&root));
149        assert!(child.root().is_same(&root));
150        assert!(grandchild.root().is_same(&root));
151    }
152
153    #[test]
154    fn test_lca_with() {
155        let root = Frame::new_origin("root");
156        let child1 = root
157            .add_child("child1", Vector3::zeros(), UnitQuaternion::identity())
158            .unwrap();
159        let child2 = root
160            .add_child("child2", Vector3::zeros(), UnitQuaternion::identity())
161            .unwrap();
162        let grandchild1 = child1
163            .add_child("grandchild1", Vector3::zeros(), UnitQuaternion::identity())
164            .unwrap();
165        let grandchild2 = child2
166            .add_child("grandchild2", Vector3::zeros(), UnitQuaternion::identity())
167            .unwrap();
168
169        // LCA of a node with itself is itself
170        assert!(child1.lca_with(&child1).unwrap().is_same(&child1));
171        // LCA of sibling nodes is their parent
172        assert!(child1.lca_with(&child2).unwrap().is_same(&root));
173        // LCA of grandchild and parent is the parent
174        assert!(grandchild1.lca_with(&child1).unwrap().is_same(&child1));
175        // LCA of two grandchildren with different parents is root
176        assert!(grandchild1.lca_with(&grandchild2).unwrap().is_same(&root));
177    }
178}
cartesian_tree/tree/traits.rs

cartesian_tree/tree/
traits.rs
