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([ (100, "b"), (1, "c"), (3, "a"), (2, "a"), (1, "a")]);
83/// let a = r.range_values();
84/// assert_eq!(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_eq!(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_eq!(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 right-most input take precedence. This approach ensures
132/// that the data from the right-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([(2..=6, "a")]);
147/// let b0 = RangeMapBlaze::from_iter([(1..=2, "b"), (5..=100, "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, "b"), (3..=4, "a"), (5..=100, "b")"#);
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, &"b"),  (3..=4, &"a"), (5..=100, &"b")])));
158///
159/// // multiway union of same type
160/// let z0 = RangeMapBlaze::from_iter([(2..=2, "z"), (6..=200, "z")]);
161/// let (z, a, b) = (z0.range_values(), a0.range_values(), b0.range_values());
162/// let result = [z, a, b].union();
163/// assert_eq!(result.into_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b"), (101..=200, "z")"#
164/// );
165///
166/// // multiway union of different types
167/// let (a, b) = (a0.range_values(), b0.range_values());
168/// let z = CheckSortedDisjointMap::new([(2..=2, &"z"), (6..=200, &"z")]);
169/// let result = union_map_dyn!(z, a, b);
170/// assert_eq!(result.into_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b"), (101..=200, "z")"# );
171///
172/// // Applying multiple operators makes only one pass through the inputs with minimal memory.
173/// let (z, a, b) = (z0.range_values(), a0.range_values(), b0.range_values());
174/// let result = b - (z | a);
175/// assert_eq!(result.into_string(), r#"(1..=1, "b")"#);
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 a0 = RangeMapBlaze::from_iter([(2..=3, "a")]);
220    /// let a = a0.range_values();
221    /// let b = CheckSortedDisjointMap::new([(1..=2, &"b")]);
222    /// let union = a.union(b);
223    /// assert_eq!(union.into_string(), r#"(1..=2, "b"), (3..=3, "a")"#);
224    ///
225    /// // Alternatively, we can use "|" because CheckSortedDisjointMap defines
226    /// // ops::bitor as SortedDisjointMap::union.
227    /// let a = a0.range_values();
228    /// let b = CheckSortedDisjointMap::new([(1..=2, &"b")]);
229    /// let union = a | b;
230    /// assert_eq!(union.into_string(), r#"(1..=2, "b"), (3..=3, "a")"#);
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 a0 = RangeMapBlaze::from_iter([(2..=3, "a")]);
252    /// let a = a0.range_values();
253    /// let b = CheckSortedDisjointMap::new([(1..=2, &"b")]);
254    /// let intersection = a.intersection(b);
255    /// assert_eq!(intersection.into_string(), r#"(2..=2, "b")"#);
256    ///
257    /// // Alternatively, we can use "&" because CheckSortedDisjointMap defines
258    /// // `ops::BitAnd` as `SortedDisjointMap::intersection`.
259    /// let a0 = RangeMapBlaze::from_iter([(2..=3, "a")]);
260    /// let a = a0.range_values();
261    /// let b = CheckSortedDisjointMap::new([(1..=2, &"b")]);
262    /// let intersection = a & b;
263    /// assert_eq!(intersection.into_string(), r#"(2..=2, "b")"#);
264    /// ```
265    #[inline]
266    fn intersection<R>(self, other: R) -> IntersectionMap<T, VR, Self, R::IntoIter>
267    where
268        R: IntoIterator<Item = Self::Item>,
269        R::IntoIter: SortedDisjointMap<T, VR>,
270        Self: Sized,
271    {
272        let other = other.into_iter();
273        let sorted_disjoint = self.into_sorted_disjoint();
274        IntersectionIterMap::new(other, sorted_disjoint)
275    }
276
277    /// Given a [`SortedDisjointMap`] iterator and a [`SortedDisjoint`] iterator,
278    /// efficiently returns a [`SortedDisjointMap`] iterator of their intersection.
279    ///
280    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
281    /// [`SortedDisjoint`]: trait.SortedDisjoint.html#table-of-contents
282    ///
283    /// # Examples
284    ///
285    /// ```
286    /// use range_set_blaze::prelude::*;
287    ///
288    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
289    /// let b = CheckSortedDisjoint::new([2..=3]);
290    /// let intersection = a.map_and_set_intersection(b);
291    /// assert_eq!(intersection.into_string(), r#"(2..=2, "a")"#);
292    /// ```
293    #[inline]
294    fn map_and_set_intersection<R>(self, other: R) -> IntersectionIterMap<T, VR, Self, R::IntoIter>
295    where
296        R: IntoIterator<Item = RangeInclusive<T>>,
297        R::IntoIter: SortedDisjoint<T>,
298        Self: Sized,
299    {
300        IntersectionIterMap::new(self, other.into_iter())
301    }
302
303    /// Given two [`SortedDisjointMap`] iterators, efficiently returns a [`SortedDisjointMap`] iterator of their set difference.
304    ///
305    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
306    ///
307    /// # Examples
308    ///
309    /// ```
310    /// use range_set_blaze::prelude::*;
311    ///
312    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
313    /// let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
314    /// let b = b0.range_values();
315    /// let difference = a.difference(b);
316    /// assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);
317    ///
318    /// // Alternatively, we can use "-" because `CheckSortedDisjointMap` defines
319    /// // `ops::Sub` as `SortedDisjointMap::difference`.
320    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
321    /// let b = b0.range_values();
322    /// let difference = a - b;
323    /// assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);
324    /// ```
325    #[inline]
326    fn difference<R>(self, other: R) -> DifferenceMap<T, VR, Self, R::IntoIter>
327    where
328        R: IntoIterator<Item = Self::Item>,
329        R::IntoIter: SortedDisjointMap<T, VR>,
330        Self: Sized,
331    {
332        let sorted_disjoint_map = other.into_iter();
333        let complement = sorted_disjoint_map.complement();
334        IntersectionIterMap::new(self, complement)
335    }
336
337    /// Given a [`SortedDisjointMap`] iterator and a [`SortedDisjoint`] iterator,
338    /// efficiently returns a [`SortedDisjointMap`] iterator of their set difference.
339    ///
340    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
341    /// [`SortedDisjoint`]: trait.SortedDisjoint.html#table-of-contents
342    ///
343    /// # Examples
344    ///
345    /// ```
346    /// use range_set_blaze::prelude::*;
347    ///
348    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
349    /// let b = RangeMapBlaze::from_iter([(2..=3, "b")]).into_ranges();
350    /// let difference = a.map_and_set_difference(b);
351    /// assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);
352    /// ```
353    #[inline]
354    fn map_and_set_difference<R>(self, other: R) -> DifferenceMapInternal<T, VR, Self, R::IntoIter>
355    where
356        R: IntoIterator<Item = RangeInclusive<T>>,
357        R::IntoIter: SortedDisjoint<T>,
358        Self: Sized,
359    {
360        let sorted_disjoint = other.into_iter();
361        let complement = sorted_disjoint.complement();
362        IntersectionIterMap::new(self, complement)
363    }
364
365    /// Returns the complement of a [`SortedDisjointMap`]'s keys as a [`SortedDisjoint`] iterator.
366    ///
367    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
368    /// [`SortedDisjoint`]: trait.SortedDisjoint.html#table-of-contents
369    ///
370    /// # Examples
371    ///
372    /// ```
373    /// use range_set_blaze::prelude::*;
374    ///
375    /// let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
376    /// let complement = a.complement();
377    /// assert_eq!(complement.into_string(), "0..=9, 21..=99, 201..=255");
378    ///
379    /// // Alternatively, we can use "!" because `CheckSortedDisjointMap` implements
380    /// // `ops::Not` as `complement`.
381    /// let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
382    /// let complement_using_not = !a;
383    /// assert_eq!(complement_using_not.into_string(), "0..=9, 21..=99, 201..=255");
384    /// ```
385    #[inline]
386    fn complement(self) -> NotIter<T, RangeValuesToRangesIter<T, VR, Self>>
387    where
388        Self: Sized,
389    {
390        let sorted_disjoint = self.into_sorted_disjoint();
391        sorted_disjoint.complement()
392    }
393
394    /// Returns the complement of a [`SortedDisjointMap`]'s keys, associating each range with the provided value `v`.
395    /// The result is a [`SortedDisjointMap`] iterator.
396    ///
397    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
398    ///
399    /// # Examples
400    ///
401    /// ```
402    /// use range_set_blaze::prelude::*;
403    ///
404    /// let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
405    /// let complement = a.complement_with(&"z");
406    /// assert_eq!(complement.into_string(), r#"(0..=9, "z"), (21..=99, "z"), (201..=255, "z")"#);
407    /// ```
408    #[inline]
409    fn complement_with(
410        self,
411        v: &VR::Target,
412    ) -> RangeToRangeValueIter<'_, T, VR::Target, NotIter<T, impl SortedDisjoint<T>>>
413    where
414        Self: Sized,
415    {
416        let complement = self.complement();
417        RangeToRangeValueIter::new(complement, v)
418    }
419
420    /// Given two [`SortedDisjointMap`] iterators, efficiently returns a [`SortedDisjointMap`] iterator
421    /// of their symmetric difference.
422    ///
423    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
424    ///
425    /// # Examples
426    ///
427    /// ```
428    /// use range_set_blaze::prelude::*;
429    ///
430    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
431    /// let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
432    /// let b = b0.range_values();
433    /// let symmetric_difference = a.symmetric_difference(b);
434    /// assert_eq!(symmetric_difference.into_string(), r#"(1..=1, "a"), (3..=3, "b")"#);
435    ///
436    /// // Alternatively, we can use "^" because CheckSortedDisjointMap defines
437    /// // ops::bitxor as SortedDisjointMap::symmetric_difference.
438    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
439    /// let b = b0.range_values();
440    /// let symmetric_difference = a ^ b;
441    /// assert_eq!(symmetric_difference.into_string(), r#"(1..=1, "a"), (3..=3, "b")"#);
442    /// ```
443    #[inline]
444    fn symmetric_difference<R>(self, other: R) -> SymDiffMergeMap<T, VR, Self, R::IntoIter>
445    where
446        R: IntoIterator<Item = Self::Item>,
447        R::IntoIter: SortedDisjointMap<T, VR>,
448        Self: Sized,
449        VR: ValueRef,
450    {
451        SymDiffIterMap::new2(self, other.into_iter())
452    }
453
454    /// Given two [`SortedDisjointMap`] iterators, efficiently tells if they are equal. Unlike most equality testing in Rust,
455    /// this method takes ownership of the iterators and consumes them.
456    ///
457    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
458    ///
459    /// # Examples
460    ///
461    /// ```
462    /// use range_set_blaze::prelude::*;
463    ///
464    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
465    /// let b0 = RangeMapBlaze::from_iter([(1..=2, "a")]);
466    /// let b = b0.range_values();
467    /// assert!(a.equal(b));
468    /// ```
469    fn equal<R>(self, other: R) -> bool
470    where
471        R: IntoIterator<Item = Self::Item>,
472        R::IntoIter: SortedDisjointMap<T, VR>,
473        Self: Sized,
474    {
475        use itertools::Itertools;
476
477        self.zip_longest(other).all(|pair| {
478            match pair {
479                itertools::EitherOrBoth::Both(
480                    (self_range, self_value),
481                    (other_range, other_value),
482                ) => {
483                    // Place your custom equality logic here for matching elements
484                    self_range == other_range && self_value.borrow() == other_value.borrow()
485                }
486                _ => false, // Handles the case where iterators are of different lengths
487            }
488        })
489    }
490
491    /// Returns `true` if the [`SortedDisjointMap`] contains no elements.
492    ///
493    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
494    ///
495    /// # Examples
496    ///
497    /// ```
498    /// use range_set_blaze::prelude::*;
499    ///
500    /// let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
501    /// assert!(!a.is_empty());
502    /// ```
503    #[inline]
504    #[allow(clippy::wrong_self_convention)]
505    fn is_empty(mut self) -> bool
506    where
507        Self: Sized,
508    {
509        self.next().is_none()
510    }
511
512    /// Create a [`RangeMapBlaze`] from a [`SortedDisjointMap`] iterator.
513    ///
514    /// *For more about constructors and performance, see [`RangeMapBlaze` Constructors](struct.RangeMapBlaze.html#rangemapblaze-constructors).*
515    ///
516    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
517    /// # Examples
518    ///
519    /// ```
520    /// use range_set_blaze::prelude::*;
521    ///
522    /// let a0 = RangeMapBlaze::from_sorted_disjoint_map(CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]));
523    /// let a1: RangeMapBlaze<i32,_> = CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]).into_range_map_blaze();
524    /// assert!(a0 == a1 && a0.to_string() == r#"(-10..=-5, "a"), (1..=2, "b")"#);
525    /// ```
526    fn into_range_map_blaze(self) -> RangeMapBlaze<T, VR::Target>
527    where
528        Self: Sized,
529    {
530        RangeMapBlaze::from_sorted_disjoint_map(self)
531    }
532}
533
534/// Converts the implementing type into a String by consuming it.
535pub trait IntoString {
536    /// Consumes the implementing type and converts it into a String.
537    fn into_string(self) -> String;
538}
539
540impl<T, I> IntoString for I
541where
542    T: Debug,
543    I: Iterator<Item = T>,
544{
545    fn into_string(self) -> String {
546        self.map(|item| format!("{item:?}"))
547            .collect::<Vec<String>>()
548            .join(", ")
549    }
550}
551
552/// Gives the [`SortedDisjointMap`] trait to any iterator of range-value pairs. Will panic
553/// if the trait is not satisfied.
554///
555/// The iterator will panic
556/// if/when it finds that the ranges are not actually sorted and disjoint or if the values overlap inappropriately.
557///
558/// [`SortedDisjointMap`]: crate::SortedDisjointMap.html#table-of-contents
559///
560/// # Performance
561///
562/// All checking is done at runtime, but it should still be fast.
563///
564/// # Example
565///
566/// ```
567/// use range_set_blaze::prelude::*;
568///
569/// let a = CheckSortedDisjointMap::new([(4..=6, &"a")]);
570/// let b = CheckSortedDisjointMap::new([(1..=3, &"z"), (5..=10, &"b")]);
571/// let union = a | b;
572/// assert_eq!(union.into_string(), r#"(1..=3, "z"), (4..=4, "a"), (5..=10, "b")"#);
573/// ```
574///
575/// Here the ranges are not sorted and disjoint, so the iterator will panic.
576/// ```should_panic
577/// use range_set_blaze::prelude::*;
578///
579/// let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (5..=10, &"b")]);
580/// let b = CheckSortedDisjointMap::new([(4..=6, &"c"), (-10..=12, &"d")]);
581/// let union = a | b;
582/// assert_eq!(union.into_string(), "1..=3 -> a, 5..=10 -> b");
583/// ```
584#[allow(clippy::module_name_repetitions)]
585#[must_use = "iterators are lazy and do nothing unless consumed"]
586#[derive(Debug, Clone)]
587pub struct CheckSortedDisjointMap<T, VR, I>
588where
589    T: Integer,
590    VR: ValueRef,
591    I: Iterator<Item = (RangeInclusive<T>, VR)>,
592{
593    iter: I,
594    seen_none: bool,
595    previous: Option<(RangeInclusive<T>, VR)>,
596}
597
598// define new
599impl<T, VR, I> CheckSortedDisjointMap<T, VR, I>
600where
601    T: Integer,
602    VR: ValueRef,
603    I: Iterator<Item = (RangeInclusive<T>, VR)>,
604{
605    /// Creates a new [`CheckSortedDisjointMap`] from an iterator of ranges and values. See [`CheckSortedDisjointMap`] for details and examples.
606    #[inline]
607    #[must_use = "iterators are lazy and do nothing unless consumed"]
608    pub fn new<J>(iter: J) -> Self
609    where
610        J: IntoIterator<Item = (RangeInclusive<T>, VR), IntoIter = I>,
611    {
612        Self {
613            iter: iter.into_iter(),
614            seen_none: false,
615            previous: None,
616        }
617    }
618}
619
620impl<T, VR, I> Default for CheckSortedDisjointMap<T, VR, I>
621where
622    T: Integer,
623    VR: ValueRef,
624    I: Iterator<Item = (RangeInclusive<T>, VR)> + Default,
625{
626    fn default() -> Self {
627        // Utilize I::default() to satisfy the iterator requirement.
628        Self::new(I::default())
629    }
630}
631
632impl<T, VR, I> FusedIterator for CheckSortedDisjointMap<T, VR, I>
633where
634    T: Integer,
635    VR: ValueRef,
636    I: Iterator<Item = (RangeInclusive<T>, VR)>,
637{
638}
639
640fn range_value_clone<T, VR>(range_value: &(RangeInclusive<T>, VR)) -> (RangeInclusive<T>, VR)
641where
642    T: Integer,
643    VR: ValueRef,
644{
645    let (range, value) = range_value;
646    (range.clone(), value.clone())
647}
648
649impl<T, VR, I> Iterator for CheckSortedDisjointMap<T, VR, I>
650where
651    T: Integer,
652    VR: ValueRef,
653    I: Iterator<Item = (RangeInclusive<T>, VR)>,
654{
655    type Item = (RangeInclusive<T>, VR);
656
657    #[allow(clippy::manual_assert)] // We use "if...panic!" for coverage auditing.
658    fn next(&mut self) -> Option<Self::Item> {
659        // Get the next item
660        let range_value = self.iter.next();
661
662        // If it's None, we're done (but remember that we've seen None)
663        let Some(range_value) = range_value else {
664            self.seen_none = true;
665            return None;
666        };
667
668        // if the next item is Some, check that we haven't seen None before
669        if self.seen_none {
670            panic!("a value must not be returned after None")
671        }
672
673        // Check that the range is not empty
674        let (start, end) = range_value.0.clone().into_inner();
675        if start > end {
676            panic!("start must be <= end")
677        }
678
679        // If previous is None, we're done (but remember this pair as previous)
680        let Some(previous) = self.previous.take() else {
681            self.previous = Some(range_value_clone(&range_value));
682            return Some(range_value);
683        };
684
685        // The next_item is Some and previous is Some, so check that the ranges are disjoint and sorted
686        let previous_end = *previous.0.end();
687        if previous_end >= start {
688            panic!("ranges must be disjoint and sorted")
689        }
690
691        if previous_end.add_one() == start && previous.1.borrow() == range_value.1.borrow() {
692            panic!("touching ranges must have different values")
693        }
694
695        // Remember this pair as previous
696        self.previous = Some(range_value_clone(&range_value));
697        Some(range_value)
698    }
699
700    fn size_hint(&self) -> (usize, Option<usize>) {
701        self.iter.size_hint()
702    }
703}
704
705/// Used internally by `MergeMap`.
706#[derive(Clone, Debug)]
707pub struct Priority<T, VR>
708where
709    T: Integer,
710    VR: ValueRef,
711{
712    range_value: (RangeInclusive<T>, VR),
713    priority_number: usize,
714}
715
716impl<T, VR> Priority<T, VR>
717where
718    T: Integer,
719    VR: ValueRef,
720{
721    pub(crate) const fn new(range_value: (RangeInclusive<T>, VR), priority_number: usize) -> Self {
722        Self {
723            range_value,
724            priority_number,
725        }
726    }
727}
728
729impl<T, VR> Priority<T, VR>
730where
731    T: Integer,
732    VR: ValueRef,
733{
734    /// Returns a reference to `range_value`.
735    pub const fn range_value(&self) -> &(RangeInclusive<T>, VR) {
736        &self.range_value
737    }
738
739    /// Consumes `Priority` and returns `range_value`.
740    pub fn into_range_value(self) -> (RangeInclusive<T>, VR) {
741        self.range_value
742    }
743
744    /// Updates the range part of `range_value`.
745    pub const fn set_range(&mut self, range: RangeInclusive<T>) {
746        self.range_value.0 = range;
747    }
748
749    /// Returns the start of the range.
750    pub const fn start(&self) -> T {
751        *self.range_value.0.start()
752    }
753
754    /// Returns the end of the range.
755    pub const fn end(&self) -> T {
756        *self.range_value.0.end()
757    }
758
759    /// Returns the start and end of the range. (Assuming direct access to start and end)
760    pub const fn start_and_end(&self) -> (T, T) {
761        ((*self.range_value.0.start()), (*self.range_value.0.end()))
762    }
763
764    /// Returns a reference to the value part of `range_value`.
765    pub const fn value(&self) -> &VR {
766        &self.range_value.1
767    }
768}
769
770// Implement `PartialEq` to allow comparison (needed for `Eq`).
771impl<T, VR> PartialEq for Priority<T, VR>
772where
773    T: Integer,
774    VR: ValueRef,
775{
776    fn eq(&self, other: &Self) -> bool {
777        self.priority_number == other.priority_number
778    }
779}
780
781// Implement `Eq` because `BinaryHeap` requires it.
782impl<T, VR> Eq for Priority<T, VR>
783where
784    T: Integer,
785    VR: ValueRef,
786{
787}
788
789// Implement `Ord` so the heap knows how to compare elements.
790impl<T, VR> Ord for Priority<T, VR>
791where
792    T: Integer,
793    VR: ValueRef,
794{
795    fn cmp(&self, other: &Self) -> Ordering {
796        debug_assert_ne!(
797            self.priority_number, other.priority_number,
798            "Priority numbers are expected to be distinct for comparison."
799        );
800        // bigger is better
801        self.priority_number.cmp(&other.priority_number)
802    }
803}
804
805// Implement `PartialOrd` to allow comparison (needed for `Ord`).
806impl<T, VR> PartialOrd for Priority<T, VR>
807where
808    T: Integer,
809    VR: ValueRef,
810{
811    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
812        Some(self.cmp(other))
813    }
814}
815
816/// Used internally by `complement_with`.
817#[must_use = "iterators are lazy and do nothing unless consumed"]
818#[derive(Clone, Debug)]
819pub struct RangeToRangeValueIter<'a, T, V, I>
820where
821    T: Integer,
822    V: Eq + Clone,
823    I: SortedDisjoint<T>,
824{
825    inner: I,
826    value: &'a V,
827    phantom: PhantomData<T>,
828}
829
830impl<'a, T, V, I> RangeToRangeValueIter<'a, T, V, I>
831where
832    T: Integer,
833    V: Eq + Clone,
834    I: SortedDisjoint<T>,
835{
836    pub(crate) const fn new(inner: I, value: &'a V) -> Self {
837        Self {
838            inner,
839            value,
840            phantom: PhantomData,
841        }
842    }
843}
844
845impl<T, V, I> FusedIterator for RangeToRangeValueIter<'_, T, V, I>
846where
847    T: Integer,
848    V: Eq + Clone,
849    I: SortedDisjoint<T>,
850{
851}
852
853impl<'a, T, V, I> Iterator for RangeToRangeValueIter<'a, T, V, I>
854where
855    T: Integer,
856    V: Eq + Clone,
857    I: SortedDisjoint<T>,
858{
859    type Item = (RangeInclusive<T>, &'a V);
860
861    fn next(&mut self) -> Option<Self::Item> {
862        self.inner.next().map(|range| (range, self.value))
863    }
864}
865
866// implements SortedDisjointMap
867impl<'a, T, V, I> SortedStartsMap<T, &'a V> for RangeToRangeValueIter<'a, T, V, I>
868where
869    T: Integer,
870    V: Eq + Clone,
871    I: SortedDisjoint<T>,
872{
873}
874impl<'a, T, V, I> SortedDisjointMap<T, &'a V> for RangeToRangeValueIter<'a, T, V, I>
875where
876    T: Integer,
877    V: Eq + Clone,
878    I: SortedDisjoint<T>,
879{
880}
881
882macro_rules! impl_sorted_map_traits_and_ops {
883    ($IterType:ty, $V:ty, $VR:ty, $($more_generics:tt)*) => {
884
885        #[allow(single_use_lifetimes)]
886        impl<$($more_generics)*, T> SortedStartsMap<T, $VR> for $IterType
887        where
888            T: Integer,
889        {
890        }
891
892        #[allow(single_use_lifetimes)]
893        impl<$($more_generics)*, T> SortedDisjointMap<T, $VR> for $IterType
894        where
895            T: Integer,
896        {
897        }
898
899        #[allow(single_use_lifetimes)]
900        impl<$($more_generics)*, T> ops::Not for $IterType
901        where
902            T: Integer,
903        {
904            type Output = NotMap<T, $VR, Self>;
905
906            #[inline]
907            fn not(self) -> Self::Output {
908                self.complement()
909            }
910        }
911
912        #[allow(single_use_lifetimes)]
913        impl<$($more_generics)*, T, R> ops::BitOr<R> for $IterType
914        where
915            T: Integer,
916            R: SortedDisjointMap<T, $VR>,
917        {
918            type Output = UnionMergeMap<T, $VR, Self, R>;
919
920            #[inline]
921            fn bitor(self, other: R) -> Self::Output {
922                SortedDisjointMap::union(self, other)
923            }
924        }
925
926        #[allow(single_use_lifetimes)]
927        impl<$($more_generics)*, T, R> ops::Sub<R> for $IterType
928        where
929            T: Integer,
930            R: SortedDisjointMap<T, $VR>,
931        {
932            type Output = DifferenceMap<T, $VR, Self, R>;
933
934            #[inline]
935            fn sub(self, other: R) -> Self::Output {
936                SortedDisjointMap::difference(self, other)
937            }
938        }
939
940        #[allow(single_use_lifetimes)]
941        impl<$($more_generics)*, T, R> ops::BitXor<R> for $IterType
942        where
943            T: Integer,
944            R: SortedDisjointMap<T, $VR>,
945        {
946            type Output = SymDiffMergeMap<T,  $VR, Self, R>;
947
948            #[allow(clippy::suspicious_arithmetic_impl)]
949            #[inline]
950            fn bitxor(self, other: R) -> Self::Output {
951                SortedDisjointMap::symmetric_difference(self, other)
952            }
953        }
954
955        #[allow(single_use_lifetimes)]
956        impl<$($more_generics)*, T, R> ops::BitAnd<R> for $IterType
957        where
958            T: Integer,
959            R: SortedDisjointMap<T, $VR>,
960        {
961            type Output = IntersectionMap<T, $VR, Self, R>;
962
963            #[inline]
964            fn bitand(self, other: R) -> Self::Output {
965                SortedDisjointMap::intersection(self, other)
966            }
967        }
968
969    }
970}
971
972// CheckList: Be sure that these are all tested in 'test_every_sorted_disjoint_map_method'
973impl_sorted_map_traits_and_ops!(CheckSortedDisjointMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: Iterator<Item = (RangeInclusive<T>,  VR)>);
974impl_sorted_map_traits_and_ops!(DynSortedDisjointMap<'a, T, VR>, VR::Value, VR, 'a, VR: ValueRef);
975impl_sorted_map_traits_and_ops!(IntersectionIterMap<T, VR, I0, I1>,  VR::Value, VR, VR: ValueRef, I0: SortedDisjointMap<T, VR>, I1: SortedDisjoint<T>);
976impl_sorted_map_traits_and_ops!(IntoRangeValuesIter<T, V>, V, Rc<V>, V: Eq + Clone);
977impl_sorted_map_traits_and_ops!(RangeValuesIter<'a, T, V>, V, &'a V, 'a, V: Eq + Clone);
978impl_sorted_map_traits_and_ops!(SymDiffIterMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: PrioritySortedStartsMap<T, VR>);
979impl_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
