1use crate::{
2 interval::traits::{CoalesceIntervals, Interval},
3 search::binary_search::BinarySearch,
4 set::{
5 contiguous_integer_set::ContiguousIntegerSet,
6 ordered_integer_set::OrderedIntegerSet, traits::Set,
7 },
8};
9use num::{integer::Integer, traits::cast::ToPrimitive};
10use std::{
11 cmp::{max, min, Ordering},
12 ops::{Sub, SubAssign},
13};
14
15impl<E: Integer + Copy + ToPrimitive> Sub<&ContiguousIntegerSet<E>>
16 for ContiguousIntegerSet<E>
17{
18 type Output = OrderedIntegerSet<E>;
19
20 fn sub(self, rhs: &ContiguousIntegerSet<E>) -> Self::Output {
21 let a = self.get_start();
22 let b = self.get_end();
23 let c = rhs.get_start();
24 let d = rhs.get_end();
25 if self.is_empty() {
26 return OrderedIntegerSet::from_ordered_coalesced_contiguous_integer_sets(vec![]);
27 }
28 if rhs.is_empty() {
29 return OrderedIntegerSet::from_ordered_coalesced_contiguous_integer_sets(vec![self]);
30 }
31 let mut diff: Vec<ContiguousIntegerSet<E>> = Vec::with_capacity(2);
33 if c > a {
34 diff.push(ContiguousIntegerSet::new(a, min(b, c - E::one())));
35 }
36 let i = ContiguousIntegerSet::new(max(d + E::one(), a), b);
37 if !i.is_empty() {
38 diff.push(i);
39 }
40 OrderedIntegerSet::from_ordered_coalesced_contiguous_integer_sets(diff)
41 }
42}
43
44impl<E: Integer + Copy + ToPrimitive> Sub for ContiguousIntegerSet<E> {
45 type Output = OrderedIntegerSet<E>;
46
47 #[inline]
48 fn sub(self, rhs: ContiguousIntegerSet<E>) -> Self::Output {
49 self - &rhs
50 }
51}
52
53impl<E: Integer + Copy + ToPrimitive> Sub<&ContiguousIntegerSet<E>>
54 for OrderedIntegerSet<E>
55{
56 type Output = Self;
57
58 #[inline]
59 fn sub(self, rhs: &ContiguousIntegerSet<E>) -> Self::Output {
60 if self.is_empty()
61 || rhs.is_empty()
62 || rhs.get_end() < self.intervals[0].get_start()
63 || rhs.get_start() > self.intervals.last().unwrap().get_end()
64 {
65 return self.clone();
66 }
67 let num_intervals = self.intervals.len();
68
69 let copy_first_n = self
70 .intervals
71 .binary_search_with_cmp(
72 0,
73 num_intervals,
74 &rhs.get_start(),
75 |interval, &rhs_start| {
76 if interval.get_end() < rhs_start {
77 Ordering::Less
78 } else {
79 Ordering::Greater
80 }
81 },
82 )
83 .unwrap_err()
84 .unwrap_or(0);
85
86 let mut diff = Vec::new();
87 diff.extend_from_slice(&self.intervals[..copy_first_n]);
88 let mut copy_from_i_to_end = None;
89 for i in copy_first_n..num_intervals {
90 let interval = self.intervals[i];
91 if interval.get_start() > rhs.get_end() {
92 copy_from_i_to_end = Some(i);
93 break;
94 }
95 let mut diff_set = interval - rhs;
96 if !diff_set.is_empty() {
97 diff.append(&mut diff_set.intervals);
98 }
99 }
100 if let Some(i) = copy_from_i_to_end {
101 diff.extend_from_slice(&self.intervals[i..]);
102 }
103 OrderedIntegerSet::from_ordered_coalesced_contiguous_integer_sets(diff)
104 }
105}
106
107impl<E: Integer + Copy + ToPrimitive> Sub<ContiguousIntegerSet<E>>
108 for OrderedIntegerSet<E>
109{
110 type Output = Self;
111
112 #[inline]
113 fn sub(self, rhs: ContiguousIntegerSet<E>) -> Self::Output {
114 self - &rhs
115 }
116}
117
118impl<E: Integer + Copy + ToPrimitive> SubAssign<&ContiguousIntegerSet<E>>
119 for OrderedIntegerSet<E>
120{
121 fn sub_assign(&mut self, rhs: &ContiguousIntegerSet<E>) {
122 *self = self.to_owned() - rhs
123 }
124}
125
126impl<E: Integer + Copy + ToPrimitive> SubAssign<ContiguousIntegerSet<E>>
127 for OrderedIntegerSet<E>
128{
129 #[inline]
130 fn sub_assign(&mut self, rhs: ContiguousIntegerSet<E>) {
131 *self = self.to_owned() - &rhs
132 }
133}
134
135impl<E: Integer + Copy + ToPrimitive> Sub<&OrderedIntegerSet<E>>
136 for ContiguousIntegerSet<E>
137{
138 type Output = OrderedIntegerSet<E>;
139
140 fn sub(self, rhs: &OrderedIntegerSet<E>) -> Self::Output {
141 let mut diff = OrderedIntegerSet::from(vec![self]);
142 for interval in rhs.intervals_iter() {
143 diff -= interval;
144 }
145 diff.into_coalesced()
146 }
147}
148
149impl<E: Integer + Copy + ToPrimitive> Sub<OrderedIntegerSet<E>>
150 for ContiguousIntegerSet<E>
151{
152 type Output = OrderedIntegerSet<E>;
153
154 #[inline]
155 fn sub(self, rhs: OrderedIntegerSet<E>) -> Self::Output {
156 self - &rhs
157 }
158}
159
160impl<E: Integer + Copy + ToPrimitive> Sub<&OrderedIntegerSet<E>>
161 for OrderedIntegerSet<E>
162{
163 type Output = Self;
164
165 fn sub(self, rhs: &OrderedIntegerSet<E>) -> Self::Output {
166 let mut diff = Vec::new();
167 let mut rhs_i = 0;
168 let num_rhs_intervals = rhs.intervals.len();
169 for interval in self.intervals.iter() {
170 let mut fragments = vec![*interval];
171 while rhs_i < num_rhs_intervals
172 && rhs.intervals[rhs_i].get_end() < interval.get_start()
173 {
174 rhs_i += 1;
175 }
176 while rhs_i < num_rhs_intervals
177 && rhs.intervals[rhs_i].get_start() <= interval.get_end()
178 {
179 match fragments.last() {
180 None => {}
181 Some(&l) => {
182 fragments.pop();
183 for frag in (l - rhs.intervals[rhs_i]).intervals {
184 fragments.push(frag);
185 }
186 }
187 };
188 if rhs.intervals[rhs_i].get_end() <= interval.get_end() {
189 rhs_i += 1;
190 } else {
191 break;
192 }
193 }
194 diff.append(&mut fragments);
195 }
196 OrderedIntegerSet::from_ordered_coalesced_contiguous_integer_sets(diff)
197 }
198}
199
200impl<E: Integer + Copy + ToPrimitive> Sub<OrderedIntegerSet<E>>
201 for OrderedIntegerSet<E>
202{
203 type Output = Self;
204
205 #[inline]
206 fn sub(self, rhs: OrderedIntegerSet<E>) -> Self::Output {
207 self - &rhs
208 }
209}
210
211impl<E: Integer + Copy + ToPrimitive> SubAssign<&OrderedIntegerSet<E>>
212 for OrderedIntegerSet<E>
213{
214 #[inline]
215 fn sub_assign(&mut self, rhs: &OrderedIntegerSet<E>) {
216 *self = self.to_owned() - rhs
217 }
218}
219
220impl<E: Integer + Copy + ToPrimitive> SubAssign<OrderedIntegerSet<E>>
221 for OrderedIntegerSet<E>
222{
223 #[inline]
224 fn sub_assign(&mut self, rhs: OrderedIntegerSet<E>) {
225 *self = self.to_owned() - &rhs
226 }
227}
228
229#[cfg(test)]
230mod tests {
231 use crate::set::{
232 contiguous_integer_set::ContiguousIntegerSet,
233 ordered_integer_set::OrderedIntegerSet,
234 };
235
236 #[test]
237 fn test_contiguous_sub_contiguous() {
238 macro_rules! test {
239 ($a:expr, $b:expr, $c:expr, $d:expr, $expected:expr) => {
240 assert_eq!(
241 ContiguousIntegerSet::new($a, $b)
242 - ContiguousIntegerSet::new($c, $d),
243 OrderedIntegerSet::from_slice($expected)
244 );
245 };
246 }
247 test!(2, 4, 5, 6, &[[2, 4]]);
248 test!(2, 4, 4, 6, &[[2, 3]]);
249 test!(2, 4, 4, 4, &[[2, 3]]);
250 test!(2, 4, 2, 2, &[[3, 4]]);
251 test!(2, 4, 3, 6, &[[2, 2]]);
252 test!(2, 5, 3, 4, &[[2, 2], [5, 5]]);
253 test!(2, 10, 4, 7, &[[2, 3], [8, 10]]);
254 test!(2, 10, 2, 2, &[[3, 10]]);
255 test!(2, 10, 2, 3, &[[4, 10]]);
256 test!(2, 10, -1, 2, &[[3, 10]]);
257 test!(2, 10, -1, 9, &[[10, 10]]);
258 test!(5, 10, 1, 8, &[[9, 10]]);
259 test!(5, 10, 1, 4, &[[5, 10]]);
260 test!(2, 5, 2, 5, &[]);
261 test!(2, 5, 0, 8, &[]);
262 }
263
264 #[test]
265 fn test_ordered_sub_contiguous() {
266 macro_rules! test {
267 ($ordered:expr, $a:expr, $b:expr, $expected:expr) => {
268 assert_eq!(
269 OrderedIntegerSet::from_slice($ordered)
270 - ContiguousIntegerSet::new($a, $b),
271 OrderedIntegerSet::from_slice($expected)
272 );
273 };
274 }
275 test!(&[], 2, 3, &[]);
276 test!(&[[4, 10]], 2, 3, &[[4, 10]]);
277 test!(&[[4, 10]], -2, 3, &[[4, 10]]);
278 test!(&[[4, 10]], 12, 13, &[[4, 10]]);
279 test!(&[[4, 10]], 3, 4, &[[5, 10]]);
280 test!(&[[4, 10]], 4, 4, &[[5, 10]]);
281 test!(&[[4, 10]], 10, 10, &[[4, 9]]);
282 test!(&[[4, 10]], 10, 12, &[[4, 9]]);
283 test!(&[[0, 10]], 3, 5, &[[0, 2], [6, 10]]);
284 test!(&[[0, 10]], 0, 10, &[]);
285 test!(&[[0, 10]], -1, 11, &[]);
286 test!(&[[0, 3], [6, 10]], 0, 11, &[]);
287 test!(&[[0, 3], [6, 10]], 0, 2, &[[3, 3], [6, 10]]);
288 test!(&[[0, 3], [6, 10]], 0, 3, &[[6, 10]]);
289 test!(&[[0, 3], [6, 10]], 0, 5, &[[6, 10]]);
290 test!(&[[0, 3], [6, 10]], 0, 6, &[[7, 10]]);
291 test!(&[[0, 3], [6, 10]], 0, 9, &[[10, 10]]);
292 test!(&[[0, 3], [6, 10]], 1, 1, &[[0, 0], [2, 3], [6, 10]]);
293 test!(&[[0, 3], [6, 10]], 1, 2, &[[0, 0], [3, 3], [6, 10]]);
294 test!(&[[0, 3], [6, 10]], 2, 3, &[[0, 1], [6, 10]]);
295 test!(&[[0, 3], [6, 10]], 2, 6, &[[0, 1], [7, 10]]);
296 test!(&[[0, 3], [6, 10]], 2, 9, &[[0, 1], [10, 10]]);
297 test!(&[[0, 3], [6, 10]], 3, 9, &[[0, 2], [10, 10]]);
298 test!(&[[0, 3], [6, 10]], 5, 9, &[[0, 3], [10, 10]]);
299 test!(&[[0, 3], [6, 10]], 8, 8, &[[0, 3], [6, 7], [9, 10]]);
300 test!(&[[0, 3], [6, 9], [12, 15]], 0, 14, &[[15, 15]]);
301 test!(&[[0, 3], [6, 9], [12, 15]], 0, 15, &[]);
302 test!(&[[0, 3], [6, 9], [12, 15]], 2, 7, &[[0, 1], [8, 9], [
303 12, 15
304 ]]);
305 test!(&[[0, 3], [6, 9], [12, 15]], 3, 12, &[[0, 2], [13, 15]]);
306 test!(&[[0, 3], [6, 9], [12, 15]], 3, 15, &[[0, 2]]);
307 test!(&[[0, 3], [6, 9], [12, 15]], 9, 12, &[[0, 3], [6, 8], [
308 13, 15
309 ]]);
310 }
311}