1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
//
// Copyright (c) DUSK NETWORK. All rights reserved.
use rkyv::Archive;
use crate::{ARef, Compound, MaybeArchived};
/// The return value from a closure to `walk` the tree.
///
/// Determines how the `Branch` is constructed
#[derive(Debug)]
pub enum Step {
/// The correct leaf was found!
Found(usize),
/// Advance search
Advance,
/// Abort search
Abort,
}
/// Information to select paths in searches
pub enum Discriminant<'a, L, A>
where
L: Archive,
{
/// Search encountered a leaf
Leaf(MaybeArchived<'a, L>),
/// Search encountered an annotated subtree
Annotation(ARef<'a, A>),
/// Search encountered an empty slot
Empty,
/// Search encountered the end of the node
End,
}
/// Wrapper trait provided to Walkers
pub trait Walkable<C, A, S>
where
C: Compound<A, S>,
{
/// Probe the location of the tree being walked
fn probe(&self, ofs: usize) -> Discriminant<C::Leaf, A>;
}
/// The trait used to construct a `Branch` or to iterate through a tree.
pub trait Walker<C, A, S>
where
C: Compound<A, S>,
{
/// Walk the tree node, returning the appropriate `Step`
fn walk(&mut self, walk: impl Walkable<C, A, S>) -> Step;
}
/// Walker that visits all leaves
#[derive(Debug)]
pub struct All;
impl<C, A, S> Walker<C, A, S> for All
where
C: Compound<A, S>,
{
fn walk(&mut self, walk: impl Walkable<C, A, S>) -> Step {
for i in 0.. {
match walk.probe(i) {
Discriminant::End => return Step::Advance,
Discriminant::Empty => (),
_ => return Step::Found(i),
}
}
unreachable!()
}
}