trailtree/implement/
path.rs

1use crate::{TrailTree, Cell};
2
3impl<K,T> TrailTree<K,T>
4where K: Clone + Ord
5{
6    /// Returns the previous sequential node in the layer.
7    /// 
8    /// # Examples
9    /// 
10    /// ```
11    /// use trailtree::TrailTree;
12    /// 
13    /// let mut con = TrailTree::<u32,()>::new();
14    /// 
15    /// let a = con.insert(&[5, 10]);
16    /// let b = con.insert(&[5, 20]);
17    /// 
18    /// assert_eq!(con.prev(b), Some(a));
19    /// assert_eq!(con.prev(a), None);
20    /// ```
21    ///
22    /// See also [`TrailTree::next`].
23    pub fn prev(&self, id:usize) -> Option<usize>
24    {
25        self.traverse(id, false)
26    }
27
28    /// Returns the next sequential node in the layer.
29    /// 
30    /// # Examples
31    /// 
32    /// ```
33    /// use trailtree::TrailTree;
34    /// 
35    /// let mut con = TrailTree::<u32,()>::new();
36    /// 
37    /// let a = con.insert(&[5, 10]);
38    /// let b = con.insert(&[5, 20]);
39    /// 
40    /// assert_eq!(con.next(a), Some(b));
41    /// assert_eq!(con.next(b), None);
42    /// ```
43    /// 
44    /// See also [`TrailTree::prev`].
45    pub fn next(&self, id:usize) -> Option<usize>
46    {
47        self.traverse(id, true)
48    }
49
50    fn traverse(&self, id:usize, next:bool) -> Option<usize>
51    {
52        let forward = if next { 2 } else { 0 };
53        let back = if next { 0 } else { 2 };
54
55        if id < self.cells.len() && let Some(node) = self.node(id) {
56            let rel = node.rel;
57
58            if rel.child[forward] != usize::MAX {
59                // Get forward child's extreme descendant in back direction.
60                let mut current = rel.child[forward];
61
62                while let Some(node) = self.node(current) && node.rel.child[back] != usize::MAX {
63                    current = node.rel.child[back];
64                }
65
66                Some(current)
67            } else {
68                // Bubble up until node enters from back direction.
69                let mut last = id;
70                let mut current = rel.parent;
71
72                while current != usize::MAX && let Some(node) = self.node(current) && node.rel.child[forward] == last {
73                    last = current;
74                    current = node.rel.parent;
75                }
76
77                if current != usize::MAX {
78                    Some(current)
79                } else {
80                    None
81                }
82            }
83        } else {
84            None
85        }
86    }
87
88    /// Returns the parent of the specified element or None if a root.
89    /// 
90    /// # Examples
91    /// 
92    /// ```
93    /// use trailtree::TrailTree;
94    /// 
95    /// let mut con = TrailTree::<u32,()>::new();
96    /// 
97    /// let leaf = con.insert(&[1, 2]);
98    /// 
99    /// let mid = con.search(&[1]);
100    /// assert!(mid.is_some());
101    /// 
102    /// assert_eq!(mid, con.parent(leaf));
103    /// assert_eq!(None, con.parent(mid.unwrap()));
104    /// ```
105    /// 
106    /// See also [`TrailTree::first`], [`TrailTree::last`].
107    pub fn parent(&self, id:usize) -> Option<usize>
108    {
109        if id < self.cells.len() && let Cell::Node(node) = &self.cells[id] {
110            if node.rel.root != usize::MAX {
111                Some(node.rel.root)
112            } else {
113                None
114            }
115        } else {
116            None
117        }
118    }
119
120    /// Returns the first element in the specified element's subtree.
121    /// If no element is specified, the first root element is returned.
122    /// 
123    /// # Examples
124    /// 
125    /// ```
126    /// use trailtree::TrailTree;
127    /// 
128    /// let mut con = TrailTree::<u32,()>::new();
129    /// 
130    /// assert_eq!(con.first(None), None);
131    /// 
132    /// let a = con.insert(&[1]);
133    /// let b = con.insert(&[1, 4]);
134    /// con.insert(&[1, 8]);
135    /// con.insert(&[2, 3]);
136    /// 
137    /// assert_eq!(con.first(None), Some(a));
138    /// assert_eq!(con.first(Some(a)), Some(b));
139    /// ```
140    /// 
141    /// See also [`TrailTree::last`], [`TrailTree::parent`].
142    pub fn first(&self, id:Option<usize>) -> Option<usize>
143    {
144        self.extent(id, false)
145    }
146
147    /// Returns the last element in the specified element's subtree.
148    /// If no element is specified, the last root element is returned.
149    /// 
150    /// # Examples
151    /// 
152    /// ```
153    /// use trailtree::TrailTree;
154    /// 
155    /// let mut con = TrailTree::<u32,()>::new();
156    /// 
157    /// assert_eq!(con.last(None), None);
158    /// 
159    /// let a = con.insert(&[1]);
160    /// con.insert(&[1, 4]);
161    /// let b = con.insert(&[1, 8]);
162    /// let c = con.insert(&[2]);
163    /// 
164    /// assert_eq!(con.last(None), Some(c));
165    /// assert_eq!(con.last(Some(a)), Some(b));
166    /// ```
167    /// 
168    /// See also [`TrailTree::first`], [`TrailTree::parent`].
169    pub fn last(&self, id:Option<usize>) -> Option<usize>
170    {
171        self.extent(id, true)
172    }
173
174    fn extent(&self, id:Option<usize>, end:bool) -> Option<usize>
175    {
176        let dir = if end { 2 } else { 0 };
177
178        let mut current = if let Some(id) = id {
179            self.rel(id).child[1]
180        } else {
181            self.root
182        };
183
184        while current != usize::MAX && let Some(node) = self.node(current) && node.rel.child[dir] != usize::MAX {
185            current = node.rel.child[dir];
186        }
187
188        if current != usize::MAX {
189            Some(current)
190        } else {
191            None
192        }
193    }
194}
trailtree/implement/path.rs

trailtree/implement/
path.rs
