Show More
@@ -272,17 +272,82 b' impl NodeTree {' | |||||
272 | &self, |
|
272 | &self, | |
273 | prefix: NodePrefixRef<'p>, |
|
273 | prefix: NodePrefixRef<'p>, | |
274 | ) -> Result<Option<Revision>, NodeMapError> { |
|
274 | ) -> Result<Option<Revision>, NodeMapError> { | |
275 | let mut visit = self.len() - 1; |
|
275 | for visit_item in self.visit(prefix) { | |
276 | for i in 0..prefix.len() { |
|
276 | if let Some(opt) = visit_item.final_revision() { | |
277 | let nybble = prefix.get_nybble(i); |
|
277 | return Ok(opt); | |
278 | match self[visit].get(nybble) { |
|
|||
279 | Element::None => return Ok(None), |
|
|||
280 | Element::Rev(r) => return Ok(Some(r)), |
|
|||
281 | Element::Block(idx) => visit = idx, |
|
|||
282 | } |
|
278 | } | |
283 | } |
|
279 | } | |
284 | Err(NodeMapError::MultipleResults) |
|
280 | Err(NodeMapError::MultipleResults) | |
285 | } |
|
281 | } | |
|
282 | ||||
|
283 | fn visit<'n, 'p>( | |||
|
284 | &'n self, | |||
|
285 | prefix: NodePrefixRef<'p>, | |||
|
286 | ) -> NodeTreeVisitor<'n, 'p> { | |||
|
287 | NodeTreeVisitor { | |||
|
288 | nt: self, | |||
|
289 | prefix: prefix, | |||
|
290 | visit: self.len() - 1, | |||
|
291 | nybble_idx: 0, | |||
|
292 | done: false, | |||
|
293 | } | |||
|
294 | } | |||
|
295 | } | |||
|
296 | ||||
|
297 | struct NodeTreeVisitor<'n, 'p> { | |||
|
298 | nt: &'n NodeTree, | |||
|
299 | prefix: NodePrefixRef<'p>, | |||
|
300 | visit: usize, | |||
|
301 | nybble_idx: usize, | |||
|
302 | done: bool, | |||
|
303 | } | |||
|
304 | ||||
|
305 | #[derive(Debug, PartialEq, Clone)] | |||
|
306 | struct NodeTreeVisitItem { | |||
|
307 | block_idx: usize, | |||
|
308 | nybble: u8, | |||
|
309 | element: Element, | |||
|
310 | } | |||
|
311 | ||||
|
312 | impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { | |||
|
313 | type Item = NodeTreeVisitItem; | |||
|
314 | ||||
|
315 | fn next(&mut self) -> Option<Self::Item> { | |||
|
316 | if self.done || self.nybble_idx >= self.prefix.len() { | |||
|
317 | return None; | |||
|
318 | } | |||
|
319 | ||||
|
320 | let nybble = self.prefix.get_nybble(self.nybble_idx); | |||
|
321 | self.nybble_idx += 1; | |||
|
322 | ||||
|
323 | let visit = self.visit; | |||
|
324 | let element = self.nt[visit].get(nybble); | |||
|
325 | if let Element::Block(idx) = element { | |||
|
326 | self.visit = idx; | |||
|
327 | } else { | |||
|
328 | self.done = true; | |||
|
329 | } | |||
|
330 | ||||
|
331 | Some(NodeTreeVisitItem { | |||
|
332 | block_idx: visit, | |||
|
333 | nybble: nybble, | |||
|
334 | element: element, | |||
|
335 | }) | |||
|
336 | } | |||
|
337 | } | |||
|
338 | ||||
|
339 | impl NodeTreeVisitItem { | |||
|
340 | // Return `Some(opt)` if this item is final, with `opt` being the | |||
|
341 | // `Revision` that it may represent. | |||
|
342 | // | |||
|
343 | // If the item is not terminal, return `None` | |||
|
344 | fn final_revision(&self) -> Option<Option<Revision>> { | |||
|
345 | match self.element { | |||
|
346 | Element::Block(_) => None, | |||
|
347 | Element::Rev(r) => Some(Some(r)), | |||
|
348 | Element::None => Some(None), | |||
|
349 | } | |||
|
350 | } | |||
286 | } |
|
351 | } | |
287 |
|
352 | |||
288 | impl From<Vec<Block>> for NodeTree { |
|
353 | impl From<Vec<Block>> for NodeTree { |
General Comments 0
You need to be logged in to leave comments.
Login now