#tree #traversal #annotation #data #structure

no-std microkelvin

A crate for tree traversal over annotated data structures

34 releases (13 breaking)

0.17.0 Oct 19, 2022
0.16.0-rkyv.3 Jun 8, 2022
0.15.0-rc.1 Feb 24, 2022
0.12.0-rc.5 Dec 14, 2021
0.5.3 Nov 17, 2020

#157 in Data structures

Download history 67/week @ 2022-10-10 132/week @ 2022-10-17 133/week @ 2022-10-24 102/week @ 2022-10-31 120/week @ 2022-11-07 116/week @ 2022-11-14 142/week @ 2022-11-21 113/week @ 2022-11-28 82/week @ 2022-12-05 132/week @ 2022-12-12 78/week @ 2022-12-19 50/week @ 2022-12-26 73/week @ 2023-01-02 95/week @ 2023-01-09 58/week @ 2023-01-16 124/week @ 2023-01-23

361 downloads per month
Used in 10 crates (6 directly)

MPL-2.0 license

33KB
801 lines

microkelvin

Repository Build Status codecov Documentation

Crate for creating and traversing recursively annotated structures.

Compound trait

/// A type that can recursively contain itself and leaves.
pub trait Compound<A>: Sized {
    /// The leaf type of the compound collection
    type Leaf;

    /// Returns a reference to a possible child at specified index
    fn child(&self, index: usize) -> Child<Self, A>;

    /// Returns a mutable reference to a possible child at specified index
    fn child_mut(&mut self, index: usize) -> ChildMut<Self, A>;
}

The Compound trait defines a type as a collection type. This means that it can be searched and have branches constructed pointing to its elements.

Branch walking

The Walker trait can be implemented for walking the tree in a user defined way. As an example, here's AllLeaves - an implementation used internally:

/// Walker that visits all leaves
pub struct AllLeaves;

impl<C, A> Walker<C, A> for AllLeaves
where
    C: Compound<A>,
{
    fn walk(&mut self, walk: Walk<C, A>) -> Step {
        for i in 0.. {
            match walk.child(i) {
                Child::Leaf(_) => return Step::Found(i),
                Child::Node(_) => return Step::Into(i),
                Child::Empty => (),
                Child::EndOfNode => return Step::Advance,
            }
        }
        unreachable!()
    }
}

Usage

Please check out the nstack implementation of a stack/vector type for a more advanced example.

Dependencies

~10KB