range_set_blaze/
sorted_disjoint_map.rs

1use crate::DifferenceMap;
2use crate::DifferenceMapInternal;
3use crate::DynSortedDisjointMap;
4use crate::IntersectionMap;
5use crate::IntoRangeValuesIter;
6use crate::NotIter;
7use crate::NotMap;
8use crate::SymDiffMergeMap;
9use crate::UnionMergeMap;
10use crate::intersection_iter_map::IntersectionIterMap;
11use crate::map::ValueRef;
12use crate::range_values::RangeValuesIter;
13use crate::range_values::RangeValuesToRangesIter;
14use crate::sorted_disjoint::SortedDisjoint;
15use crate::sym_diff_iter_map::SymDiffIterMap;
16use crate::{Integer, RangeMapBlaze, union_iter_map::UnionIterMap};
17use alloc::format;
18use alloc::rc::Rc;
19use alloc::string::String;
20use alloc::vec::Vec;
21use core::cmp::Ordering;
22use core::fmt::Debug;
23use core::iter::FusedIterator;
24use core::marker::PhantomData;
25use core::ops;
26use core::ops::RangeInclusive;
27
28/// Used internally. Marks iterators that provide `(range, value)` pairs that are sorted by the range's start, but
29/// that are not necessarily disjoint.
30pub trait SortedStartsMap<T, VR>: Iterator<Item = (RangeInclusive<T>, VR)> + FusedIterator
31where
32    T: Integer,
33    VR: ValueRef,
34{
35}
36
37/// Used internally by [`UnionIterMap`] and [`SymDiffIterMap`].
38pub trait PrioritySortedStartsMap<T, VR>: Iterator<Item = Priority<T, VR>> + FusedIterator
39where
40    T: Integer,
41    VR: ValueRef,
42{
43}
44
45/// Marks iterators that provide `(range, value)` pairs that are sorted and disjoint. Set operations on
46/// iterators that implement this trait can be performed in linear time.
47///
48/// # Table of Contents
49/// * [`SortedDisjointMap` Constructors](#sorteddisjointmap-constructors)
50///   * [Examples](#constructor-examples)
51/// * [`SortedDisjointMap` Set Operations](#sorteddisjointmap-set-operations)
52///   * [Performance](#performance)
53///   * [Examples](#examples)
54/// * [How to mark your type as `SortedDisjointMap`](#how-to-mark-your-type-as-sorteddisjointmap)
55///
56/// # `SortedDisjointMap` Constructors
57///
58/// You'll usually construct a `SortedDisjointMap` iterator from a [`RangeMapBlaze`] or a [`CheckSortedDisjointMap`].
59/// Here is a summary table, followed by [examples](#constructor-examples).  You can also [define your own
60/// `SortedDisjointMap`](#how-to-mark-your-type-as-sorteddisjointmap).
61///
62/// | Input type | Method |
63/// |------------|--------|
64/// | [`RangeMapBlaze`] | [`range_values`] |
65/// | [`RangeMapBlaze`] | [`into_range_values`] |
66/// | sorted & disjoint ranges and values | [`CheckSortedDisjointMap::new`] |
67/// |  *your iterator type* | *[How to mark your type as `SortedDisjointMap`][1]* |
68///
69/// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
70/// [`range_values`]: RangeMapBlaze::range_values
71/// [`into_range_values`]: RangeMapBlaze::into_range_values
72/// [1]: #how-to-mark-your-type-as-sorteddisjointmap
73/// [`RangesIter`]: crate::RangesIter
74/// [`BitAnd`]: core::ops::BitAnd
75/// [`Not`]: core::ops::Not
76///
77/// ## Constructor Examples
78/// ```
79/// use range_set_blaze::prelude::*;
80///
81/// // RangeMapBlaze's .range_values(), and .into_range_values()
82/// let r = RangeMapBlaze::from_iter([(3, "a"), (2, "a"), (1, "a"), (100, "b"), (1, "c")]);
83/// let a = r.range_values();
84/// assert!(a.into_string() == r#"(1..=3, "a"), (100..=100, "b")"#);
85/// // 'into_range_values' takes ownership of the 'RangeMapBlaze'
86/// let a = r.into_range_values();
87/// assert!(a.into_string() == r#"(1..=3, "a"), (100..=100, "b")"#);
88///
89/// // CheckSortedDisjointMap -- unsorted or overlapping input ranges will cause a panic.
90/// let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (100..=100, &"b")]);
91/// assert!(a.into_string() == r#"(1..=3, "a"), (100..=100, "b")"#);
92/// ```
93///
94/// # `SortedDisjointMap` Set Operations
95///
96/// You can perform set operations on `SortedDisjointMap`s and `SortedDisjoint` sets using operators.
97/// In the table below, `a`, `b`, and `c` are `SortedDisjointMap` and `s` is a `SortedDisjoint` set.
98///
99/// | Set Operator               | Operator                      | Multiway (same type)                                      | Multiway (different types)                     |
100/// |----------------------------|-------------------------------|-----------------------------------------------------------|-----------------------------------------------|
101/// | [`union`]                  | [`a` &#124; `b`]              | `[a, b, c].`[`union`][multiway_union]`() `                | [`union_map_dyn!`](a, b, c)                    |
102/// | [`intersection`]           | [`a & b`]                     | `[a, b, c].`[`intersection`][multiway_intersection]`() `  | [`intersection_map_dyn!`](a, b, c)             |
103/// | `intersection`             | [`a.map_and_set_intersection(s)`] | *n/a*                                                     | *n/a*                                          |
104/// | [`difference`]             | [`a - b`]                     | *n/a*                                                     | *n/a*                                          |
105/// | `difference`               | [`a.map_and_set_difference(s)`] | *n/a*                                                     | *n/a*                                          |
106/// | [`symmetric_difference`]   | [`a ^ b`]                     | `[a, b, c].`[`symmetric_difference`][multiway_symmetric_difference]`() ` | [`symmetric_difference_map_dyn!`](a, b, c) |
107/// | [`complement`] (to set)    | [`!a`]                        | *n/a*                                                     | *n/a*                                          |
108/// | `complement` (to map)      | [`a.complement_with(&value)`] | *n/a*                                                     | *n/a*                                          |
109///
110/// [`union`]: trait.SortedDisjointMap.html#method.union
111/// [`intersection`]: trait.SortedDisjointMap.html#method.intersection
112/// [`difference`]: trait.SortedDisjointMap.html#method.difference
113/// [`symmetric_difference`]: trait.SortedDisjointMap.html#method.symmetric_difference
114/// [`complement`]: trait.SortedDisjointMap.html#method.complement
115/// [`a` &#124; `b`]: trait.SortedDisjointMap.html#method.union
116/// [`a & b`]: trait.SortedDisjointMap.html#method.intersection
117/// [`a.map_and_set_intersection(s)`]: trait.SortedDisjointMap.html#method.map_and_set_intersection
118/// [`a - b`]: trait.SortedDisjointMap.html#method.difference
119/// [`a.map_and_set_difference(s)`]: trait.SortedDisjointMap.html#method.map_and_set_difference
120/// [`a ^ b`]: trait.SortedDisjointMap.html#method.symmetric_difference
121/// [`!a`]: trait.SortedDisjointMap.html#method.complement
122/// [`a.complement_with(&value)`]: trait.SortedDisjointMap.html#method.complement_with
123/// [multiway_union]: trait.MultiwaySortedDisjointMap.html#method.union
124/// [multiway_intersection]: trait.MultiwaySortedDisjointMap.html#method.intersection
125/// [multiway_symmetric_difference]: trait.MultiwaySortedDisjointMap.html#method.symmetric_difference
126/// [`union_map_dyn!`]: macro.union_map_dyn.html
127/// [`intersection_map_dyn!`]: macro.intersection_map_dyn.html
128/// [`symmetric_difference_map_dyn!`]: macro.symmetric_difference_map_dyn.html
129///
130/// The union of any number of maps is defined such that, for any overlapping keys,
131/// the values from the left-most input take precedence. This approach ensures
132/// that the data from the left-most inputs remains dominant when merging with
133/// later inputs. Likewise, for symmetric difference of three or more maps.
134///
135/// ## Performance
136///
137/// Every operation is implemented as a single pass over the sorted & disjoint ranges, with minimal memory.
138///
139/// This is true even when applying multiple operations. The last example below demonstrates this.
140///
141/// ## Examples
142///
143/// ```
144/// use range_set_blaze::prelude::*;
145///
146/// let a0 = RangeMapBlaze::from_iter([(1..=2, "a"), (5..=100, "a")]);
147/// let b0 = RangeMapBlaze::from_iter([(2..=6, "b")]);
148///
149/// // 'union' method and 'into_string' method
150/// let (a, b) = (a0.range_values(), b0.range_values());
151/// let result = a.union(b);
152/// assert_eq!(result.into_string(), r#"(1..=2, "a"), (3..=4, "b"), (5..=100, "a")"#);
153///
154/// // '|' operator and 'equal' method
155/// let (a, b) = (a0.range_values(), b0.range_values());
156/// let result = a | b;
157/// assert!(result.equal(CheckSortedDisjointMap::new([(1..=2, &"a"),  (3..=4, &"b"), (5..=100, &"a")])));
158///
159/// // multiway union of same type
160/// let c0 = RangeMapBlaze::from_iter([(2..=2, "c"), (6..=200, "c")]);
161/// let (a, b, c) = (a0.range_values(), b0.range_values(), c0.range_values());
162/// let result = [a, b, c].union();
163/// assert_eq!(result.into_string(), r#"(1..=2, "a"), (3..=4, "b"), (5..=100, "a"), (101..=200, "c")"#
164/// );
165///
166/// // multiway union of different types
167/// let (a, b) = (a0.range_values(), b0.range_values());
168/// let c = CheckSortedDisjointMap::new([(2..=2, &"c"), (6..=200, &"c")]);
169/// let result = union_map_dyn!(a, b, c);
170/// assert_eq!(result.into_string(), r#"(1..=2, "a"), (3..=4, "b"), (5..=100, "a"), (101..=200, "c")"# );
171///
172/// // Applying multiple operators makes only one pass through the inputs with minimal memory.
173/// let (a, b, c) = (a0.range_values(), b0.range_values(), c0.range_values());
174/// let result = a - (b | c);
175/// assert_eq!(result.into_string(), r#"(1..=1, "a")"#);
176/// ```
177/// # How to mark your type as `SortedDisjointMap`
178///
179/// To mark your iterator type as `SortedDisjointMap`, you implement the `SortedStartsMap` and `SortedDisjointMap` traits.
180/// This is your promise to the compiler that your iterator will provide inclusive ranges that are
181/// disjoint and sorted by start.
182///
183/// When you do this, your iterator will get access to the
184/// efficient set operations methods, such as [`intersection`] and [`complement`].
185///
186/// > To use operators such as `&` and `!`, you must also implement the [`BitAnd`], [`Not`], etc. traits.
187/// >
188/// > If you want others to use your marked iterator type, reexport:
189/// > `pub use range_set_blaze::{SortedDisjointMap, SortedStartsMap};`
190pub trait SortedDisjointMap<T, VR>: SortedStartsMap<T, VR>
191where
192    T: Integer,
193    VR: ValueRef,
194{
195    /// Converts a [`SortedDisjointMap`] iterator into a [`SortedDisjoint`] iterator.
196    ///```
197    /// use range_set_blaze::prelude::*;
198    ///
199    /// let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (100..=100, &"b")]);
200    /// let b = a.into_sorted_disjoint();
201    /// assert!(b.into_string() == "1..=3, 100..=100");
202    /// ```
203    #[inline]
204    fn into_sorted_disjoint(self) -> RangeValuesToRangesIter<T, VR, Self>
205    where
206        Self: Sized,
207    {
208        RangeValuesToRangesIter::new(self)
209    }
210    /// Given two [`SortedDisjointMap`] iterators, efficiently returns a [`SortedDisjointMap`] iterator of their union.
211    ///
212    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
213    ///
214    /// # Examples
215    ///
216    /// ```
217    /// use range_set_blaze::prelude::*;
218    ///
219    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
220    /// let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
221    /// let b = b0.range_values();
222    /// let union = a.union(b);
223    /// assert_eq!(union.into_string(), r#"(1..=2, "a"), (3..=3, "b")"#);
224    ///
225    /// // Alternatively, we can use "|" because CheckSortedDisjointMap defines
226    /// // ops::bitor as SortedDisjointMap::union.
227    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
228    /// let b = b0.range_values();
229    /// let union = a | b;
230    /// assert_eq!(union.into_string(), r#"(1..=2, "a"), (3..=3, "b")"#);
231    /// ```
232    #[inline]
233    fn union<R>(self, other: R) -> UnionMergeMap<T, VR, Self, R::IntoIter>
234    where
235        R: IntoIterator<Item = Self::Item>,
236        R::IntoIter: SortedDisjointMap<T, VR>,
237        Self: Sized,
238    {
239        UnionIterMap::new2(self, other.into_iter())
240    }
241
242    /// Given two [`SortedDisjointMap`] iterators, efficiently returns a [`SortedDisjointMap`] iterator of their intersection.
243    ///
244    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
245    ///
246    /// # Examples
247    ///
248    /// ```
249    /// use range_set_blaze::prelude::*;
250    ///
251    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
252    /// let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
253    /// let b = b0.range_values();
254    /// let intersection = a.intersection(b);
255    /// assert_eq!(intersection.into_string(), r#"(2..=2, "a")"#);
256    ///
257    /// // Alternatively, we can use "&" because CheckSortedDisjointMap defines
258    /// // `ops::BitAnd` as `SortedDisjointMap::intersection`.
259    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
260    /// let b = b0.range_values();
261    /// let intersection = a & b;
262    /// assert_eq!(intersection.into_string(), r#"(2..=2, "a")"#);
263    /// ```
264    #[inline]
265    fn intersection<R>(self, other: R) -> IntersectionMap<T, VR, Self, R::IntoIter>
266    where
267        R: IntoIterator<Item = Self::Item>,
268        R::IntoIter: SortedDisjointMap<T, VR>,
269        Self: Sized,
270    {
271        let sorted_disjoint_map = other.into_iter();
272        let sorted_disjoint = sorted_disjoint_map.into_sorted_disjoint();
273        IntersectionIterMap::new(self, sorted_disjoint)
274    }
275
276    /// Given a [`SortedDisjointMap`] iterator and a [`SortedDisjoint`] iterator,
277    /// efficiently returns a [`SortedDisjointMap`] iterator of their intersection.
278    ///
279    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
280    /// [`SortedDisjoint`]: trait.SortedDisjoint.html#table-of-contents
281    ///
282    /// # Examples
283    ///
284    /// ```
285    /// use range_set_blaze::prelude::*;
286    ///
287    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
288    /// let b = CheckSortedDisjoint::new([2..=3]);
289    /// let intersection = a.map_and_set_intersection(b);
290    /// assert_eq!(intersection.into_string(), r#"(2..=2, "a")"#);
291    /// ```
292    #[inline]
293    fn map_and_set_intersection<R>(self, other: R) -> IntersectionIterMap<T, VR, Self, R::IntoIter>
294    where
295        R: IntoIterator<Item = RangeInclusive<T>>,
296        R::IntoIter: SortedDisjoint<T>,
297        Self: Sized,
298    {
299        IntersectionIterMap::new(self, other.into_iter())
300    }
301
302    /// Given two [`SortedDisjointMap`] iterators, efficiently returns a [`SortedDisjointMap`] iterator of their set difference.
303    ///
304    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
305    ///
306    /// # Examples
307    ///
308    /// ```
309    /// use range_set_blaze::prelude::*;
310    ///
311    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
312    /// let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
313    /// let b = b0.range_values();
314    /// let difference = a.difference(b);
315    /// assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);
316    ///
317    /// // Alternatively, we can use "-" because `CheckSortedDisjointMap` defines
318    /// // `ops::Sub` as `SortedDisjointMap::difference`.
319    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
320    /// let b = b0.range_values();
321    /// let difference = a - b;
322    /// assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);
323    /// ```
324    #[inline]
325    fn difference<R>(self, other: R) -> DifferenceMap<T, VR, Self, R::IntoIter>
326    where
327        R: IntoIterator<Item = Self::Item>,
328        R::IntoIter: SortedDisjointMap<T, VR>,
329        Self: Sized,
330    {
331        let sorted_disjoint_map = other.into_iter();
332        let complement = sorted_disjoint_map.complement();
333        IntersectionIterMap::new(self, complement)
334    }
335
336    /// Given a [`SortedDisjointMap`] iterator and a [`SortedDisjoint`] iterator,
337    /// efficiently returns a [`SortedDisjointMap`] iterator of their set difference.
338    ///
339    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
340    /// [`SortedDisjoint`]: trait.SortedDisjoint.html#table-of-contents
341    ///
342    /// # Examples
343    ///
344    /// ```
345    /// use range_set_blaze::prelude::*;
346    ///
347    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
348    /// let b = RangeMapBlaze::from_iter([(2..=3, "b")]).into_ranges();
349    /// let difference = a.map_and_set_difference(b);
350    /// assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);
351    /// ```
352    #[inline]
353    fn map_and_set_difference<R>(self, other: R) -> DifferenceMapInternal<T, VR, Self, R::IntoIter>
354    where
355        R: IntoIterator<Item = RangeInclusive<T>>,
356        R::IntoIter: SortedDisjoint<T>,
357        Self: Sized,
358    {
359        let sorted_disjoint = other.into_iter();
360        let complement = sorted_disjoint.complement();
361        IntersectionIterMap::new(self, complement)
362    }
363
364    /// Returns the complement of a [`SortedDisjointMap`]'s keys as a [`SortedDisjoint`] iterator.
365    ///
366    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
367    /// [`SortedDisjoint`]: trait.SortedDisjoint.html#table-of-contents
368    ///
369    /// # Examples
370    ///
371    /// ```
372    /// use range_set_blaze::prelude::*;
373    ///
374    /// let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
375    /// let complement = a.complement();
376    /// assert_eq!(complement.into_string(), "0..=9, 21..=99, 201..=255");
377    ///
378    /// // Alternatively, we can use "!" because `CheckSortedDisjointMap` implements
379    /// // `ops::Not` as `complement`.
380    /// let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
381    /// let complement_using_not = !a;
382    /// assert_eq!(complement_using_not.into_string(), "0..=9, 21..=99, 201..=255");
383    /// ```
384    #[inline]
385    fn complement(self) -> NotIter<T, RangeValuesToRangesIter<T, VR, Self>>
386    where
387        Self: Sized,
388    {
389        let sorted_disjoint = self.into_sorted_disjoint();
390        sorted_disjoint.complement()
391    }
392
393    /// Returns the complement of a [`SortedDisjointMap`]'s keys, associating each range with the provided value `v`.
394    /// The result is a [`SortedDisjointMap`] iterator.
395    ///
396    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
397    ///
398    /// # Examples
399    ///
400    /// ```
401    /// use range_set_blaze::prelude::*;
402    ///
403    /// let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
404    /// let complement = a.complement_with(&"z");
405    /// assert_eq!(complement.into_string(), r#"(0..=9, "z"), (21..=99, "z"), (201..=255, "z")"#);
406    /// ```
407    #[inline]
408    fn complement_with(
409        self,
410        v: &VR::Target,
411    ) -> RangeToRangeValueIter<'_, T, VR::Target, NotIter<T, impl SortedDisjoint<T>>>
412    where
413        Self: Sized,
414    {
415        let complement = self.complement();
416        RangeToRangeValueIter::new(complement, v)
417    }
418
419    /// Given two [`SortedDisjointMap`] iterators, efficiently returns a [`SortedDisjointMap`] iterator
420    /// of their symmetric difference.
421    ///
422    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
423    ///
424    /// # Examples
425    ///
426    /// ```
427    /// use range_set_blaze::prelude::*;
428    ///
429    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
430    /// let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
431    /// let b = b0.range_values();
432    /// let symmetric_difference = a.symmetric_difference(b);
433    /// assert_eq!(symmetric_difference.into_string(), r#"(1..=1, "a"), (3..=3, "b")"#);
434    ///
435    /// // Alternatively, we can use "^" because CheckSortedDisjointMap defines
436    /// // ops::bitxor as SortedDisjointMap::symmetric_difference.
437    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
438    /// let b = b0.range_values();
439    /// let symmetric_difference = a ^ b;
440    /// assert_eq!(symmetric_difference.into_string(), r#"(1..=1, "a"), (3..=3, "b")"#);
441    /// ```
442    #[inline]
443    fn symmetric_difference<R>(self, other: R) -> SymDiffMergeMap<T, VR, Self, R::IntoIter>
444    where
445        R: IntoIterator<Item = Self::Item>,
446        R::IntoIter: SortedDisjointMap<T, VR>,
447        Self: Sized,
448        VR: ValueRef,
449    {
450        SymDiffIterMap::new2(self, other.into_iter())
451    }
452
453    /// Given two [`SortedDisjointMap`] iterators, efficiently tells if they are equal. Unlike most equality testing in Rust,
454    /// this method takes ownership of the iterators and consumes them.
455    ///
456    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
457    ///
458    /// # Examples
459    ///
460    /// ```
461    /// use range_set_blaze::prelude::*;
462    ///
463    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
464    /// let b0 = RangeMapBlaze::from_iter([(1..=2, "a")]);
465    /// let b = b0.range_values();
466    /// assert!(a.equal(b));
467    /// ```
468    fn equal<R>(self, other: R) -> bool
469    where
470        R: IntoIterator<Item = Self::Item>,
471        R::IntoIter: SortedDisjointMap<T, VR>,
472        Self: Sized,
473    {
474        use itertools::Itertools;
475
476        self.zip_longest(other).all(|pair| {
477            match pair {
478                itertools::EitherOrBoth::Both(
479                    (self_range, self_value),
480                    (other_range, other_value),
481                ) => {
482                    // Place your custom equality logic here for matching elements
483                    self_range == other_range && self_value.borrow() == other_value.borrow()
484                }
485                _ => false, // Handles the case where iterators are of different lengths
486            }
487        })
488    }
489
490    /// Returns `true` if the [`SortedDisjointMap`] contains no elements.
491    ///
492    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
493    ///
494    /// # Examples
495    ///
496    /// ```
497    /// use range_set_blaze::prelude::*;
498    ///
499    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
500    /// assert!(!a.is_empty());
501    /// ```
502    #[inline]
503    #[allow(clippy::wrong_self_convention)]
504    fn is_empty(mut self) -> bool
505    where
506        Self: Sized,
507    {
508        self.next().is_none()
509    }
510
511    /// Create a [`RangeMapBlaze`] from a [`SortedDisjointMap`] iterator.
512    ///
513    /// *For more about constructors and performance, see [`RangeMapBlaze` Constructors](struct.RangeMapBlaze.html#rangemapblaze-constructors).*
514    ///
515    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
516    /// # Examples
517    ///
518    /// ```
519    /// use range_set_blaze::prelude::*;
520    ///
521    /// let a0 = RangeMapBlaze::from_sorted_disjoint_map(CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]));
522    /// let a1: RangeMapBlaze<i32,_> = CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]).into_range_map_blaze();
523    /// assert!(a0 == a1 && a0.to_string() == r#"(-10..=-5, "a"), (1..=2, "b")"#);
524    /// ```
525    fn into_range_map_blaze(self) -> RangeMapBlaze<T, VR::Target>
526    where
527        Self: Sized,
528    {
529        RangeMapBlaze::from_sorted_disjoint_map(self)
530    }
531}
532
533/// Converts the implementing type into a String by consuming it.
534pub trait IntoString {
535    /// Consumes the implementing type and converts it into a String.
536    fn into_string(self) -> String;
537}
538
539impl<T, I> IntoString for I
540where
541    T: Debug,
542    I: Iterator<Item = T>,
543{
544    fn into_string(self) -> String {
545        self.map(|item| format!("{item:?}"))
546            .collect::<Vec<String>>()
547            .join(", ")
548    }
549}
550
551/// Gives the [`SortedDisjointMap`] trait to any iterator of range-value pairs. Will panic
552/// if the trait is not satisfied.
553///
554/// The iterator will panic
555/// if/when it finds that the ranges are not actually sorted and disjoint or if the values overlap inappropriately.
556///
557/// [`SortedDisjointMap`]: crate::SortedDisjointMap.html#table-of-contents
558///
559/// # Performance
560///
561/// All checking is done at runtime, but it should still be fast.
562///
563/// # Example
564///
565/// ```
566/// use range_set_blaze::prelude::*;
567///
568/// let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (5..=10, &"b")]);
569/// let b = CheckSortedDisjointMap::new([(4..=6, &"c")]);
570/// let union = a | b;
571/// assert_eq!(union.into_string(), r#"(1..=3, "a"), (4..=4, "c"), (5..=10, "b")"#);
572/// ```
573///
574/// Here the ranges are not sorted and disjoint, so the iterator will panic.
575/// ```should_panic
576/// use range_set_blaze::prelude::*;
577///
578/// let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (5..=10, &"b")]);
579/// let b = CheckSortedDisjointMap::new([(4..=6, &"c"), (-10..=12, &"d")]);
580/// let union = a | b;
581/// assert_eq!(union.into_string(), "1..=3 -> a, 5..=10 -> b");
582/// ```
583#[allow(clippy::module_name_repetitions)]
584#[must_use = "iterators are lazy and do nothing unless consumed"]
585#[derive(Debug, Clone)]
586pub struct CheckSortedDisjointMap<T, VR, I>
587where
588    T: Integer,
589    VR: ValueRef,
590    I: Iterator<Item = (RangeInclusive<T>, VR)>,
591{
592    iter: I,
593    seen_none: bool,
594    previous: Option<(RangeInclusive<T>, VR)>,
595}
596
597// define new
598impl<T, VR, I> CheckSortedDisjointMap<T, VR, I>
599where
600    T: Integer,
601    VR: ValueRef,
602    I: Iterator<Item = (RangeInclusive<T>, VR)>,
603{
604    /// Creates a new [`CheckSortedDisjointMap`] from an iterator of ranges and values. See [`CheckSortedDisjointMap`] for details and examples.
605    #[inline]
606    #[must_use = "iterators are lazy and do nothing unless consumed"]
607    pub fn new<J>(iter: J) -> Self
608    where
609        J: IntoIterator<Item = (RangeInclusive<T>, VR), IntoIter = I>,
610    {
611        Self {
612            iter: iter.into_iter(),
613            seen_none: false,
614            previous: None,
615        }
616    }
617}
618
619impl<T, VR, I> Default for CheckSortedDisjointMap<T, VR, I>
620where
621    T: Integer,
622    VR: ValueRef,
623    I: Iterator<Item = (RangeInclusive<T>, VR)> + Default,
624{
625    fn default() -> Self {
626        // Utilize I::default() to satisfy the iterator requirement.
627        Self::new(I::default())
628    }
629}
630
631impl<T, VR, I> FusedIterator for CheckSortedDisjointMap<T, VR, I>
632where
633    T: Integer,
634    VR: ValueRef,
635    I: Iterator<Item = (RangeInclusive<T>, VR)>,
636{
637}
638
639fn range_value_clone<T, VR>(range_value: &(RangeInclusive<T>, VR)) -> (RangeInclusive<T>, VR)
640where
641    T: Integer,
642    VR: ValueRef,
643{
644    let (range, value) = range_value;
645    (range.clone(), value.clone())
646}
647
648impl<T, VR, I> Iterator for CheckSortedDisjointMap<T, VR, I>
649where
650    T: Integer,
651    VR: ValueRef,
652    I: Iterator<Item = (RangeInclusive<T>, VR)>,
653{
654    type Item = (RangeInclusive<T>, VR);
655
656    #[allow(clippy::manual_assert)] // We use "if...panic!" for coverage auditing.
657    fn next(&mut self) -> Option<Self::Item> {
658        // Get the next item
659        let range_value = self.iter.next();
660
661        // If it's None, we're done (but remember that we've seen None)
662        let Some(range_value) = range_value else {
663            self.seen_none = true;
664            return None;
665        };
666
667        // if the next item is Some, check that we haven't seen None before
668        if self.seen_none {
669            panic!("a value must not be returned after None")
670        }
671
672        // Check that the range is not empty
673        let (start, end) = range_value.0.clone().into_inner();
674        if start > end {
675            panic!("start must be <= end")
676        }
677
678        // If previous is None, we're done (but remember this pair as previous)
679        let Some(previous) = self.previous.take() else {
680            self.previous = Some(range_value_clone(&range_value));
681            return Some(range_value);
682        };
683
684        // The next_item is Some and previous is Some, so check that the ranges are disjoint and sorted
685        let previous_end = *previous.0.end();
686        if previous_end >= start {
687            panic!("ranges must be disjoint and sorted")
688        }
689
690        if previous_end.add_one() == start && previous.1.borrow() == range_value.1.borrow() {
691            panic!("touching ranges must have different values")
692        }
693
694        // Remember this pair as previous
695        self.previous = Some(range_value_clone(&range_value));
696        Some(range_value)
697    }
698
699    fn size_hint(&self) -> (usize, Option<usize>) {
700        self.iter.size_hint()
701    }
702}
703
704/// Used internally by `MergeMap`.
705#[derive(Clone, Debug)]
706pub struct Priority<T, VR>
707where
708    T: Integer,
709    VR: ValueRef,
710{
711    range_value: (RangeInclusive<T>, VR),
712    priority_number: usize,
713}
714
715impl<T, VR> Priority<T, VR>
716where
717    T: Integer,
718    VR: ValueRef,
719{
720    pub(crate) const fn new(range_value: (RangeInclusive<T>, VR), priority_number: usize) -> Self {
721        Self {
722            range_value,
723            priority_number,
724        }
725    }
726}
727
728impl<T, VR> Priority<T, VR>
729where
730    T: Integer,
731    VR: ValueRef,
732{
733    /// Returns a reference to `range_value`.
734    pub const fn range_value(&self) -> &(RangeInclusive<T>, VR) {
735        &self.range_value
736    }
737
738    /// Consumes `Priority` and returns `range_value`.
739    pub fn into_range_value(self) -> (RangeInclusive<T>, VR) {
740        self.range_value
741    }
742
743    /// Updates the range part of `range_value`.
744    pub const fn set_range(&mut self, range: RangeInclusive<T>) {
745        self.range_value.0 = range;
746    }
747
748    /// Returns the start of the range.
749    pub const fn start(&self) -> T {
750        *self.range_value.0.start()
751    }
752
753    /// Returns the end of the range.
754    pub const fn end(&self) -> T {
755        *self.range_value.0.end()
756    }
757
758    /// Returns the start and end of the range. (Assuming direct access to start and end)
759    pub const fn start_and_end(&self) -> (T, T) {
760        ((*self.range_value.0.start()), (*self.range_value.0.end()))
761    }
762
763    /// Returns a reference to the value part of `range_value`.
764    pub const fn value(&self) -> &VR {
765        &self.range_value.1
766    }
767}
768
769// Implement `PartialEq` to allow comparison (needed for `Eq`).
770impl<T, VR> PartialEq for Priority<T, VR>
771where
772    T: Integer,
773    VR: ValueRef,
774{
775    fn eq(&self, other: &Self) -> bool {
776        self.priority_number == other.priority_number
777    }
778}
779
780// Implement `Eq` because `BinaryHeap` requires it.
781impl<T, VR> Eq for Priority<T, VR>
782where
783    T: Integer,
784    VR: ValueRef,
785{
786}
787
788// Implement `Ord` so the heap knows how to compare elements.
789impl<T, VR> Ord for Priority<T, VR>
790where
791    T: Integer,
792    VR: ValueRef,
793{
794    fn cmp(&self, other: &Self) -> Ordering {
795        // smaller is better
796        other.priority_number.cmp(&self.priority_number)
797    }
798}
799
800// Implement `PartialOrd` to allow comparison (needed for `Ord`).
801impl<T, VR> PartialOrd for Priority<T, VR>
802where
803    T: Integer,
804    VR: ValueRef,
805{
806    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
807        Some(self.cmp(other))
808    }
809}
810
811/// Used internally by `complement_with`.
812#[must_use = "iterators are lazy and do nothing unless consumed"]
813#[derive(Clone, Debug)]
814pub struct RangeToRangeValueIter<'a, T, V, I>
815where
816    T: Integer,
817    V: Eq + Clone,
818    I: SortedDisjoint<T>,
819{
820    inner: I,
821    value: &'a V,
822    phantom: PhantomData<T>,
823}
824
825impl<'a, T, V, I> RangeToRangeValueIter<'a, T, V, I>
826where
827    T: Integer,
828    V: Eq + Clone,
829    I: SortedDisjoint<T>,
830{
831    pub(crate) const fn new(inner: I, value: &'a V) -> Self {
832        Self {
833            inner,
834            value,
835            phantom: PhantomData,
836        }
837    }
838}
839
840impl<T, V, I> FusedIterator for RangeToRangeValueIter<'_, T, V, I>
841where
842    T: Integer,
843    V: Eq + Clone,
844    I: SortedDisjoint<T>,
845{
846}
847
848impl<'a, T, V, I> Iterator for RangeToRangeValueIter<'a, T, V, I>
849where
850    T: Integer,
851    V: Eq + Clone,
852    I: SortedDisjoint<T>,
853{
854    type Item = (RangeInclusive<T>, &'a V);
855
856    fn next(&mut self) -> Option<Self::Item> {
857        self.inner.next().map(|range| (range, self.value))
858    }
859}
860
861// implements SortedDisjointMap
862impl<'a, T, V, I> SortedStartsMap<T, &'a V> for RangeToRangeValueIter<'a, T, V, I>
863where
864    T: Integer,
865    V: Eq + Clone,
866    I: SortedDisjoint<T>,
867{
868}
869impl<'a, T, V, I> SortedDisjointMap<T, &'a V> for RangeToRangeValueIter<'a, T, V, I>
870where
871    T: Integer,
872    V: Eq + Clone,
873    I: SortedDisjoint<T>,
874{
875}
876
877macro_rules! impl_sorted_map_traits_and_ops {
878    ($IterType:ty, $V:ty, $VR:ty, $($more_generics:tt)*) => {
879
880        #[allow(single_use_lifetimes)]
881        impl<$($more_generics)*, T> SortedStartsMap<T, $VR> for $IterType
882        where
883            T: Integer,
884        {
885        }
886
887        #[allow(single_use_lifetimes)]
888        impl<$($more_generics)*, T> SortedDisjointMap<T, $VR> for $IterType
889        where
890            T: Integer,
891        {
892        }
893
894        #[allow(single_use_lifetimes)]
895        impl<$($more_generics)*, T> ops::Not for $IterType
896        where
897            T: Integer,
898        {
899            type Output = NotMap<T, $VR, Self>;
900
901            fn not(self) -> Self::Output {
902                self.complement()
903            }
904        }
905
906        #[allow(single_use_lifetimes)]
907        impl<$($more_generics)*, T, R> ops::BitOr<R> for $IterType
908        where
909            T: Integer,
910            R: SortedDisjointMap<T, $VR>,
911        {
912            type Output = UnionMergeMap<T, $VR, Self, R>;
913
914            fn bitor(self, other: R) -> Self::Output {
915                SortedDisjointMap::union(self, other)
916            }
917        }
918
919        #[allow(single_use_lifetimes)]
920        impl<$($more_generics)*, T, R> ops::Sub<R> for $IterType
921        where
922            T: Integer,
923            R: SortedDisjointMap<T, $VR>,
924        {
925            type Output = DifferenceMap<T, $VR, Self, R>;
926
927            fn sub(self, other: R) -> Self::Output {
928                SortedDisjointMap::difference(self, other)
929            }
930        }
931
932        #[allow(single_use_lifetimes)]
933        impl<$($more_generics)*, T, R> ops::BitXor<R> for $IterType
934        where
935            T: Integer,
936            R: SortedDisjointMap<T, $VR>,
937        {
938            type Output = SymDiffMergeMap<T,  $VR, Self, R>;
939
940            #[allow(clippy::suspicious_arithmetic_impl)]
941            fn bitxor(self, other: R) -> Self::Output {
942                SortedDisjointMap::symmetric_difference(self, other)
943            }
944        }
945
946        #[allow(single_use_lifetimes)]
947        impl<$($more_generics)*, T, R> ops::BitAnd<R> for $IterType
948        where
949            T: Integer,
950            R: SortedDisjointMap<T, $VR>,
951        {
952            type Output = IntersectionMap<T, $VR, Self, R>;
953
954            fn bitand(self, other: R) -> Self::Output {
955                SortedDisjointMap::intersection(self, other)
956            }
957        }
958
959    }
960}
961
962// CheckList: Be sure that these are all tested in 'test_every_sorted_disjoint_map_method'
963impl_sorted_map_traits_and_ops!(CheckSortedDisjointMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: Iterator<Item = (RangeInclusive<T>,  VR)>);
964impl_sorted_map_traits_and_ops!(DynSortedDisjointMap<'a, T, VR>, VR::Value, VR, 'a, VR: ValueRef);
965impl_sorted_map_traits_and_ops!(IntersectionIterMap<T, VR, I0, I1>,  VR::Value, VR, VR: ValueRef, I0: SortedDisjointMap<T, VR>, I1: SortedDisjoint<T>);
966impl_sorted_map_traits_and_ops!(IntoRangeValuesIter<T, V>, V, Rc<V>, V: Eq + Clone);
967impl_sorted_map_traits_and_ops!(RangeValuesIter<'a, T, V>, V, &'a V, 'a, V: Eq + Clone);
968impl_sorted_map_traits_and_ops!(SymDiffIterMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: PrioritySortedStartsMap<T, VR>);
969impl_sorted_map_traits_and_ops!(UnionIterMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: PrioritySortedStartsMap<T, VR>);
range_set_blaze/sorted_disjoint_map.rs

range_set_blaze/
sorted_disjoint_map.rs
