Trait range_set_blaze::SortedDisjoint

pub trait SortedDisjoint<T: Integer>: SortedStarts<T> {
    // Provided methods
    fn union<R>(self, other: R) -> BitOrMerge<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn intersection<R>(self, other: R) -> BitAndMerge<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             Self: Sized { ... }
    fn difference<R>(self, other: R) -> BitSubMerge<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
    ) -> BitXOrTee<T, Self, R::IntoIter>
       where R: IntoIterator<Item = Self::Item>,
             R::IntoIter: SortedDisjoint<T>,
             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_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 { ... }
}

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

• SortedDisjoint Constructors
  • Examples
• SortedDisjoint Set and Other 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
RangeSetBlaze’s RangesIter	clone
sorted & disjoint ranges	CheckSortedDisjoint::new
SortedDisjoint iterator	itertools tee
SortedDisjoint iterator	crate::dyn_sorted_disjoint::DynSortedDisjoint::new
your iterator type	How to mark your type as SortedDisjoint

Constructor Examples

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

// RangeSetBlaze's .ranges(), .range().clone() and .into_ranges()
let r = RangeSetBlaze::from_iter([3, 2, 1, 100, 1]);
let a = r.ranges();
let b = a.clone();
assert!(a.to_string() == "1..=3, 100..=100");
assert!(b.to_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.to_string() == "1..=3, 100..=100");

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

// tee of a SortedDisjoint iterator
let a = CheckSortedDisjoint::from([1..=3, 100..=100]);
let (a, b) = a.tee();
assert!(a.to_string() == "1..=3, 100..=100");
assert!(b.to_string() == "1..=3, 100..=100");

// DynamicSortedDisjoint of a SortedDisjoint iterator
let a = CheckSortedDisjoint::from([1..=3, 100..=100]);
let b = DynSortedDisjoint::new(a);
assert!(b.to_string() == "1..=3, 100..=100");

SortedDisjoint 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 = RangeSetBlaze::from_iter([1..=2, 5..=100]);
let b0 = RangeSetBlaze::from_iter([2..=6]);
let c0 = RangeSetBlaze::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.to_string(), "1..=100");

// '|' operator and 'equal' method
let (a, b) = (a0.ranges(), b0.ranges());
let result = a | b;
assert!(result.equal(CheckSortedDisjoint::from([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.to_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.to_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.to_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 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;
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 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::from([244..=273]);
let september_weekdays = september.intersection(weekends.complement());
assert_eq!(
    september_weekdays.to_string(),
    "244..=244, 247..=251, 254..=258, 261..=265, 268..=272"
);

Provided Methods

fn union<R>(self, other: R) -> BitOrMerge<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::from([1..=1]);
let b = RangeSetBlaze::from_iter([2..=2]).into_ranges();
let union = a.union(b);
assert_eq!(union.to_string(), "1..=2");

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

fn intersection<R>(self, other: R) -> BitAndMerge<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::from([1..=2]);
let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
let intersection = a.intersection(b);
assert_eq!(intersection.to_string(), "2..=2");

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

fn difference<R>(self, other: R) -> BitSubMerge<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::from([1..=2]);
let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
let difference = a.difference(b);
assert_eq!(difference.to_string(), "1..=1");

// Alternatively, we can use "-" because CheckSortedDisjoint defines
// ops::sub as SortedDisjoint::difference.
let a = CheckSortedDisjoint::from([1..=2]);
let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
let difference = a - b;
assert_eq!(difference.to_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::from([-10i16..=0, 1000..=2000]);
let complement = a.complement();
assert_eq!(complement.to_string(), "-32768..=-11, 1..=999, 2001..=32767");

// Alternatively, we can use "!" because CheckSortedDisjoint defines
// ops::not as SortedDisjoint::complement.
let a = CheckSortedDisjoint::from([-10i16..=0, 1000..=2000]);
let complement = !a;
assert_eq!(complement.to_string(), "-32768..=-11, 1..=999, 2001..=32767");

fn symmetric_difference<R>(self, other: R) -> BitXOrTee<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 symmetric difference.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjoint::from([1..=2]);
let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
let symmetric_difference = a.symmetric_difference(b);
assert_eq!(symmetric_difference.to_string(), "1..=1, 3..=3");

// Alternatively, we can use "^" because CheckSortedDisjoint defines
// ops::bitxor as SortedDisjoint::symmetric_difference.
let a = CheckSortedDisjoint::from([1..=2]);
let b = RangeSetBlaze::from_iter([2..=3]).into_ranges();
let symmetric_difference = a ^ b;
assert_eq!(symmetric_difference.to_string(), "1..=1, 3..=3");

fn equal<R>(self, other: R) -> boolwhere 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::from([1..=2]);
let b = RangeSetBlaze::from_iter([1..=2]).into_ranges();
assert!(a.equal(b));

fn to_string(self) -> Stringwhere Self: Sized,

Given a SortedDisjoint iterators, produces a string version. Unlike most to_string and fmt in Rust, this method takes ownership of the iterator and consumes it.

Examples

use range_set_blaze::prelude::*;

let a = CheckSortedDisjoint::from([1..=2]);
assert_eq!(a.to_string(), "1..=2");

fn is_empty(self) -> boolwhere Self: Sized,

Returns true if the set contains no elements.

Examples

use range_set_blaze::RangeSetBlaze;

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

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

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

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

fn is_superset<R>(self, other: R) -> boolwhere 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) -> boolwhere 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::from([-10..=-5, 1..=2]));
let a1: RangeSetBlaze<i32> = CheckSortedDisjoint::from([-10..=-5, 1..=2]).into_range_set_blaze();
assert!(a0 == a1 && a0.to_string() == "-10..=-5, 1..=2");

Implementations on Foreign Types

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

Implementors

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

impl<T: Integer> SortedDisjoint<T> for IntoRangesIter<T>

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

impl<T: Integer, I> SortedDisjoint<T> for CheckSortedDisjoint<T, I>where I: Iterator<Item = RangeInclusive<T>>,

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

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