1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236

//! Algebraic manipulations of `PetitSets`
use crate::set::PetitSet;

#[cfg(feature = "set_algebra")]
use crate::set::PetitSetIter;

impl<T: Eq + Clone, const CAP: usize> PetitSet<T, CAP> {
    #[cfg(feature = "set_algebra")]
    /// Returns an iterator of references to the values that are in `self` but not in `other`.
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([7, 13, 5]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([15, 7, 3, 4, 5]);
    ///  
    /// let set_a_minus_b: PetitSet<usize, 3> = PetitSet::from_iter([13]);
    /// let set_b_minus_a: PetitSet<usize, 5> = PetitSet::from_iter([15, 3, 4]);
    ///
    /// let computed_set_a_minus_b = set_a.difference(&set_b).into_set();
    /// let computed_set_b_minus_a = set_b.difference(&set_a).into_set();
    ///
    /// assert_eq!(set_a_minus_b, computed_set_a_minus_b);
    /// assert_eq!(set_b_minus_a, computed_set_b_minus_a);
    /// ```
    pub fn difference<const OTHER_CAP: usize>(
        &self,
        other: &PetitSet<T, OTHER_CAP>,
    ) -> PetitSetIter<T, CAP> {
        let mut iter: PetitSetIter<T, CAP> = PetitSetIter::default();
        for s in self.iter() {
            if !other.contains(s) {
                iter.set.insert_unchecked(s.clone());
            }
        }

        iter
    }

    #[cfg(feature = "set_algebra")]
    /// Returns an iterator of references to the values that are not in both `self` and `other`.
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([7, 13, 5]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([15, 7, 3, 4, 5]);
    ///  
    /// let set_a_sym_diff_b: PetitSet<usize, 8> = PetitSet::from_iter([13, 15, 3, 4]);
    ///
    /// let computed_set_a_sym_diff_b = set_a.symmetric_difference(&set_b).into_set();
    /// let computed_set_b_sym_diff_a = set_b.symmetric_difference(&set_a).into_set();
    ///
    /// assert_eq!(set_a_sym_diff_b, computed_set_a_sym_diff_b);
    /// assert_eq!(computed_set_a_sym_diff_b, computed_set_b_sym_diff_a);
    /// ```
    pub fn symmetric_difference<const OTHER_CAP: usize>(
        &self,
        other: &PetitSet<T, OTHER_CAP>,
    ) -> PetitSetIter<T, { CAP + OTHER_CAP }> {
        let mut iter: PetitSetIter<T, { CAP + OTHER_CAP }> = PetitSetIter::default();
        for s in self.iter() {
            if !other.contains(s) {
                iter.set.insert_unchecked(s.clone());
            }
        }

        for o in other.iter() {
            if !self.contains(o) {
                iter.set.insert_unchecked(o.clone());
            }
        }

        iter
    }
    #[cfg(feature = "set_algebra")]
    /// Returns an iterator of references to the values that are in both `self` and `other`.
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([7, 13, 5]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([15, 7, 3, 4, 5]);
    ///  
    /// let set_a_intersection_b: PetitSet<usize, 5> = PetitSet::from_iter([7, 5]);
    ///
    /// let computed_set_a_intersection_b = set_a.intersection(&set_b).into_set();
    /// let computed_set_b_intersection_a = set_b.intersection(&set_a).into_set();
    ///
    /// assert_eq!(set_a_intersection_b, computed_set_a_intersection_b);
    /// assert_eq!(computed_set_a_intersection_b, computed_set_b_intersection_a);
    /// ```
    pub fn intersection<const OTHER_CAP: usize>(
        &self,
        other: &PetitSet<T, OTHER_CAP>,
    ) -> PetitSetIter<T, { max_of(CAP, OTHER_CAP) }> {
        let mut iter: PetitSetIter<T, { max_of(CAP, OTHER_CAP) }> = PetitSetIter::default();
        for s in self.iter() {
            if other.contains(s) {
                iter.set.insert_unchecked(s.clone());
            }
        }
        iter
    }

    #[cfg(feature = "set_algebra")]
    /// Returns an iterator of references to the values that are in either `self` and `other`.
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([7, 13, 5]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([15, 7, 3, 4, 5]);
    ///  
    /// let set_a_union_b: PetitSet<usize, 8> = PetitSet::from_iter([7, 13, 5, 15, 3, 4]);
    ///
    /// let computed_set_a_union_b = set_a.union(&set_b).into_set();
    /// let computed_set_b_union_a = set_b.union(&set_a).into_set();
    ///
    /// assert_eq!(set_a_union_b, computed_set_a_union_b);
    /// assert_eq!(computed_set_a_union_b, computed_set_b_union_a);
    /// ```
    pub fn union<const OTHER_CAP: usize>(
        &self,
        other: &PetitSet<T, OTHER_CAP>,
    ) -> PetitSetIter<T, { CAP + OTHER_CAP }> {
        let mut iter: PetitSetIter<T, { CAP + OTHER_CAP }> = PetitSetIter::default();
        for s in self.iter() {
            iter.set.insert_unchecked(s.clone());
        }

        for o in other.iter() {
            // We are not guaranteed uniqueness by construction here
            iter.set.insert(o.clone());
        }

        iter
    }

    /// Do the sets contain any common elements?
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([7, 13, 5]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([15, 7, 3, 4, 5]);
    /// let mut set_c: PetitSet<usize, 1> = PetitSet::default();
    /// set_c.insert(42);
    ///
    /// assert!(!set_a.is_disjoint(&set_b));
    /// assert!(!set_b.is_disjoint(&set_a));
    ///
    /// assert!(set_a.is_disjoint(&set_c));
    /// assert!(set_c.is_disjoint(&set_a));
    /// ```
    pub fn is_disjoint<const OTHER_CAP: usize>(&self, other: &PetitSet<T, OTHER_CAP>) -> bool {
        for s in self.iter() {
            for o in other.iter() {
                if s == o {
                    return false;
                }
            }
        }
        true
    }

    /// Are all elements in `self` contained in `other`?
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([1, 2, 3]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([2, 3]);
    ///
    /// assert!(set_a.is_subset(&set_a));
    ///
    /// assert!(!set_a.is_subset(&set_b));
    /// assert!(set_b.is_subset(&set_a));
    /// ```
    pub fn is_subset<const OTHER_CAP: usize>(&self, other: &PetitSet<T, OTHER_CAP>) -> bool {
        'outer: for s in self.iter() {
            '_inner: for o in other.iter() {
                if s == o {
                    // If we've found a match in other, check the next element
                    continue 'outer;
                }
            }
            // If no match could be found, there is an element in self that is not in other
            return false;
        }
        true
    }

    /// Are all elements in `other` contained in `self`?
    ///
    /// # Examples
    /// ```rust
    /// use petitset::PetitSet;
    ///
    /// let set_a: PetitSet<usize, 3> = PetitSet::from_iter([1, 2, 3]);
    /// let set_b: PetitSet<usize, 5> = PetitSet::from_iter([2, 3]);
    ///
    /// assert!(set_a.is_superset(&set_a));
    ///
    /// assert!(set_a.is_superset(&set_b));
    /// assert!(!set_b.is_superset(&set_a));
    /// ```
    pub fn is_superset<const OTHER_CAP: usize>(&self, other: &PetitSet<T, OTHER_CAP>) -> bool {
        'outer: for o in other.iter() {
            '_inner: for s in self.iter() {
                if o == s {
                    // If we've found a match in self, check the next element
                    continue 'outer;
                }
            }
            // If no match could be found, there is an element in other that is not in self
            return false;
        }
        true
    }
}

/// Trivial const replacement for `std::comp::Ord::max`
pub const fn max_of(a: usize, b: usize) -> usize {
    if a >= b {
        a
    } else {
        b
    }
}