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    /// Returns `true` if the map contains all possible integers.
513    ///
514    /// For type `T`, this means the ranges start at `T::min_value()` and continue contiguously up to `T::max_value()`.
515    /// Complexity: O(n) to verify contiguity across ranges.
516    ///
517    /// # Examples
518    ///
519    /// ```
520    /// use range_set_blaze::prelude::*;
521    ///
522    /// let b = CheckSortedDisjointMap::new([(0_u8..=100, &"x"), (101..=255, &"y")]);
523    /// assert!(b.is_universal());
524    ///
525    /// let c = CheckSortedDisjointMap::new([(1_u8..=255, &"z")]);
526    /// assert!(!c.is_universal());
527    /// ```
528    #[inline]
529    #[allow(clippy::wrong_self_convention)]
530    fn is_universal(self) -> bool
531    where
532        Self: Sized,
533    {
534        let mut expected_start = T::min_value();
535
536        for (range, _) in self {
537            let (start, end) = range.into_inner();
538
539            // Check if this range starts where we expect
540            if start != expected_start {
541                return false;
542            }
543
544            // If this range reaches the maximum value, we're done
545            if end == T::max_value() {
546                return true;
547            }
548
549            // Set up for the next range
550            expected_start = end.add_one();
551        }
552
553        // If we get here, we didn't reach the maximum value
554        false
555    }
556
557    /// Create a [`RangeMapBlaze`] from a [`SortedDisjointMap`] iterator.
558    ///
559    /// *For more about constructors and performance, see [`RangeMapBlaze` Constructors](struct.RangeMapBlaze.html#rangemapblaze-constructors).*
560    ///
561    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
562    /// # Examples
563    ///
564    /// ```
565    /// use range_set_blaze::prelude::*;
566    ///
567    /// let a0 = RangeMapBlaze::from_sorted_disjoint_map(CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]));
568    /// let a1: RangeMapBlaze<i32,_> = CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]).into_range_map_blaze();
569    /// assert!(a0 == a1 && a0.to_string() == r#"(-10..=-5, "a"), (1..=2, "b")"#);
570    /// ```
571    fn into_range_map_blaze(self) -> RangeMapBlaze<T, VR::Target>
572    where
573        Self: Sized,
574    {
575        RangeMapBlaze::from_sorted_disjoint_map(self)
576    }
577}
578
579/// Converts the implementing type into a String by consuming it.
580pub trait IntoString {
581    /// Consumes the implementing type and converts it into a String.
582    fn into_string(self) -> String;
583}
584
585impl<T, I> IntoString for I
586where
587    T: Debug,
588    I: Iterator<Item = T>,
589{
590    fn into_string(self) -> String {
591        self.map(|item| format!("{item:?}"))
592            .collect::<Vec<String>>()
593            .join(", ")
594    }
595}
596
597/// Gives the [`SortedDisjointMap`] trait to any iterator of range-value pairs. Will panic
598/// if the trait is not satisfied.
599///
600/// The iterator will panic
601/// if/when it finds that the ranges are not actually sorted and disjoint or if the values overlap inappropriately.
602///
603/// [`SortedDisjointMap`]: crate::SortedDisjointMap.html#table-of-contents
604///
605/// # Performance
606///
607/// All checking is done at runtime, but it should still be fast.
608///
609/// # Example
610///
611/// ```
612/// use range_set_blaze::prelude::*;
613///
614/// let a = CheckSortedDisjointMap::new([(4..=6, &"a")]);
615/// let b = CheckSortedDisjointMap::new([(1..=3, &"z"), (5..=10, &"b")]);
616/// let union = a | b;
617/// assert_eq!(union.into_string(), r#"(1..=3, "z"), (4..=4, "a"), (5..=10, "b")"#);
618/// ```
619///
620/// Here the ranges are not sorted and disjoint, so the iterator will panic.
621/// ```should_panic
622/// use range_set_blaze::prelude::*;
623///
624/// let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (5..=10, &"b")]);
625/// let b = CheckSortedDisjointMap::new([(4..=6, &"c"), (-10..=12, &"d")]);
626/// let union = a | b;
627/// assert_eq!(union.into_string(), "1..=3 -> a, 5..=10 -> b");
628/// ```
629#[allow(clippy::module_name_repetitions)]
630#[must_use = "iterators are lazy and do nothing unless consumed"]
631#[derive(Debug, Clone)]
632pub struct CheckSortedDisjointMap<T, VR, I>
633where
634    T: Integer,
635    VR: ValueRef,
636    I: Iterator<Item = (RangeInclusive<T>, VR)>,
637{
638    iter: I,
639    seen_none: bool,
640    previous: Option<(RangeInclusive<T>, VR)>,
641}
642
643// define new
644impl<T, VR, I> CheckSortedDisjointMap<T, VR, I>
645where
646    T: Integer,
647    VR: ValueRef,
648    I: Iterator<Item = (RangeInclusive<T>, VR)>,
649{
650    /// Creates a new [`CheckSortedDisjointMap`] from an iterator of ranges and values. See [`CheckSortedDisjointMap`] for details and examples.
651    #[inline]
652    #[must_use = "iterators are lazy and do nothing unless consumed"]
653    pub fn new<J>(iter: J) -> Self
654    where
655        J: IntoIterator<Item = (RangeInclusive<T>, VR), IntoIter = I>,
656    {
657        Self {
658            iter: iter.into_iter(),
659            seen_none: false,
660            previous: None,
661        }
662    }
663}
664
665impl<T, VR, I> Default for CheckSortedDisjointMap<T, VR, I>
666where
667    T: Integer,
668    VR: ValueRef,
669    I: Iterator<Item = (RangeInclusive<T>, VR)> + Default,
670{
671    fn default() -> Self {
672        // Utilize I::default() to satisfy the iterator requirement.
673        Self::new(I::default())
674    }
675}
676
677impl<T, VR, I> FusedIterator for CheckSortedDisjointMap<T, VR, I>
678where
679    T: Integer,
680    VR: ValueRef,
681    I: Iterator<Item = (RangeInclusive<T>, VR)>,
682{
683}
684
685fn range_value_clone<T, VR>(range_value: &(RangeInclusive<T>, VR)) -> (RangeInclusive<T>, VR)
686where
687    T: Integer,
688    VR: ValueRef,
689{
690    let (range, value) = range_value;
691    (range.clone(), value.clone())
692}
693
694impl<T, VR, I> Iterator for CheckSortedDisjointMap<T, VR, I>
695where
696    T: Integer,
697    VR: ValueRef,
698    I: Iterator<Item = (RangeInclusive<T>, VR)>,
699{
700    type Item = (RangeInclusive<T>, VR);
701
702    #[allow(clippy::manual_assert)] // We use "if...panic!" for coverage auditing.
703    fn next(&mut self) -> Option<Self::Item> {
704        // Get the next item
705        let range_value = self.iter.next();
706
707        // If it's None, we're done (but remember that we've seen None)
708        let Some(range_value) = range_value else {
709            self.seen_none = true;
710            return None;
711        };
712
713        // if the next item is Some, check that we haven't seen None before
714        if self.seen_none {
715            panic!("a value must not be returned after None")
716        }
717
718        // Check that the range is not empty
719        let (start, end) = range_value.0.clone().into_inner();
720        if start > end {
721            panic!("start must be <= end")
722        }
723
724        // If previous is None, we're done (but remember this pair as previous)
725        let Some(previous) = self.previous.take() else {
726            self.previous = Some(range_value_clone(&range_value));
727            return Some(range_value);
728        };
729
730        // The next_item is Some and previous is Some, so check that the ranges are disjoint and sorted
731        let previous_end = *previous.0.end();
732        if previous_end >= start {
733            panic!("ranges must be disjoint and sorted")
734        }
735
736        if previous_end.add_one() == start && previous.1.borrow() == range_value.1.borrow() {
737            panic!("touching ranges must have different values")
738        }
739
740        // Remember this pair as previous
741        self.previous = Some(range_value_clone(&range_value));
742        Some(range_value)
743    }
744
745    fn size_hint(&self) -> (usize, Option<usize>) {
746        self.iter.size_hint()
747    }
748}
749
750/// Used internally by `MergeMap`.
751#[derive(Clone, Debug)]
752pub struct Priority<T, VR>
753where
754    T: Integer,
755    VR: ValueRef,
756{
757    range_value: (RangeInclusive<T>, VR),
758    priority_number: usize,
759}
760
761impl<T, VR> Priority<T, VR>
762where
763    T: Integer,
764    VR: ValueRef,
765{
766    pub(crate) const fn new(range_value: (RangeInclusive<T>, VR), priority_number: usize) -> Self {
767        Self {
768            range_value,
769            priority_number,
770        }
771    }
772}
773
774impl<T, VR> Priority<T, VR>
775where
776    T: Integer,
777    VR: ValueRef,
778{
779    /// Returns a reference to `range_value`.
780    pub const fn range_value(&self) -> &(RangeInclusive<T>, VR) {
781        &self.range_value
782    }
783
784    /// Consumes `Priority` and returns `range_value`.
785    pub fn into_range_value(self) -> (RangeInclusive<T>, VR) {
786        self.range_value
787    }
788
789    /// Updates the range part of `range_value`.
790    pub const fn set_range(&mut self, range: RangeInclusive<T>) {
791        self.range_value.0 = range;
792    }
793
794    /// Returns the start of the range.
795    pub const fn start(&self) -> T {
796        *self.range_value.0.start()
797    }
798
799    /// Returns the end of the range.
800    pub const fn end(&self) -> T {
801        *self.range_value.0.end()
802    }
803
804    /// Returns the start and end of the range. (Assuming direct access to start and end)
805    pub const fn start_and_end(&self) -> (T, T) {
806        ((*self.range_value.0.start()), (*self.range_value.0.end()))
807    }
808
809    /// Returns a reference to the value part of `range_value`.
810    pub const fn value(&self) -> &VR {
811        &self.range_value.1
812    }
813}
814
815// Implement `PartialEq` to allow comparison (needed for `Eq`).
816impl<T, VR> PartialEq for Priority<T, VR>
817where
818    T: Integer,
819    VR: ValueRef,
820{
821    fn eq(&self, other: &Self) -> bool {
822        self.priority_number == other.priority_number
823    }
824}
825
826// Implement `Eq` because `BinaryHeap` requires it.
827impl<T, VR> Eq for Priority<T, VR>
828where
829    T: Integer,
830    VR: ValueRef,
831{
832}
833
834// Implement `Ord` so the heap knows how to compare elements.
835impl<T, VR> Ord for Priority<T, VR>
836where
837    T: Integer,
838    VR: ValueRef,
839{
840    fn cmp(&self, other: &Self) -> Ordering {
841        debug_assert_ne!(
842            self.priority_number, other.priority_number,
843            "Priority numbers are expected to be distinct for comparison."
844        );
845        // bigger is better
846        self.priority_number.cmp(&other.priority_number)
847    }
848}
849
850// Implement `PartialOrd` to allow comparison (needed for `Ord`).
851impl<T, VR> PartialOrd for Priority<T, VR>
852where
853    T: Integer,
854    VR: ValueRef,
855{
856    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
857        Some(self.cmp(other))
858    }
859}
860
861/// Used internally by `complement_with`.
862#[must_use = "iterators are lazy and do nothing unless consumed"]
863#[derive(Clone, Debug)]
864pub struct RangeToRangeValueIter<'a, T, V, I>
865where
866    T: Integer,
867    V: Eq + Clone,
868    I: SortedDisjoint<T>,
869{
870    inner: I,
871    value: &'a V,
872    phantom: PhantomData<T>,
873}
874
875impl<'a, T, V, I> RangeToRangeValueIter<'a, T, V, I>
876where
877    T: Integer,
878    V: Eq + Clone,
879    I: SortedDisjoint<T>,
880{
881    pub(crate) const fn new(inner: I, value: &'a V) -> Self {
882        Self {
883            inner,
884            value,
885            phantom: PhantomData,
886        }
887    }
888}
889
890impl<T, V, I> FusedIterator for RangeToRangeValueIter<'_, T, V, I>
891where
892    T: Integer,
893    V: Eq + Clone,
894    I: SortedDisjoint<T>,
895{
896}
897
898impl<'a, T, V, I> Iterator for RangeToRangeValueIter<'a, T, V, I>
899where
900    T: Integer,
901    V: Eq + Clone,
902    I: SortedDisjoint<T>,
903{
904    type Item = (RangeInclusive<T>, &'a V);
905
906    fn next(&mut self) -> Option<Self::Item> {
907        self.inner.next().map(|range| (range, self.value))
908    }
909}
910
911// implements SortedDisjointMap
912impl<'a, T, V, I> SortedStartsMap<T, &'a V> for RangeToRangeValueIter<'a, T, V, I>
913where
914    T: Integer,
915    V: Eq + Clone,
916    I: SortedDisjoint<T>,
917{
918}
919impl<'a, T, V, I> SortedDisjointMap<T, &'a V> for RangeToRangeValueIter<'a, T, V, I>
920where
921    T: Integer,
922    V: Eq + Clone,
923    I: SortedDisjoint<T>,
924{
925}
926
927macro_rules! impl_sorted_map_traits_and_ops {
928    ($IterType:ty, $V:ty, $VR:ty, $($more_generics:tt)*) => {
929
930        #[allow(single_use_lifetimes)]
931        impl<$($more_generics)*, T> SortedStartsMap<T, $VR> for $IterType
932        where
933            T: Integer,
934        {
935        }
936
937        #[allow(single_use_lifetimes)]
938        impl<$($more_generics)*, T> SortedDisjointMap<T, $VR> for $IterType
939        where
940            T: Integer,
941        {
942        }
943
944        #[allow(single_use_lifetimes)]
945        impl<$($more_generics)*, T> ops::Not for $IterType
946        where
947            T: Integer,
948        {
949            type Output = NotMap<T, $VR, Self>;
950
951            #[inline]
952            fn not(self) -> Self::Output {
953                self.complement()
954            }
955        }
956
957        #[allow(single_use_lifetimes)]
958        impl<$($more_generics)*, T, R> ops::BitOr<R> for $IterType
959        where
960            T: Integer,
961            R: SortedDisjointMap<T, $VR>,
962        {
963            type Output = UnionMergeMap<T, $VR, Self, R>;
964
965            #[inline]
966            fn bitor(self, other: R) -> Self::Output {
967                SortedDisjointMap::union(self, other)
968            }
969        }
970
971        #[allow(single_use_lifetimes)]
972        impl<$($more_generics)*, T, R> ops::Sub<R> for $IterType
973        where
974            T: Integer,
975            R: SortedDisjointMap<T, $VR>,
976        {
977            type Output = DifferenceMap<T, $VR, Self, R>;
978
979            #[inline]
980            fn sub(self, other: R) -> Self::Output {
981                SortedDisjointMap::difference(self, other)
982            }
983        }
984
985        #[allow(single_use_lifetimes)]
986        impl<$($more_generics)*, T, R> ops::BitXor<R> for $IterType
987        where
988            T: Integer,
989            R: SortedDisjointMap<T, $VR>,
990        {
991            type Output = SymDiffMergeMap<T,  $VR, Self, R>;
992
993            #[allow(clippy::suspicious_arithmetic_impl)]
994            #[inline]
995            fn bitxor(self, other: R) -> Self::Output {
996                SortedDisjointMap::symmetric_difference(self, other)
997            }
998        }
999
1000        #[allow(single_use_lifetimes)]
1001        impl<$($more_generics)*, T, R> ops::BitAnd<R> for $IterType
1002        where
1003            T: Integer,
1004            R: SortedDisjointMap<T, $VR>,
1005        {
1006            type Output = IntersectionMap<T, $VR, Self, R>;
1007
1008            #[inline]
1009            fn bitand(self, other: R) -> Self::Output {
1010                SortedDisjointMap::intersection(self, other)
1011            }
1012        }
1013
1014    }
1015}
1016
1017// CheckList: Be sure that these are all tested in 'test_every_sorted_disjoint_map_method'
1018impl_sorted_map_traits_and_ops!(CheckSortedDisjointMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: Iterator<Item = (RangeInclusive<T>,  VR)>);
1019impl_sorted_map_traits_and_ops!(DynSortedDisjointMap<'a, T, VR>, VR::Value, VR, 'a, VR: ValueRef);
1020impl_sorted_map_traits_and_ops!(IntersectionIterMap<T, VR, I0, I1>,  VR::Value, VR, VR: ValueRef, I0: SortedDisjointMap<T, VR>, I1: SortedDisjoint<T>);
1021impl_sorted_map_traits_and_ops!(IntoRangeValuesIter<T, V>, V, Rc<V>, V: Eq + Clone);
1022impl_sorted_map_traits_and_ops!(RangeValuesIter<'a, T, V>, V, &'a V, 'a, V: Eq + Clone);
1023impl_sorted_map_traits_and_ops!(SymDiffIterMap<T, VR, I>, VR::Value, VR, VR: ValueRef, I: PrioritySortedStartsMap<T, VR>);
1024impl_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
