indextree 4.9.0

Arena based tree structure by using indices instead of reference counted pointers
Documentation 
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

# indextree

[![GitHub Actions](https://github.com/saschagrunert/indextree/actions/workflows/test.yml/badge.svg)](https://github.com/saschagrunert/indextree/actions/workflows/test.yml)
[![Coverage](https://codecov.io/gh/saschagrunert/indextree/branch/main/graph/badge.svg)](https://codecov.io/gh/saschagrunert/indextree)
[![Dependency Status](https://deps.rs/repo/github/saschagrunert/indextree/status.svg)](https://deps.rs/repo/github/saschagrunert/indextree)
[![Doc indextree](https://img.shields.io/badge/main-indextree-blue.svg)](https://saschagrunert.github.io/indextree/doc/indextree)
[![License MIT](https://img.shields.io/badge/license-MIT-blue.svg)](https://github.com/saschagrunert/indextree/blob/main/LICENSE)
[![Crates.io](https://img.shields.io/crates/v/indextree.svg)](https://crates.io/crates/indextree)
[![doc.rs](https://docs.rs/indextree/badge.svg)](https://docs.rs/indextree)

## Arena based tree structure with multithreading support

This arena tree structure is using just a single `Vec` and numerical identifiers
(indices in the vector) instead of reference counted pointers. This means there
is no `RefCell` and mutability is handled in a way much more idiomatic to Rust
through unique (&mut) access to the arena. The tree can be sent or shared across
threads like a `Vec`. This enables general multiprocessing support like
parallel tree traversals.

### Minimum Supported Rust Version (MSRV)

The current MSRV is **1.85.0**.

### Features

| Feature    | Default | Description                                                        |
| ---------- | ------- | ------------------------------------------------------------------ |
| `std`      | yes     | Standard library support. Disable for `no_std` (requires `alloc`). |
| `macros`   | yes     | `tree!` macro for declarative tree construction.                   |
| `serde`    | no      | Serde serialization and deserialization.                           |
| `par_iter` | no      | Parallel iteration via rayon.                                      |

The legacy feature name `deser` is still accepted as an alias for `serde`.

### Example usage

```rust
use indextree::Arena;

// Create a new arena
let arena = &mut Arena::new();

// Add some new nodes to the arena
let a = arena.new_node(1);
let b = arena.new_node(2);

// Append b to a
a.append(b, arena);
assert_eq!(b.ancestors(arena).count(), 2);
```

### Building trees with the `tree!` macro

The optional `macros` feature (enabled by default) provides a `tree!` macro
for declarative tree construction:

```rust
use indextree::{Arena, macros::tree};

let arena = &mut Arena::new();
let root = tree!(arena, "root" => {
    "child_1" => {
        "grandchild_1",
        "grandchild_2",
    },
    "child_2",
    "child_3",
});

assert_eq!(root.child_count(arena), 3);
assert_eq!(root.descendants(arena).count(), 6);
```

### Building a file system tree

```rust
use indextree::Arena;

let arena = &mut Arena::new();
let root = arena.new_node("/");
let etc = root.append_value("etc/", arena);
let usr = root.append_value("usr/", arena);

etc.append_value("hosts", arena);
etc.append_value("resolv.conf", arena);

let bin = usr.append_value("bin/", arena);
bin.append_value("rustc", arena);

// Traverse and collect paths
let descendants: Vec<_> = root
    .descendants(arena)
    .map(|id| *arena[id].get())
    .collect();
assert_eq!(
    descendants,
    vec!["/", "etc/", "hosts", "resolv.conf", "usr/", "bin/", "rustc"]
);
```

### Parallel iteration

With the `par_iter` feature, trees can be traversed in parallel using
[rayon](https://crates.io/crates/rayon):

```rust,ignore
use indextree::Arena;
use rayon::prelude::*;

let arena = &mut Arena::new();
let root = arena.new_node(0);
for i in 1..=1000 {
    root.append_value(i, arena);
}

let sum: i64 = arena.par_iter().map(|node| *node.get()).sum();
assert_eq!(sum, 500500);
```

### `no_std` usage

Disable default features and the crate works in `no_std` environments
(requires `alloc`):

```toml
[dependencies]
indextree = { version = "4", default-features = false }
```