pulau_rs/quickunion/
mod.rs

1use crate::{Owned, VertexType};
2use core::marker::PhantomData;
3use rand_core::RngCore;
4
5pub mod algorithm_container;
6pub mod borrowed_impls;
7pub mod constructors;
8pub mod heuristics;
9pub mod traits_impl;
10
11pub use heuristics::{ByRandom, ByRank, BySize, Unweighted};
12
13/// Heuristic for quick union algorithm
14pub trait Heuristic {
15    type RngProvider: RngCore;
16
17    fn handle_decision<T>(
18        a: T::IdentifierType,
19        b: T::IdentifierType,
20        heuristic: &mut [usize],
21        representative: &mut [T],
22        r: &mut Self::RngProvider,
23    ) where
24        T: VertexType;
25}
26
27/// [`QuickUnion`] algorithm
28///
29/// This algorithm is parameterized by the following
30/// - `H` - Heuristic Type. Available types: [`ByRank`], [`BySize`], [`Unweighted`]
31/// - `COMPRESS_PATH` - boolean value, enables path compression during find operation
32///
33/// By default, [`ByRank`] heuristic is used and path compression is enabled
34#[derive(Debug, Default)]
35pub struct QuickUnion<H = ByRank<Owned>, const COMPRESS_PATH: bool = true> {
36    heuristic: PhantomData<H>,
37}
38
39// Tests for ByRandom heuristic
40#[cfg(test)]
41mod by_random_tests {
42    use crate::{quickunion::heuristics::ByRandom, UnionFind};
43
44    use super::*;
45
46    use rand_core::SeedableRng;
47    use rand_hc::Hc128Rng;
48
49    #[cfg(test)]
50    mod size_tests {
51        use core::mem;
52
53        use rand_core::SeedableRng;
54        use rand_hc::Hc128Rng;
55
56        use crate::{quickunion::ByRandom, Borrowed, Fat, Owned, QuickUnion, Thin, UnionFind};
57
58        #[test]
59        fn test_one_union() {
60            // Use a seeded RNG for deterministic tests
61            let rng = Hc128Rng::seed_from_u64(67);
62            let mut uf = UnionFind::<QuickUnion<ByRandom<Hc128Rng, Owned>>, u8, 2>::new(rng);
63
64            uf.union_sets(0, 1);
65
66            assert!(uf.connected(0, 1));
67        }
68
69        #[test]
70        fn test_size() {
71            const N: usize = 128;
72            assert_eq!(
73                mem::size_of::<UnionFind::<'_, QuickUnion<ByRandom<Hc128Rng, Owned>, false>, u8, N>>(
74                ),
75                mem::size_of::<[u8; N]>()
76                    + mem::size_of::<[usize; 0]>()
77                    + mem::size_of::<Hc128Rng>()
78            );
79        }
80
81        #[test]
82        fn test_size_borrowed_rng() {
83            const N: usize = 128;
84            assert_eq!(
85                mem::size_of::<
86                    UnionFind::<'_, QuickUnion<ByRandom<&mut Hc128Rng, Owned>, false>, u8, N>,
87                >(),
88                mem::size_of::<[u8; N]>()
89                    + mem::size_of::<[usize; 0]>()
90                    + mem::size_of::<&Hc128Rng>()
91            );
92        }
93
94        #[test]
95        fn borrowed_rng_ctor() {
96            const N: usize = 10;
97            let mut rng = Hc128Rng::seed_from_u64(67);
98
99            let mut uf =
100                UnionFind::<'_, QuickUnion<ByRandom<&mut Hc128Rng, Owned>, false>, u8, N>::new(
101                    &mut rng,
102                );
103
104            uf.union_sets(0, 1);
105
106            assert!(uf.connected(0, 1));
107        }
108
109        #[test]
110        fn test_size_padded() {
111            const M: usize = 100;
112
113            assert_eq!(
114                mem::size_of::<UnionFind::<'_, QuickUnion<ByRandom<Hc128Rng, Owned>, false>, u8, M>>(
115                ),
116                mem::size_of::<[u8; M]>()
117                    + mem::size_of::<[usize; 0]>()
118                    + mem::size_of::<Hc128Rng>()
119                    + 4 // padding
120            );
121        }
122
123        #[test]
124        fn test_size_borrowed_thin() {
125            const N: usize = 128;
126            assert_eq!(
127                mem::size_of::<
128                    UnionFind::<'_, QuickUnion<ByRandom<Hc128Rng, Borrowed<Thin>>, false>, u8, N>,
129                >(),
130                mem::size_of::<&[u8; N]>() + mem::size_of::<Hc128Rng>()
131            );
132        }
133
134        #[test]
135        fn test_size_borrowed_fat() {
136            const N: usize = 128;
137            assert_eq!(
138                mem::size_of::<
139                    UnionFind::<'_, QuickUnion<ByRandom<Hc128Rng, Borrowed<Fat>>, false>, u8, N>,
140                >(),
141                mem::size_of::<&[u8]>() + mem::size_of::<Hc128Rng>()
142            );
143        }
144    }
145
146    #[test]
147    fn test_by_random_basic() {
148        // Use a seeded RNG for deterministic tests
149        let rng = Hc128Rng::seed_from_u64(67);
150        let mut uf = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 10>::new(rng);
151
152        uf.union_sets(0, 1);
153        uf.union_sets(2, 3);
154        uf.union_sets(4, 5);
155
156        // These should be connected
157        assert!(uf.connected(0, 1));
158        assert!(uf.connected(2, 3));
159        assert!(uf.connected(4, 5));
160
161        // These should not be connected
162        assert!(!uf.connected(1, 2));
163        assert!(!uf.connected(2, 5));
164    }
165}
166
167#[cfg(test)]
168mod tests {
169    use super::{BySize, Heuristic, Unweighted};
170    use crate::{
171        rng::PhantomRng, tests::CityVertex, AlgorithmContainer, Borrowed, ByRank, QuickUnion, Thin,
172        UnionFind, VertexType,
173    };
174    use core::mem;
175
176    #[test]
177    fn test_qu() {
178        let mut uf = UnionFind::<QuickUnion<Unweighted, false>, u8, 10>::default();
179        uf.union_sets(4, 3);
180        uf.union_sets(3, 8);
181        uf.union_sets(6, 5);
182        uf.union_sets(9, 4);
183        assert!(uf.connected(3, 9));
184    }
185
186    #[test]
187    fn test_getter_qu() {
188        let mut uf = UnionFind::<QuickUnion<Unweighted, false>, u8, 10>::default();
189        uf.union_sets(4, 3);
190        uf.union_sets(3, 8);
191        uf.union_sets(6, 5);
192        uf.union_sets(9, 4);
193        for _ in uf.heuristic() {
194            panic!("Should not even loop!");
195        }
196    }
197
198    #[test]
199    fn test_qu_mem_owned_u32() {
200        assert_eq!(
201            mem::size_of::<[u32; 10]>(),
202            mem::size_of::<UnionFind::<'_, QuickUnion<Unweighted, false>, u32, 10>>()
203        );
204    }
205
206    #[test]
207    fn test_qu_mem_owned_city_vertex() {
208        assert_eq!(
209            mem::size_of::<[CityVertex<'_>; 10]>(),
210            mem::size_of::<UnionFind::<'_, QuickUnion<Unweighted, false>, CityVertex<'_>, 10>>()
211        );
212    }
213
214    #[test]
215    fn test_qu_mem_borrowed_u32() {
216        assert_eq!(
217            mem::size_of::<&[u32]>(),
218            mem::size_of::<UnionFind::<'_, QuickUnion<Unweighted<Borrowed>, false>, u32, 10>>()
219        );
220    }
221
222    #[test]
223    fn test_qu_mem_borrowed_city_vertex() {
224        assert_eq!(
225            mem::size_of::<&[CityVertex<'_>]>(),
226            mem::size_of::<
227                UnionFind::<'_, QuickUnion<Unweighted<Borrowed>, false>, CityVertex<'_>, 10>,
228            >()
229        );
230    }
231
232    #[test]
233    fn test_qu_mem_borrowed_thin_u32() {
234        // HeuristicContainer is [usize; 0] (zero-sized), so only the representative pointer counts
235        assert_eq!(
236            mem::size_of::<&[u32; 10]>(),
237            mem::size_of::<UnionFind::<'_, QuickUnion<Unweighted<Borrowed<Thin>>, false>, u32, 10>>(
238            )
239        );
240    }
241
242    #[test]
243    fn test_qu_mem_borrowed_thin_city_vertex() {
244        // HeuristicContainer is [usize; 0] (zero-sized), so only the representative pointer counts
245        assert_eq!(
246            mem::size_of::<&[CityVertex<'_>; 10]>(),
247            mem::size_of::<
248                UnionFind::<'_, QuickUnion<Unweighted<Borrowed<Thin>>, false>, CityVertex<'_>, 10>,
249            >()
250        );
251    }
252
253    #[test]
254    fn test_qupc() {
255        let mut uf = UnionFind::<QuickUnion<Unweighted, true>, u8, 10>::default();
256        uf.union_sets(4, 3);
257        uf.union_sets(3, 8);
258        uf.union_sets(6, 5);
259        uf.union_sets(9, 4);
260        assert!(uf.connected(3, 9));
261    }
262
263    #[test]
264    fn test_getter_qupc() {
265        let mut uf = UnionFind::<QuickUnion<Unweighted, true>, u8, 10>::default();
266        uf.union_sets(4, 3);
267        uf.union_sets(3, 8);
268        uf.union_sets(6, 5);
269        uf.union_sets(9, 4);
270        for _ in uf.heuristic() {
271            panic!("Should not even loop!");
272        }
273    }
274
275    #[test]
276    fn test_qupc_mem_owned_u32() {
277        assert_eq!(
278            mem::size_of::<[u32; 10]>(),
279            mem::size_of::<UnionFind::<'_, QuickUnion<Unweighted, true>, u32, 10>>()
280        );
281    }
282
283    #[test]
284    fn test_qupc_mem_owned_city_vertex() {
285        assert_eq!(
286            mem::size_of::<[CityVertex<'_>; 10]>(),
287            mem::size_of::<UnionFind::<'_, QuickUnion<Unweighted, true>, CityVertex<'_>, 10>>()
288        );
289    }
290
291    #[test]
292    fn test_wqupc_sz() {
293        let mut uf = UnionFind::<QuickUnion<BySize>, u8, 10>::default();
294        uf.union_sets(1, 2);
295        uf.union_sets(2, 3);
296        uf.union_sets(3, 4);
297        assert_eq!([1, 4, 1, 1, 1, 1, 1, 1, 1, 1], uf.heuristic);
298        uf.union_sets(5, 6);
299        uf.union_sets(6, 7);
300        uf.union_sets(7, 8);
301        uf.union_sets(8, 9);
302        assert_eq!([1, 4, 1, 1, 1, 5, 1, 1, 1, 1], uf.heuristic);
303        assert_eq!([0, 1, 1, 1, 1, 5, 5, 5, 5, 5], uf.representative);
304        uf.union_sets(4, 5);
305        assert_eq!([0, 5, 1, 1, 1, 5, 5, 5, 5, 5], uf.representative);
306    }
307
308    #[test]
309    fn test_wqupc_sz_mem_owned_u32() {
310        assert_eq!(
311            mem::size_of::<[u32; 10]>() + mem::size_of::<[usize; 10]>(),
312            mem::size_of::<UnionFind::<'_, QuickUnion<BySize>, u32, 10>>()
313        );
314    }
315
316    #[test]
317    fn test_wqupc_sz_mem_borrowed_u32() {
318        assert_eq!(
319            mem::size_of::<&[u32]>() + mem::size_of::<&[usize]>(),
320            mem::size_of::<UnionFind::<'_, QuickUnion<BySize<Borrowed>>, u32, 10>>()
321        );
322    }
323
324    #[test]
325    fn test_wqupc_sz_mem_owned_city_vertex() {
326        assert_eq!(
327            mem::size_of::<[CityVertex<'_>; 10]>() + mem::size_of::<[usize; 10]>(),
328            mem::size_of::<UnionFind::<'_, QuickUnion<BySize, true>, CityVertex<'_>, 10>>()
329        );
330    }
331
332    #[test]
333    fn test_wqupc_sz_mem_borrowed_city_vertex() {
334        assert_eq!(
335            mem::size_of::<&'_ [CityVertex<'_>]>() + mem::size_of::<&'_ [usize]>(),
336            mem::size_of::<UnionFind::<'_, QuickUnion<BySize<Borrowed>, true>, CityVertex<'_>, 10>>(
337            )
338        );
339    }
340
341    #[test]
342    fn test_wqupc_rank() {
343        let mut uf = UnionFind::<QuickUnion, u8, 12>::default();
344        uf.union_sets(1, 2);
345        uf.union_sets(2, 3);
346        uf.union_sets(3, 4);
347        assert_eq!([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], uf.heuristic);
348        uf.union_sets(5, 6);
349        uf.union_sets(6, 7);
350        uf.union_sets(7, 8);
351        uf.union_sets(8, 9);
352        assert_eq!([0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
353        assert_eq!([0, 1, 1, 1, 1, 5, 5, 5, 5, 5, 10, 11], uf.representative);
354        uf.union_sets(4, 5);
355        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 11], uf.representative);
356        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
357        uf.union_sets(4, 11);
358        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 1], uf.representative);
359        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
360    }
361
362    #[test]
363    fn test_wqupc_rank_mem_owned_u32() {
364        assert_eq!(
365            mem::size_of::<[u32; 10]>() + mem::size_of::<[usize; 10]>(),
366            mem::size_of::<UnionFind::<'_, QuickUnion, u32, 10>>()
367        );
368    }
369
370    #[test]
371    fn test_wqupc_rank_mem_borrowed_u32() {
372        assert_eq!(
373            mem::size_of::<&[u32]>() + mem::size_of::<&[usize]>(),
374            mem::size_of::<UnionFind::<'_, QuickUnion<ByRank<Borrowed>>, u32, 10>>()
375        );
376    }
377
378    #[test]
379    fn test_wqupc_rank_mem_owned_city_vertex() {
380        assert_eq!(
381            mem::size_of::<[CityVertex<'_>; 10]>() + mem::size_of::<[usize; 10]>(),
382            mem::size_of::<UnionFind::<'_, QuickUnion, CityVertex<'_>, 10>>()
383        );
384    }
385
386    struct ByRankHeaplessVec;
387
388    impl AlgorithmContainer for QuickUnion<ByRankHeaplessVec> {
389        type HeuristicKind<'a> = ByRankHeaplessVec;
390        type HeuristicContainer<'a, const N: usize> = heapless::Vec<usize, N>;
391        type RepresentativeContainer<'a, R: VertexType + 'a, const N: usize> = heapless::Vec<R, N>;
392        type RngKind<'a> = PhantomRng;
393    }
394
395    impl<const N: usize> UnionFind<'_, QuickUnion<ByRankHeaplessVec>, u8, N> {
396        pub fn new() -> Self {
397            let mut representative = heapless::Vec::<_, N>::new();
398            let _ = representative.resize(N, 0);
399
400            for i in 0..(N as u8) {
401                representative[i as usize] = i;
402            }
403
404            let heuristic = heapless::Vec::<usize, N>::from_slice(&[0; N]).unwrap();
405
406            Self {
407                representative,
408                heuristic,
409                algorithm: Default::default(),
410                rng: PhantomRng,
411            }
412        }
413    }
414
415    impl Heuristic for ByRankHeaplessVec {
416        type RngProvider = PhantomRng;
417
418        #[inline(always)]
419        fn handle_decision<T>(
420            mut a: T::IdentifierType,
421            mut b: T::IdentifierType,
422            rank: &mut [usize],
423            representative: &mut [T],
424            _r: &mut Self::RngProvider,
425        ) where
426            T: VertexType,
427        {
428            if a != b {
429                if rank[T::usize(a)] < rank[T::usize(b)] {
430                    core::mem::swap(&mut a, &mut b);
431                }
432                representative[T::usize(b)] = representative[T::usize(a)];
433                if rank[T::usize(a)] == rank[T::usize(b)] {
434                    rank[T::usize(a)] += 1;
435                }
436            }
437        }
438    }
439
440    #[test]
441    fn test_wqupc_rank_mem_heapless_vec_u8() {
442        assert_eq!(
443            mem::size_of::<heapless::Vec<u8, 12>>() + mem::size_of::<heapless::Vec<usize, 12>>(),
444            mem::size_of::<UnionFind::<'_, QuickUnion<ByRankHeaplessVec>, u8, 12>>()
445        );
446    }
447
448    #[test]
449    fn test_wqupc_rank_mem_heapless_vec_city_vertex() {
450        assert_eq!(
451            mem::size_of::<heapless::Vec<CityVertex<'_>, 10>>()
452                + mem::size_of::<heapless::Vec<usize, 10>>(),
453            mem::size_of::<UnionFind::<'_, QuickUnion<ByRankHeaplessVec>, CityVertex<'_>, 10>>()
454        );
455    }
456
457    #[test]
458    fn test_vec_heapless() {
459        let mut uf = UnionFind::<QuickUnion<ByRankHeaplessVec>, u8, 12>::new();
460
461        uf.union_sets(1, 2);
462        uf.union_sets(2, 3);
463        uf.union_sets(3, 4);
464        assert_eq!([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], uf.heuristic);
465        uf.union_sets(5, 6);
466        uf.union_sets(6, 7);
467        uf.union_sets(7, 8);
468        uf.union_sets(8, 9);
469        assert_eq!([0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
470        assert_eq!([0, 1, 1, 1, 1, 5, 5, 5, 5, 5, 10, 11], uf.representative);
471        uf.union_sets(4, 5);
472        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 11], uf.representative);
473        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
474        uf.union_sets(4, 11);
475        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 1], uf.representative);
476        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
477    }
478
479    #[test]
480    fn test_vec_heapless_borrowed() {
481        const N: usize = 12;
482        let mut representative = heapless::Vec::<_, N>::new();
483        let _ = representative.resize(N, 0);
484
485        for i in 0..(N as u8) {
486            representative[i as usize] = i;
487        }
488
489        let mut heuristic = heapless::Vec::<usize, N>::from_slice(&[0; N]).unwrap();
490
491        let mut uf = UnionFind::<QuickUnion<ByRank<Borrowed>>, u8, 12>::new(
492            &mut representative,
493            &mut heuristic,
494        );
495
496        uf.union_sets(1, 2);
497        uf.union_sets(2, 3);
498        uf.union_sets(3, 4);
499        assert_eq!([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], uf.heuristic);
500        uf.union_sets(5, 6);
501        uf.union_sets(6, 7);
502        uf.union_sets(7, 8);
503        uf.union_sets(8, 9);
504        assert_eq!([0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
505        assert_eq!([0, 1, 1, 1, 1, 5, 5, 5, 5, 5, 10, 11], uf.representative);
506        uf.union_sets(4, 5);
507        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 11], uf.representative);
508        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
509        uf.union_sets(4, 11);
510        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 1], uf.representative);
511        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
512    }
513
514    #[test]
515    fn test_slice() {
516        let mut representative = (0..12).collect::<heapless::Vec<u8, 12>>();
517        let mut heuristic = heapless::Vec::<usize, 12>::from_slice(&[0; 12]).unwrap();
518
519        let mut uf = UnionFind::<QuickUnion<ByRank<Borrowed>>, u8, 12>::new(
520            &mut representative,
521            &mut heuristic,
522        );
523
524        uf.union_sets(1, 2);
525        uf.union_sets(2, 3);
526        uf.union_sets(3, 4);
527        assert_eq!([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], uf.heuristic);
528        uf.union_sets(5, 6);
529        uf.union_sets(6, 7);
530        uf.union_sets(7, 8);
531        uf.union_sets(8, 9);
532        assert_eq!([0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
533        assert_eq!([0, 1, 1, 1, 1, 5, 5, 5, 5, 5, 10, 11], uf.representative);
534        uf.union_sets(4, 5);
535        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 11], uf.representative);
536        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
537        uf.union_sets(4, 11);
538        assert_eq!([0, 1, 1, 1, 1, 1, 5, 5, 5, 5, 10, 1], uf.representative);
539        assert_eq!([0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], uf.heuristic);
540    }
541
542    #[test]
543    fn test_slice_by_size() {
544        let mut representative = (0..10).collect::<heapless::Vec<_, 10>>();
545        let mut heuristic = heapless::Vec::<usize, 10>::from_slice(&[1; 10]).unwrap();
546
547        let mut uf = UnionFind::<QuickUnion<BySize<Borrowed>>, u8, 10>::new(
548            &mut representative,
549            &mut heuristic,
550        );
551
552        uf.union_sets(1, 2);
553        uf.union_sets(2, 3);
554        uf.union_sets(3, 4);
555        assert_eq!([1, 4, 1, 1, 1, 1, 1, 1, 1, 1], uf.heuristic);
556        uf.union_sets(5, 6);
557        uf.union_sets(6, 7);
558        uf.union_sets(7, 8);
559        uf.union_sets(8, 9);
560        assert_eq!([1, 4, 1, 1, 1, 5, 1, 1, 1, 1], uf.heuristic);
561        assert_eq!([0, 1, 1, 1, 1, 5, 5, 5, 5, 5], uf.representative);
562        uf.union_sets(4, 5);
563        assert_eq!([0, 5, 1, 1, 1, 5, 5, 5, 5, 5], uf.representative);
564    }
565    // #[test]
566    // fn test_by_random_deterministic() {
567    //     // With the same seed, we should get the same results
568    //     let rng1 = Hc128Rng::seed_from_u64(12345);
569    //     let mut uf1 = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 10>::new(rng1);
570
571    //     let rng2 = Hc128Rng::seed_from_u64(12345);
572    //     let mut uf2 = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 10>::new(rng2);
573
574    //     // Perform same operations
575    //     for i in 0..4 {
576    //         uf1.union_sets(i, i + 1);
577    //         uf2.union_sets(i, i + 1);
578    //     }
579
580    //     // Both should have the same representative array
581    //     assert_eq!(uf1.representative, uf2.representative);
582    // }
583
584    // #[test]
585    // fn test_by_random_large_tree() {
586    //     let rng = Hc128Rng::seed_from_u64(999);
587    //     let mut uf = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 20>::new(rng);
588
589    //     // Build a large connected component
590    //     for i in 0..19 {
591    //         uf.union_sets(i, i + 1);
592    //     }
593
594    //     // All elements should be in the same component
595    //     for i in 0..19 {
596    //         assert!(uf.connected(0, i));
597    //     }
598    // }
599
600    // #[test]
601    // fn test_by_random_multiple_components() {
602    //     let rng = Hc128Rng::seed_from_u64(777);
603    //     let mut uf = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 12>::new(rng);
604
605    //     // Create component 1: {0, 1, 2, 3}
606    //     uf.union_sets(0, 1);
607    //     uf.union_sets(1, 2);
608    //     uf.union_sets(2, 3);
609
610    //     // Create component 2: {4, 5, 6}
611    //     uf.union_sets(4, 5);
612    //     uf.union_sets(5, 6);
613
614    //     // Create component 3: {7, 8, 9}
615    //     uf.union_sets(7, 8);
616    //     uf.union_sets(8, 9);
617
618    //     // Verify components
619    //     assert!(uf.connected(0, 3));
620    //     assert!(uf.connected(4, 6));
621    //     assert!(uf.connected(7, 9));
622
623    //     // Verify separation
624    //     assert!(!uf.connected(0, 4));
625    //     assert!(!uf.connected(4, 7));
626    //     assert!(!uf.connected(0, 7));
627    // }
628
629    // #[test]
630    // fn test_by_random_union_same_element() {
631    //     let rng = Hc128Rng::seed_from_u64(555);
632    //     let mut uf = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 10>::new(rng);
633
634    //     // Union an element with itself should be a no-op
635    //     uf.union_sets(5, 5);
636    //     assert_eq!(5, uf.find_set(5));
637    // }
638
639    // #[test]
640    // fn test_by_random_borrowed() {
641    //     let rng = Hc128Rng::seed_from_u64(42);
642    //     let mut representative = (0..10).collect::<heapless::Vec<u8, 10>>();
643    //     let mut heuristic = heapless::Vec::<usize, 10>::from_slice(&[0; 10]).unwrap();
644
645    //     let mut uf = UnionFind::<QuickUnion<ByRandom<Hc128Rng, Borrowed>>, u8, 10>::new_with_rng(
646    //         &mut representative,
647    //         &mut heuristic,
648    //         rng,
649    //     );
650
651    //     uf.union_sets(1, 2);
652    //     uf.union_sets(3, 4);
653    //     uf.union_sets(5, 6);
654
655    //     assert!(uf.connected(1, 2));
656    //     assert!(uf.connected(3, 4));
657    //     assert!(uf.connected(5, 6));
658    //     assert!(!uf.connected(1, 3));
659    // }
660
661    // #[test]
662    // fn test_by_random_different_seeds() {
663    //     // Different seeds should potentially produce different tree structures
664    //     let rng1 = Hc128Rng::seed_from_u64(111);
665    //     let mut uf1 = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 10>::new(rng1);
666
667    //     let rng2 = Hc128Rng::seed_from_u64(222);
668    //     let mut uf2 = UnionFind::<QuickUnion<ByRandom<Hc128Rng>>, u8, 10>::new(rng2);
669
670    //     // Perform same operations
671    //     for i in 0..5 {
672    //         uf1.union_sets(i, i + 1);
673    //         uf2.union_sets(i, i + 1);
674    //     }
675
676    //     // Both should have same connectivity
677    //     for i in 0..5 {
678    //         assert!(uf1.connected(0, i));
679    //         assert!(uf2.connected(0, i));
680    //     }
681
682    //     // But potentially different tree structures (representative arrays may differ)
683    //     // This is expected behavior with random linking
684    // }
685    // }
686}
pulau_rs/quickunion/mod.rs

pulau_rs/quickunion/
mod.rs
