B-Tree range map

A range map is a map where keys are aggregated into ranges of keys for efficient storage. Every time you need to store a large number numeric-keyed items in a map or set, a range map (or range set) should be used.

This library provides a range map implementation based on btree-slab's B-tree. It defines three basic types RangeSet<T>, RangeMap<K, V> and RangeMultiMap<K, S>.

Usage

The RangeSet<T> and RangeMap<K, V> behave similarly to the standard BTreeSet<T> and BTreeMap<K, V> types. However in addition to PartialOrd, the key type must also implement the Measure trait defining how keys are merged into ranges. This trait is implemented by default for char, integer types and float types.

use btree_range_map::RangeMap;

let mut range_map: RangeMap<i32, bool> = RangeMap::new();
range_map.insert(00..=05, true);
range_map.insert(4, false);
assert_eq!(range_map.range_count(), 3);
assert_eq!(range_map.get(03), Some(&true));
assert_eq!(range_map.get(04), Some(&false));
assert_eq!(range_map.get(05), Some(&true));

This library supports included and excluded bounds:

range_map.insert(..1, true);
range_map.insert(..=1, true);
range_map.insert(2, true);
range_map.insert(3..5, true);
range_map.insert(5..=7, true);
range_map.insert(7.., true);
assert_eq!(range_map.range_count(), 1);

It also supports non standard ranges with excluded start bounds:

use btree_range_map::{
  RangeFromExcluded,
  RangeFromExcludedTo,
  RangeFromExcludedToIncluded
};

// same as       `4..`
range_map.insert(RangeFromExcluded::new(3), true);

// same as       `3`
range_map.insert(RangeFromExcludedTo::new(2, 4), true);

// same as       `1..=2`
range_map.insert(RangeFromExcludedToIncluded::new(0, 2), true);

assert_eq!(range_map.range_count(), 1);

Floats

Floating point numbers f32 and f64 are handled as one might expect.

use btree_range_map::{RangeMap, RangeFromExcluded};
let mut range_map: RangeMap<f32, bool> = RangeMap::new();

// sets all `f32` below zero to `false`.
range_map.insert(..0.0, false);

// sets all `f32` above zero to `true`.
range_map.insert(RangeFromExcluded::new(0.0), true);

assert_eq!(range_map.range_count(), 2);
assert_eq!(range_map.get(0.0), None); // only `0.0` is unmapped.

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.