5 releases

new 0.0.5 Jun 18, 2021
0.0.4 Jun 9, 2021
0.0.3 Mar 20, 2020
0.0.2 Mar 18, 2020
0.0.1 Mar 17, 2020

#114 in Data structures

Download history 327/week @ 2021-02-25 591/week @ 2021-03-04 468/week @ 2021-03-11 276/week @ 2021-03-18 352/week @ 2021-03-25 269/week @ 2021-04-01 293/week @ 2021-04-08 135/week @ 2021-04-15 209/week @ 2021-04-22 129/week @ 2021-04-29 90/week @ 2021-05-06 175/week @ 2021-05-13 389/week @ 2021-05-20 425/week @ 2021-05-27 463/week @ 2021-06-03 497/week @ 2021-06-10

1,231 downloads per month

MIT license

63KB
1.5K SLoC

This crates implements map and set with interval keys (ranges x..y).

IntervalMap is implemented using red-black binary tree, where each node contains information about the smallest start and largest end in its subtree. The tree takes O(N) space and allows insertion in O(log N). IntervalMap allows to search for all entries overlapping a query (interval or a point, output would be sorted by keys). Search takes O(log N + K) where K is the size of the output. Additionally, you can extract smallest/largest interval with its value in O(log N).

IntervalSet is a newtype over IntervalMap with empty values.

Any iterator that goes over the IntervalMap or IntervalSet returns intervals/values sorted lexicographically by intervals.

Usage

The following code constructs a small interval map and search for intervals/values overlapping various queries.

let mut map = iset::IntervalMap::new();
map.insert(20..30, "a");
map.insert(15..25, "b");
map.insert(10..20, "c");

// Iterate over (interval, &value) pairs that overlap query (.. here).
// Output is sorted by intervals.
let a: Vec<_> = map.iter(..).collect();
assert_eq!(a, &[(10..20, &"c"), (15..25, &"b"), (20..30, &"a")]);

// Iterate over intervals that overlap query (..20 here). Output is sorted.
let b: Vec<_> = map.intervals(..20).collect();
assert_eq!(b, &[10..20, 15..25]);

// Iterate over values that overlap query (20.. here). Output is sorted by intervals.
let c: Vec<_> = map.values(20..).collect();
assert_eq!(c, &[&"b", &"a"]);

println!("{:?}", map);
// {10..20: "c", 15..25: "b", 20..30: "a"}

You can find more detailed usage here.

Future features:

  • Remove intervals from IntervalMap and IntervalSet.
  • Get all (interval, value) pairs by exact match with the query.
  • Join two maps/sets, split map/set into two.

Changelog

You can find changelog here.

Issues

Please submit issues here or send them to timofey.prodanov[at]gmail.com.

Dependencies

~77–285KB