trailtree/implement/access.rs
1use crate::{TrailTree, Cell};
2
3use core::cmp::Ordering;
4use alloc::vec::Vec;
5
6impl<K,T> TrailTree<K,T>
7where K: Clone + Ord
8{
9 /// Returns the id of the element following a path from the root.
10 ///
11 /// # Examples
12 ///
13 /// ```
14 /// use trailtree::TrailTree;
15 ///
16 /// let mut con = TrailTree::<u32,()>::new();
17 ///
18 /// let leaf = con.insert(&[1, 2, 3, 4]);
19 ///
20 /// assert_eq!(con.search(&[1, 2, 3, 4]), Some(leaf));
21 /// assert_eq!(con.search(&[2, 4, 6]), None);
22 /// ```
23 ///
24 /// See also [`TrailTree::search_from`].
25 pub fn search(&self, path:&[K]) -> Option<usize>
26 {
27 self.search_traverse(self.root, path)
28 }
29
30 /// Returns the id of the element following a path from the specified element.
31 ///
32 /// # Examples
33 ///
34 /// ```
35 /// use trailtree::TrailTree;
36 ///
37 /// let mut con = TrailTree::<u32,()>::new();
38 ///
39 /// let leaf = con.insert(&[1, 2, 3, 4]);
40 ///
41 /// let mid = con.search(&[1, 2]);
42 /// assert!(mid.is_some());
43 ///
44 /// assert_eq!(con.search_from(mid.unwrap(), &[3, 4]), Some(leaf));
45 /// ```
46 ///
47 /// See also [`TrailTree::search`].
48 pub fn search_from(&self, id:usize, path:&[K]) -> Option<usize>
49 {
50 if let Some(node) = self.node(id) {
51 self.search_traverse(node.rel.child[1], path)
52 } else {
53 None
54 }
55 }
56
57 fn search_traverse(&self, id:usize, path:&[K]) -> Option<usize>
58 {
59 let mut current = id;
60 if id == usize::MAX { return None; }
61
62 for (depth, key) in path.iter().enumerate() {
63 let mut traverse = true;
64
65 while traverse {
66 let node = self.node(current)?;
67
68 (traverse, current) = match key.cmp(&node.key) {
69 Ordering::Less => (true, node.rel.child[0]),
70 Ordering::Greater => (true, node.rel.child[2]),
71 Ordering::Equal => (false, if depth + 1 < path.len() { node.rel.child[1] } else { current }),
72 };
73
74 if current == usize::MAX {
75 return None;
76 }
77 }
78 }
79
80 Some(current)
81 }
82
83 /// Returns the key of the specified element.
84 ///
85 /// # Examples
86 ///
87 /// ```
88 /// use trailtree::TrailTree;
89 ///
90 /// let mut con = TrailTree::<u32,()>::new();
91 ///
92 /// let leaf = con.insert(&[1, 2]);
93 ///
94 /// assert_eq!(con.key(leaf), Some(2));
95 /// ```
96 pub fn key(&self, id:usize) -> Option<K>
97 {
98 if id < self.cells.len() && let Cell::Node(node) = &self.cells[id] {
99 Some(node.key.clone())
100 } else {
101 None
102 }
103 }
104
105 /// Returns an ordered list of keys available from the root.
106 ///
107 /// # Examples
108 ///
109 /// ```
110 /// use trailtree::TrailTree;
111 ///
112 /// let mut con = TrailTree::<u32,()>::new();
113 ///
114 /// con.insert(&[10]);
115 /// con.insert(&[2]);
116 /// con.insert(&[12]);
117 ///
118 /// assert_eq!(&con.keys(), &[2, 10, 12]);
119 /// ```
120 pub fn keys(&self) -> Vec<K>
121 {
122 self.keys_inner(self.root)
123 }
124
125 /// Returns an ordered list of keys available from the specified element.
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// use trailtree::TrailTree;
131 ///
132 /// let mut con = TrailTree::<u32,()>::new();
133 ///
134 /// con.insert(&[1, 10]);
135 /// con.insert(&[1, 2]);
136 /// con.insert(&[1, 12]);
137 ///
138 /// let mid = con.search(&[1]);
139 /// assert!(mid.is_some());
140 ///
141 /// assert_eq!(&con.keys_from(mid.unwrap()), &[2, 10, 12]);
142 /// ```
143 pub fn keys_from(&self, id:usize) -> Vec<K>
144 {
145 if id < self.cells.len() && let Some(node) = self.node(id) {
146 self.keys_inner(node.rel.child[1])
147 } else {
148 Vec::new()
149 }
150 }
151
152 fn keys_inner(&self, id:usize) -> Vec<K>
153 {
154 let mut keys = Vec::new();
155
156 let mut current = id;
157 let mut stack = Vec::new();
158
159 while current != usize::MAX || stack.len() > 0 {
160
161 // Walk to lesser-most child.
162 while current != usize::MAX {
163 let rel = self.rel(current);
164 stack.push(current);
165 current = rel.child[0];
166 }
167
168 let id = stack.pop().unwrap();
169 if let Some(node) = self.node(id) {
170 keys.push(node.key.clone());
171 current = node.rel.child[2];
172 } else { return keys }
173 }
174
175 keys
176 }
177
178 /// Returns a reference to the data associated with the specified element.
179 ///
180 /// # Examples
181 ///
182 /// ```
183 /// use trailtree::TrailTree;
184 ///
185 /// let mut con = TrailTree::<u32,u32>::new();
186 ///
187 /// let leaf = con.insert(&[100, 50]);
188 ///
189 /// con.set(leaf, 9001);
190 ///
191 /// assert_eq!(con.get(leaf), Some(9001).as_ref());
192 /// ```
193 pub fn get(&self, id:usize) -> Option<&T>
194 {
195 if id < self.cells.len() && let Cell::Node(node) = &self.cells[id] {
196 node.data.as_ref()
197 } else {
198 None
199 }
200 }
201
202 /// Returns a mutable reference to the data associated with the specified element.
203 ///
204 /// # Examples
205 ///
206 /// ```
207 /// use trailtree::TrailTree;
208 ///
209 /// let mut con = TrailTree::<u32,u32>::new();
210 ///
211 /// let leaf = con.insert(&[100, 50]);
212 ///
213 /// con.set(leaf, 9001);
214 /// if let Some(data) = con.get_mut(leaf) {
215 /// *data = 1009;
216 /// }
217 ///
218 /// assert_eq!(con.get(leaf), Some(1009).as_ref());
219 /// ```
220 pub fn get_mut(&mut self, id:usize) -> Option<&mut T>
221 {
222 if id < self.cells.len() && let Cell::Node(node) = &mut self.cells[id] {
223 node.data.as_mut()
224 } else {
225 None
226 }
227 }
228
229 /// Returns the key path to the specified element.
230 ///
231 /// # Examples
232 ///
233 /// ```
234 /// use trailtree::TrailTree;
235 ///
236 /// let mut con = TrailTree::<u32,()>::new();
237 ///
238 /// let leaf = con.insert(&[10, 12, 2]);
239 ///
240 /// assert_eq!(&con.path(leaf), &[10, 12, 2]);
241 /// ```
242 pub fn path(&self, mut id:usize) -> Vec<K>
243 {
244 let mut path = Vec::new();
245
246 while id != usize::MAX && let Some(node) = self.node(id) {
247 path.push(node.key.clone());
248 id = node.rel.root;
249 }
250
251 path.reverse();
252 path
253 }
254}