pulau_rs/
quickfind.rs

1//! Quick Find implementations
2
3use core::marker::PhantomData;
4
5use crate::{
6    quickunion::Heuristic, rng::PhantomRng, AlgorithmContainer, Borrowed, Connected, Find, Owned,
7    Union, UnionFind, VertexType,
8};
9
10/// [`QuickFind`] algorithm
11#[derive(Debug, Default)]
12pub struct QuickFind<K = Owned> {
13    _p: PhantomData<K>,
14}
15
16pub struct NoHeuristic;
17
18impl Heuristic for NoHeuristic {
19    type RngProvider = PhantomRng;
20
21    fn handle_decision<T>(
22        _a: T::IdentifierType,
23        _b: T::IdentifierType,
24        _heuristic: &mut [usize],
25        _representative: &mut [T],
26        _r: &mut Self::RngProvider,
27    ) where
28        T: VertexType,
29    {
30        unreachable!("Should not be called!")
31    }
32}
33
34impl AlgorithmContainer for QuickFind<Owned> {
35    type HeuristicKind<'a> = NoHeuristic;
36    type HeuristicContainer<'a, const N: usize> = [usize; 0];
37    type RepresentativeContainer<'a, R: VertexType + 'a, const N: usize> = [R; N];
38    type RngKind<'a> = PhantomRng;
39}
40
41impl AlgorithmContainer for QuickFind<Borrowed> {
42    type HeuristicKind<'a> = NoHeuristic;
43    type HeuristicContainer<'a, const N: usize> = [usize; 0];
44    type RepresentativeContainer<'a, R: VertexType + 'a, const N: usize> = &'a mut [R];
45    type RngKind<'a> = PhantomRng;
46}
47
48macro_rules! generate_default_ctor_quickfind {
49    ($($num_type:ident), *) => {
50        $(
51        impl<const N: usize> Default for UnionFind<'_, QuickFind, $num_type, N>
52        {
53            fn default() -> Self {
54                let mut representative = [0; N];
55
56                for i in 0..(N as $num_type) {
57                    representative[i as usize] = i;
58                }
59
60                Self {
61                    representative,
62                    heuristic: [0; 0],
63                    algorithm: Default::default(),
64                    rng: PhantomRng
65                }
66            }
67        }
68        )*
69    };
70}
71
72impl<'a, T, const N: usize> UnionFind<'a, QuickFind<Borrowed>, T, N>
73where
74    T: VertexType,
75{
76    pub fn new(representative: &'a mut [T]) -> Self {
77        Self {
78            representative,
79            heuristic: [0; 0],
80            algorithm: Default::default(),
81            rng: PhantomRng,
82        }
83    }
84}
85
86impl<T, K> Connected<T> for QuickFind<K>
87where
88    T: VertexType,
89    Self: Find<T>,
90{
91    fn connected(representative: &mut [T], a: T::IdentifierType, b: T::IdentifierType) -> bool {
92        Self::find(representative, a) == Self::find(representative, b)
93    }
94}
95
96impl<T, K> Union<T, NoHeuristic> for QuickFind<K>
97where
98    T: VertexType,
99    Self: Find<T>,
100{
101    fn union_sets(
102        representative: &mut [T],
103        _heuristic: &mut [usize],
104        a: T::IdentifierType,
105        b: T::IdentifierType,
106        _r: &mut PhantomRng,
107    ) {
108        let root_a = Self::find(representative, a);
109        let root_b = Self::find(representative, b);
110        for item in representative {
111            if *item == root_a {
112                *item = root_b;
113            }
114        }
115    }
116}
117
118impl<T, K> Find<T> for QuickFind<K>
119where
120    T: VertexType,
121{
122    fn find(representative: &mut [T], a: T::IdentifierType) -> T {
123        assert!(T::usize(a) < representative.len());
124        representative[T::usize(a)]
125    }
126}
127
128generate_default_ctor_quickfind!(u8, u16, u32, u64, usize);
129
130#[cfg(test)]
131mod tests {
132    use crate::{rng::PhantomRng, tests::CityVertex, Borrowed, QuickFind, UnionFind};
133    use core::{mem, panic};
134
135    #[test]
136    fn test_qf() {
137        let mut uf = UnionFind::<QuickFind, u32, 10>::default();
138        uf.union_sets(4, 3);
139        uf.union_sets(3, 8);
140        uf.union_sets(6, 5);
141        uf.union_sets(9, 4);
142        assert!(uf.connected(3, 9));
143    }
144
145    #[test]
146    fn test_qf_slice() {
147        let mut representative = (0..10).collect::<heapless::Vec<_, 10>>();
148        let mut uf = UnionFind::<QuickFind<Borrowed>, u32, 10>::new(representative.as_mut());
149        uf.union_sets(4, 3);
150        uf.union_sets(3, 8);
151        uf.union_sets(6, 5);
152        uf.union_sets(9, 4);
153        assert!(uf.connected(3, 9));
154    }
155
156    impl<'a, const N: usize> TryFrom<[CityVertex<'a>; N]>
157        for UnionFind<'_, QuickFind, CityVertex<'a>, N>
158    {
159        type Error = &'static str;
160
161        fn try_from(cities: [CityVertex<'a>; N]) -> Result<Self, Self::Error> {
162            for id in 0..N {
163                if cities[id].id as usize != id {
164                    return Err("Invalid cities id!");
165                }
166            }
167
168            Ok(Self {
169                representative: cities,
170                heuristic: [0; 0],
171                algorithm: Default::default(),
172                rng: PhantomRng,
173            })
174        }
175    }
176
177    #[test]
178    fn test_custom_type() {
179        let cities = [
180            CityVertex::new(0, "Zurich", 320),
181            CityVertex::new(1, "Munich", 210),
182            CityVertex::new(2, "Paris", 180),
183            CityVertex::new(3, "London", 190),
184            CityVertex::new(4, "Oslo", 250),
185            CityVertex::new(5, "Stockholm", 280),
186            CityVertex::new(6, "Helsinki", 280),
187        ];
188
189        let mut uf = UnionFind::<QuickFind, CityVertex<'static>, 7>::try_from(cities).unwrap();
190        uf.union_sets(4, 3);
191        uf.union_sets(3, 2);
192        uf.union_sets(6, 5);
193        assert!(uf.connected(4, 2));
194        assert!(uf.connected(6, 5));
195    }
196
197    #[test]
198    fn test_sz() {
199        assert_eq!(
200            mem::size_of::<[u32; 10]>(),
201            mem::size_of::<UnionFind::<'_, QuickFind, u32, 10>>()
202        );
203        assert_eq!(
204            mem::size_of::<&'_ [u32]>(),
205            mem::size_of::<UnionFind::<'_, QuickFind<Borrowed>, u32, 10>>()
206        );
207        assert_eq!(
208            mem::size_of::<[CityVertex<'_>; 10]>(),
209            mem::size_of::<UnionFind::<'_, QuickFind, CityVertex<'_>, 10>>()
210        );
211    }
212
213    #[test]
214    fn test_getter() {
215        let mut uf = UnionFind::<QuickFind, u32, 10>::default();
216        uf.union_sets(4, 3);
217        uf.union_sets(3, 8);
218        uf.union_sets(6, 5);
219        uf.union_sets(9, 4);
220        for _ in uf.heuristic() {
221            panic!("Should not even loop!");
222        }
223    }
224}
pulau_rs/quickfind.rs

pulau_rs/
quickfind.rs
