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 divides the elements of this vector in sets.
The elements each start in their own set and these 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.
α(n) has value below 5 for any n that can be written in the observable
universe. The elements of the iterator returned by set are found in O(1)
time.
This can be used for example to keep track of the connected components of an undirected graph. This struct can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle. The Union–Find 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.
For each element of a PartitionVec<T> we need to store three additional
usize values. A more compact implementation is included that has the same
functionality but only needs to store an additional two usize values.
This is done by using a few bits of these two values to store the third.
On 32 bit and 64 bit systems we use 3 bits, this means a PartitionVec<T> can
store 536870912 and 2305843009213693952 values respectfully and will
panic if we go above this limit.
This is 8 times less than the amount of memory addresses but should still be
enough for the fast majority of uses.
This is a feature and can be enabled by adding the following to your
Cargo.toml file:
toml
[dependencies.partitions]
version = "0.1"
features = ["compact"]
The recommended way to use this crate is to add a line into your Cargo.toml
such as:
toml
[dependencies]
partitions = "0.1"
and then add the following to to your lib.rs or main.rs:
rust
extern crate partitions;
Partitions is distributed under the terms of the Apache License (Version 2.0).