2 unstable releases
0.2.0 | Dec 5, 2024 |
---|---|
0.1.0 | Dec 5, 2024 |
#402 in Data structures
1,168 downloads per month
66KB
1.5K
SLoC
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
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.