pulau_rs/
lib.rs

1#![no_std]
2#![cfg_attr(not(debug_assertions), deny(warnings))]
3#![forbid(unsafe_code)]
4#![warn(
5    clippy::all,
6    clippy::await_holding_lock,
7    clippy::char_lit_as_u8,
8    clippy::checked_conversions,
9    clippy::dbg_macro,
10    clippy::debug_assert_with_mut_call,
11    clippy::doc_markdown,
12    clippy::empty_enum,
13    clippy::enum_glob_use,
14    clippy::exit,
15    clippy::expl_impl_clone_on_copy,
16    clippy::explicit_deref_methods,
17    clippy::explicit_into_iter_loop,
18    clippy::fallible_impl_from,
19    clippy::filter_map_next,
20    clippy::float_cmp_const,
21    clippy::fn_params_excessive_bools,
22    clippy::if_let_mutex,
23    clippy::imprecise_flops,
24    clippy::inefficient_to_string,
25    clippy::invalid_upcast_comparisons,
26    clippy::large_types_passed_by_value,
27    clippy::let_unit_value,
28    clippy::linkedlist,
29    clippy::lossy_float_literal,
30    clippy::macro_use_imports,
31    clippy::manual_ok_or,
32    clippy::map_flatten,
33    clippy::match_on_vec_items,
34    clippy::match_same_arms,
35    clippy::match_wildcard_for_single_variants,
36    clippy::mem_forget,
37    clippy::mismatched_target_os,
38    clippy::missing_errors_doc,
39    clippy::missing_safety_doc,
40    clippy::mut_mut,
41    clippy::mutex_integer,
42    clippy::needless_borrow,
43    clippy::needless_continue,
44    clippy::needless_pass_by_value,
45    clippy::option_option,
46    clippy::path_buf_push_overwrite,
47    clippy::ptr_as_ptr,
48    clippy::ref_option_ref,
49    clippy::rest_pat_in_fully_bound_structs,
50    clippy::same_functions_in_if_condition,
51    clippy::string_add_assign,
52    clippy::string_add,
53    clippy::string_lit_as_bytes,
54    clippy::string_to_string,
55    clippy::todo,
56    clippy::trait_duplication_in_bounds,
57    clippy::unimplemented,
58    clippy::unnested_or_patterns,
59    clippy::unused_self,
60    clippy::useless_transmute,
61    clippy::verbose_file_reads,
62    clippy::zero_sized_map_values,
63    future_incompatible,
64    nonstandard_style,
65    rust_2018_idioms
66)]
67#![doc = include_str!("../libdoc.md")]
68
69pub mod quickfind;
70pub mod quickunion;
71pub mod rng;
72
73use core::marker::PhantomData;
74use core::ops::AddAssign;
75
76use rand_core::RngCore;
77
78pub use crate::quickfind::QuickFind;
79use crate::quickunion::Heuristic;
80pub use crate::quickunion::QuickUnion;
81pub use crate::quickunion::{ByRank, BySize, Unweighted};
82
83// slice pointer types
84pub struct Fat;
85pub struct Thin;
86
87pub struct Owned;
88pub struct Borrowed<P: PointerType + ?Sized = Fat>(PhantomData<P>);
89
90pub trait PointerType {}
91impl PointerType for Fat {}
92impl PointerType for Thin {}
93
94/// Any type that can be used to index internal buffer
95pub trait VertexType: Eq + Copy {
96    type IdentifierType: Copy + Eq + PartialOrd + AddAssign<Self::IdentifierType>;
97
98    fn id(&self) -> Self::IdentifierType;
99    fn usize(a: Self::IdentifierType) -> usize;
100}
101
102macro_rules! generate_index_type_impl{
103    ($($num_type:ident), *) => {
104        $(
105            impl VertexType for $num_type {
106                type IdentifierType = Self;
107
108                #[inline(always)]
109                fn id(&self) -> Self {
110                    *self
111                }
112
113                #[inline(always)]
114                fn usize(a: Self) -> usize {
115                    a as usize
116                }
117            }
118        )*
119    };
120}
121
122generate_index_type_impl!(u8, u16, u32, u64, usize);
123
124/// [`UnionFind`] data structure
125///
126/// This data structure stores a collection of disjoint (non-overlapping) sets.
127///
128/// [`UnionFind`] is parameterized by the following
129/// - `A` - Algorithm, e.g., [`QuickFind`], [`QuickUnion`]
130/// - `T` - Any unsigned integral types, e.g., [`u8`], [`u16`], [`u32`], [`u64`], [`usize`] or any type that implements [`VertexType`]
131/// - `N` - Constant size of internal representative buffer
132///
133/// # Example
134/// ```rust
135/// use pulau_rs::{UnionFind, QuickFind, QuickUnion};
136/// fn make_uf_quickfind() {
137///     // construct with quickfind algorithm with fixed size 10
138///     let mut uf = UnionFind::<QuickFind, u32, 10>::default();
139/// }
140///
141/// fn make_uf_quickunion() {
142///     // construct with weighted quickunion with path compression algorithm with fixed size 10
143///     let mut uf = UnionFind::<QuickUnion, u32, 10>::default();
144/// }
145/// ```
146///
147/// # Size Guarantees
148/// Size of [`UnionFind`] depends on whether the algorithm you have chosen is weighted
149///
150/// Assuming no padding,
151/// If it's weighted then, size of [`UnionFind`] is `T * N + size_of(usize) * N`
152///
153/// Else it will be `T * N`
154///
155/// If you are using borrowed buffers, then the size will be the `core::mem::size_of::<usize>() * 2`
156/// if it's weighted, else it will just be `core::mem::size_of::<usize>()`
157pub struct UnionFind<'a, A, T, const N: usize>
158where
159    T: VertexType + 'a,
160    A: AlgorithmContainer,
161{
162    representative: A::RepresentativeContainer<'a, T, N>,
163    heuristic: A::HeuristicContainer<'a, N>,
164    rng: A::RngKind<'a>,
165    algorithm: PhantomData<A>,
166}
167
168impl<'a, A, T, const N: usize> UnionFind<'a, A, T, N>
169where
170    T: VertexType,
171    A: AlgorithmContainer + Union<T, A::HeuristicKind<'a>> + Find<T> + Connected<T>,
172{
173    /// Checks whether 2 nodes are connected to each other
174    pub fn connected(&mut self, a: T::IdentifierType, b: T::IdentifierType) -> bool {
175        A::connected(self.representative.as_mut(), a, b)
176    }
177
178    /// Finds a node
179    pub fn find(&mut self, a: T::IdentifierType) -> T {
180        A::find(self.representative.as_mut(), a)
181    }
182
183    /// Unions 2 node. If those 2 nodes are already part of the same component
184    /// then this does nothing
185    pub fn union_sets(&mut self, a: T::IdentifierType, b: T::IdentifierType) {
186        A::union_sets(
187            self.representative.as_mut(),
188            self.heuristic.as_mut(),
189            a,
190            b,
191            &mut self.rng,
192        )
193    }
194    /// Gets the representative slice
195    pub fn representative(&self) -> &A::RepresentativeContainer<'a, T, N> {
196        &self.representative
197    }
198
199    /// Gets the heuristic slice
200    pub fn heuristic(&self) -> &A::HeuristicContainer<'a, N> {
201        &self.heuristic
202    }
203}
204
205/// This trait represents the kind of containers that is required for a particular algorithm to function
206pub trait AlgorithmContainer {
207    type HeuristicKind<'a>: Heuristic<RngProvider = Self::RngKind<'a>>;
208
209    /// Any kind of contiguous container
210    ///
211    /// # Examples
212    /// - `[T; N]`
213    /// - `[T; 0]`
214    /// - `heapless::Vec<T, N>`
215    type HeuristicContainer<'a, const N: usize>: AsRef<[usize]> + AsMut<[usize]>;
216
217    /// Any kind of contiguous container (should not be ZST). `R` must also live as long as `'a`
218    ///
219    /// # Examples
220    /// - `[T; N]`
221    /// - `heaples::Vec<T, N>`
222    type RepresentativeContainer<'a, V: VertexType + 'a, const N: usize>: AsRef<[V]> + AsMut<[V]>;
223
224    /// Any kind of RNG
225    type RngKind<'a>: RngCore;
226}
227
228/// Union operation
229pub trait Union<T: VertexType, H: Heuristic> {
230    fn union_sets(
231        representative: &mut [T],
232        heuristic: &mut [usize],
233        a: T::IdentifierType,
234        b: T::IdentifierType,
235        rng: &mut H::RngProvider,
236    );
237}
238
239/// Find operation
240pub trait Find<T: VertexType> {
241    fn find(representative: &mut [T], a: T::IdentifierType) -> T;
242}
243
244/// Connected operation
245pub trait Connected<T: VertexType> {
246    fn connected(representative: &mut [T], a: T::IdentifierType, b: T::IdentifierType) -> bool;
247}
248
249#[cfg(test)]
250mod tests {
251    use crate::{QuickFind, QuickUnion, UnionFind, VertexType};
252    use core::mem::size_of;
253
254    #[test]
255    fn test_qf_sz() {
256        assert_eq!(
257            size_of::<UnionFind::<'_, QuickFind, u32, 32>>(),
258            size_of::<[u32; 32]>()
259        );
260        assert_eq!(
261            size_of::<UnionFind::<'_, QuickFind, u8, 32>>(),
262            size_of::<[u8; 32]>()
263        );
264        assert_eq!(
265            size_of::<UnionFind::<'_, QuickFind, usize, 32>>(),
266            size_of::<[usize; 32]>()
267        );
268    }
269
270    #[test]
271    fn test_wqupc_sz() {
272        assert_eq!(
273            size_of::<UnionFind::<'_, QuickUnion, usize, 32>>(),
274            size_of::<[usize; 32]>() * 2
275        );
276
277        assert_eq!(
278            size_of::<UnionFind::<'_, QuickUnion, usize, 32>>(),
279            size_of::<[usize; 32]>() + size_of::<[usize; 32]>()
280        );
281    }
282
283    #[derive(Clone, Copy)]
284    pub struct CityVertex<'a> {
285        pub id: u8,
286        pub name: &'a str,
287        pub road_cost: u32,
288    }
289
290    impl<'a> CityVertex<'a> {
291        pub fn new(id: u8, name: &'a str, road_cost: u32) -> Self {
292            Self {
293                id,
294                name,
295                road_cost,
296            }
297        }
298    }
299
300    impl PartialEq for CityVertex<'_> {
301        fn eq(&self, other: &Self) -> bool {
302            self.id == other.id
303        }
304    }
305
306    impl PartialOrd for CityVertex<'_> {
307        fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
308            Some(self.id.cmp(&other.id))
309        }
310    }
311
312    impl Eq for CityVertex<'_> {}
313
314    impl VertexType for CityVertex<'_> {
315        type IdentifierType = u8;
316
317        fn id(&self) -> u8 {
318            self.id
319        }
320
321        fn usize(a: u8) -> usize {
322            a as usize
323        }
324    }
325}
pulau_rs/lib.rs

pulau_rs/
lib.rs
