partitions 0.2.0

A disjoint-sets/union-find implementation that allows for efficient iteration over elements of a set.
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

# Partitions

A [disjoint-sets/union-find] implementation of a vector partitioned in sets that
allows for efficient iteration over the elements of a set.

The main struct of this crate is [`PartitionVec<T>`] which has the functionality
of a `Vec<T>` and in addition devides the elements of this vector in sets.
The elements each start in their own set and sets can be joined with the
[`union`] method.
You can check if elements share a set with the [`same_set`] method and iterate
on the elements in a set with the [`set`] method.
The [`union`] and [`same_set`] methods are extremely fast and have an amortized
complexity of `O(α(n))` where 'α' is the inverse Ackermann function and `n` is
the length.
This complexity is proven to be optimal and `α(n)` has value below 5 for any `n`
that can be written in the observable universe.
The next element of the iterator returned by [`set`] is found in `O(1)` time.

The Disjoint-Sets algorithm is used in high-performance implementations of
unification.
It is also a key component in implementing Kruskal's algorithm to find the
minimum spanning tree of a graph.

[disjoint-sets/union-find]:
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
[`PartitionVec<T>`]:
https://docs.rs/partitions/0.2.0/partitions/partition_vec/struct.PartitionVec.html
[`union`]:
https://docs.rs/partitions/0.2.0/partitions/partition_vec/struct.PartitionVec.html#method.union
[`same_set`]:
https://docs.rs/partitions/0.2.0/partitions/partition_vec/struct.PartitionVec.html#method.same_set
[`set`]:
https://docs.rs/partitions/0.2.0/partitions/partition_vec/struct.PartitionVec.html#method.set
[`make_singleton`]:
https://docs.rs/partitions/0.2.0/partitions/partition_vec/struct.PartitionVec.html#method.make_singleton

## Using Partitions

The recommended way to use this crate is to add a line into your `Cargo.toml`
such as:

```toml
[dependencies]
partitions = "0.2"
```

and then add the following to to your `lib.rs` or `main.rs`:

```rust
extern crate partitions;
```

## License

Partitions is distributed under the terms of the Apache License (Version 2.0).