normalize_interval/tine_tree.rs
1// Copyright 2024 Skylor R. Schermer.
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8////////////////////////////////////////////////////////////////////////////////
9//! Interval `TineTree` implementation.
10////////////////////////////////////////////////////////////////////////////////
11// NOTE: Unused results are permitted here because the `TineTree` calls
12// `BTreeSet::insert` frequently without concern for its return value.
13#![allow(unused_results)]
14
15// Internal library imports.
16use crate::bound::Bound;
17use crate::raw_interval::RawInterval;
18use crate::tine::Tine;
19
20// External library imports.
21#[cfg(feature="serde")] use serde::Deserialize;
22#[cfg(feature="serde")] use serde::Serialize;
23use few::Few;
24
25// Standard library imports.
26use std::collections::BTreeSet;
27use std::collections::btree_set;
28use std::iter::FromIterator;
29
30
31////////////////////////////////////////////////////////////////////////////////
32// TineTree
33////////////////////////////////////////////////////////////////////////////////
34/// A possibly noncontiguous collection of `RawInterval`s of the type `T`.
35/// Implemented as an ordered list of `Tine`s. Used to implement the internal
36/// state of `Selection`.
37///
38/// Informally, a `TineTree` acts like a number line with markers (`Tine`s) on
39/// it for each `Interval` bound in a possibly disjoint union of `Interval`s.
40///
41/// [`RawInterval`]: raw_interval/struct.RawInterval.html
42/// [`Selection`]: selection/struct.Selection.html
43/// [`Tine`]: tine_tree/struct.Tine.html
44/// [`Interval`]: interval/struct.Interval.html
45///
46#[repr(transparent)]
47#[derive(Debug, Clone, PartialEq, Eq, Hash)]
48#[cfg_attr(feature="serde", derive(Deserialize, Serialize))]
49#[cfg_attr(feature="serde", serde(transparent))]
50#[cfg_attr(feature="serde",
51 serde(bound="for<'a> T: Ord + Serialize + Deserialize<'a> + Clone + 'a"))]
52pub struct TineTree<T>(BTreeSet<Tine<T>>);
53
54impl<T> TineTree<T> where T: Ord + Clone {
55 ////////////////////////////////////////////////////////////////////////////
56 // Constructors
57 ////////////////////////////////////////////////////////////////////////////
58
59 /// Constructs an empty `TineTree`.
60 #[must_use]
61 pub fn new() -> Self {
62 Self(BTreeSet::new())
63 }
64
65 /// Constructs a `TineTree` from a `RawInterval`.
66 #[must_use]
67 pub fn from_raw_interval(interval: RawInterval<T>) -> Self {
68 Self(Tine::from_raw_interval(interval).collect())
69 }
70
71 ////////////////////////////////////////////////////////////////////////////
72 // Bound accessors
73 ////////////////////////////////////////////////////////////////////////////
74
75 /// Returns the lower [`Bound`] of the `TineTree`, or `None` if the
76 /// `TineTree` is empty.
77 #[inline]
78 pub fn lower_bound(&self) -> Option<Bound<T>> {
79 self.0.iter().next().cloned().map(Tine::into_inner)
80 }
81
82 /// Returns the upper [`Bound`] of the `TineTree`, or `None` if the
83 /// `TineTree` is empty.
84 #[inline]
85 pub fn upper_bound(&self) -> Option<Bound<T>> {
86 self.0.iter().next_back().cloned().map(Tine::into_inner)
87 }
88
89
90 ////////////////////////////////////////////////////////////////////////////
91 // Query operations
92 ////////////////////////////////////////////////////////////////////////////
93
94 /// Returns `true` if the `TineTree` is empty.
95 #[must_use]
96 pub fn is_empty(&self) -> bool {
97 self.0.is_empty()
98 }
99
100 /// Returns `true` if the `TineTree` is full.
101 #[must_use]
102 pub fn is_full(&self) -> bool {
103 self.0.iter().collect::<Vec<_>>() == [
104 &Tine::Lower(Bound::Infinite),
105 &Tine::Upper(Bound::Infinite)]
106 }
107
108 /// Returns `true` if the `TineTree` contains the given point.
109 #[must_use]
110 pub fn contains(&self, point: &T) -> bool {
111 // TODO: Could be optimized by splitting the tree and looking around.
112 for interval in self.interval_iter() {
113 if interval.contains(point) {return true;}
114 }
115 false
116 }
117
118 ////////////////////////////////////////////////////////////////////////////
119 // Set Operations
120 ////////////////////////////////////////////////////////////////////////////
121
122 /// Returns a `TineTree` containing all points not in present in the
123 /// `TineTree`.
124 #[allow(clippy::missing_panics_doc)]
125 #[must_use]
126 pub fn complement(&self) -> Self {
127 use Bound::*;
128 use Tine::*;
129
130 // Early exit if we're complementing an empty interval.
131 if self.0.is_empty() {
132 return RawInterval::Full.into();
133 }
134
135 let mut complement = Self::new();
136 let mut tine_iter = self.0.iter();
137
138 // Early exit if we're complementing a point interval.
139 if self.0.len() == 1 {
140 let tine = tine_iter
141 .next()
142 .expect("nonempty TineTree")
143 .clone()
144 .invert();
145 debug_assert!(tine.is_point_exclude());
146
147 complement.0.insert(Lower(Infinite));
148 complement.0.insert(tine);
149 complement.0.insert(Upper(Infinite));
150 return complement;
151 }
152
153 // Get first and last to handle infinite bounds.
154 match tine_iter.next() {
155 Some(&Lower(Infinite)) => {/* Do Nothing. */},
156 Some(tine) => {
157 complement.0.insert(Lower(Infinite));
158 complement.0.insert(tine.clone().invert());
159 },
160 _ => unreachable!("TineTree len > 1"),
161 }
162 match tine_iter.next_back() {
163 Some(&Upper(Infinite)) => {/* Do Nothing. */},
164 Some(tine) => {
165 complement.0.insert(Upper(Infinite));
166 complement.0.insert(tine.clone().invert());
167 },
168 _ => unreachable!("TineTree len > 0"),
169 }
170
171 // Invert all remaining tines.
172 for tine in tine_iter {
173 complement.0.insert(tine.clone().invert());
174 }
175
176 complement
177 }
178
179 /// Returns a `TineTree` containing all points in present in both of the
180 /// `TineTree`s.
181 #[must_use]
182 pub fn intersect(&self, other: &Self) -> Self {
183 let mut intersection = Self::new();
184 let self_intervals = self.interval_iter();
185 let mut other_intervals = other.interval_iter();
186
187 for self_interval in self_intervals {
188 'segment: loop {
189 if let Some(other_interval) = other_intervals.next() {
190 let i = self_interval.intersect(&other_interval);
191 if i.is_empty() {
192 // Nothing else overlaps in this segment.
193 break 'segment;
194 }
195
196 intersection.union_in_place(&i);
197 } else {
198 // Nothing else overlaps anywhere.
199 return intersection;
200 }
201 }
202 }
203 intersection
204 }
205
206 /// Returns a `TineTree` containing all points present in either of the
207 /// `TineTree`s.
208 #[must_use]
209 pub fn union(&self, other: &Self) -> Self {
210 let mut union = self.clone();
211 for interval in other.interval_iter() {
212 union.union_in_place(&interval);
213 }
214 union
215 }
216
217 /// Returns a `TineTree` containing the intersection of the given
218 /// `TineTree`'s intervals.
219 #[must_use]
220 pub fn minus(&self, other: &Self) -> Self {
221 let mut minus = self.clone();
222 for interval in other.interval_iter() {
223 minus.minus_in_place(&interval);
224 }
225 minus
226 }
227
228 /// Returns the smallest `RawInterval` containing all of the points in the
229 /// `TineTree`.
230 #[allow(clippy::missing_panics_doc)]
231 #[must_use]
232 pub fn enclose(&self) -> RawInterval<T> {
233 // Early exit if we're enclosing an empty interval.
234 if self.0.is_empty() {
235 return RawInterval::Empty;
236 }
237
238 let mut tine_iter = self.0.iter();
239
240 // Early exit if we're enclosing a point interval.
241 if self.0.len() == 1 {
242 let tine = tine_iter
243 .next()
244 .expect("nonempty TineTree");
245 debug_assert!(tine.is_point_include());
246 let pt = tine
247 .as_ref()
248 .expect("point Tine value")
249 .clone();
250 return RawInterval::Point(pt);
251 }
252
253 // Get first and last tines.
254 let lb = tine_iter
255 .next()
256 .expect("first tine with len > 1")
257 .clone()
258 .into_inner();
259 let ub = tine_iter
260 .next_back()
261 .expect("last tine with len > 1")
262 .clone()
263 .into_inner();
264
265 RawInterval::new(lb, ub)
266 }
267
268 /// Returns the smallest closed `RawInterval` containing all of the points
269 /// in the `TineTree`.
270 #[must_use]
271 pub fn closure(&self) -> RawInterval<T> {
272 self.enclose().closure()
273 }
274
275 ////////////////////////////////////////////////////////////////////////////
276 // In-place operations
277 ////////////////////////////////////////////////////////////////////////////
278
279 /// Intersects the given interval with the contents of the tree.
280 pub fn intersect_in_place(&mut self, interval: &RawInterval<T>) {
281 use Bound::*;
282 use Tine::*;
283
284 // Early exit if we're intersecting a full interval or are empty.
285 if self.0.is_empty() || interval.is_full() {return};
286
287 // Early exit if we're intersection an empty interval.
288 if interval.is_empty() {
289 *self = Self::new();
290 return;
291 }
292
293 // Early exit if we're intersection a point interval.
294 if let RawInterval::Point(pt) = interval {
295 if self.contains(pt) {
296 *self = Self::from_raw_interval(interval.clone());
297 } else {
298 *self = Self::new();
299 }
300 return;
301 }
302
303 match Tine::from_raw_interval(interval.clone()) {
304 Few::Zero => {
305 *self = Self::new();
306 },
307 Few::One(Point(Include(p))) => {
308 if self.contains(&p) {
309 *self = Self::from_raw_interval(RawInterval::Point(p));
310 } else {
311 *self = Self::new();
312 }
313 },
314 Few::Two(l, u) => {
315 self.intersect_proper_interval(l, u);
316 },
317 Few::One(_) => unreachable!("invalid Tine from interval"),
318 }
319 }
320
321 /// Internal implementation of `intersect_in_place`, handling the proper
322 /// interval case.
323 fn intersect_proper_interval(&mut self, l: Tine<T>, u: Tine<T>) {
324 let mut ts = self.interior_split_for_proper_interval(&l, &u);
325
326 // Merge tines if overlap or use given ones. We should only have `None`
327 // in the case of a intersection annhiliation.
328 let merged_l = if ts[2].is_some() {
329 ts[2].take().and_then(|lower| lower.intersect(&l))
330 } else {
331 Some(l)
332 };
333
334 let merged_u = if ts[3].is_some() {
335 ts[3].take().and_then(|upper| upper.intersect(&u))
336 } else {
337 Some(u)
338 };
339
340 // Ensure inner tines have the correct bounds.
341 debug_assert!(merged_l
342 .as_ref()
343 .map_or(true, Tine::is_lower_bound));
344 debug_assert!(merged_u
345 .as_ref()
346 .map_or(true, Tine::is_upper_bound));
347
348
349 // We need to detect whether the point is inside or outside an interval.
350 // To do this, we look at the tines inside and outside the interval.
351 let open_before = ts[0]
352 .as_ref()
353 .is_some_and(Tine::is_lower_bound);
354 let closed_after = ts[5]
355 .as_ref()
356 .is_some_and(Tine::is_upper_bound);
357
358 let in_l = ts[1]
359 .as_ref()
360 .is_some_and(Tine::is_upper_bound);
361 let in_r = ts[4]
362 .as_ref()
363 .is_some_and(Tine::is_lower_bound);
364
365
366 // Insert tines into the tree, ignoring them if the are not wrapped by a
367 // surrounding interval, or not wrapping a surrounding interval.
368 match (open_before, merged_l, in_l, in_r, merged_u, closed_after) {
369 (_, Some(l), true, true, Some(u), _ ) |
370 (_, Some(l), false, false, Some(u), _ ) => {
371 // ( ) ( )
372 // ( )
373 // O R
374 // ( )
375 // ( )
376 // O R
377 // ( )
378 // ( )
379 // O R
380 // ( )
381 // ( )
382 self.0.insert(l);
383 self.0.insert(u);
384 },
385 (true, Some(l), true, false, _, false) => {
386 // ( )
387 // ( )
388 // O R
389 // ( ) ( )
390 // ( )
391 self.0.insert(l);
392 },
393 (false, _, false, true, Some(u), true) => {
394 // ( )
395 // ( )
396 // O R
397 // ( ) ( )
398 // ( )
399 self.0.insert(u);
400 },
401 (false, _, false, false, _, false) => {
402 // ) (
403 // ( )
404 // O R
405 // ( )
406 // ( )
407 /* Do nothing. */
408 },
409 _ => unreachable!("invalid bounds for intersection interval"),
410 }
411 }
412
413 /// Unions the given interval with the contents of the tree.
414 pub fn union_in_place(&mut self, interval: &RawInterval<T>) {
415 // Early exit if we're unioning a full interval.
416 if interval.is_full() {
417 *self = Self::from_raw_interval(RawInterval::Full);
418 return;
419 }
420
421 match Tine::from_raw_interval(interval.clone()) {
422 Few::Zero => (),
423 Few::One(p) => self.union_point_interval(p),
424 Few::Two(l, u) => self.union_proper_interval(l, u),
425 }
426 }
427
428 /// Internal implementation of `union_in_place`, handling the point interval
429 /// case.
430 #[allow(clippy::cognitive_complexity)]
431 fn union_point_interval(&mut self, p: Tine<T>) {
432 let mut ts = self.exterior_split_for_point_interval(&p);
433
434 let p = if ts[1].is_some() {
435 if let Some(merged) = ts[1]
436 .take()
437 .and_then(|pt| pt.union(&p))
438 {
439 merged
440 } else {
441 // If the point annhilates, then we've already joined two
442 // intervals by removing the Point(Exclude(_)) from the tree in
443 // exterior_split_for_point_interval. So nothing else needs to happen.
444 return;
445 }
446 } else {
447 p
448 };
449
450 // We need to detect whether the point is inside or outside an interval.
451 // To do this, we look at the tines before and after the interval.
452 let open_before = ts[0]
453 .as_ref()
454 .is_some_and(Tine::is_lower_bound);
455 let closed_after = ts[2]
456 .as_ref()
457 .is_some_and(Tine::is_upper_bound);
458
459 // Insert tine into the tree, ignoring it if it is wrapped by a
460 // surrounding interval.
461 match (open_before, closed_after) {
462 (true, true) => {
463 // ( )
464 // |
465 // Do nothing.
466 },
467 (true, false) => {
468 // ( ) ( )
469 // |
470 debug_assert!(!p.is_lower_bound());
471 self.0.insert(p);
472 },
473 (false, true) => {
474 // ( ) ( )
475 // |
476 debug_assert!(!p.is_upper_bound());
477 self.0.insert(p);
478 },
479 (false, false) => {
480 // ( ) ( )
481 // |
482 self.0.insert(p);
483 },
484 }
485 }
486
487 /// Internal implementation of `union_in_place`, handling the proper
488 /// interval case.
489 fn union_proper_interval(&mut self, l: Tine<T>, u: Tine<T>) {
490 let mut ts = self.exterior_split_for_proper_interval(&l, &u);
491
492 // Merge tines if overlap or use given one. We should only have `None`
493 // in the case of a union annhiliation.
494 let merged_l = if ts[1].is_some() {
495 ts[1].take().and_then(|lower| lower.union(&l))
496 } else {
497 Some(l)
498 };
499
500 let merged_u = if ts[2].is_some() {
501 ts[2].take().and_then(|upper| upper.union(&u))
502 } else {
503 Some(u)
504 };
505
506 // Ensure inner tines have the correct bounds.
507 debug_assert!(merged_l
508 .as_ref()
509 .map_or(true, Tine::is_lower_bound));
510 debug_assert!(merged_u
511 .as_ref()
512 .map_or(true, Tine::is_upper_bound));
513
514 // We need to detect whether the interval is inside or outside an
515 // existing interval. To do this, we look at the tines before and after
516 // the interval.
517 let open_before = ts[0]
518 .as_ref()
519 .is_some_and(Tine::is_lower_bound);
520 let closed_after = ts[3]
521 .as_ref()
522 .is_some_and(Tine::is_upper_bound);
523
524 // Insert tines into the tree, ignoring them if the are wrapped by a
525 // surrounding interval.
526 match (open_before, merged_l, merged_u, closed_after) {
527 (true, Some(l), Some(u), true) => {
528 // ( ) ( )
529 // ( )
530 if l.is_upper_bound() {self.0.insert(l);}
531 if u.is_lower_bound() {self.0.insert(u);}
532 },
533 (true, Some(l), Some(u), false) => {
534 // ( ) ( ) ( )
535 // ( )
536 // O R
537 // ( ) ( )
538 // ( )
539 if l.is_upper_bound() {self.0.insert(l);}
540 debug_assert!(!u.is_lower_bound());
541 self.0.insert(u);
542 },
543 (false, Some(l), Some(u), true) => {
544 // ( ) ( ) ( )
545 // ( )
546 // O R
547 // ( ) ( ) ( )
548 // [ )
549 debug_assert!(!l.is_upper_bound());
550 self.0.insert(l);
551 if u.is_lower_bound() {self.0.insert(u);}
552
553 },
554 (false, Some(l), Some(u), false) => {
555 // ( ) ( ) ( )
556 // [ ]
557 // O R
558 // ( ) ( )
559 // [ ]
560 // O R
561 // ( ) ( ) ( )
562 // [ )
563 // O R
564 // ( ) ( )
565 // [ ]
566 debug_assert!(!l.is_upper_bound());
567 self.0.insert(l);
568 debug_assert!(!u.is_lower_bound());
569 self.0.insert(u);
570 },
571
572 (true, Some(l), None, true) => {
573 // ( ) ( ) ( )
574 // ( ]
575 if l.is_point_exclude() {self.0.insert(l);}
576 },
577 (false, Some(l), None, true) => {
578 // ( ) ( ) ( )
579 // [ ]
580 // O R
581 // ( ) ( ) ( )
582 // [ ]
583 debug_assert!(!l.is_upper_bound());
584 self.0.insert(l);
585 },
586
587 (true, None, Some(u), true) => {
588 // ( ) ( ) ( )
589 // [ )
590 if u.is_point_exclude() {self.0.insert(u);}
591 },
592 (true, None, Some(u), false) => {
593 // ( ) ( ) ( )
594 // [ ]
595 // O R
596 // ( ) ( ) ( )
597 // [ ]
598 debug_assert!(!u.is_lower_bound());
599 self.0.insert(u);
600 },
601
602 (true, None, None, true) => {
603 // ( ) ( ) ( )
604 // [ ]
605 // Do nothing.
606 },
607 _ => unreachable!("invalid bounds for union interval"),
608 }
609 }
610
611 /// Minuses the given interval from the contents of the tree.
612 pub fn minus_in_place(&mut self, interval: &RawInterval<T>) {
613 // Early exit if we're minusing an empty interval or are empty.
614 if self.0.is_empty() || interval.is_empty() {return};
615
616 // Early exit if we're minusing a full interval.
617 if interval.is_full() {
618 *self = Self::new();
619 return;
620 }
621
622 match Tine::from_raw_interval(interval.clone()) {
623 Few::Zero => (),
624 Few::One(p) => self.minus_point_interval(p),
625 Few::Two(l, u) => self.minus_proper_interval(l, u),
626 }
627 }
628
629 /// Internal implementation of `minus_in_place`, handling the point interval
630 /// case.
631 fn minus_point_interval(&mut self, p: Tine<T>) {
632 let mut ts = self.exterior_split_for_point_interval(&p);
633
634 let p = if ts[1].is_some() {
635 if let Some(merged) = ts[1]
636 .take()
637 .and_then(|pt| pt.minus(&p))
638 {
639 merged
640 } else {
641 // If the point annhilates, then we've already joined two
642 // intervals by removing the Point(Exclude(_)) from the tree in
643 // minus_split_tree_point. So nothing else needs to happen.
644 return;
645 }
646 } else {
647 p
648 };
649
650 // We need to detect whether the point is inside or outside an interval.
651 // To do this, we look at the tines before and after the interval.
652 let open_before = ts[0]
653 .as_ref()
654 .is_some_and(Tine::is_lower_bound);
655 let closed_after = ts[2]
656 .as_ref()
657 .is_some_and(Tine::is_upper_bound);
658
659 // Insert tine into the tree, ignoring it if it is wrapped by a
660 // surrounding interval.
661 // NOTE: We cannot have a Point(Exclude) here, because those will never
662 // result from an interval-tine conversion.
663 match (open_before, closed_after) {
664 (true, true) => {
665 // ( )
666 // |
667 self.0.insert(p.invert());
668 },
669 (true, false) => {
670 // ( ) ( )
671 // |
672 debug_assert!(p.is_upper_bound());
673 self.0.insert(p);
674 },
675 (false, true) => {
676 // ( ) ( )
677 // |
678 debug_assert!(p.is_lower_bound());
679 self.0.insert(p);
680 },
681 (false, false) => {
682 // ( ) ( )
683 // |
684 // Do nothing.
685 },
686 }
687 }
688
689
690 /// Internal implementation of `minus_in_place`, handling the proper
691 /// interval case.
692 #[allow(clippy::items_after_statements)]
693 fn minus_proper_interval(&mut self, l: Tine<T>, u: Tine<T>) {
694 let mut ts = self.exterior_split_for_proper_interval(&l, &u);
695
696 // Merge tines if overlap
697 let merged_l = if ts[1].is_some() {
698 ts[1].take().and_then(|lower| lower.minus(&l))
699 } else {
700 Some(l)
701 };
702
703 let merged_u = if ts[2].is_some() {
704 ts[2].take().and_then(|upper| upper.minus(&u))
705 } else {
706 Some(u)
707 };
708
709 // We need to detect whether the interval is inside or outside an
710 // existing interval. To do this, we look at the tines before and after
711 // the interval.
712 let open_before = ts[0]
713 .as_ref()
714 .is_some_and(Tine::is_lower_bound);
715 let closed_after = ts[3]
716 .as_ref()
717 .is_some_and(Tine::is_upper_bound);
718
719 // Insert tines into the tree, ignoring them if the are not wrapped by a
720 // surounding interval.
721 use Bound::*;
722 use Tine::*;
723 match (open_before, merged_l, merged_u, closed_after) {
724 (true, Some(l), Some(u), true) => {
725 // ( ) ( )
726 // ( )
727 // O R
728 // ( ) ( )
729 // ( )
730 self.0.insert(if l.is_upper_bound() {l} else {l.invert()});
731 self.0.insert(if u.is_lower_bound() {u} else {u.invert()});
732 },
733 (true, Some(l), upper, false) => {
734 // ( )
735 // ( )
736 // O R
737 // ( )
738 // ( )
739 // O R
740 // ( )
741 // ( )
742 // O R
743 // ( ]
744 // ( )
745 // O R
746 self.0.insert(if l.is_upper_bound() {l} else {l.invert()});
747 if let Some(Point(Include(p))) = upper {
748 self.0.insert(Point(Include(p)));
749 }
750 },
751 (false, lower, Some(u), true) => {
752 // ( )
753 // ( )
754 // O R
755 // ( )
756 // ( )
757 // O R
758 // ( )
759 // ( )
760 // O R
761 // [ )
762 // ( )
763 self.0.insert(if u.is_lower_bound() {u} else {u.invert()});
764 if let Some(Point(Include(p))) = lower {
765 self.0.insert(Point(Include(p)));
766 }
767 },
768 (false, Some(l), Some(u), false) => {
769 // ( )
770 // ( )
771 // O R
772 // [ ]
773 // ( )
774 if l.is_point_include() { self.0.insert(l); }
775 if u.is_point_include() { self.0.insert(u); }
776 },
777
778 (false, Some(l), None, false) => {
779 // [ )
780 // ( )
781 // O R
782 // |
783 // ( ]
784 if l.is_point_include() { self.0.insert(l); }
785 },
786
787 (false, None, Some(u), false) => {
788 // ( ]
789 // ( )
790 // O R
791 // |
792 // [ )
793 if u.is_point_include() { self.0.insert(u); }
794 },
795
796 (false, None, None, false) => {
797 // ( )
798 // ( )
799 // Do nothing.
800 },
801 _ => unreachable!("invalid bounds for minus interval"),
802 }
803 }
804
805 /// Splits the tine tree into three sections for an interval-like Tine to
806 /// prepare for an intersect operation.
807 ///
808 /// The resulting array contains the following values:
809 /// ```rust,ignore
810 /// [
811 /// 0 => Copy of the first tine less than the lower tine.
812 /// 1 => Copy of the first tine greater than the lower tine.
813 /// 2 => The tine equal to the lower tine.
814 /// 3 => The tine equal to the upper tine.
815 /// 4 => Copy of the first tine less than the upper tine.
816 /// 5 => Copy of the first tine greater than the upper tine.
817 /// ]
818 /// ```
819 ///
820 /// Any tines not between lower and upper are dropped.
821 fn interior_split_for_proper_interval(
822 &mut self,
823 lower: &Tine<T>,
824 upper: &Tine<T>)
825 -> [Option<Tine<T>>; 6]
826 {
827 debug_assert!(lower < upper);
828 let mut res = [None, None, None, None, None, None];
829
830 // Get lower and upper if they are in the tree.
831 res[2] = self.0.take(lower);
832 res[3] = self.0.take(upper);
833
834 // Get before and after points and drop anything not in the center.
835 let mut center = self.0.split_off(lower);
836 let right_side = center.split_off(upper);
837
838 {
839 let mut backward = self.0.iter();
840 res[0] = backward.next_back().cloned();
841
842 let mut forward = center.iter();
843 res[1] = forward.next().cloned();
844 }
845
846 {
847 let mut backward = center.iter().rev();
848 res[4] = backward.next().cloned();
849
850 let mut forward = right_side.iter();
851 res[5] = forward.next().cloned();
852 }
853
854 debug_assert_eq!(res[1].is_some(), res[4].is_some());
855
856 self.0 = center;
857 res
858 }
859
860 /// Splits the tine tree into three sections for a point-like Tine to
861 /// prepare for a union operation.
862 ///
863 /// The resulting array contains the following values:
864 /// ```rust,ignore
865 /// [
866 /// 0 => Copy of the first tine less than the given tine.
867 /// 1 => The tine equal to the given tine.
868 /// 2 => Copy of the first tine greater than the given tine.
869 /// ]
870 /// ```
871 fn exterior_split_for_point_interval(&mut self, tine: &Tine<T>)
872 -> [Option<Tine<T>>; 3]
873 {
874 let mut res = [None, None, None];
875
876 // Get pt if it is in the tree.
877 res[1] = self.0.take(tine);
878
879 // Get before and after points.
880 let mut right_side = self.0.split_off(tine);
881 res[0] = self.0.iter().next_back().cloned();
882 res[2] = right_side.iter().next().cloned();
883
884 self.0.append(&mut right_side);
885 res
886 }
887
888 /// Splits the tine tree into three sections for an interval-like Tine in
889 /// preperation for a union or minus operation.
890 ///
891 /// The resulting array contains the following values:
892 /// ```rust,ignore
893 /// [
894 /// 0 => Copy of the first tine less than the lower tine.
895 /// 1 => The tine equal to the lower tine.
896 /// 2 => The tine equal to the upper tine.
897 /// 3 => Copy of the first tine greater than the upper tine.
898 /// ]
899 /// ```
900 ///
901 /// Any tines between lower and upper are dropped.
902 fn exterior_split_for_proper_interval(
903 &mut self,
904 lower: &Tine<T>,
905 upper: &Tine<T>)
906 -> [Option<Tine<T>>; 4]
907 {
908 let mut res = [None, None, None, None];
909
910 // Get lower and upper if they are in the tree.
911 res[1] = self.0.take(lower);
912 res[2] = self.0.take(upper);
913
914 // Get before and after points and drop anything in the center.
915 let mut center = self.0.split_off(lower);
916 {
917 let mut backward = self.0.iter();
918 res[0] = backward.next_back().cloned();
919 }
920
921 let mut right_side = center.split_off(upper);
922 {
923 let mut forward = right_side.iter();
924 res[3] = forward.next().cloned();
925 }
926
927 self.0.append(&mut right_side);
928 res
929 }
930
931 ////////////////////////////////////////////////////////////////////////////
932 // Iterator conversions
933 ////////////////////////////////////////////////////////////////////////////
934
935 /// Returns an iterator over each of the `RawInterval`s in the tree.
936 #[must_use]
937 pub fn interval_iter(&self) -> Iter<'_, T> {
938 Iter {
939 tine_iter: self.0.iter(),
940 saved_lower: None,
941 saved_upper: None,
942 }
943 }
944}
945
946impl<T> Default for TineTree<T> where T: Ord + Clone {
947 fn default() -> Self {
948 Self::new()
949 }
950}
951
952////////////////////////////////////////////////////////////////////////////////
953// Conversion traits
954////////////////////////////////////////////////////////////////////////////////
955impl<T> From<RawInterval<T>> for TineTree<T> where T: Ord + Clone {
956 fn from(interval: RawInterval<T>) -> Self {
957 Self::from_raw_interval(interval)
958 }
959}
960
961impl<T, I> From<I> for TineTree<T>
962 where
963 T: Ord + Clone,
964 I: Iterator<Item=RawInterval<T>>
965{
966 fn from(iter: I) -> Self {
967 let mut tine_tree = Self::new();
968 for interval in iter {
969 tine_tree.union_in_place(&interval);
970 }
971 tine_tree
972 }
973}
974
975impl<T> FromIterator<RawInterval<T>> for TineTree<T>
976 where T: Ord + Clone
977{
978 fn from_iter<I>(iter: I) -> Self
979 where I: IntoIterator<Item=RawInterval<T>>
980 {
981 let mut tine_tree = Self::new();
982 for interval in iter {
983 tine_tree.union_in_place(&interval);
984 }
985 tine_tree
986 }
987}
988
989impl<T> IntoIterator for TineTree<T>
990 where T: Ord + Clone
991{
992 type Item = RawInterval<T>;
993 type IntoIter = IntoIter<T>;
994
995 fn into_iter(self) -> Self::IntoIter {
996 IntoIter {
997 inner: self.0.into_iter(),
998 saved_lower: None,
999 saved_upper: None,
1000 }
1001 }
1002}
1003
1004
1005////////////////////////////////////////////////////////////////////////////////
1006// IntoIter
1007////////////////////////////////////////////////////////////////////////////////
1008/// An owning `Iterator` over the `TineTree`s `RawInterval`s.
1009#[derive(Debug)]
1010pub struct IntoIter<T> {
1011 /// The tree's `Tine`s in order.
1012 inner: btree_set::IntoIter<Tine<T>>,
1013 /// A saved lower-bound tine.
1014 saved_lower: Option<Tine<T>>,
1015 /// A saved upper-bound tine.
1016 saved_upper: Option<Tine<T>>,
1017}
1018
1019impl<T> Iterator for IntoIter<T> where T: Ord + Clone {
1020 type Item = RawInterval<T>;
1021
1022 fn next(&mut self) -> Option<Self::Item> {
1023 use Bound::*;
1024 use Tine::*;
1025 self.saved_lower
1026 .take()
1027 .or_else(|| self.inner.next())
1028 .map(|lower| {
1029 if let Point(Include(p)) = lower {
1030 // Next tine is a single point.
1031 RawInterval::Point(p)
1032 } else {
1033 // Next tine must be a lower bound of an interval.
1034 debug_assert!(lower.is_lower_bound());
1035
1036 let upper = self.inner.next()
1037 .or_else(|| self.saved_upper.take())
1038 .expect("interval is not partial");
1039
1040 if upper.is_point_exclude() {
1041 self.saved_lower = Some(upper.clone());
1042 }
1043
1044 // ... and the next tine after must be an upper bound.
1045 debug_assert!(upper.is_upper_bound());
1046
1047 let lower = lower.into_inner();
1048 let upper = upper.into_inner();
1049 RawInterval::new(lower, upper)
1050 }
1051 })
1052 }
1053}
1054
1055impl<T> DoubleEndedIterator for IntoIter<T>
1056 where T: Ord + Clone
1057{
1058 fn next_back(&mut self) -> Option<Self::Item> {
1059 use Bound::*;
1060 use Tine::*;
1061 self.saved_upper
1062 .take()
1063 .or_else(|| self.inner.next_back())
1064 .map(|upper| {
1065 if let Point(Include(p)) = upper {
1066 // Next tine is a single point.
1067 RawInterval::Point(p)
1068 } else {
1069 // Next tine must be an upper bound of an interval.
1070 debug_assert!(upper.is_upper_bound());
1071
1072 let lower = self.inner.next_back()
1073 .or_else(|| self.saved_lower.take())
1074 .expect("interval is not partial");
1075
1076 if lower.is_point_exclude() {
1077 self.saved_lower = Some(lower.clone());
1078 }
1079
1080 // ... and the next tine after must be a lower bound.
1081 debug_assert!(lower.is_lower_bound());
1082
1083 let upper = upper.into_inner();
1084 let lower = lower.into_inner();
1085 RawInterval::new(lower, upper)
1086 }
1087 })
1088 }
1089}
1090
1091////////////////////////////////////////////////////////////////////////////////
1092// Iter
1093////////////////////////////////////////////////////////////////////////////////
1094/// An `Iterator` that constructs `RawInterval`s from a sequence of `Tine`s.
1095#[derive(Debug)]
1096pub struct Iter<'t, T> {
1097 /// The tree's `Tine`s in order.
1098 #[allow(clippy::struct_field_names)]
1099 tine_iter: btree_set::Iter<'t, Tine<T>>,
1100 /// A saved lower-bound tine.
1101 saved_lower: Option<Tine<T>>,
1102 /// A saved upper-bound tine.
1103 saved_upper: Option<Tine<T>>,
1104}
1105
1106impl<'t, T> Iterator for Iter<'t, T>
1107 where T: Ord + Clone
1108{
1109 type Item = RawInterval<T>;
1110
1111 fn next(&mut self) -> Option<Self::Item> {
1112 use Bound::*;
1113 use Tine::*;
1114 self.saved_lower
1115 .take()
1116 .or_else(|| self.tine_iter.next().cloned())
1117 .map(|lower| {
1118 if let Point(Include(p)) = lower {
1119 // Next tine is a single point.
1120 RawInterval::Point(p)
1121 } else {
1122 // Next tine must be a lower bound of an interval.
1123 debug_assert!(lower.is_lower_bound());
1124
1125 let upper = self.tine_iter.next().cloned()
1126 .or_else(|| self.saved_upper.take())
1127 .expect("interval is not partial");
1128
1129 if upper.is_point_exclude() {
1130 self.saved_lower = Some(upper.clone());
1131 }
1132
1133 // ... and the next tine after must be an upper bound.
1134 debug_assert!(upper.is_upper_bound());
1135
1136 let lower = lower.into_inner();
1137 let upper = upper.into_inner();
1138 RawInterval::new(lower, upper)
1139 }
1140 })
1141
1142 }
1143}
1144
1145impl<'t, T> DoubleEndedIterator for Iter<'t, T>
1146 where T: Ord + Clone
1147{
1148 fn next_back(&mut self) -> Option<Self::Item> {
1149 use Bound::*;
1150 use Tine::*;
1151 self.saved_upper
1152 .take()
1153 .or_else(|| self.tine_iter.next_back().cloned())
1154 .map(|upper| {
1155 if let Point(Include(p)) = upper {
1156 // Next tine is a single point.
1157 RawInterval::Point(p)
1158 } else {
1159 // Next tine must be an upper bound of an interval.
1160 debug_assert!(upper.is_upper_bound());
1161
1162 let lower = self.tine_iter.next_back().cloned()
1163 .or_else(|| self.saved_lower.take())
1164 .expect("interval is not partial");
1165
1166 if lower.is_point_exclude() {
1167 self.saved_lower = Some(lower.clone());
1168 }
1169
1170 // ... and the next tine after must be a lower bound.
1171 debug_assert!(lower.is_lower_bound());
1172
1173 let upper = upper.into_inner();
1174 let lower = lower.into_inner();
1175 RawInterval::new(lower, upper)
1176 }
1177 })
1178 }
1179}