# Crate partitions

source ·## Expand description

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

The main struct of this crate is `PartitionVec<T>`

which has the functionality of a `Vec<T>`

and in addition divides 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.

This implementation stores three integers as `usize`

values for every element in the
`PartitionVec<T>`

, two values are needed to get the best complexity of the Disjoint-Sets
algorithm and the third is used to allow iteration over sets and other methods like the
`make_singleton`

method that removes the element of its current set and gives it its own set.

A more compact implementation is included that has the same functionality but only needs to
store an additional two `usize`

values instead of three for every element.
This is done by using a few bits of these two integers to store the third.
Because this third value is always very small we only need three bits on a 32 or 64 bit system.
This does mean that the maximum amounts of elements stored on 32 and 64 bit systems are
536 870 912 and 2 305 843 009 213 693 952 respectively.
This limit should never be reached under any normal circumstances but if you do the struct
will panic.
This representation can be enabled by adding the following to your `Cargo.toml`

file:

```
[dependencies.partitions]
version = "0.2"
features = ["compact"]
```

## Re-exports

`pub use partition_vec::PartitionVec;`

## Modules

## Macros

`PartitionVec`

containing the arguments.