OrdMask

> Chinese Version: 中文文档

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:
  • WithMax
  • WithOne
  • std::ops::Add
• 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)]
);