pulau_rs/quickunion/
traits_impl.rs

1//! Trait implementations for QuickUnion: Connected, Union, Find
2
3use crate::{Connected, Find, Union, VertexType, quickunion::Heuristic};
4use super::QuickUnion;
5
6impl<H, T, const PATH_COMPRESS: bool> Connected<T> for QuickUnion<H, PATH_COMPRESS>
7where
8    T: VertexType,
9    Self: Find<T>,
10{
11    fn connected(representative: &mut [T], a: T::IdentifierType, b: T::IdentifierType) -> bool {
12        Self::find(representative, a) == Self::find(representative, b)
13    }
14}
15
16impl<H, T, const COMPRESS_PATH: bool> Union<T, H> for QuickUnion<H, COMPRESS_PATH>
17where
18    T: VertexType,
19    H: Heuristic,
20    Self: Find<T>,
21{
22    fn union_sets<'a>(
23        representative: &mut [T],
24        heuristic: &mut [usize],
25        mut a: T::IdentifierType,
26        mut b: T::IdentifierType,
27        r: &mut H::RngProvider,
28    ) {
29        a = Self::find(representative, a).id();
30        b = Self::find(representative, b).id();
31        H::handle_decision(a, b, heuristic, representative, r)
32    }
33}
34
35impl<H, V: VertexType, const COMPRESS_PATH: bool> Find<V> for QuickUnion<H, COMPRESS_PATH> {
36    fn find(representative: &mut [V], mut a: V::IdentifierType) -> V {
37        while a != representative[V::usize(a)].id() {
38            // path compression
39            if COMPRESS_PATH {
40                representative[V::usize(a)] =
41                    representative[V::usize(representative[V::usize(a)].id()).id()];
42            }
43            a = representative[V::usize(a)].id()
44        }
45        representative[V::usize(a)]
46    }
47}
pulau_rs/quickunion/traits_impl.rs

pulau_rs/quickunion/
traits_impl.rs
