range-set-blaze

Integer sets as fast, sorted integer ranges; Maps with integer-range keys; Full set operations

• Supports all of Rust's integer-like types, u8 to u128, i8 to i128, char (Unicode characters), Ipv4Addr, and Ipv6Addr. Also supports floating-point ranges for f32 and f64 through the NotNanF32, NotNanF64, TotalF32, and TotalF64 wrappers.
• union, intersection, difference, symmetric difference, and complement—available on both sets and maps.
• Can also work directly with ranges and gaps, not just individual integer-like values.
• Joins (inner, left, and full, two-way and multiway) combine the values of range maps by key.

The crate's main structs are:

• RangeSetBlaze, a set of integers. See the set documentation for details.
• RangeMapBlaze, a map from integers to values. See the map documentation for details.

For a side-by-side introduction to range lookups and gap filling for both containers, see the Ranges and gaps guide.

Unlike the standard BTreeSet/BTreeMap and HashSet/HashMap, RangeSetBlaze does not store every integer in the set. Rather, it stores sorted & disjoint ranges of integers in a cache-efficient BTreeMap. It differs from other interval libraries -- that we know of -- by offering full set operations and by being optimized for sets of clumpy integers.

We can construct a RangeSetBlaze or RangeMapBlaze from unsorted & redundant integers (or ranges). When the inputs are clumpy, construction will be linear in the number of inputs and set operations will be sped up quadratically.

⚠️ Warning: All RangeMapBlaze operations (into_iter, union, difference, symmetric difference, etc.) now give precedence to the right-hand map when ranges overlap. This change (from version 0.2.0) aligns with the behavior of BTreeMap and HashMap.

The crate's main traits are

• SortedDisjoint, implemented by iterators of sorted & disjoint ranges of integers. See documentation for details.
• SortedDisjointMap, implemented by iterators of pairs, where the first item is a sorted & disjoint range of integers. The second item is a value. See documentation for details.

With any SortedDisjoint or SortedDisjointMap iterator we can perform set operations in one pass through the ranges and with minimal (constant) memory. The package enforces the "sorted & disjoint" constraint at compile time (making invalid states unrepresentable).

no_std, WASM, and embedded

The crate supports no_std, WASM, and embedded (with alloc) projects. For no_std, etc., Use the command:

cargo add range-set-blaze --no-default-features

Benchmarks

See the set benchmarks and map benchmarks for performance comparisons with other range-related crates.

Generally, for many tasks involving clumpy integers and ranges, RangeSetBlaze is much faster than alternatives.

The benchmarks are in the benches directory. To run them, use cargo bench.

Articles

• Nine Rules for Creating Fast, Safe, and Compatible Data Structures in Rust: Lessons from RangeSetBlaze in Towards Data Science. It provides a high-level overview of the crate and its design.

• Nine Rules for Running Rust on the Web and on Embedded: Practical Lessons from Porting range-set-blaze to no_std and WASM in Towards Data Science. It covers porting to "no_std".

• Check AI-Generated Code Perfectly and Automatically My Experience Applying Kani’s Formal Verification to ChatGPT-Suggested Rust Code. Shows how to prove overflow safety.

• Nine Rules to Formally Validate Rust Algorithms with Dafny in Towards Data Science. It shows how to formally validate one of the crate's algorithms.

• Nine Rules for SIMD Acceleration of your Rust Code: General Lessons from Boosting Data Ingestion in the range-set-blaze Crate by 7x in Towards Data Science

• Also see: CHANGELOG and the release checklist

Examples

Example 1: Set Operations

---

Here we take the union (operator “|”) of two RangeSetBlaze's:

use range_set_blaze::prelude::*;

 // a is the set of integers from 100 to 499 (inclusive) and 501 to 1000 (inclusive)
let a = RangeSetBlaze::from_iter([100..=499, 501..=999]);
 // b is the set of integers -20 and the range 400 to 599 (inclusive)
let b = RangeSetBlaze::from_iter([-20..=-20, 400..=599]);
// c is the union of a and b, namely -20 and 100 to 999 (inclusive)
let c = a | b;
assert_eq!(c, RangeSetBlaze::from_iter([-20..=-20, 100..=999]));

Example 2: Maps (and Network Addresses)

---

In networking, we can use RangeMapBlaze to visualize routing tables. It efficiently merges adjacent or overlapping routes with identical next-hops, removes overlaps (respecting priority), and provides fast lookups. While specialized prefix trees (tries) are typically used in production routers for maximum efficiency, this example shows how RangeMapBlaze makes the information more understandable. Similar concepts apply when working with other range-mappings like font tables.

use range_set_blaze::prelude::*;
use std::net::Ipv4Addr;

// A routing table, sorted by prefix length (so, highest priority last)
let routing = [
    // destination, prefix, next hop, interface
    ("0.0.0.0", 0, "152.10.0.0", "eth0"),
    ("10.0.0.0", 8, "10.3.4.2", "eth1"),
    ("10.0.1.12", 30, "10.1.1.0", "eth2"),
    ("10.0.1.8", 30, "10.1.1.0", "eth2"),
    ("10.0.1.7", 32, "10.1.1.0", "eth2"),
];

// Create a RangeMapBlaze from the routing table
let range_map = routing
    .iter()
    .map(|(dest, prefix_len, next_hop, interface)| {
        let dest: Ipv4Addr = dest.parse().unwrap();
        let next_hop: Ipv4Addr = next_hop.parse().unwrap();
        let mask = u32::MAX.checked_shr(*prefix_len).unwrap_or(0);
        let range_start = Ipv4Addr::from(u32::from(dest) & !mask);
        let range_end = Ipv4Addr::from(u32::from(dest) | mask);
        (range_start..=range_end, (next_hop, interface))
    })
    .collect::<RangeMapBlaze<_, _>>();

// Print the now disjoint, sorted ranges and their associated values
for (range, (next_hop, interface)) in range_map.range_values() {
    println!("{range:?} → ({next_hop}, {interface})");
}

// Look up an address
assert_eq!(
    range_map.get(Ipv4Addr::new(10, 0, 1, 6)),
    Some(&(Ipv4Addr::new(10, 3, 4, 2), &"eth1"))
);

Output:

0.0.0.0..=9.255.255.255 → (152.10.0.0, eth0)
10.0.0.0..=10.0.1.6 → (10.3.4.2, eth1)
10.0.1.7..=10.0.1.15 → (10.1.1.0, eth2)
10.0.1.16..=10.255.255.255 → (10.3.4.2, eth1)
11.0.0.0..=255.255.255.255 → (152.10.0.0, eth0)

Example 3: Biology

---

In biology, suppose we want to find the intron regions of a gene but we are given only the transcription region and the exon regions.

We create a RangeSetBlaze for the transcription region and a RangeSetBlaze for all the exon regions. Then we take the difference between the transcription region and exon regions to find the intron regions.

use range_set_blaze::prelude::*;

let line = "chr15   29370   37380   29370,32358,36715   30817,32561,37380";

// split the line on white space
let mut iter = line.split_whitespace();
let chrom = iter.next().unwrap();

// Parse the start and end of the transcription region into a RangeSetBlaze
let trans_start: i32 = iter.next().unwrap().parse().unwrap();
let trans_end: i32 = iter.next().unwrap().parse().unwrap();
let trans = RangeSetBlaze::from_iter([trans_start..=trans_end]);
assert_eq!(trans, RangeSetBlaze::from_iter([29370..=37380]));

// Parse the start and end of the exons into a RangeSetBlaze
let exon_starts = iter.next().unwrap().split(',').map(|s| s.parse::<i32>());
let exon_ends = iter.next().unwrap().split(',').map(|s| s.parse::<i32>());
let exon_ranges = exon_starts
    .zip(exon_ends)
    .map(|(s, e)| s.unwrap()..=e.unwrap());
let exons = RangeSetBlaze::from_iter(exon_ranges);
assert_eq!(exons, RangeSetBlaze::from_iter([29370..=30817, 32358..=32561, 36715..=37380]));

// Use 'set difference' to find the introns
let intron = trans - exons;
assert_eq!(intron, RangeSetBlaze::from_iter([30818..=32357, 32562..=36714]));
for range in intron.ranges() {
    let (start, end) = range.into_inner();
    println!("{chrom}\t{start}\t{end}");
}

Cargo Features

The available Cargo features are:

• default — Enables the std feature. Use --no-default-features for a no_std build.
• std — Enables std-specific conveniences and trait implementations. The crate's core functionality remains available with no_std and alloc; see the no_std usage above.
• cursor_nightly_experimental — Uses Rust's (nightly-only) B-tree cursor API to speed up insert/ranges_insert on both RangeSetBlaze (roughly 1.8x–2.2x, geometric mean ~2.0x) and RangeMapBlaze (roughly 1.5x–2.1x, geometric mean ~1.7x). Same public API.
• from_slice — Enables the nightly-only RangeSetBlaze::from_slice constructor, which can speed up construction from array-like collections using SIMD where available.
• float_nightly_experimental — Enables the nightly-only f16 and f128 floating-point wrappers; see the floating-point module documentation. This requires a nightly Rust compiler.
• test_util — Test/benchmark helpers used internally by the crate; not needed by downstream users.

The published API documentation includes all optional features. Feature-gated items are marked with the feature required to use them; optional features are not enabled by default for users of the crate.

Contributing

Contributions are welcome! For development workflow, local testing, and CI information, see the contribution guide.

Quick start for developers:

# Install just task runner
cargo install just

# Run all checks before pushing
just check-all

See just --list for all available development commands (defined in justfile).

Policy on AI-assisted development and contributions

The use of AI tools is permitted for development and contributions to this repository. AI may be used as a productivity aid for drafting, exploration, and refactoring.

All code and documentation contributed to this repository must be reviewed, edited, and validated by a human contributor. AI tools are not a substitute for design judgment, testing, or responsibility for correctness.

AGENTS.md contains the general instructions and constraints given to AI tools used during development of this repository.