range_set_blaze/
sorted_disjoint.rs

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

range_set_blaze/
sorted_disjoint.rs
