span-map

Map span of scalar value to some data.

A data structure that maps spans (ranges) of scalar values to sets of data. Each span represents an interval with start and end bounds, which can be inclusive, exclusive, or unbounded.

Features

Support for inclusive, exclusive and unbounded bounds
Efficient range queries
Support for overlapping spans
Generic over key and value types
Thread-safe with standard Rust thread safety guarantees

Usage

use span_map::SpanMap;

let mut map = SpanMap::<i32, String>::new();

// Map span (-∞, 5] to "a"
map.insert(..=5, "a".to_string());

// Map span [3, 7) to "b"
map.insert(3..7, "b".to_string());

// Get values at point 4
let values: Vec<_> = map.get(&4).collect();
assert_eq!(values, vec!["a", "b"]); // Point 4 is in both spans

Performance

Benchmark results showing performance for different usage patterns:

SpanMap::get/single_range
                        time:   [5.8936 ns 5.9107 ns 5.9278 ns]

SpanMap::get/overlapping_ranges_10_overlapping
                        time:   [9.2159 ns 9.2476 ns 9.2822 ns]

SpanMap::get/large_value_set_100_overlapping
                        time:   [72.247 ns 72.636 ns 73.081 ns]

SpanMap::get/many_ranges_1000_no_overlapping
                        time:   [24.023 ns 24.108 ns 24.196 ns]

SpanMap::get/string_keys_1_overlapping
                        time:   [31.465 ns 31.503 ns 31.543 ns]

SpanMap::get/worst_case_1000_overlapping
                        time:   [743.59 ns 747.56 ns 752.72 ns]

License

Licensed under either of

Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution