irange: a Rust Library to Manipulate Ranges of Integers

2024-08-28 Dev

When I began developing RegexSolver, I faced a challenge: efficiently storing automata in memory.

Representing transitions as individual characters wasn't possible due to the performance requirements.

I needed to be able to store transitions conditions as sets of characters and perform set operations such as intersection, union, complement and difference. All of that efficiently with minimum memory footprint.

To address this challenge, I created a library called irange.

What is `irange`?

irange is a Rust library designed to manage and manipulate ranges of integers efficiently. It supports a wide range of integer types, including u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, and isize.

Here's how you can use irange to create and operate on range sets:

use irange::RangeSet;

// [ -32768..=-2 3..=4 5..=12 ]
let range1 = RangeSet::<i16>::new_from_ranges(&[
    AnyRange::from(3..=4),
    AnyRange::from(7..9),
    AnyRange::from(5..13),
    AnyRange::from(..-1)
]);

// [ -2..=4 ]
let range2 = RangeSet::<i16>::new_from_range(-2..=4);

 // [ -1..=2 5..=4 13..=32767 ]
println!("{}", range1.complement());

// [ -32768..=12 ]
println!("{}", range1.union(&range2));

// [ -2..=-2 3..=4 ]
println!("{}", range1.intersection(&range2));

// [ -32768..=-3 5..=12 ]
println!("{}", range1.difference(&range2));

Key Features

Efficient Storage: RangeSet is backed by a Vec where elements are stored in order with lower bounds at even indices and upper bounds at odd indices. This ensures no duplication of ranges or values, maintaining a minimal memory footprint.
Comprehensive Operations: irange supports a variety of set operations with optimal time and space complexity:

Operation	Time complexity	Space complexity
`union`	`O(n)`	`O(n)`
`intersection`	`O(n)`	`O(n)`
`difference`	`O(n)`	`O(n)`
`complement`	`O(n)`	`O(n)`
`has_intersection`	`O(n)`	`O(1)`
`contains`	`O(n)`	`O(1)`
`contains_all`	`O(n)`	`O(1)`
`is_total`	`O(1)`	`O(1)`
`is_empty`	`O(1)`	`O(1)`

Example Usage

use irange::RangeSet;

let range1 = RangeSet::<i64>::new_from_range(123..);
let range2 = RangeSet::<i64>::new_from_range(..134);

let range3 = RangeSet::<i64>::new_from_range(12..=32);

// false
println!("{}", range1.contains_all(&range3));

// true
println!("{}", range2.contains_all(&range3));

// true
println!("{}", range1.intersection(&range3).is_empty());

// true
println!("{}", range1.union(&range2).is_total());

Get Started

If you're interested in integrating irange into your project, you can find it on crates.io and view the full documentation here.

Contribute