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!()
    }
}