Lib.rs

此 crate 实现了具有区间键（范围 x..y）的映射和集合。 IntervalMap 使用红黑二叉树实现，其中每个节点包含其子树中最小起始和最大结束的信息。该树占用 O(N) 空间，并允许以 O(log N) 的时间进行插入、删除和搜索。 IntervalMap 允许以 O(log N + K) 的时间搜索所有与查询（区间或点）重叠的条目（输出按键排序），其中 K 是输出的大小。

IntervalSet 是一个在 IntervalMap 上定义的新类型，具有空值。

使用方法

以下代码构建了一个小型的区间映射并搜索与各种查询重叠的区间/值。

use iset::interval_map;

let mut map = interval_map!{ 20..30 => 'a', 15..25 => 'b', 10..20 => 'c' };
assert_eq!(map.insert(10..20, 'd'), Some('c'));
assert_eq!(map.insert(5..15, 'e'), None);

// Iterator over all pairs (range, value). Output is sorted.
let a: Vec<_> = map.iter(..).collect();
assert_eq!(a, &[(5..15, &'e'), (10..20, &'d'), (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, &[5..15, 10..20, 15..25]);

assert_eq!(map[15..25], 'b');
// Replace 15..25 => 'b' into 'z'.
*map.get_mut(15..25).unwrap() = 'z';

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

// Remove 10..20 => 'd'.
assert_eq!(map.remove(10..20), Some('d'));

println!("{:?}", map);
// {5..15 => 'e', 15..25 => 'z', 20..30 => 'a'}

更多详细的使用方法请在此找到。

变更日志

请在此找到变更日志。

问题

请在此提交问题或将它们发送到 timofey.prodanov[at]gmail.com。