union_find/
traits.rs

1// Copyright 2016 union-find-rs Developers
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8use std::iter::FromIterator;
9
10/// The value that can be contained with `Union`.
11pub trait Union: Sized {
12    /// Union two value into one.
13    ///
14    /// This is used by `UnionFind::union` operation.
15    fn union(lval: Self, rval: Self) -> UnionResult<Self>;
16}
17
18/// Return value of the [`Union::union`].
19#[allow(missing_docs)]
20#[derive(Copy, Clone, Debug)]
21pub enum UnionResult<T> {
22    Left(T),
23    Right(T),
24}
25
26/// APIs for Union-Find operation.
27pub trait UnionFind<V: Union>: FromIterator<V> + Extend<V> + Sized {
28    /// Creates empty `UnionFind` struct.
29    #[inline]
30    fn new(len: usize) -> Self
31    where
32        V: Default,
33    {
34        Self::from_iter((0..len).map(|_| Default::default()))
35    }
36
37    /// Returns the size of `self`.
38    fn size(&self) -> usize;
39
40    /// Inserts a new set into the union.
41    ///
42    /// Returns the key of the inserted set.
43    fn insert(&mut self, data: V) -> usize;
44
45    /// Join two sets that contains given keys (union operation).
46    ///
47    /// Returns `true` if these keys are belonged to different sets.
48    fn union(&mut self, key0: usize, key1: usize) -> bool;
49
50    /// Returns the identifier of the set that the key belongs to.
51    fn find(&mut self, key: usize) -> usize;
52
53    /// Returns the reference to the value of the set that the key belongs to.
54    fn get(&mut self, key: usize) -> &V;
55
56    /// Returns the mutable reference to the value of the set that the key belongs to.
57    fn get_mut(&mut self, key: usize) -> &mut V;
58}
union_find/traits.rs

union_find/
traits.rs
