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

cartesian_tree/tree/
traits.rs
