Trait SortedDisjointMap 

pub trait SortedDisjointMap<T, VR>: SortedStartsMap<T, VR>
where
    T: Integer,
    VR: ValueRef,
{
    // Provided methods
    fn into_sorted_disjoint(self) -> RangeValuesToRangesIter<T, VR, Self> 
       where Self: Sized { ... }
    fn union<R>(self, other: R) -> UnionMergeMap<T, VR, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, VR>,
             Self: Sized { ... }
    fn intersection<R>(
        self,
        other: R,
    ) -> IntersectionMap<T, VR, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, VR>,
             Self: Sized { ... }
    fn map_and_set_intersection<R>(
        self,
        other: R,
    ) -> IntersectionIterMap<T, VR, Self, R::IntoIter> 
       where R: IntoIterator<Item = RangeInclusive<T>>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn difference<R>(self, other: R) -> DifferenceMap<T, VR, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, VR>,
             Self: Sized { ... }
    fn map_and_set_difference<R>(
        self,
        other: R,
    ) -> IntersectionIterMap<T, VR, Self, NotIter<T, R::IntoIter>> 
       where R: IntoIterator<Item = RangeInclusive<T>>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn complement(self) -> NotIter<T, RangeValuesToRangesIter<T, VR, Self>> 
       where Self: Sized { ... }
    fn complement_with(
        self,
        v: &VR::Target,
    ) -> RangeToRangeValueIter<'_, T, VR::Target, NotIter<T, impl SortedDisjoint<T>>>
       where Self: Sized { ... }
    fn symmetric_difference<R>(
        self,
        other: R,
    ) -> SymDiffMergeMap<T, VR, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, VR>,
             Self: Sized,
             VR: ValueRef { ... }
    fn equal<R>(self, other: R) -> bool
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjointMap<T, VR>,
             Self: Sized { ... }
    fn is_empty(self) -> bool
       where Self: Sized { ... }
    fn is_universal(self) -> bool
       where Self: Sized { ... }
    fn into_range_map_blaze(self) -> RangeMapBlaze<T, VR::Target>
       where Self: Sized { ... }
}

Marks iterators that provide (range, value) pairs that are sorted and disjoint. Set operations on iterators that implement this trait can be performed in linear time.

Table of Contents

• SortedDisjointMap Constructors
  • Examples
• SortedDisjointMap Set Operations
  • Performance
  • Examples
• How to mark your type as SortedDisjointMap

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	range_values
RangeMapBlaze	into_range_values
sorted & disjoint ranges and values	CheckSortedDisjointMap::new
your iterator type	How to mark your type as SortedDisjointMap

Constructor Examples

use range_set_blaze::prelude::*;

// RangeMapBlaze's .range_values(), and .into_range_values()
let r = RangeMapBlaze::from_iter([ (100, "b"), (1, "c"), (3, "a"), (2, "a"), (1, "a")]);
let a = r.range_values();
assert_eq!(a.into_string(), r#"(1..=3, "a"), (100..=100, "b")"#);
// 'into_range_values' takes ownership of the 'RangeMapBlaze'
let a = r.into_range_values();
assert_eq!(a.into_string(), r#"(1..=3, "a"), (100..=100, "b")"#);

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

SortedDisjointMap Set Operations

You can perform set operations on SortedDisjointMaps and SortedDisjoint sets using operators. In the table below, a, b, and c are SortedDisjointMap and s is a SortedDisjoint set.

Set Operator	Operator	Multiway (same type)	Multiway (different types)
union	a | b	[a, b, c].union()	union_map_dyn!(a, b, c)
intersection	a & b	[a, b, c].intersection()	intersection_map_dyn!(a, b, c)
intersection	a.map_and_set_intersection(s)	n/a	n/a
difference	a - b	n/a	n/a
difference	a.map_and_set_difference(s)	n/a	n/a
symmetric_difference	a ^ b	[a, b, c].symmetric_difference()	symmetric_difference_map_dyn!(a, b, c)
complement (to set)	!a	n/a	n/a
complement (to map)	a.complement_with(&value)	n/a	n/a

The union of any number of maps is defined such that, for any overlapping keys, the values from the right-most input take precedence. This approach ensures that the data from the right-most inputs remains dominant when merging with later inputs. Likewise, for symmetric difference of three or more maps.

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([(2..=6, "a")]);
let b0 = RangeMapBlaze::from_iter([(1..=2, "b"), (5..=100, "b")]);

// 'union' method and 'into_string' method
let (a, b) = (a0.range_values(), b0.range_values());
let result = a.union(b);
assert_eq!(result.into_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b")"#);

// '|' operator and 'equal' method
let (a, b) = (a0.range_values(), b0.range_values());
let result = a | b;
assert!(result.equal(CheckSortedDisjointMap::new([(1..=2, &"b"),  (3..=4, &"a"), (5..=100, &"b")])));

// multiway union of same type
let z0 = RangeMapBlaze::from_iter([(2..=2, "z"), (6..=200, "z")]);
let (z, a, b) = (z0.range_values(), a0.range_values(), b0.range_values());
let result = [z, a, b].union();
assert_eq!(result.into_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b"), (101..=200, "z")"#
);

// multiway union of different types
let (a, b) = (a0.range_values(), b0.range_values());
let z = CheckSortedDisjointMap::new([(2..=2, &"z"), (6..=200, &"z")]);
let result = union_map_dyn!(z, a, b);
assert_eq!(result.into_string(), r#"(1..=2, "b"), (3..=4, "a"), (5..=100, "b"), (101..=200, "z")"# );

// Applying multiple operators makes only one pass through the inputs with minimal memory.
let (z, a, b) = (z0.range_values(), a0.range_values(), b0.range_values());
let result = b - (z | a);
assert_eq!(result.into_string(), r#"(1..=1, "b")"#);

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 are 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.

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};

Provided Methods

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

where Self: Sized,

Converts a SortedDisjointMap iterator into a SortedDisjoint iterator.

 use range_set_blaze::prelude::*;

 let a = CheckSortedDisjointMap::new([(1..=3, &"a"), (100..=100, &"b")]);
 let b = a.into_sorted_disjoint();
 assert!(b.into_string() == "1..=3, 100..=100");

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

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

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

Examples

use range_set_blaze::prelude::*;

let a0 = RangeMapBlaze::from_iter([(2..=3, "a")]);
let a = a0.range_values();
let b = CheckSortedDisjointMap::new([(1..=2, &"b")]);
let union = a.union(b);
assert_eq!(union.into_string(), r#"(1..=2, "b"), (3..=3, "a")"#);

// Alternatively, we can use "|" because CheckSortedDisjointMap defines
// ops::bitor as SortedDisjointMap::union.
let a = a0.range_values();
let b = CheckSortedDisjointMap::new([(1..=2, &"b")]);
let union = a | b;
assert_eq!(union.into_string(), r#"(1..=2, "b"), (3..=3, "a")"#);

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

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

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

Examples

use range_set_blaze::prelude::*;

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

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

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

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

Given a SortedDisjointMap iterator and a SortedDisjoint iterator, efficiently returns a SortedDisjointMap iterator of their intersection.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
let b = CheckSortedDisjoint::new([2..=3]);
let intersection = a.map_and_set_intersection(b);
assert_eq!(intersection.into_string(), r#"(2..=2, "a")"#);

fn difference<R>(self, other: R) -> DifferenceMap<T, VR, Self, R::IntoIter>

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

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

Examples

use range_set_blaze::prelude::*;

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

// Alternatively, we can use "-" because `CheckSortedDisjointMap` defines
// `ops::Sub` as `SortedDisjointMap::difference`.
let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
let b = b0.range_values();
let difference = a - b;
assert_eq!(difference.into_string(), r#"(1..=1, "a")"#);

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

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

Given a SortedDisjointMap iterator and a SortedDisjoint iterator, efficiently returns a SortedDisjointMap iterator of their set difference.

Examples

use range_set_blaze::prelude::*;

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

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

where Self: Sized,

Returns the complement of a SortedDisjointMap’s keys as a SortedDisjoint iterator.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
let complement = a.complement();
assert_eq!(complement.into_string(), "0..=9, 21..=99, 201..=255");

// Alternatively, we can use "!" because `CheckSortedDisjointMap` implements
// `ops::Not` as `complement`.
let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
let complement_using_not = !a;
assert_eq!(complement_using_not.into_string(), "0..=9, 21..=99, 201..=255");

fn complement_with( self, v: &VR::Target, ) -> RangeToRangeValueIter<'_, T, VR::Target, NotIter<T, impl SortedDisjoint<T>>>

where Self: Sized,

Returns the complement of a SortedDisjointMap’s keys, associating each range with the provided value v. The result is a SortedDisjointMap iterator.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([(10_u8..=20, &"a"), (100..=200, &"b")]);
let complement = a.complement_with(&"z");
assert_eq!(complement.into_string(), r#"(0..=9, "z"), (21..=99, "z"), (201..=255, "z")"#);

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

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

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, &"a")]);
let b0 = RangeMapBlaze::from_iter([(2..=3, "b")]);
let b = b0.range_values();
let symmetric_difference = a.symmetric_difference(b);
assert_eq!(symmetric_difference.into_string(), r#"(1..=1, "a"), (3..=3, "b")"#);

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

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

where R: IntoIterator<Item = Self::Item>, R::IntoIter: SortedDisjointMap<T, 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, &"a")]);
let b0 = RangeMapBlaze::from_iter([(1..=2, "a")]);
let b = b0.range_values();
assert!(a.equal(b));

fn is_empty(self) -> bool

where Self: Sized,

Returns true if the SortedDisjointMap contains no elements.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjointMap::new([(1..=2, &"a")]);
assert!(!a.is_empty());

fn is_universal(self) -> bool

where Self: Sized,

Returns true if the map contains all possible integers.

For type T, this means the ranges start at T::min_value() and continue contiguously up to T::max_value(). Complexity: O(n) to verify contiguity across ranges.

Examples

use range_set_blaze::prelude::*;

let b = CheckSortedDisjointMap::new([(0_u8..=100, &"x"), (101..=255, &"y")]);
assert!(b.is_universal());

let c = CheckSortedDisjointMap::new([(1_u8..=255, &"z")]);
assert!(!c.is_universal());

fn into_range_map_blaze(self) -> RangeMapBlaze<T, VR::Target>

where Self: Sized,

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_map(CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]));
let a1: RangeMapBlaze<i32,_> = CheckSortedDisjointMap::new([(-10..=-5, &"a"), (1..=2, &"b")]).into_range_map_blaze();
assert!(a0 == a1 && a0.to_string() == r#"(-10..=-5, "a"), (1..=2, "b")"#);

Implementors

impl<'a, V: Eq + Clone, T> SortedDisjointMap<T, &'a V> for RangeValuesIter<'a, T, V>

where T: Integer,

impl<'a, VR: ValueRef, T> SortedDisjointMap<T, VR> for DynSortedDisjointMap<'a, T, VR>

where T: Integer,

impl<V: Eq + Clone, T> SortedDisjointMap<T, Rc<V>> for IntoRangeValuesIter<T, V>

where T: Integer,

impl<VR: ValueRef, I0: SortedDisjointMap<T, VR>, I1: SortedDisjoint<T>, T> SortedDisjointMap<T, VR> for IntersectionIterMap<T, VR, I0, I1>

where T: Integer,

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

where T: Integer,

impl<VR: ValueRef, I: PrioritySortedStartsMap<T, VR>, T> SortedDisjointMap<T, VR> for SymDiffIterMap<T, VR, I>

where T: Integer,

impl<VR: ValueRef, I: PrioritySortedStartsMap<T, VR>, T> SortedDisjointMap<T, VR> for UnionIterMap<T, VR, I>

where T: Integer,