pulau_rs/quickunion/heuristics/
by_rank.rs

1//! ByRank heuristic for QuickUnion
2
3use core::marker::PhantomData;
4
5use crate::{Owned, VertexType, quickunion::Heuristic, rng::PhantomRng};
6
7pub struct ByRank<K = Owned>(PhantomData<K>);
8
9impl<K> Heuristic for ByRank<K> {
10    type RngProvider = PhantomRng;
11
12    #[inline(always)]
13    fn handle_decision<T>(
14        mut a: T::IdentifierType,
15        mut b: T::IdentifierType,
16        rank: &mut [usize],
17        representative: &mut [T],
18        _r: &mut Self::RngProvider,
19    ) where
20        T: VertexType,
21    {
22        if a != b {
23            if rank[T::usize(a)] < rank[T::usize(b)] {
24                core::mem::swap(&mut a, &mut b);
25            }
26            representative[T::usize(b)] = representative[T::usize(a)];
27            if rank[T::usize(a)] == rank[T::usize(b)] {
28                rank[T::usize(a)] += 1;
29            }
30        }
31    }
32}

pulau_rs/quickunion/heuristics/by_rank.rs

pulau_rs/quickunion/heuristics/
by_rank.rs