#tree-traversal #tree #traversal #structure #annotations

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

#527 in Data structures

Download history 3/week @ 2024-07-13 87/week @ 2024-07-27 2/week @ 2024-08-03 11/week @ 2024-08-10 24/week @ 2024-08-17 2/week @ 2024-08-24 10/week @ 2024-08-31 1/week @ 2024-09-07 63/week @ 2024-09-21 35/week @ 2024-09-28 24/week @ 2024-10-05 111/week @ 2024-10-12 19/week @ 2024-10-19 1/week @ 2024-10-26

158 downloads per month
Used in 5 crates (4 directly)

MPL-2.0 license

34KB
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