1use {
2 crate::{
3 rect::{Container, NoTag, RectRaw, Tag},
4 windows::WindowsExt,
5 },
6 std::{cmp::Ordering, collections::BinaryHeap, marker::PhantomData, mem, ops::Deref},
7};
8
9pub fn union(left: &Container, right: &Container) -> Container {
10 op::<_, _, _, Union>(left, right)
11}
12
13pub fn subtract(left: &Container, right: &Container) -> Container {
14 op::<_, _, _, Subtract>(left, right)
15}
16
17pub fn intersect(left: &Container, right: &Container) -> Container {
18 op::<_, _, _, Intersect<NoTag>>(left, right)
19}
20
21pub fn intersect_tagged(left: &Container<u32>, right: &Container) -> Container<u32> {
22 op::<_, _, _, Intersect<u32>>(left, right)
23}
24
25struct Bands<'a, T>
26where
27 T: Tag,
28{
29 rects: &'a [RectRaw<T>],
30}
31
32#[derive(Copy, Clone)]
33struct Band<'a, T>
34where
35 T: Tag,
36{
37 rects: &'a [RectRaw<T>],
38 y1: i32,
39 y2: i32,
40}
41
42impl<'a, T> Band<'a, T>
43where
44 T: Tag,
45{
46 fn can_merge_with(&self, next: &Band<'_, T>) -> bool {
47 next.rects.len() == self.rects.len()
48 && next.y1 == self.y2
49 && next
50 .rects
51 .iter()
52 .zip(self.rects.iter())
53 .all(|(a, b)| (a.x1, a.x2, a.tag) == (b.x1, b.x2, b.tag))
54 }
55}
56
57impl<'a, T> Iterator for Bands<'a, T>
58where
59 T: Tag,
60{
61 type Item = Band<'a, T>;
62
63 fn next(&mut self) -> Option<Self::Item> {
64 if self.rects.is_empty() {
65 return None;
66 }
67 let y1 = self.rects[0].y1;
68 let y2 = self.rects[0].y2;
69 for (pos, rect) in self.rects[1..].iter().enumerate() {
70 if rect.y1 != y1 {
71 let (res, rects) = self.rects.split_at(pos + 1);
72 self.rects = rects;
73 return Some(Band { rects: res, y1, y2 });
74 }
75 }
76 Some(Band {
77 rects: mem::replace(&mut self.rects, &[]),
78 y1,
79 y2,
80 })
81 }
82}
83
84#[inline]
85pub fn extents<T>(a: &[RectRaw<T>]) -> RectRaw
86where
87 T: Tag,
88{
89 let mut a = a.iter();
90 let mut res = match a.next() {
91 Some(a) => *a,
92 _ => return RectRaw::default(),
93 };
94 for a in a {
95 res.x1 = res.x1.min(a.x1);
96 res.y1 = res.y1.min(a.y1);
97 res.x2 = res.x2.max(a.x2);
98 res.y2 = res.y2.max(a.y2);
99 }
100 RectRaw {
101 x1: res.x1,
102 y1: res.y1,
103 x2: res.x2,
104 y2: res.y2,
105 tag: NoTag,
106 }
107}
108
109fn op<T1, T2, T3, O: Op<T1, T2, T3>>(a: &[RectRaw<T2>], b: &[RectRaw<T3>]) -> Container<T1>
110where
111 T1: Tag,
112 T2: Tag,
113 T3: Tag,
114{
115 let mut res = Container::new();
116
117 let mut prev_band_y2 = 0;
118 let mut prev_band_start = 0;
119 let mut cur_band_start;
120
121 let mut a_bands = Bands { rects: a };
122 let mut b_bands = Bands { rects: b };
123
124 let mut a_opt = a_bands.next();
125 let mut b_opt = b_bands.next();
126
127 macro_rules! fixup_new_band {
128 ($y1:expr, $y2:expr) => {{
129 if prev_band_y2 != $y1 || !coalesce(&mut res, prev_band_start, cur_band_start, $y2) {
130 prev_band_start = cur_band_start;
131 }
132 prev_band_y2 = $y2;
133 }};
134 }
135
136 macro_rules! append_nonoverlapping {
137 ($append_opt:expr, $map:ident, $a:expr, $a_opt:expr, $a_bands:expr, $b:expr) => {{
138 if $append_opt {
139 let y2 = $a.y2.min($b.y1);
140 cur_band_start = res.len();
141 res.reserve($a.rects.len());
142 for rect in $a.rects {
143 res.push(RectRaw {
144 x1: rect.x1,
145 y1: $a.y1,
146 x2: rect.x2,
147 y2,
148 tag: O::$map(rect.tag),
149 });
150 }
151 fixup_new_band!($a.y1, y2);
152 }
153 if $a.y2 <= $b.y1 {
154 $a_opt = $a_bands.next();
155 } else {
156 $a.y1 = $b.y1;
157 }
158 }};
159 }
160
161 while let (Some(a), Some(b)) = (&mut a_opt, &mut b_opt) {
162 if a.y1 < b.y1 {
163 append_nonoverlapping!(O::APPEND_NON_A, map_t2_to_t1, a, a_opt, a_bands, b);
164 } else if b.y1 < a.y1 {
165 append_nonoverlapping!(O::APPEND_NON_B, map_t3_to_t1, b, b_opt, b_bands, a);
166 } else {
167 let y2 = a.y2.min(b.y2);
168 cur_band_start = res.len();
169 O::handle_band(&mut res, a.rects, b.rects, a.y1, y2);
170 if res.len() > cur_band_start {
171 fixup_new_band!(a.y1, y2);
172 }
173 if a.y2 == y2 {
174 a_opt = a_bands.next();
175 } else {
176 a.y1 = y2;
177 }
178 if b.y2 == y2 {
179 b_opt = b_bands.next();
180 } else {
181 b.y1 = y2;
182 }
183 }
184 }
185
186 macro_rules! push_trailing {
187 ($a_opt:expr, $a_bands:expr, $map:ident) => {{
188 while let Some(a) = $a_opt {
189 cur_band_start = res.len();
190 res.reserve(a.rects.len());
191 for rect in a.rects {
192 res.push(RectRaw {
193 x1: rect.x1,
194 y1: a.y1,
195 x2: rect.x2,
196 y2: a.y2,
197 tag: O::$map(rect.tag),
198 });
199 }
200 fixup_new_band!(a.y1, a.y2);
201 $a_opt = $a_bands.next();
202 }
203 }};
204 }
205
206 if O::APPEND_NON_A {
207 push_trailing!(a_opt, a_bands, map_t2_to_t1);
208 }
209
210 if O::APPEND_NON_B {
211 push_trailing!(b_opt, b_bands, map_t3_to_t1);
212 }
213
214 res.shrink_to_fit();
215 res
216}
217
218fn coalesce<T>(new: &mut Container<T>, a: usize, b: usize, y2: i32) -> bool
219where
220 T: Tag,
221{
222 if new.len() - b != b - a {
223 return false;
224 }
225 let slice_a = &new[a..b];
226 let slice_b = &new[b..];
227 for (a, b) in slice_a.iter().zip(slice_b.iter()) {
228 if (a.x1, a.x2, a.tag) != (b.x1, b.x2, b.tag) {
229 return false;
230 }
231 }
232 for rect in &mut new[a..b] {
233 rect.y2 = y2;
234 }
235 new.truncate(b);
236 true
237}
238
239trait Op<T1, T2, T3>
240where
241 T1: Tag,
242 T2: Tag,
243 T3: Tag,
244{
245 const APPEND_NON_A: bool;
246 const APPEND_NON_B: bool;
247
248 fn handle_band(new: &mut Container<T1>, a: &[RectRaw<T2>], b: &[RectRaw<T3>], y1: i32, y2: i32);
249
250 fn map_t2_to_t1(tag: T2) -> T1;
251
252 fn map_t3_to_t1(tag: T3) -> T1;
253}
254
255struct Union;
256
257impl Op<NoTag, NoTag, NoTag> for Union {
258 const APPEND_NON_A: bool = true;
259 const APPEND_NON_B: bool = true;
260
261 fn handle_band(new: &mut Container, mut a: &[RectRaw], mut b: &[RectRaw], y1: i32, y2: i32) {
262 let mut x1;
263 let mut x2;
264
265 macro_rules! push {
266 () => {
267 new.push(RectRaw {
268 x1,
269 y1,
270 x2,
271 y2,
272 tag: NoTag,
273 });
274 };
275 }
276
277 macro_rules! merge {
278 ($r:expr) => {
279 if $r.x1 <= x2 {
280 if $r.x2 > x2 {
281 x2 = $r.x2;
282 }
283 } else {
284 push!();
285 x1 = $r.x1;
286 x2 = $r.x2;
287 }
288 };
289 }
290
291 if a[0].x1 < b[0].x1 {
292 x1 = a[0].x1;
293 x2 = a[0].x2;
294 a = &a[1..];
295 } else {
296 x1 = b[0].x1;
297 x2 = b[0].x2;
298 b = &b[1..];
299 }
300
301 let mut a_iter = a.iter();
302 let mut b_iter = b.iter();
303
304 let mut a_opt = a_iter.next();
305 let mut b_opt = b_iter.next();
306
307 while let (Some(a), Some(b)) = (a_opt, b_opt) {
308 if a.x1 < b.x1 {
309 merge!(a);
310 a_opt = a_iter.next();
311 } else {
312 merge!(b);
313 b_opt = b_iter.next();
314 }
315 }
316
317 while let Some(a) = a_opt {
318 merge!(a);
319 a_opt = a_iter.next();
320 }
321
322 while let Some(b) = b_opt {
323 merge!(b);
324 b_opt = b_iter.next();
325 }
326
327 push!();
328 }
329
330 #[inline(always)]
331 fn map_t2_to_t1(_tag: NoTag) -> NoTag {
332 NoTag
333 }
334
335 #[inline(always)]
336 fn map_t3_to_t1(_tag: NoTag) -> NoTag {
337 NoTag
338 }
339}
340
341struct Subtract;
342
343impl Op<NoTag, NoTag, NoTag> for Subtract {
344 const APPEND_NON_A: bool = true;
345 const APPEND_NON_B: bool = false;
346
347 fn handle_band(new: &mut Container, a: &[RectRaw], b: &[RectRaw], y1: i32, y2: i32) {
348 let mut x1;
349 let mut x2;
350
351 macro_rules! push {
352 ($x2:expr) => {
353 new.push(RectRaw {
354 x1,
355 y1,
356 x2: $x2,
357 y2,
358 tag: NoTag,
359 });
360 };
361 }
362
363 let mut a_iter = a.iter();
364 let mut b_iter = b.iter();
365
366 macro_rules! pull {
367 () => {
368 match a_iter.next() {
369 Some(n) => {
370 x1 = n.x1;
371 x2 = n.x2;
372 }
373 _ => return,
374 }
375 };
376 }
377
378 pull!();
379
380 let mut b_opt = b_iter.next();
381
382 while let Some(b) = b_opt {
383 if b.x2 <= x1 {
384 b_opt = b_iter.next();
385 } else if b.x1 >= x2 {
386 push!(x2);
387 pull!();
388 } else {
389 if b.x1 > x1 {
390 push!(b.x1);
391 }
392 if b.x2 < x2 {
393 x1 = b.x2;
394 } else {
395 pull!();
396 }
397 }
398 }
399
400 loop {
401 push!(x2);
402 pull!();
403 }
404 }
405
406 #[inline(always)]
407 fn map_t2_to_t1(_tag: NoTag) -> NoTag {
408 NoTag
409 }
410
411 #[inline(always)]
412 fn map_t3_to_t1(_tag: NoTag) -> NoTag {
413 NoTag
414 }
415}
416
417struct Intersect<T>(PhantomData<T>);
418
419impl<T> Op<T, T, NoTag> for Intersect<T>
420where
421 T: Tag,
422{
423 const APPEND_NON_A: bool = false;
424 const APPEND_NON_B: bool = false;
425
426 fn handle_band(new: &mut Container<T>, a: &[RectRaw<T>], b: &[RectRaw], y1: i32, y2: i32) {
427 let mut x1;
428 let mut x2;
429 let mut tag;
430
431 macro_rules! push {
432 ($x2:expr) => {
433 new.push(RectRaw {
434 x1,
435 y1,
436 x2: $x2,
437 y2,
438 tag,
439 });
440 };
441 }
442
443 let mut a_iter = a.iter();
444 let mut b_iter = b.iter();
445
446 macro_rules! pull {
447 () => {
448 match a_iter.next() {
449 Some(n) => {
450 x1 = n.x1;
451 x2 = n.x2;
452 tag = n.tag;
453 }
454 _ => return,
455 }
456 };
457 }
458
459 pull!();
460
461 let mut b_opt = b_iter.next();
462
463 while let Some(b) = b_opt {
464 if b.x2 <= x1 {
465 b_opt = b_iter.next();
466 } else if b.x1 >= x2 {
467 pull!();
468 } else {
469 x1 = x1.max(b.x1);
470 if x2 <= b.x2 {
471 push!(x2);
472 pull!();
473 } else {
474 push!(b.x2);
475 b_opt = b_iter.next();
476 }
477 }
478 }
479 }
480
481 #[inline(always)]
482 fn map_t2_to_t1(_tag: T) -> T {
483 unreachable!()
484 }
485
486 #[inline(always)]
487 fn map_t3_to_t1(_tag: NoTag) -> T {
488 unreachable!()
489 }
490}
491
492pub fn rects_to_bands(rects_tmp: &[RectRaw]) -> Container {
493 rects_to_bands_(rects_tmp)
494}
495
496pub fn rects_to_bands_tagged(rects_tmp: &[RectRaw<u32>]) -> Container<u32> {
497 rects_to_bands_(rects_tmp)
498}
499
500#[inline(always)]
501fn rects_to_bands_<T>(rects_tmp: &[RectRaw<T>]) -> Container<T>
502where
503 T: Tag,
504{
505 #[derive(Copy, Clone)]
506 struct W<T>(RectRaw<T>)
507 where
508 T: Tag;
509 impl<T> Eq for W<T> where T: Tag {}
510 impl<T> PartialEq<Self> for W<T>
511 where
512 T: Tag,
513 {
514 fn eq(&self, other: &Self) -> bool {
515 self.0 == other.0
516 }
517 }
518 impl<T> PartialOrd<Self> for W<T>
519 where
520 T: Tag,
521 {
522 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
523 Some(self.cmp(other))
524 }
525 }
526 impl<T> Ord for W<T>
527 where
528 T: Tag,
529 {
530 fn cmp(&self, other: &Self) -> Ordering {
531 self.0
532 .y1
533 .cmp(&other.0.y1)
534 .then_with(|| self.0.x1.cmp(&other.0.x1))
535 .then_with(|| self.0.tag.cmp(&other.0.tag))
536 .reverse()
537 }
538 }
539 impl<T> Deref for W<T>
540 where
541 T: Tag,
542 {
543 type Target = RectRaw<T>;
544 fn deref(&self) -> &Self::Target {
545 &self.0
546 }
547 }
548
549 let ys = {
550 let mut tmp: Vec<_> = rects_tmp.iter().flat_map(|r| [r.y1, r.y2]).collect();
551 tmp.sort_unstable();
552 let mut last = None;
553 let mut res = vec![];
554 for y in tmp {
555 if Some(y) != last {
556 last = Some(y);
557 res.push(y);
558 }
559 }
560 res
561 };
562
563 let mut rects = BinaryHeap::with_capacity(rects_tmp.len());
564 for rect in rects_tmp.iter().copied() {
565 if !rect.is_empty() {
566 rects.push(W(rect));
567 }
568 }
569
570 let mut res = Container::new();
571
572 for &[y1, y2] in ys.array_windows_ext::<2>() {
573 #[expect(clippy::never_loop)]
574 loop {
575 macro_rules! check_rect {
576 ($rect:expr) => {{
577 if $rect.y1 != y1 {
578 break;
579 }
580 rects.pop();
581 if y2 < $rect.y2 {
582 $rect.0.y1 = y2;
583 rects.push($rect);
584 }
585 }};
586 }
587 if let Some(mut rect) = rects.peek().copied() {
588 check_rect!(rect);
589 let mut x1 = rect.x1;
590 let mut x2 = rect.x2;
591 let mut tag: T = rect.tag;
592 while let Some(mut rect) = rects.peek().copied() {
593 check_rect!(rect);
594 if rect.x1 > x2 || (rect.tag != tag && rect.x1 == x2) {
595 res.push(RectRaw {
596 x1,
597 x2,
598 y1,
599 y2,
600 tag: tag.constrain(),
601 });
602 x1 = rect.x1;
603 x2 = rect.x2;
604 tag = rect.tag;
605 } else {
606 if rect.tag == tag {
607 x2 = x2.max(rect.x2);
608 } else if rect.tag > tag {
609 if rect.x2 > x2 {
610 rect.0.x1 = x2;
611 rect.0.y1 = y1;
612 rect.0.y2 = y2;
613 rects.push(rect);
614 }
615 } else {
616 if x2 > rect.x2 {
617 rects.push(W(RectRaw {
618 x1: rect.x2,
619 y1,
620 x2,
621 y2,
622 tag,
623 }));
624 }
625 res.push(RectRaw {
626 x1,
627 y1,
628 x2: rect.x1,
629 y2,
630 tag: tag.constrain(),
631 });
632 x1 = rect.x1;
633 x2 = rect.x2;
634 tag = rect.tag;
635 }
636 }
637 }
638 res.push(RectRaw {
639 x1,
640 x2,
641 y1,
642 y2,
643 tag: tag.constrain(),
644 });
645 }
646 break;
647 }
648 }
649
650 let mut needs_merge = false;
651 let mut num_elements = res.len();
652 let mut bands = Bands { rects: &res }.peekable();
653 while let Some(band) = bands.next() {
654 let next = match bands.peek() {
655 Some(next) => next,
656 _ => break,
657 };
658 if band.can_merge_with(next) {
659 needs_merge = true;
660 num_elements -= band.rects.len();
661 }
662 }
663
664 if !needs_merge {
665 res.shrink_to_fit();
666 return res;
667 }
668
669 let mut merged = Container::with_capacity(num_elements);
670 let mut bands = Bands { rects: &res }.peekable();
671 while let Some(mut band) = bands.next() {
672 while let Some(next) = bands.peek() {
673 if band.can_merge_with(next) {
674 band.y2 = next.y2;
675 bands.next();
676 } else {
677 break;
678 }
679 }
680 for mut rect in band.rects.iter().copied() {
681 rect.y2 = band.y2;
682 merged.push(rect);
683 }
684 }
685
686 merged
687}