range_set_blaze/
sorted_disjoint.rs

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

range_set_blaze/
sorted_disjoint.rs
