nstack 0.6.0

Arity 4 stack for the kelvin merkle toolkit
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


# nstack

nstack is a stack merkle datastructure for storing and accessing indexed values.

It builds on [kelvin](https://github.com/dusk-network/kelvin) for database backing and merkle operations.

# Usage example

```rust

use kelvin::{annotations::Cardinality, Blake2b};

let n: usize = 256;
let mut nt = NStack::<_, Cardinality<u64>, Blake2b>::new();

for i in 0..n {
    nt.push(i).unwrap();
}

// get a mutable reference to the 128'th element

let element = &mut *nt.get_mut(128).unwrap().unwrap();

```

# Structure

The general structure of the NStack is a 4-way splitting tree that is always populated from the "bottom left".

As new nodes are added, they get added to the right of the last leaf, creating a new root level on top when neccesary.

The leaves of the tree are always located at the same depth relative to the root.

Here's a representation, using width of 2 instead of 4 for easier comprehension.

```
containing 1 element:

[0, - ]

containing 3 elements:

  [ *,  * ]
   /     \
[0, 1] [2, -]

containing 5 elements:

      [ *    ,    *  ]
       /           \
  [ * , * ]      [ * , - ]
   /     \        /
[0, 1] [2, 3] [ 4, - ]
```