union_find/
union.rs

1// Copyright 2016 union-find-rs Developers
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8use crate::{Union, UnionResult};
9use std::cmp::Ordering;
10
11/// Operates the `union` with using the size of the sets as weight.
12///
13/// A smaller sized set will be the children of a larger sized set.
14#[derive(Copy, Clone, Debug)]
15pub struct UnionBySize(usize);
16
17impl Union for UnionBySize {
18    #[inline]
19    fn union(left: UnionBySize, right: UnionBySize) -> UnionResult<UnionBySize> {
20        let lsize = left.size();
21        let rsize = right.size();
22        let result = UnionBySize(lsize + rsize);
23        if lsize >= rsize {
24            UnionResult::Left(result)
25        } else {
26            UnionResult::Right(result)
27        }
28    }
29}
30
31impl Default for UnionBySize {
32    #[inline]
33    fn default() -> UnionBySize {
34        UnionBySize(1)
35    }
36}
37
38impl UnionBySize {
39    /// Returns the size of the set.
40    #[inline]
41    pub fn size(&self) -> usize {
42        let UnionBySize(size) = *self;
43        size
44    }
45}
46
47/// Operates the `union` with using the rank of the sets as weight.
48///
49/// A smaller ranked set will be the children of a larger ranked set.
50/// If both sets have the same rank, the size of the set is used.
51#[derive(Copy, Clone, Debug, Default)]
52pub struct UnionByRank(u8);
53
54impl Union for UnionByRank {
55    #[inline]
56    fn union(left: UnionByRank, right: UnionByRank) -> UnionResult<UnionByRank> {
57        let lrank = left.rank();
58        let rrank = right.rank();
59        match lrank.cmp(&rrank) {
60            Ordering::Less => UnionResult::Right(right),
61            Ordering::Greater => UnionResult::Left(left),
62            Ordering::Equal => UnionResult::Left(UnionByRank(lrank + 1)),
63        }
64    }
65}
66
67impl UnionByRank {
68    /// Returns the rankq of the set.
69    #[inline]
70    pub fn rank(&self) -> u8 {
71        let UnionByRank(rank) = *self;
72        rank
73    }
74}
75
76/// Operates the `union` with using the size and the rank of the sets as weight.
77///
78/// A smaller sized set will be the children of a larger sized set.
79/// If both sets have the same size, compared by the rank.
80#[derive(Copy, Clone, Debug)]
81pub struct UnionBySizeRank(usize, u8);
82
83impl Union for UnionBySizeRank {
84    #[inline]
85    fn union(left: UnionBySizeRank, right: UnionBySizeRank) -> UnionResult<UnionBySizeRank> {
86        let lsize = left.size();
87        let lrank = left.rank();
88        let rsize = right.size();
89        let rrank = right.rank();
90
91        let rank_cmp = lrank.cmp(&rrank);
92        let new_size = lsize + rsize;
93        let new_rank = match rank_cmp {
94            Ordering::Less => rrank,
95            Ordering::Greater => lrank,
96            Ordering::Equal => lrank + 1,
97        };
98
99        let result = UnionBySizeRank(new_size, new_rank);
100        match lsize.cmp(&rsize) {
101            Ordering::Less => UnionResult::Right(result),
102            Ordering::Greater => UnionResult::Left(result),
103            Ordering::Equal => match rank_cmp {
104                Ordering::Less => UnionResult::Right(result),
105                _ => UnionResult::Left(result),
106            },
107        }
108    }
109}
110
111impl Default for UnionBySizeRank {
112    #[inline]
113    fn default() -> UnionBySizeRank {
114        UnionBySizeRank(1, 0)
115    }
116}
117
118impl UnionBySizeRank {
119    /// Returns the size of the set.
120    #[inline]
121    pub fn size(&self) -> usize {
122        let UnionBySizeRank(size, _) = *self;
123        size
124    }
125
126    /// Returns the rank of the set.
127    #[inline]
128    pub fn rank(&self) -> u8 {
129        let UnionBySizeRank(_, rank) = *self;
130        rank
131    }
132}
133
134/// Operates the `union` with using the rank and the size of the sets as weight.
135///
136/// A smaller ranked set will be the children of a larger ranked set.
137/// If both sets have the same rank, compared by the size.
138#[derive(Copy, Clone, Debug)]
139pub struct UnionByRankSize(u8, usize);
140
141impl Union for UnionByRankSize {
142    #[inline]
143    fn union(left: UnionByRankSize, right: UnionByRankSize) -> UnionResult<UnionByRankSize> {
144        let lrank = left.rank();
145        let lsize = left.size();
146        let rrank = right.rank();
147        let rsize = right.size();
148
149        let rank_cmp = lrank.cmp(&rrank);
150        let new_size = lsize + rsize;
151        let new_rank = match rank_cmp {
152            Ordering::Less => rrank,
153            Ordering::Greater => lrank,
154            Ordering::Equal => lrank + 1,
155        };
156
157        let result = UnionByRankSize(new_rank, new_size);
158        match rank_cmp {
159            Ordering::Less => UnionResult::Right(result),
160            Ordering::Greater => UnionResult::Left(result),
161            Ordering::Equal => match lsize.cmp(&rsize) {
162                Ordering::Less => UnionResult::Right(result),
163                _ => UnionResult::Left(result),
164            },
165        }
166    }
167}
168
169impl Default for UnionByRankSize {
170    #[inline]
171    fn default() -> UnionByRankSize {
172        UnionByRankSize(1, 0)
173    }
174}
175
176impl UnionByRankSize {
177    /// Returns the rank of the set.
178    #[inline]
179    pub fn rank(&self) -> u8 {
180        let UnionByRankSize(rank, _) = *self;
181        rank
182    }
183
184    /// Returns the size of the set.
185    #[inline]
186    pub fn size(&self) -> usize {
187        let UnionByRankSize(_, size) = *self;
188        size
189    }
190}
union_find/union.rs

union_find/
union.rs
