# 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 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.
```rust
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.
```rust
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:
```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`. 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`
```rust
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)]
);
```