Trait range_set_blaze::SortedDisjointMap

pub trait SortedDisjointMap<T, V, VR>: SortedStartsMap<T, V, VR>
where
    T: Integer,
    V: ValueOwned,
    VR: CloneBorrow<V>,
{
    // Provided methods
    fn into_sorted_disjoint(self) -> RangeValuesToRangesIter<T, V, VR, Self> 
       where Self: Sized { ... }
    fn union<R>(self, other: R) -> BitOrMapMerge<T, V, VR, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, V, VR>,
             Self: Sized { ... }
    fn intersection<R>(
        self,
        other: R
    ) -> IntersectionIterMap<T, V, VR, Self, RangeValuesToRangesIter<T, V, VR, R::IntoIter>> 
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, V, VR>,
             Self: Sized { ... }
    fn intersection_with_set<R>(
        self,
        other: R
    ) -> IntersectionIterMap<T, V, VR, Self, R::IntoIter> 
       where R: IntoIterator<Item = RangeInclusive<T>>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn difference<R>(
        self,
        other: R
    ) -> IntersectionIterMap<T, V, VR, Self, NotIter<T, RangeValuesToRangesIter<T, V, VR, R::IntoIter>>> 
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, V, VR>,
             Self: Sized { ... }
    fn difference_with_set<R>(
        self,
        other: R
    ) -> IntersectionIterMap<T, V, VR, Self, NotIter<T, R::IntoIter>> 
       where R: IntoIterator<Item = RangeInclusive<T>>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn complement_to_set(
        self
    ) -> NotIter<T, RangeValuesToRangesIter<T, V, VR, Self>> 
       where Self: Sized { ... }
    fn complement(
        self,
        v: &V
    ) -> RangeToRangeValueIter<'_, T, V, NotIter<T, impl SortedDisjoint<T>>>
       where Self: Sized { ... }
    fn symmetric_difference<R>(
        self,
        other: R
    ) -> BitXorMapMerge<T, V, VR, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, V, VR>,
             Self: Sized,
             VR: CloneBorrow<V> { ... }
    fn equal<R>(self, other: R) -> bool
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, V, VR>,
             Self: Sized { ... }
    fn is_empty(self) -> bool
       where Self: Sized { ... }
    fn into_range_map_blaze(self) -> RangeMapBlaze<T, V>
       where Self: Sized,
             V: Clone { ... }
}

The trait used to mark iterators that provide ranges that are sorted by start and disjoint. Set operations on iterators that implement this trait can be performed in linear time.

Table of Contents

• SortedDisjointMap Constructors
  • Examples
• SortedDisjointMap Set and Other Operations
  • Performance
  • Examples
• How to mark your type as SortedDisjointMap
  • Example – Find the ordinal weekdays in September 2023

SortedDisjointMap Constructors

You’ll usually construct a SortedDisjointMap iterator from a RangeMapBlaze or a CheckSortedDisjointMap. Here is a summary table, followed by examples. You can also define your own SortedDisjointMap.

Input type	Method
RangeMapBlaze	ranges
RangeMapBlaze	into_ranges
RangeMapBlaze’s RangesIter	clone
sorted & disjoint ranges	CheckSortedDisjointMap::new
SortedDisjointMap iterator	itertools tee
SortedDisjointMap iterator	[crate::dyn_sorted_disjoint::DynSortedDisjointMap::new]
your iterator type	How to mark your type as SortedDisjointMap

Constructor Examples

use range_set_blaze::prelude::*;
use itertools::Itertools;

// RangeMapBlaze's .ranges(), .range().clone() and .into_ranges()
let r = RangeMapBlaze::from_iter([3, 2, 1, 100, 1]);
let a = r.ranges();
let b = a.clone();
assert!(a.into_string() == "1..=3, 100..=100");
assert!(b.into_string() == "1..=3, 100..=100");
//    'into_ranges' takes ownership of the 'RangeMapBlaze'
let a = RangeMapBlaze::from_iter([3, 2, 1, 100, 1]).into_ranges();
assert!(a.into_string() == "1..=3, 100..=100");

// CheckSortedDisjointMap -- unsorted or overlapping input ranges will cause a panic.
let a = CheckSortedDisjointMap::new([1..=3, 100..=100]);
assert!(a.into_string() == "1..=3, 100..=100");

// tee of a SortedDisjointMap iterator
let a = CheckSortedDisjointMap::new([1..=3, 100..=100]);
let (a, b) = a.tee();
assert!(a.into_string() == "1..=3, 100..=100");
assert!(b.into_string() == "1..=3, 100..=100");

// DynamicSortedDisjointMap of a SortedDisjointMap iterator
let a = CheckSortedDisjointMap::new([1..=3, 100..=100]);
let b = DynSortedDisjointMap::new(a);
assert!(b.into_string() == "1..=3, 100..=100");

SortedDisjointMap Set Operations

Method	Operator	Multiway (same type)	Multiway (different types)
a.union(b)	a | b	[a, b, c].union()	crate::MultiwayRangeSetBlaze::union!(a, b, c)
a.intersection(b)	a & b	[a, b, c].intersection()	crate::MultiwayRangeSetBlaze::intersection!(a, b, c)
a.difference(b)	a - b
a.symmetric_difference(b)	a ^ b
a.complement()	!a

Performance

Every operation is implemented as a single pass over the sorted & disjoint ranges, with minimal memory.

This is true even when applying multiple operations. The last example below demonstrates this.

Examples

use range_set_blaze::prelude::*;

let a0 = RangeMapBlaze::from_iter([1..=2, 5..=100]);
let b0 = RangeMapBlaze::from_iter([2..=6]);
let c0 = RangeMapBlaze::from_iter([2..=2, 6..=200]);

// 'union' method and 'to_string' method
let (a, b) = (a0.ranges(), b0.ranges());
let result = a.union(b);
assert_eq!(result.into_string(), "1..=100");

// '|' operator and 'equal' method
let (a, b) = (a0.ranges(), b0.ranges());
let result = a | b;
assert!(result.equal(CheckSortedDisjointMap::new([1..=100])));

// multiway union of same type
let (a, b, c) = (a0.ranges(), b0.ranges(), c0.ranges());
let result = [a, b, c].union();
assert_eq!(result.into_string(), "1..=200");

// multiway union of different types
let (a, b, c) = (a0.ranges(), b0.ranges(), c0.ranges());
let result = union_dyn!(a, b, !c);
assert_eq!(result.into_string(), "-2147483648..=100, 201..=2147483647");

// Applying multiple operators makes only one pass through the inputs with minimal memory.
let (a, b, c) = (a0.ranges(), b0.ranges(), c0.ranges());
let result = a - (b | c);
assert!(result.into_string() == "1..=1");

How to mark your type as SortedDisjointMap

To mark your iterator type as SortedDisjointMap, you implement the SortedStartsMap and SortedDisjointMap traits. This is your promise to the compiler that your iterator will provide inclusive ranges that disjoint and sorted by start.

When you do this, your iterator will get access to the efficient set operations methods, such as intersection and complement. The example below shows this.

To use operators such as & and !, you must also implement the BitAnd, Not, etc. traits.

If you want others to use your marked iterator type, reexport: pub use range_set_blaze::{SortedDisjointMap, SortedStartsMap};

Example – Find the ordinal weekdays in September 2023

use core::ops::RangeInclusive;
pub use range_set_blaze::{SortedDisjointMap, SortedStartsMap};

// Ordinal dates count January 1 as day 1, February 1 as day 32, etc.
struct OrdinalWeekends2023 {
    next_range: RangeInclusive<i32>,
}

// We promise the compiler that our iterator will provide
// ranges that are sorted and disjoint.
impl SortedStartsMap<i32> for OrdinalWeekends2023 {}
impl SortedDisjointMap<i32> for OrdinalWeekends2023 {}

impl OrdinalWeekends2023 {
    fn new() -> Self {
        Self { next_range: 0..=1 }
    }
}
impl Iterator for OrdinalWeekends2023 {
    type Item = RangeInclusive<i32>;
    fn next(&mut self) -> Option<Self::Item> {
        let (start, end) = self.next_range.clone().into_inner();
        if start > 365 {
            None
        } else {
            self.next_range = (start + 7)..=(end + 7);
            Some(start.max(1)..=end.min(365))
        }
    }
}

use range_set_blaze::prelude::*;

let weekends = OrdinalWeekends2023::new();
let september = CheckSortedDisjointMap::new([244..=273]);
let september_weekdays = september.intersection(weekends.complement());
assert_eq!(
    september_weekdays.into_string(),
    "244..=244, 247..=251, 254..=258, 261..=265, 268..=272"
);

Provided Methods

fn into_sorted_disjoint(self) -> RangeValuesToRangesIter<T, V, VR, Self>

where Self: Sized,

cmk

fn union<R>(self, other: R) -> BitOrMapMerge<T, V, VR, Self, R::IntoIter>

where R: IntoIterator<Item = Self::Item>, R::IntoIter: SortedDisjointMap<T, V, VR>, Self: Sized,

Given two SortedDisjointMap iterators, efficiently returns a SortedDisjointMap iterator of their union.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=1]);
let b = RangeMapBlaze::from_iter([2..=2]).into_ranges();
let union = a.union(b);
assert_eq!(union.into_string(), "1..=2");

// Alternatively, we can use "|" because CheckSortedDisjointMap defines
// ops::bitor as SortedDisjointMap::union.
let a = CheckSortedDisjointMap::new([1..=1]);
let b = RangeMapBlaze::from_iter([2..=2]).into_ranges();
let union = a | b;
assert_eq!(union.into_string(), "1..=2");

fn intersection<R>( self, other: R ) -> IntersectionIterMap<T, V, VR, Self, RangeValuesToRangesIter<T, V, VR, R::IntoIter>>

where R: IntoIterator<Item = Self::Item>, R::IntoIter: SortedDisjointMap<T, V, VR>, Self: Sized,

Given two SortedDisjointMap iterators, efficiently returns a SortedDisjointMap iterator of their intersection.

/// cmk Tell that right-and-side must be a set, not a map

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let intersection = a.intersection(b);
assert_eq!(intersection.into_string(), "2..=2");

// Alternatively, we can use "&" because CheckSortedDisjointMap defines
// ops::bitand as SortedDisjointMap::intersection.
let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let intersection = a & b;
assert_eq!(intersection.into_string(), "2..=2");

fn intersection_with_set<R>( self, other: R ) -> IntersectionIterMap<T, V, VR, Self, R::IntoIter>

where R: IntoIterator<Item = RangeInclusive<T>>, R::IntoIter: SortedDisjoint<T>, Self: Sized,

Given two SortedDisjointMap iterators, efficiently returns a SortedDisjointMap iterator of their intersection.

/// cmk Tell that right-and-side must be a set, not a map

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let intersection = a.intersection(b);
assert_eq!(intersection.into_string(), "2..=2");

// Alternatively, we can use "&" because CheckSortedDisjointMap defines
// ops::bitand as SortedDisjointMap::intersection.
let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let intersection = a & b;
assert_eq!(intersection.into_string(), "2..=2");

fn difference<R>( self, other: R ) -> IntersectionIterMap<T, V, VR, Self, NotIter<T, RangeValuesToRangesIter<T, V, VR, R::IntoIter>>>

where R: IntoIterator<Item = Self::Item>, R::IntoIter: SortedDisjointMap<T, V, VR>, Self: Sized,

Given two SortedDisjointMap iterators, efficiently returns a SortedDisjointMap iterator of their set difference.

cmk Tell that right-and-side must be a set, not a map

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let difference = a.difference(b);
assert_eq!(difference.into_string(), "1..=1");

// Alternatively, we can use "-" because CheckSortedDisjointMap defines
// ops::sub as SortedDisjointMap::difference.
let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let difference = a - b;
assert_eq!(difference.into_string(), "1..=1");

fn difference_with_set<R>( self, other: R ) -> IntersectionIterMap<T, V, VR, Self, NotIter<T, R::IntoIter>>

where R: IntoIterator<Item = RangeInclusive<T>>, R::IntoIter: SortedDisjoint<T>, Self: Sized,

Given two SortedDisjointMap iterators, efficiently returns a SortedDisjointMap iterator of their set difference.

cmk Tell that right-and-side must be a set, not a map

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let difference = a.difference(b);
assert_eq!(difference.into_string(), "1..=1");

// Alternatively, we can use "-" because CheckSortedDisjointMap defines
// ops::sub as SortedDisjointMap::difference.
let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let difference = a - b;
assert_eq!(difference.into_string(), "1..=1");

fn complement_to_set( self ) -> NotIter<T, RangeValuesToRangesIter<T, V, VR, Self>>

where Self: Sized,

cmk returns a set, not a map

fn complement( self, v: &V ) -> RangeToRangeValueIter<'_, T, V, NotIter<T, impl SortedDisjoint<T>>>

where Self: Sized,

cmk returns a set, not a map

fn symmetric_difference<R>( self, other: R ) -> BitXorMapMerge<T, V, VR, Self, R::IntoIter>

where R: IntoIterator<Item = Self::Item>, R::IntoIter: SortedDisjointMap<T, V, VR>, Self: Sized, VR: CloneBorrow<V>,

Given two SortedDisjointMap iterators, efficiently returns a SortedDisjointMap iterator of their symmetric difference.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let symmetric_difference = a.symmetric_difference(b);
assert_eq!(symmetric_difference.into_string(), "1..=1, 3..=3");

// Alternatively, we can use "^" because CheckSortedDisjointMap defines
// ops::bitxor as SortedDisjointMap::symmetric_difference.
let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([2..=3]).into_ranges();
let symmetric_difference = a ^ b;
assert_eq!(symmetric_difference.into_string(), "1..=1, 3..=3");

fn equal<R>(self, other: R) -> bool

where R: IntoIterator<Item = Self::Item>, R::IntoIter: SortedDisjointMap<T, V, VR>, Self: Sized,

Given two SortedDisjointMap iterators, efficiently tells if they are equal. Unlike most equality testing in Rust, this method takes ownership of the iterators and consumes them.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([1..=2]);
let b = RangeMapBlaze::from_iter([1..=2]).into_ranges();
assert!(a.equal(b));

fn is_empty(self) -> bool

where Self: Sized,

Returns true if the set contains no elements.

Examples

use range_set_blaze::RangeMapBlaze;

let mut v = RangeMapBlaze::new();
assert!(v.is_empty());
v.insert(1);
assert!(!v.is_empty());

fn into_range_map_blaze(self) -> RangeMapBlaze<T, V>

where Self: Sized, V: Clone,

Returns true if the set is a subset of another, i.e., other contains at least all the elements in self.

Examples

use range_set_blaze::prelude::*;

let sup = CheckSortedDisjointMap::new([1..=3]);
let set: CheckSortedDisjointMap<i32, _> = [].into();
assert_eq!(set.is_subset(sup), true);

let sup = CheckSortedDisjointMap::new([1..=3]);
let set = CheckSortedDisjointMap::new([2..=2]);
assert_eq!(set.is_subset(sup), true);

let sup = CheckSortedDisjointMap::new([1..=3]);
let set = CheckSortedDisjointMap::new([2..=2, 4..=4]);
assert_eq!(set.is_subset(sup), false);

Returns true if the set is a superset of another, i.e., self contains at least all the elements in other.

Examples

use range_set_blaze::RangeMapBlaze;

let sub = RangeMapBlaze::from_iter([1, 2]);
let mut set = RangeMapBlaze::new();

assert_eq!(set.is_superset(&sub), false);

set.insert(0);
set.insert(1);
assert_eq!(set.is_superset(&sub), false);

set.insert(2);
assert_eq!(set.is_superset(&sub), true);

Returns true if self has no elements in common with other. This is equivalent to checking for an empty intersection.

Examples

use range_set_blaze::RangeMapBlaze;

let a = RangeMapBlaze::from_iter([1..=3]);
let mut b = RangeMapBlaze::new();

assert_eq!(a.is_disjoint(&b), true);
b.insert(4);
assert_eq!(a.is_disjoint(&b), true);
b.insert(1);
assert_eq!(a.is_disjoint(&b), false);

Create a RangeMapBlaze from a SortedDisjointMap iterator.

For more about constructors and performance, see RangeMapBlaze Constructors.

Examples

use range_set_blaze::prelude::*;

let a0 = RangeMapBlaze::from_sorted_disjoint(CheckSortedDisjointMap::new([-10..=-5, 1..=2]));
let a1: RangeMapBlaze<i32> = CheckSortedDisjointMap::new([-10..=-5, 1..=2]).into_range_set_blaze();
assert!(a0 == a1 && a0.into_string() == "-10..=-5, 1..=2");

Implementors

impl<'a, V: ValueOwned, T> SortedDisjointMap<T, V, &'a V> for RangeValuesIter<'a, T, V>

where T: Integer,

impl<'a, V: ValueOwned, VR: CloneBorrow<V>, T> SortedDisjointMap<T, V, VR> for DynSortedDisjointMap<'a, T, V, VR>

where T: Integer,

impl<V: ValueOwned, VR: CloneBorrow<V>, I0: SortedDisjointMap<T, V, VR>, I1: SortedDisjoint<T>, T> SortedDisjointMap<T, V, VR> for IntersectionIterMap<T, V, VR, I0, I1>

where T: Integer,

impl<V: ValueOwned, VR: CloneBorrow<V>, I: Iterator<Item = (RangeInclusive<T>, VR)>, T> SortedDisjointMap<T, V, VR> for CheckSortedDisjointMap<T, V, VR, I>

where T: Integer,

impl<VR: CloneBorrow<V>, V: ValueOwned, I: PrioritySortedStartsMap<T, V, VR>, T> SortedDisjointMap<T, V, VR> for SymDiffIterMap<T, V, VR, I>

where T: Integer,

impl<VR: CloneBorrow<V>, V: ValueOwned, I: PrioritySortedStartsMap<T, V, VR>, T> SortedDisjointMap<T, V, VR> for UnionIterMap<T, V, VR, I>

where T: Integer,