Trait SortedDisjoint 

pub trait SortedDisjoint<T: Integer>: SortedStarts<T> {
    // Provided methods
    fn union<R>(self, other: R) -> UnionMerge<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn intersection<R>(
        self,
        other: R,
    ) -> IntersectionMerge<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn difference<R>(self, other: R) -> DifferenceMerge<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn complement(self) -> NotIter<T, Self> 
       where Self: Sized { ... }
    fn symmetric_difference<R>(
        self,
        other: R,
    ) -> SymDiffMerge<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             <R as IntoIterator>::IntoIter:,
             Self: Sized { ... }
    fn equal<R>(self, other: R) -> bool
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn to_string(self) -> String
       where Self: Sized { ... }
    fn is_empty(self) -> bool
       where Self: Sized { ... }
    fn is_universal(self) -> bool
       where Self: Sized { ... }
    fn is_subset<R>(self, other: R) -> bool
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn is_superset<R>(self, other: R) -> bool
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn is_disjoint<R>(self, other: R) -> bool
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn into_range_set_blaze(self) -> RangeSetBlaze<T>
       where Self: Sized { ... }
}

Marks 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

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

SortedDisjoint Constructors

You’ll usually construct a SortedDisjoint iterator from a RangeSetBlaze or a CheckSortedDisjoint. Here is a summary table, followed by examples. You can also define your own SortedDisjoint.

Input type	Method
RangeSetBlaze	ranges
RangeSetBlaze	into_ranges
sorted & disjoint ranges	CheckSortedDisjoint::new
RangeInclusive	RangeOnce::new
your iterator type	How to mark your type as SortedDisjoint

Constructor Examples

use range_set_blaze::prelude::*;

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

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

SortedDisjoint Set Operations

You can perform set operations on SortedDisjoints using operators.

Set Operators	Operator	Multiway (same type)	Multiway (different types)
union	a | b	[a, b, c].union()	union_dyn!(a, b, c)
intersection	a & b	[a, b, c].intersection()	intersection_dyn!(a, b, c)
difference	a - b	n/a	n/a
symmetric_difference	a ^ b	[a, b, c].symmetric_difference()	symmetric_difference_dyn!(a, b, c)
complement	!a	n/a	n/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 = RangeSetBlaze::from_iter([1..=2, 5..=100]);
let b0 = RangeSetBlaze::from_iter([2..=6]);

// '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(CheckSortedDisjoint::new([1..=100])));

// multiway union of same type
let c0 = RangeSetBlaze::from_iter([2..=2, 6..=200]);
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 SortedDisjoint

To mark your iterator type as SortedDisjoint, you implement the SortedStarts and SortedDisjoint 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. 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::{SortedDisjoint, SortedStarts};

Example – Find the ordinal weekdays in September 2023

use core::ops::RangeInclusive;
use core::iter::FusedIterator;
pub use range_set_blaze::{SortedDisjoint, SortedStarts};

// 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 FusedIterator for OrdinalWeekends2023 {}
impl SortedStarts<i32> for OrdinalWeekends2023 {}
impl SortedDisjoint<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 = CheckSortedDisjoint::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 union<R>(self, other: R) -> UnionMerge<T, Self, R::IntoIter>

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

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

Examples

use range_set_blaze::prelude::*;

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

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

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

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

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

Examples

use range_set_blaze::prelude::*;

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

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

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

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

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

Examples

use range_set_blaze::prelude::*;

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

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

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

where Self: Sized,

Given a SortedDisjoint iterator, efficiently returns a SortedDisjoint iterator of its complement.

Examples

use range_set_blaze::prelude::*;

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

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

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

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

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

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjoint::new([1..=2]);
let b = RangeSetBlaze::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 CheckSortedDisjoint defines
// ops::bitxor as SortedDisjoint::symmetric_difference.
let a = CheckSortedDisjoint::new([1..=2]);
let b = RangeSetBlaze::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: SortedDisjoint<T>, Self: Sized,

Given two SortedDisjoint 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 = CheckSortedDisjoint::new([1..=2]);
let b = RangeSetBlaze::from_iter([1..=2]).into_ranges();
assert!(a.equal(b));

fn to_string(self) -> String

where Self: Sized,

👎Deprecated since 0.2.0: Use into_string instead

Deprecated. Use into_string instead.

fn is_empty(self) -> bool

where Self: Sized,

Returns true if the set contains no elements.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjoint::new([1..=2]);
assert!(!a.is_empty());

fn is_universal(self) -> bool

where Self: Sized,

Returns true if the set contains all possible integers.

For type T, this means exactly one range spanning T::min_value()..=T::max_value(). Complexity: O(1) on the first item.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjoint::new([1_u8..=2]);
assert!(!a.is_universal());

let universal = CheckSortedDisjoint::new([0_u8..=255]);
assert!(universal.is_universal());

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

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

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 = CheckSortedDisjoint::new([1..=3]);
let set: CheckSortedDisjoint<i32, _> = [].into();
assert_eq!(set.is_subset(sup), true);

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

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

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

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

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::RangeSetBlaze;

let sub = RangeSetBlaze::from_iter([1, 2]);
let mut set = RangeSetBlaze::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);

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

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

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::RangeSetBlaze;

let a = RangeSetBlaze::from_iter([1..=3]);
let mut b = RangeSetBlaze::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);

fn into_range_set_blaze(self) -> RangeSetBlaze<T>

where Self: Sized,

Create a RangeSetBlaze from a SortedDisjoint iterator.

For more about constructors and performance, see RangeSetBlaze Constructors.

Examples

use range_set_blaze::prelude::*;

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

Implementors

impl<'a, T: Integer> SortedDisjoint<T> for DynSortedDisjoint<'a, T>

impl<'a, T: Integer> SortedDisjoint<T> for RangesIter<'a, T>

impl<'a, V: Eq + Clone, T: Integer> SortedDisjoint<T> for MapRangesIter<'a, T, V>

impl<'ignore, T: Integer> SortedDisjoint<T> for IntoRangesIter<T>

impl<'ignore, T: Integer> SortedDisjoint<T> for RangeOnce<T>

impl<I: SortedDisjoint<T>, T: Integer> SortedDisjoint<T> for NotIter<T, I>

impl<I: SortedStarts<T>, T: Integer> SortedDisjoint<T> for SymDiffIter<T, I>

impl<I: SortedStarts<T>, T: Integer> SortedDisjoint<T> for UnionIter<T, I>

impl<I: AnythingGoes<T>, T: Integer> SortedDisjoint<T> for CheckSortedDisjoint<T, I>

impl<V: Eq + Clone, T: Integer> SortedDisjoint<T> for MapIntoRangesIter<T, V>

impl<VR: ValueRef, I: SortedDisjointMap<T, VR>, T: Integer> SortedDisjoint<T> for RangeValuesToRangesIter<T, VR, I>