Crate rb_interval_map

interval_map is a thread-safe map based on interval tree.

It fully implements the insertion and deletion functionality of a red-black tree, ensuring that each modification operation requires at most O(logN) time complexity.

To safely and efficiently handle insertion and deletion operations in Rust, interval_map innovatively uses arrays to simulate pointers for managing the parent-child references in the red-black tree. This approach also ensures that interval_map has the Send and Unpin traits, allowing it to be safely transferred between threads and to maintain a fixed memory location during asynchronous operations.

Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
let int = Interval::new(1, 2);
map.insert(int.clone(), 123456);
assert_eq!(map.get(&int), Some(&123456));

Structs

FilterIter

A filter iterator over the entries of a IntervalMap.It’s equal to iter().filter() but faster than the latter.

Interval

The interval stored in IntervalMap represents [low, high)

IntervalMap

An interval-value map, which support operations on dynamic sets of intervals.

IntoIter

An into iterator over the entries of a IntervalMap.

Iter

An iterator over the entries of a IntervalMap.

OccupiedEntry

A view into an occupied entry in a IntervalMap. It is part of the Entry enum.

UnsortedIter

An unsorted iterator over the entries of a IntervalMap.

VacantEntry

A view into a vacant entry in a IntervalMap. It is part of the Entry enum.

Enums

Entry

A view into a single entry in a map, which may either be vacant or occupied.