# OrdMask
[> Chinese Version: 中文文档](README_CN.md)
`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
```rust
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:
```rust
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
```rust
use ordmask::{OrdMask, ordmask};
let a = ordmask![0, 15];
let b = ordmask![5, 20];
let c = ordmask![10, 30];
// a | b | c: non-reference operators move (consume) the values
assert_eq!(a | b | c, ordmask![0, 30]);
```
## Intersection
```rust
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
```rust
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
```rust
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.
```rust
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:
```rust
use ordmask::ordmask;
assert_eq!(
ordmask![.., 1, 2_i32].into_spans().collect::<Vec<_>>(),
vec![(i32::MIN, 1), (2, i32::MAX)]
);
```
### Span Count and Size
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.
```rust
use ordmask::{ordmask, spans::SumSize};
// 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);
// Sum of span sizes
// [0, 10)
assert_eq!(ordmask![<u32> .., 10].spans().sum_size(), 10);
// [0, 10), [20, MAX]
assert_eq!(ordmask![<u32> .., 10, 20].spans().sum_size(), u32::MAX - 10 + 1);
// Empty mask has size 0
assert_eq!(ordmask![<u32>].spans().sum_size(), 0);
```
> **Warning**: `.spans().sum_size()` may panic due to overflow when called on a universal mask (because `MAX - MIN + 1` overflows). Use `.is_universal()` to check before calling this.
## 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:
```rust
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`
- To use `.spans()` or `.into_spans()`, also implement `WithMax`
- To use `.spans().sum_size()`, also implement `OrderedSub`
> **Note**: `spans_count()` is special—it only requires `WithMin`, not `WithMax`.
```rust
use ordmask::{OrderedSub, WithMax, WithMin, ordmask, spans::SumSize};
#[derive(Clone, Debug, Ord, PartialOrd, Eq, PartialEq)]
struct MyType(i32);
// Required implementation, Enables `.spans_count()`
impl WithMin for MyType {
const MIN: Self = MyType(i32::MIN);
}
// Enables `.spans()`, `.into_spans()`
impl WithMax for MyType {
const MAX: Self = MyType(i32::MAX);
}
// Enables `.spans().sum_size()`
impl OrderedSub for MyType {
type Target = u32;
fn ordered_sub(&self, other: &Self) -> Self::Target {
self.0.ordered_sub(&other.0) // Same as the library does for i32
}
}
assert!(ordmask![..].included(&MyType(1)));
assert_eq!(ordmask![MyType(0), MyType(10)].spans().sum_size(), 10);
```