pstree 0.1.0

Segment Tree of Placements
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

# Segment Tree of Placements

The `pstree` crate allows you to create an `n` to `k` segment tree of placements based on a `key` in the range `0..=n`.
This `key` will be used as the root and leaves of the tree.
So other vertices will be taken in the ranges `0..key` and `key + 1..=n`.

The structure is designed to quickly respond to queries to change a vertex or edge in a weighted directed graph that allows edges of negative weight.

## Example

```rust
use pstree::PSTree;

fn main() {
    let pstree = PSTree::new(3, 2, 0, 0);
    let _shortest = pstree.update_vertex(1, 1);
    let _shortest = pstree.update_edge(0, 1, 2);
}
```

The `PSTree::new(3, 2, 0, 0)` creates a `3` by `2` tree of placements based on key `0` with initial value `0`:

```
0
├── 1
│   ├── 2
│   │   └── 0
│   └── 3
│       └── 0
├── 2
│   ├── 1
│   │   └── 0
│   └── 3
│       └── 0
└── 3
    ├── 1
    │   └── 0
    └── 2
        └── 0
```

The `pstree.update_vertex(1, 1)` updates vertex `1` with value `1`, so the distances will be recalculated, returning the shortest distance from `key` of length `k`:

```
0
├── 1
│   '-- 2
│   '   '-- 0
│   '-- 3
│       '-- 0
├── 2
│   ├── 1
│   │   '-- 0
│   └── 3
│       └── 0
└── 3
    ├── 1
    │   '-- 0
    └── 2
        └── 0
```

The `pstree.update_edge(0, 1, 2)` updates edge from `0` to `1` with value `2`, so the distances will be recalculated, returning the shortest distance from `key` of length `k`:

```
0
'-- 1
│   '-- 2
│   '   '-- 0
│   '-- 3
│       '-- 0
├── 2
│   ├── 1
│   │   └── 0
│   └── 3
│       └── 0
└── 3
    ├── 1
    │   └── 0
    └── 2
        └── 0
```

## Usage

```
[dependencies]
pstree = "0.1"
```

## License

Licensed under either of

* MIT license
  ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
* Apache License, Version 2.0
  ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)

at your option.