microkelvin 0.5.2

A library for tree traversal over annotated datastructures
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
76
77
78

# microkelvin

Library for creating and searching through annotated merkle trees.

Built on the [`canonical`](http://github.com/dusk-network/canonical) serialization and FFI library.

# Compound trait

```rust
/// Trait for compound datastructures
pub trait Compound<S>
where
    Self: Canon<S>,
    S: Store,
{
    /// The leaf type of the collection
    type Leaf;

    /// The annotation type of the connection
    type Annotation;

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

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

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.

# Annotation trait

The annotation trait keeps annotations of subtrees, for example total leaf amount (`Cardinality` in reference implementation), or which leaf compares the greatest (`Max` in reference implementation)

# Branch walking

This is ane example of walking a recursive structure to yieald a branch pointing at a specific leaf.

It i implemented on any type implementing `Compound` whose annotation can be borrowed as `Cardinality`. Giving this capability to any such structure.

```rust
impl<'a, C, S> Nth<'a, S> for C
where
    C: Compound<S>,
    C::Annotation: Annotation<C, S> + Borrow<Cardinality>,
    S: Store,
{
    fn nth<const N: usize>(
        &'a self,
        mut index: u64,
    ) -> Result<Option<Branch<'a, Self, S, N>>, S::Error> {
        Branch::walk(self, |f| match f {
            Walk::Leaf(l) => {
                if index == 0 {
                    Step::Found(l)
                } else {
                    index -= 1;
                    Step::Next
                }
            }
            Walk::Node(n) => {
                let &Cardinality(card) = n.annotation().borrow();
                if card <= index {
                    index -= card;
                    Step::Next
                } else {
                    Step::Into(n)
                }
            }
        })
    }
		// [ ... ]
}
```
# usage

Please check out the [`nstack`](http://github.com/dusk-network/nstack) implementation of a stack/vector type for a more advanced example.