Crate ordmask

Expand description

ordmask is a library for efficient range-based set operations and membership checking. It represents a set of values as a collection of intervals and supports various set operations.

§Features

Efficient range membership checking
Support for union, intersection, minus, complement, and symmetric_difference operations
Works with any type that implements Ord, Clone, and WithMin traits
Zero-allocation operations where possible
Optional serde feature for serialization/deserialization

§Construction

use ordmask::{OrdMask, ordmask};

// [0, 10), [20, 30) and [40, MAX]
let mask = ordmask![0, 10, 20, 30, 40];
assert!(mask.included(&5));
assert!(mask.excluded(&10));
assert!(mask.included(&50));

// Create from `Vec<T>`
assert_eq!(mask, OrdMask::from(vec![0, 10, 20, 30, 40]));

// Create from suspicious_points and a predicate
use std::collections::BTreeSet;
assert_eq!(mask, OrdMask::from_suspicious_points_set(
    BTreeSet::from([0, 10, 20, 30, 40]),
    |x| matches!(x, 0..10 | 20..30 | 40..),
    false
));

// Create from suspicious_points_map
use std::collections::BTreeMap;
let map = BTreeMap::from([(0, true), (10, false), (20, true), (30, false), (40, true)]);
assert_eq!(mask, OrdMask::from_suspicious_points_map(map, false));

// [MIN, 10)
let mask = ordmask![.., 10];
assert_eq!(mask, OrdMask::less_than(10));
assert!(mask.included(&9));
assert!(mask.excluded(&10));

// [10, MAX]
let mask = ordmask![10];
assert_eq!(mask, OrdMask::not_less_than(10));
assert!(mask.excluded(&9));
assert!(mask.included(&10));

// [10, 20)
let mask = ordmask![10, 20];
assert_eq!(mask, OrdMask::in_range(10, 20));
assert!(mask.included(&10));
assert!(mask.included(&15));
assert!(mask.excluded(&20));
assert!(mask.excluded(&25));

// Universal
let mask = ordmask![..];
assert_eq!(mask, OrdMask::universal());
assert!(mask.is_universal());
assert!(mask.included(&0));

// Empty
let mask = ordmask![];
assert_eq!(mask, OrdMask::empty());
assert!(mask.is_empty());
assert!(mask.excluded(&0));

§Type Annotation

You can specify the type explicitly using the <T> syntax in the macro:

use ordmask::{OrdMask, ordmask};

// Explicit type annotation with <T>
let mask = ordmask![<i64>];        // Empty
let mask = ordmask![<u8> ..];      // Universal
let mask = ordmask![<u64> 10];     // [10, MAX]
let mask = ordmask![<i32> 10, 20]; // [10, 20)
let mask = ordmask![<u32> .., 10]; // [MIN, 10)

§Union

use ordmask::{OrdMask, ordmask};

let a = ordmask![0, 15];
let b = ordmask![5, 20];
let c = ordmask![10, 30];
// &a | &b | &c: reference operators do not move (consume) the values
assert_eq!(&a | &b | &c, OrdMask::union(&[&a, &b, &c]));
// a | b | c: non-reference operators move (consume) the values
assert_eq!(a | b | c, ordmask![0, 30]);

§Intersection

use ordmask::{OrdMask, ordmask};

let a = ordmask![0, 15];
let b = ordmask![5, 20];
let c = ordmask![10, 30];
// &a & &b & &c: reference operators do not move (consume) the values
assert_eq!(&a & &b & &c, OrdMask::intersection(&[&a, &b, &c]));
// a & b & c: non-reference operators move (consume) the values
assert_eq!(a & b & c, ordmask![10, 15]);

§Minus and Complement

use ordmask::{OrdMask, ordmask};

let a = ordmask![0, 15];
let b = ordmask![5, 8];
let c = ordmask![10, 20];
// &a - &b - &c: reference operators do not move (consume) the values
assert_eq!(&a - &b - &c, OrdMask::minus(&a, &[&b, &c]));
// a - b - c: non-reference operators move (consume) the values
assert_eq!(a - b - c, ordmask![0, 5, 8, 10]);

let a = ordmask![0, 15];
// !&a: reference operator and `a.complement()` do not move (consume) the value
assert_eq!(!&a, a.complement());
// !a: non-reference operator and `a.to_complement()` move (consume) the value
assert_eq!(!a, ordmask![.., 0, 15]);

§Symmetric Difference

use ordmask::{OrdMask, ordmask};

let a = ordmask![0, 15];
let b = ordmask![5, 20];
// &a ^ &b: reference operators do not move (consume) the values
assert_eq!(&a ^ &b, OrdMask::symmetric_difference(&a, &b));
// a ^ b: non-reference operators move (consume) the values
assert_eq!(a ^ b, ordmask![0, 5, 15, 20]);

§Spans

OrdMask provides methods to iterate over included spans. Each span is returned as a tuple (start, end) representing a half-open interval [start, end).

Note:

Using spans requires type T to implement the WithMax trait (the library provides implementations for all standard integer types).

Since spans are half-open intervals [start, end), whether MAX is included can be confusing. Use .is_max_value_included() to check if the maximum value is in the mask.

§Basic Iteration

Use .spans() to iterate over included spans.

use ordmask::ordmask;

// Empty mask has no spans
assert_eq!(ordmask![<i32>].spans().collect::<Vec<_>>(), vec![]);

// Universal mask has one span [MIN, MAX]
assert_eq!(
    ordmask![..].spans().collect::<Vec<_>>(),
    vec![(i32::MIN, i32::MAX)]
);

// Single span [1, 2)
assert_eq!(ordmask![1, 2].spans().collect::<Vec<_>>(), vec![(1, 2)]);

// Multiple spans: [MIN, 1) and [2, MAX]
assert_eq!(
    ordmask![.., 1, 2].spans().collect::<Vec<_>>(),
    vec![(i32::MIN, 1), (2, i32::MAX)]
);

§Owning Iteration

Use .into_spans() to consume the mask and return an owning iterator:

use ordmask::ordmask;

assert_eq!(
    ordmask![.., 1, 2_i32].into_spans().collect::<Vec<_>>(),
    vec![(i32::MIN, 1), (2, i32::MAX)]
);

§Span Count and Values Count

Use .spans_count() to get the number of spans in O(1) time without consuming an iterator. It’s equivalent to .spans().count() but more efficient.

Use .values_count() to get the total count of included values. It supports lazy comparison without computing the full count.

use ordmask::ordmask;

// Span count
assert_eq!(ordmask![.., 10].spans_count(), 1);      // [MIN, 10)
assert_eq!(ordmask![.., 10, 20].spans_count(), 2);  // [MIN, 10), [20, MAX]
assert_eq!(ordmask![<u32>].spans_count(), 0);
assert_eq!(ordmask![<u32>..].spans_count(), 1);

// Values count (lazy comparison)
// [0, 10)
assert!(ordmask![<u32> .., 10].values_count() == 10);
// [0, 10), [20, MAX]
assert!(ordmask![<u32> .., 10, 20].values_count() == u32::MAX - 10 + 1);
// Empty mask has count 0
assert!(ordmask![<u32>].values_count() == 0);

Warning: Calling .values_count().get() may panic due to overflow when called on a universal mask (because MAX - MIN + 1 overflows). Use .is_universal() to check before calling .get(). However, lazy comparisons (e.g., values_count() < value) are safe because they can stop early without computing the full count.

§Value Iteration

Use .values() and .into_values() to iterate over individual included values (rather than spans).

Note: Value iteration requires type T to implement std::ops::Add<Output = T> and WithOne (in addition to WithMin and WithMax). The library provides implementations for all standard integer types.

use ordmask::ordmask;

// [1, 4) contains values 1, 2, 3
assert_eq!(ordmask![1, 4].values().collect::<Vec<_>>(), vec![1, 2, 3]);

// Multiple spans: [1, 3) and [5, 7)
assert_eq!(
    ordmask![1, 3, 5, 7].values().collect::<Vec<_>>(),
    vec![1, 2, 5, 6]
);

// Using into_iter() consumes the mask
assert_eq!(ordmask![1, 4].into_values().collect::<Vec<_>>(), vec![1, 2, 3]);

// For loop support
let mask = ordmask![1, 4];
let mut sum = 0;
for v in mask.values() {
    sum += v;
}
assert_eq!(sum, 6);

Warning: For large masks (e.g., universal mask), value iteration can produce a huge number of values. Use with caution.

§Type Requirements

OrdMask<T> requires T to implement the WithMin trait, a trait for types that have a minimum value. The library provides implementations for all standard integer types:

use ordmask::WithMin;

// Built-in implementations for:
// u8, u16, u32, u64, u128, usize
// i8, i16, i32, i64, i128, isize

assert_eq!(i32::MIN, <i32 as WithMin>::MIN);
assert_eq!(u64::MIN, <u64 as WithMin>::MIN);

To use custom types, at minimum, implement WithMin to use OrdMask. And then:

.spans_count() is already implemented
To use .spans() or .into_spans(), also implement WithMax
To use .values() or .into_values(), also implement:
To use .values_count(), also implement:
- WithMax
- OrderedSub<Target = COUNT>, and COUNT should implement:
  - WithZero
  - WithOne
  - std::ops::Add
  - [Optionally] PartialOrd to use comparison operators with COUNT

use ordmask::prelude::*;

#[derive(Clone, Ord, Debug, PartialOrd, Eq, PartialEq)]
struct MyType(i32);

// Required implementation. Enables `.spans_count()`.
impl WithMin for MyType {
    const MIN: Self = MyType(i32::MIN);
}

assert!(ordmask![..].included(&MyType(1)));

// Enables `.spans()` and `.into_spans()`.
impl WithMax for MyType {
    const MAX: Self = MyType(i32::MAX);
}

assert_eq!(
    ordmask![MyType(0), MyType(10)].spans().collect::<Vec<_>>(),
    vec![(MyType(0), MyType(10))]
);

// Enables `.values_count()` and comparison operators with `COUNT`.
impl OrderedSub for MyType {
    type Target = u32; // WithZero, WithOne, std::ops::Add, PartialOrd

    fn ordered_sub(&self, other: &Self) -> Self::Target {
        self.0.ordered_sub(&other.0) // Same as the library does for i32
    }
}

assert!(ordmask![MyType(0), MyType(10)].values_count() == 10);

// Enables `.values()` and `.into_values()`.
impl WithOne for MyType {
    const ONE: Self = MyType(1);
}

impl std::ops::Add for MyType {
    type Output = Self;

    fn add(self, other: Self) -> Self {
        Self(self.0 + other.0)
    }
}

assert_eq!(
    ordmask![MyType(0), MyType(3)].values().collect::<Vec<_>>(),
    vec![MyType(0), MyType(1), MyType(2)]
);

Modules§

iter: Module for efficiently iterating over the included spans and values of an OrdMask.
prelude: Commonly used types and traits.
utils: Utility functions

Macros§

ordmask: Create an OrdMask from key points.
ordmask_uncheck: Create an OrdMask from key points without validation.

Structs§

OrdMask: A mask for efficiently checking if a value is included.

Enums§

Error: Error for OrdMask.

Traits§

OrderedSub: A trait to provide a non-overflowing result of subtraction.
WithMax: A trait for types that have a maximum value.
WithMin: A trait for types that have a minimum value.
WithOne: A trait for types that have a one value.
WithZero: A trait for types that have a zero value.

Crate ordmask

Crate ordmask Copy item path

§Features

§Construction

§Type Annotation

§Union

§Intersection

§Minus and Complement

§Symmetric Difference

§Spans

§Basic Iteration

§Owning Iteration

§Span Count and Values Count

§Value Iteration

§Type Requirements

Modules§

Macros§

Structs§

Enums§

Traits§

Crate ordmask