range_set_blaze/
sorted_disjoint.rs

1use crate::map::ValueRef;
2use crate::range_values::{MapIntoRangesIter, MapRangesIter, RangeValuesToRangesIter};
3use crate::ranges_iter::RangesIter;
4use crate::sorted_disjoint_map::IntoString;
5use crate::RangeSetBlaze;
6use crate::{IntoRangesIter, UnionIter, UnionMerge};
7use alloc::string::String;
8use core::array;
9use core::{
10    iter::FusedIterator,
11    ops::{self, RangeInclusive},
12};
13
14use crate::SortedDisjointMap;
15
16use crate::{
17    DifferenceMerge, DynSortedDisjoint, Integer, IntersectionMerge, NotIter, SymDiffIter,
18    SymDiffMerge,
19};
20
21/// Used internally. Marks iterators that provide ranges sorted by start, but
22/// that are not necessarily disjoint. The ranges are non-empty.
23pub trait SortedStarts<T: Integer>: Iterator<Item = RangeInclusive<T>> + FusedIterator {}
24
25/// Marks iterators that provide ranges that are sorted by start and disjoint. Set operations on
26/// iterators that implement this trait can be performed in linear time.
27///
28/// # Table of Contents
29/// * [`SortedDisjoint` Constructors](#sorteddisjoint-constructors)
30///   * [Examples](#constructor-examples)
31/// * [`SortedDisjoint` Set Operations](#sorteddisjoint-set-operations)
32///   * [Performance](#performance)
33///   * [Examples](#examples)
34/// * [How to mark your type as `SortedDisjoint`](#how-to-mark-your-type-as-sorteddisjoint)
35///   * [Example – Find the ordinal weekdays in September 2023](#example--find-the-ordinal-weekdays-in-september-2023)
36///
37/// # `SortedDisjoint` Constructors
38///
39/// You'll usually construct a `SortedDisjoint` iterator from a [`RangeSetBlaze`] or a [`CheckSortedDisjoint`].
40/// Here is a summary table, followed by [examples](#constructor-examples). You can also [define your own
41/// `SortedDisjoint`](#how-to-mark-your-type-as-sorteddisjoint).
42///
43/// | Input type | Method |
44/// |------------|--------|
45/// | [`RangeSetBlaze`] | [`ranges`] |
46/// | [`RangeSetBlaze`] | [`into_ranges`] |
47/// | sorted & disjoint ranges | [`CheckSortedDisjoint::new`] |
48/// |  *your iterator type* | *[How to mark your type as `SortedDisjoint`][1]* |
49///
50/// [`ranges`]: RangeSetBlaze::ranges
51/// [`into_ranges`]: RangeSetBlaze::into_ranges
52/// [1]: #how-to-mark-your-type-as-sorteddisjoint
53/// [`RangesIter`]: crate::RangesIter
54/// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
55///
56/// ## Constructor Examples
57/// ```
58/// use range_set_blaze::prelude::*;
59///
60/// // RangeSetBlaze's .ranges() and .into_ranges()
61/// let r = RangeSetBlaze::from_iter([3, 2, 1, 100, 1]);
62/// let a = r.ranges();
63/// assert!(a.into_string() == "1..=3, 100..=100");
64/// // 'into_ranges' takes ownership of the 'RangeSetBlaze'
65/// let a = RangeSetBlaze::from_iter([3, 2, 1, 100, 1]).into_ranges();
66/// assert!(a.into_string() == "1..=3, 100..=100");
67///
68/// // CheckSortedDisjoint -- unsorted or overlapping input ranges will cause a panic.
69/// let a = CheckSortedDisjoint::new([1..=3, 100..=100]);
70/// assert!(a.into_string() == "1..=3, 100..=100");
71/// ```
72///
73/// # `SortedDisjoint` Set Operations
74///
75/// You can perform set operations on `SortedDisjoint`s using operators.
76///
77/// | Set Operators                             | Operator    | Multiway (same type)                              | Multiway (different types)           |
78/// |------------------------------------|-------------|---------------------------------------------------|--------------------------------------|
79/// | [`union`]                      | [`a` &#124; `b`] | `[a, b, c].`[`union`][multiway_union]`() `        | [`union_dyn!`]`(a, b, c)`         |                    
80/// | [`intersection`]               | [`a & b`]     | `[a, b, c].`[`intersection`][multiway_intersection]`() ` | [`intersection_dyn!`]`(a, b, c)`|
81/// | [`difference`]                 | [`a - b`]     | *n/a*                                             | *n/a*                                |
82/// | [`symmetric_difference`]       | [`a ^ b`]     | `[a, b, c].`[`symmetric_difference`][multiway_symmetric_difference]`() ` | [`symmetric_difference_dyn!`]`(a, b, c)` |
83/// | [`complement`]                 | [`!a`]        | *n/a*                                             | *n/a*                                |
84///
85/// [`a` &#124; `b`]: trait.SortedDisjoint.html#method.union
86/// [`a & b`]: trait.SortedDisjoint.html#method.intersection
87/// [`a - b`]: trait.SortedDisjoint.html#method.difference
88/// [`a ^ b`]: trait.SortedDisjoint.html#method.symmetric_difference
89/// [`!a`]: trait.SortedDisjoint.html#method.complement
90/// [multiway_union]: trait.MultiwaySortedDisjoint.html#method.union
91/// [multiway_intersection]: trait.MultiwaySortedDisjoint.html#method.intersection
92/// [multiway_symmetric_difference]: trait.MultiwaySortedDisjoint.html#method.symmetric_difference
93/// [`union_dyn!`]: macro.union_dyn.html
94/// [`intersection_dyn!`]: macro.intersection_dyn.html
95/// [`symmetric_difference_dyn!`]: macro.symmetric_difference_dyn.html
96///
97/// ## Performance
98///
99/// Every operation is implemented as a single pass over the sorted & disjoint ranges, with minimal memory.
100///
101/// This is true even when applying multiple operations. The last example below demonstrates this.
102///
103/// ## Examples
104///
105/// ```
106/// use range_set_blaze::prelude::*;
107///
108/// let a0 = RangeSetBlaze::from_iter([1..=2, 5..=100]);
109/// let b0 = RangeSetBlaze::from_iter([2..=6]);
110///
111/// // 'union' method and 'to_string' method
112/// let (a, b) = (a0.ranges(), b0.ranges());
113/// let result = a.union(b);
114/// assert_eq!(result.into_string(), "1..=100");
115///
116/// // '|' operator and 'equal' method
117/// let (a, b) = (a0.ranges(), b0.ranges());
118/// let result = a | b;
119/// assert!(result.equal(CheckSortedDisjoint::new([1..=100])));
120///
121/// // multiway union of same type
122/// let c0 = RangeSetBlaze::from_iter([2..=2, 6..=200]);
123/// let (a, b, c) = (a0.ranges(), b0.ranges(), c0.ranges());
124/// let result = [a, b, c].union();
125/// assert_eq!(result.into_string(), "1..=200");
126///
127/// // multiway union of different types
128/// let (a, b, c) = (a0.ranges(), b0.ranges(), c0.ranges());
129/// let result = union_dyn!(a, b, !c);
130/// assert_eq!(result.into_string(), "-2147483648..=100, 201..=2147483647");
131///
132/// // Applying multiple operators makes only one pass through the inputs with minimal memory.
133/// let (a, b, c) = (a0.ranges(), b0.ranges(), c0.ranges());
134/// let result = a - (b | c);
135/// assert!(result.into_string() == "1..=1");
136/// ```
137///
138/// # How to mark your type as `SortedDisjoint`
139///
140/// To mark your iterator type as `SortedDisjoint`, you implement the `SortedStarts` and `SortedDisjoint` traits.
141/// This is your promise to the compiler that your iterator will provide inclusive ranges that are
142/// disjoint and sorted by start.
143///
144/// When you do this, your iterator will get access to the
145/// efficient set operations methods, such as [`intersection`] and [`complement`]. The example below shows this.
146///
147/// > To use operators such as `&` and `!`, you must also implement the [`BitAnd`], [`Not`], etc. traits.
148/// >
149/// > If you want others to use your marked iterator type, reexport:
150/// > `pub use range_set_blaze::{SortedDisjoint, SortedStarts};`
151///
152/// [`BitAnd`]: core::ops::BitAnd
153/// [`Not`]: core::ops::Not
154/// [`intersection`]: SortedDisjoint::intersection
155/// [`complement`]: SortedDisjoint::complement
156/// [`union`]: SortedDisjoint::union
157/// [`symmetric_difference`]: SortedDisjoint::symmetric_difference
158/// [`difference`]: SortedDisjoint::difference
159/// [`to_string`]: SortedDisjoint::to_string
160/// [`equal`]: SortedDisjoint::equal
161/// [multiway_union]: crate::MultiwaySortedDisjoint::union
162/// [multiway_intersection]: crate::MultiwaySortedDisjoint::intersection
163///
164/// ## Example -- Find the ordinal weekdays in September 2023
165/// ```
166/// use core::ops::RangeInclusive;
167/// use core::iter::FusedIterator;
168/// pub use range_set_blaze::{SortedDisjoint, SortedStarts};
169///
170/// // Ordinal dates count January 1 as day 1, February 1 as day 32, etc.
171/// struct OrdinalWeekends2023 {
172///     next_range: RangeInclusive<i32>,
173/// }
174///
175/// // We promise the compiler that our iterator will provide
176/// // ranges that are sorted and disjoint.
177/// impl FusedIterator for OrdinalWeekends2023 {}
178/// impl SortedStarts<i32> for OrdinalWeekends2023 {}
179/// impl SortedDisjoint<i32> for OrdinalWeekends2023 {}
180///
181/// impl OrdinalWeekends2023 {
182///     fn new() -> Self {
183///         Self { next_range: 0..=1 }
184///     }
185/// }
186/// impl Iterator for OrdinalWeekends2023 {
187///     type Item = RangeInclusive<i32>;
188///     fn next(&mut self) -> Option<Self::Item> {
189///         let (start, end) = self.next_range.clone().into_inner();
190///         if start > 365 {
191///             None
192///         } else {
193///             self.next_range = (start + 7)..=(end + 7);
194///             Some(start.max(1)..=end.min(365))
195///         }
196///     }
197/// }
198///
199/// use range_set_blaze::prelude::*;
200///
201/// let weekends = OrdinalWeekends2023::new();
202/// let september = CheckSortedDisjoint::new([244..=273]);
203/// let september_weekdays = september.intersection(weekends.complement());
204/// assert_eq!(
205///     september_weekdays.into_string(),
206///     "244..=244, 247..=251, 254..=258, 261..=265, 268..=272"
207/// );
208/// ```
209pub trait SortedDisjoint<T: Integer>: SortedStarts<T> {
210    // I think this is 'Sized' because will sometimes want to create a struct (e.g. BitOrIter) that contains a field of this type
211
212    /// Given two [`SortedDisjoint`] iterators, efficiently returns a [`SortedDisjoint`] iterator of their union.
213    ///
214    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
215    ///
216    /// # Examples
217    ///
218    /// ```
219    /// use range_set_blaze::prelude::*;
220    ///
221    /// let a = CheckSortedDisjoint::new([1..=1]);
222    /// let b = RangeSetBlaze::from_iter([2..=2]).into_ranges();
223    /// let union = a.union(b);
224    /// assert_eq!(union.into_string(), "1..=2");
225    ///
226    /// // Alternatively, we can use "|" because CheckSortedDisjoint defines
227    /// // ops::bitor as SortedDisjoint::union.
228    /// let a = CheckSortedDisjoint::new([1..=1]);
229    /// let b = RangeSetBlaze::from_iter([2..=2]).into_ranges();
230    /// let union = a | b;
231    /// assert_eq!(union.into_string(), "1..=2");
232    /// ```
233    #[inline]
234    fn union<R>(self, other: R) -> UnionMerge<T, Self, R::IntoIter>
235    where
236        R: IntoIterator<Item = Self::Item>,
237        R::IntoIter: SortedDisjoint<T>,
238        Self: Sized,
239    {
240        UnionMerge::new2(self, other.into_iter())
241    }
242
243    /// Given two [`SortedDisjoint`] iterators, efficiently returns a [`SortedDisjoint`] iterator of their intersection.
244    ///
245    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
246    ///
247    /// # Examples
248    ///
249    /// ```
250    /// use range_set_blaze::prelude::*;
251    ///
252    /// let a = CheckSortedDisjoint::new([1..=2]);
253    /// let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
254    /// let intersection = a.intersection(b);
255    /// assert_eq!(intersection.into_string(), "2..=2");
256    ///
257    /// // Alternatively, we can use "&" because CheckSortedDisjoint defines
258    /// // ops::bitand as SortedDisjoint::intersection.
259    /// let a = CheckSortedDisjoint::new([1..=2]);
260    /// let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
261    /// let intersection = a & b;
262    /// assert_eq!(intersection.into_string(), "2..=2");
263    /// ```
264    #[inline]
265    fn intersection<R>(self, other: R) -> IntersectionMerge<T, Self, R::IntoIter>
266    where
267        R: IntoIterator<Item = Self::Item>,
268        R::IntoIter: SortedDisjoint<T>,
269        Self: Sized,
270    {
271        !(self.complement() | other.into_iter().complement())
272    }
273
274    /// Given two [`SortedDisjoint`] iterators, efficiently returns a [`SortedDisjoint`] iterator of their set difference.
275    ///
276    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
277    ///
278    /// # Examples
279    ///
280    /// ```
281    /// use range_set_blaze::prelude::*;
282    ///
283    /// let a = CheckSortedDisjoint::new([1..=2]);
284    /// let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
285    /// let difference = a.difference(b);
286    /// assert_eq!(difference.into_string(), "1..=1");
287    ///
288    /// // Alternatively, we can use "-" because CheckSortedDisjoint defines
289    /// // ops::sub as SortedDisjoint::difference.
290    /// let a = CheckSortedDisjoint::new([1..=2]);
291    /// let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
292    /// let difference = a - b;
293    /// assert_eq!(difference.into_string(), "1..=1");
294    /// ```
295    #[inline]
296    fn difference<R>(self, other: R) -> DifferenceMerge<T, Self, R::IntoIter>
297    where
298        R: IntoIterator<Item = Self::Item>,
299        R::IntoIter: SortedDisjoint<T>,
300        Self: Sized,
301    {
302        !(self.complement() | other.into_iter())
303    }
304
305    /// Given a [`SortedDisjoint`] iterator, efficiently returns a [`SortedDisjoint`] iterator of its complement.
306    ///
307    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
308    ///
309    /// # Examples
310    ///
311    /// ```
312    /// use range_set_blaze::prelude::*;
313    ///
314    /// let a = CheckSortedDisjoint::new([10_u8..=20, 100..=200]);
315    /// let complement = a.complement();
316    /// assert_eq!(complement.into_string(), "0..=9, 21..=99, 201..=255");
317    ///
318    /// // Alternatively, we can use "!" because CheckSortedDisjoint defines
319    /// // `ops::Not` as `SortedDisjoint::complement`.
320    /// let a = CheckSortedDisjoint::new([10_u8..=20, 100..=200]);
321    /// let complement = !a;
322    /// assert_eq!(complement.into_string(), "0..=9, 21..=99, 201..=255");
323    /// ```
324    #[inline]
325    fn complement(self) -> NotIter<T, Self>
326    where
327        Self: Sized,
328    {
329        NotIter::new(self)
330    }
331
332    /// Given two [`SortedDisjoint`] iterators, efficiently returns a [`SortedDisjoint`] iterator
333    /// of their symmetric difference.
334    ///
335    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
336    /// # Examples
337    ///
338    /// ```
339    /// use range_set_blaze::prelude::*;
340    ///
341    /// let a = CheckSortedDisjoint::new([1..=2]);
342    /// let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
343    /// let symmetric_difference = a.symmetric_difference(b);
344    /// assert_eq!(symmetric_difference.into_string(), "1..=1, 3..=3");
345    ///
346    /// // Alternatively, we can use "^" because CheckSortedDisjoint defines
347    /// // ops::bitxor as SortedDisjoint::symmetric_difference.
348    /// let a = CheckSortedDisjoint::new([1..=2]);
349    /// let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
350    /// let symmetric_difference = a ^ b;
351    /// assert_eq!(symmetric_difference.into_string(), "1..=1, 3..=3");
352    /// ```
353    #[inline]
354    fn symmetric_difference<R>(self, other: R) -> SymDiffMerge<T, Self, R::IntoIter>
355    where
356        R: IntoIterator<Item = Self::Item>,
357        R::IntoIter: SortedDisjoint<T>,
358        <R as IntoIterator>::IntoIter:,
359        Self: Sized,
360    {
361        let result: SymDiffIter<T, crate::Merge<T, Self, <R as IntoIterator>::IntoIter>> =
362            SymDiffIter::new2(self, other.into_iter());
363        result
364    }
365
366    /// Given two [`SortedDisjoint`] iterators, efficiently tells if they are equal. Unlike most equality testing in Rust,
367    /// this method takes ownership of the iterators and consumes them.
368    ///
369    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
370    ///
371    /// # Examples
372    ///
373    /// ```
374    /// use range_set_blaze::prelude::*;
375    ///
376    /// let a = CheckSortedDisjoint::new([1..=2]);
377    /// let b = RangeSetBlaze::from_iter([1..=2]).into_ranges();
378    /// assert!(a.equal(b));
379    /// ```
380    fn equal<R>(self, other: R) -> bool
381    where
382        R: IntoIterator<Item = Self::Item>,
383        R::IntoIter: SortedDisjoint<T>,
384        Self: Sized,
385    {
386        itertools::equal(self, other)
387    }
388
389    /// Deprecated. Use [`into_string`] instead.
390    ///
391    /// [`into_string`]: trait.IntoString.html
392    #[deprecated(since = "0.2.0", note = "Use `into_string` instead")]
393    fn to_string(self) -> String
394    where
395        Self: Sized,
396    {
397        self.into_string()
398    }
399
400    /// Returns `true` if the set contains no elements.
401    ///
402    /// # Examples
403    ///
404    /// ```
405    /// use range_set_blaze::prelude::*;
406    ///
407    /// let a = CheckSortedDisjoint::new([1..=2]);
408    /// assert!(!a.is_empty());
409    /// ```
410    #[inline]
411    #[allow(clippy::wrong_self_convention)]
412    fn is_empty(mut self) -> bool
413    where
414        Self: Sized,
415    {
416        self.next().is_none()
417    }
418
419    /// Returns `true` if the set is a subset of another,
420    /// i.e., `other` contains at least all the elements in `self`.
421    ///
422    /// # Examples
423    ///
424    /// ```
425    /// use range_set_blaze::prelude::*;
426    ///
427    /// let sup = CheckSortedDisjoint::new([1..=3]);
428    /// let set: CheckSortedDisjoint<i32, _> = [].into();
429    /// assert_eq!(set.is_subset(sup), true);
430    ///
431    /// let sup = CheckSortedDisjoint::new([1..=3]);
432    /// let set = CheckSortedDisjoint::new([2..=2]);
433    /// assert_eq!(set.is_subset(sup), true);
434    ///
435    /// let sup = CheckSortedDisjoint::new([1..=3]);
436    /// let set = CheckSortedDisjoint::new([2..=2, 4..=4]);
437    /// assert_eq!(set.is_subset(sup), false);
438    /// ```
439    #[must_use]
440    #[inline]
441    #[allow(clippy::wrong_self_convention)]
442    fn is_subset<R>(self, other: R) -> bool
443    where
444        R: IntoIterator<Item = Self::Item>,
445        R::IntoIter: SortedDisjoint<T>,
446        Self: Sized,
447    {
448        // LATER: Could be made a little more efficient by coding the logic directly into the iterators.
449        self.difference(other).is_empty()
450    }
451
452    /// Returns `true` if the set is a superset of another,
453    /// i.e., `self` contains at least all the elements in `other`.
454    ///
455    /// # Examples
456    ///
457    /// ```
458    /// use range_set_blaze::RangeSetBlaze;
459    ///
460    /// let sub = RangeSetBlaze::from_iter([1, 2]);
461    /// let mut set = RangeSetBlaze::new();
462    ///
463    /// assert_eq!(set.is_superset(&sub), false);
464    ///
465    /// set.insert(0);
466    /// set.insert(1);
467    /// assert_eq!(set.is_superset(&sub), false);
468    ///
469    /// set.insert(2);
470    /// assert_eq!(set.is_superset(&sub), true);
471    /// ```
472    #[inline]
473    #[must_use]
474    #[allow(clippy::wrong_self_convention)]
475    fn is_superset<R>(self, other: R) -> bool
476    where
477        R: IntoIterator<Item = Self::Item>,
478        R::IntoIter: SortedDisjoint<T>,
479        Self: Sized,
480    {
481        other.into_iter().is_subset(self)
482    }
483
484    /// Returns `true` if `self` has no elements in common with `other`.
485    /// This is equivalent to checking for an empty intersection.
486    ///
487    /// # Examples
488    ///
489    /// ```
490    /// use range_set_blaze::RangeSetBlaze;
491    ///
492    /// let a = RangeSetBlaze::from_iter([1..=3]);
493    /// let mut b = RangeSetBlaze::new();
494    ///
495    /// assert_eq!(a.is_disjoint(&b), true);
496    /// b.insert(4);
497    /// assert_eq!(a.is_disjoint(&b), true);
498    /// b.insert(1);
499    /// assert_eq!(a.is_disjoint(&b), false);
500    /// ```
501    #[must_use]
502    #[inline]
503    #[allow(clippy::wrong_self_convention)]
504    fn is_disjoint<R>(self, other: R) -> bool
505    where
506        R: IntoIterator<Item = Self::Item>,
507        R::IntoIter: SortedDisjoint<T>,
508        Self: Sized,
509    {
510        self.intersection(other).is_empty()
511    }
512
513    /// Create a [`RangeSetBlaze`] from a [`SortedDisjoint`] iterator.
514    ///
515    /// *For more about constructors and performance, see [`RangeSetBlaze` Constructors](struct.RangeSetBlaze.html#rangesetblaze-constructors).*
516    ///
517    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
518    ///
519    /// # Examples
520    ///
521    /// ```
522    /// use range_set_blaze::prelude::*;
523    ///
524    /// let a0 = RangeSetBlaze::from_sorted_disjoint(CheckSortedDisjoint::new([-10..=-5, 1..=2]));
525    /// let a1: RangeSetBlaze<i32> = CheckSortedDisjoint::new([-10..=-5, 1..=2]).into_range_set_blaze();
526    /// assert!(a0 == a1 && a0.to_string() == "-10..=-5, 1..=2");
527    /// ```
528    fn into_range_set_blaze(self) -> RangeSetBlaze<T>
529    where
530        Self: Sized,
531    {
532        RangeSetBlaze::from_sorted_disjoint(self)
533    }
534}
535
536/// Gives the [`SortedDisjoint`] trait to any iterator of ranges. The iterator will panic
537/// if/when it finds that the ranges are not actually sorted and disjoint.
538///
539/// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
540///
541/// # Performance
542///
543/// All checking is done at runtime, but it should still be fast.
544///
545/// # Example
546///
547/// ```
548/// use range_set_blaze::prelude::*;
549///
550/// let a = CheckSortedDisjoint::new([1..=2, 5..=100]);
551/// let b = CheckSortedDisjoint::new([2..=6]);
552/// let union = a | b;
553/// assert_eq!(union.into_string(), "1..=100");
554/// ```
555///
556/// Here the ranges are not sorted and disjoint, so the iterator will panic.
557///```should_panic
558/// use range_set_blaze::prelude::*;
559///
560/// let a = CheckSortedDisjoint::new([1..=2, 5..=100]);
561/// let b = CheckSortedDisjoint::new([2..=6,-10..=-5]);
562/// let union = a | b;
563/// assert_eq!(union.into_string(), "1..=100");
564/// ```
565#[derive(Debug, Clone)]
566#[must_use = "iterators are lazy and do nothing unless consumed"]
567#[allow(clippy::module_name_repetitions)]
568pub struct CheckSortedDisjoint<T, I>
569where
570    T: Integer,
571    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
572{
573    pub(crate) iter: I,
574    prev_end: Option<T>,
575    seen_none: bool,
576}
577
578impl<T, I> CheckSortedDisjoint<T, I>
579where
580    T: Integer,
581    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
582{
583    /// Creates a new [`CheckSortedDisjoint`] from an iterator of ranges. See [`CheckSortedDisjoint`] for details and examples.
584    #[inline]
585    pub fn new<J: IntoIterator<IntoIter = I>>(iter: J) -> Self {
586        Self {
587            iter: iter.into_iter(),
588            prev_end: None,
589            seen_none: false,
590        }
591    }
592}
593
594impl<T> Default for CheckSortedDisjoint<T, array::IntoIter<RangeInclusive<T>, 0>>
595where
596    T: Integer,
597{
598    // Default is an empty iterator.
599    fn default() -> Self {
600        Self::new([])
601    }
602}
603
604impl<T, I> FusedIterator for CheckSortedDisjoint<T, I>
605where
606    T: Integer,
607    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
608{
609}
610
611impl<T, I> Iterator for CheckSortedDisjoint<T, I>
612where
613    T: Integer,
614    I: Iterator<Item = RangeInclusive<T>> + FusedIterator,
615{
616    type Item = RangeInclusive<T>;
617
618    fn next(&mut self) -> Option<Self::Item> {
619        let next = self.iter.next();
620
621        let Some(range) = next.as_ref() else {
622            self.seen_none = true;
623            return next;
624        };
625
626        assert!(
627            !self.seen_none,
628            "iterator cannot return Some after returning None"
629        );
630        let (start, end) = range.clone().into_inner();
631        assert!(start <= end, "start must be less or equal to end");
632        if let Some(prev_end) = self.prev_end {
633            assert!(
634                prev_end < T::max_value() && prev_end.add_one() < start,
635                "ranges must be disjoint"
636            );
637        }
638        self.prev_end = Some(end);
639
640        next
641    }
642
643    fn size_hint(&self) -> (usize, Option<usize>) {
644        self.iter.size_hint()
645    }
646}
647
648impl<T: Integer, const N: usize> From<[RangeInclusive<T>; N]>
649    for CheckSortedDisjoint<T, array::IntoIter<RangeInclusive<T>, N>>
650{
651    /// Deprecated: Use `new` instead.
652    fn from(arr: [RangeInclusive<T>; N]) -> Self {
653        Self::new(arr)
654    }
655}
656
657pub trait AnythingGoes<T: Integer>: Iterator<Item = RangeInclusive<T>> + FusedIterator {}
658impl<T: Integer, I> AnythingGoes<T> for I where I: Iterator<Item = RangeInclusive<T>> + FusedIterator
659{}
660
661macro_rules! impl_sorted_traits_and_ops {
662    ($IterType:ty, $($more_generics:tt)*) => {
663        #[allow(single_use_lifetimes)]
664        impl<$($more_generics)*, T: Integer> SortedStarts<T> for $IterType {}
665        #[allow(single_use_lifetimes)]
666        impl<$($more_generics)*, T: Integer> SortedDisjoint<T> for $IterType {}
667
668        #[allow(single_use_lifetimes)]
669        impl<$($more_generics)*, T: Integer> ops::Not for $IterType
670        {
671            type Output = NotIter<T, Self>;
672
673            fn not(self) -> Self::Output {
674                self.complement()
675            }
676        }
677
678        #[allow(single_use_lifetimes)]
679        impl<$($more_generics)*, T: Integer, R> ops::BitOr<R> for $IterType
680        where
681            R: SortedDisjoint<T>,
682        {
683            type Output = UnionMerge<T, Self, R>;
684
685            fn bitor(self, other: R) -> Self::Output {
686                SortedDisjoint::union(self, other)
687            }
688        }
689
690        #[allow(single_use_lifetimes)]
691        impl<$($more_generics)*, T: Integer, R> ops::Sub<R> for $IterType
692        where
693            R: SortedDisjoint<T>,
694        {
695            type Output = DifferenceMerge<T, Self, R>;
696
697            fn sub(self, other: R) -> Self::Output {
698                // It would be fun to optimize !!self.iter into self.iter
699                // but that would require also considering fields 'start_not' and 'next_time_return_none'.
700                SortedDisjoint::difference(self, other)
701            }
702        }
703
704        #[allow(single_use_lifetimes)]
705        impl<$($more_generics)*, T: Integer, R> ops::BitXor<R> for $IterType
706        where
707            R: SortedDisjoint<T>,
708        {
709            type Output = SymDiffMerge<T, Self, R>;
710
711            #[allow(clippy::suspicious_arithmetic_impl)]
712            fn bitxor(self, other: R) -> Self::Output {
713                SortedDisjoint::symmetric_difference(self, other)
714            }
715        }
716
717        #[allow(single_use_lifetimes)]
718        impl<$($more_generics)*, T: Integer, R> ops::BitAnd<R> for $IterType
719        where
720            R: SortedDisjoint<T>,
721        {
722            type Output = IntersectionMerge<T, Self, R>;
723
724            fn bitand(self, other: R) -> Self::Output {
725                SortedDisjoint::intersection(self, other)
726            }
727        }
728    };
729}
730
731//CheckList: Be sure that these are all tested in 'test_every_sorted_disjoint_method'
732impl_sorted_traits_and_ops!(CheckSortedDisjoint<T, I>, I: AnythingGoes<T>);
733impl_sorted_traits_and_ops!(DynSortedDisjoint<'a, T>, 'a);
734impl_sorted_traits_and_ops!(IntoRangesIter<T>, 'ignore);
735impl_sorted_traits_and_ops!(MapIntoRangesIter<T, V>, V: Eq + Clone);
736impl_sorted_traits_and_ops!(MapRangesIter<'a, T, V>, 'a, V: Eq + Clone);
737impl_sorted_traits_and_ops!(NotIter<T, I>, I: SortedDisjoint<T>);
738impl_sorted_traits_and_ops!(RangesIter<'a, T>, 'a);
739impl_sorted_traits_and_ops!(RangeValuesToRangesIter<T, VR, I>, VR: ValueRef, I: SortedDisjointMap<T, VR>);
740impl_sorted_traits_and_ops!(SymDiffIter<T, I>, I: SortedStarts<T>);
741impl_sorted_traits_and_ops!(UnionIter<T, I>, I: SortedStarts<T>);
742
743// We're not allowed to define methods on outside types, so we only define the traits
range_set_blaze/sorted_disjoint.rs

range_set_blaze/
sorted_disjoint.rs
