#spans #range #map #interval #key-value

span-map

A data structure for efficiently managing sets of values over spans/ranges

2 unstable releases

0.2.0 Dec 5, 2024
0.1.0 Dec 5, 2024

#402 in Data structures

Download history 376/week @ 2024-12-02 792/week @ 2024-12-09

1,168 downloads per month

MIT/Apache

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

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.

No runtime deps