intrex 0.2.0

Intrusive collections with items addressed by indices
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

# intrex
    
<p>
<a href="https://docs.rs/intrex/"><img src="https://docs.rs/intrex/badge.svg" alt="docs.rs"></a> <a href="https://crates.io/crates/intrex"><img src="https://img.shields.io/crates/v/intrex"></a> <img src="https://img.shields.io/badge/license-MIT%2FApache--2.0-blue">
</p>

Intrusive collections with items stored in an application-provided object pool and addressed by indices.

## Features

- `#![no_std]` + no-`alloc`

- Intrusive doubly-linked lists

- Intrusive binary trees with optional search capability
    - Unbalanced
    - Red-black with reshaping hooks (useful for implementing [order-statistic trees][1], etc.; see `tests/rbtree_order_stats.rs` for an example)

- A generic subroutine to sort singly-linked lists

## Example: Doubly-Linked List

```rust
use intrex::list::{Head, Link};

struct Node {
    value: i32,
    siblings: Option<Link>,
}

let mut nodes: Vec<_> = (0..4)
    .map(|value| Node { value, siblings: None })
    .collect();
let mut head = Head::default();

// Add [2, 3, 1, 0] to the list
let mut accessor = head.write_ref(&mut nodes, |n: &mut Node| &mut n.siblings);
accessor.push_back(3);
accessor.push_back(0);
accessor.insert(1, Some(0));
accessor.push_front(2);

// Inspect the list
let accessor = head.read_ref(&nodes, |n| &n.siblings);
assert_eq!(accessor.front().unwrap().value, 2);
assert_eq!(accessor.back().unwrap().value, 0);
assert_eq!(
    accessor.values().map(|n| n.value).collect::<Vec<_>>(),
    vec![2, 3, 1, 0],
);

// Sort the list
head.write_ref(&mut nodes, |n: &mut Node| &mut n.siblings)
    .sort_by_key(|nodes, i| nodes.pool[i].value);

let accessor = head.read_ref(&nodes, |n| &n.siblings);
assert_eq!(
    accessor.values().map(|n| n.value).collect::<Vec<_>>(),
    vec![0, 1, 2, 3],
);
```

## License

MIT/Apache-2.0

[1]: https://en.wikipedia.org/wiki/Order_statistic_tree