6 releases

Uses new Rust 2021

new 0.3.0 May 12, 2022
0.2.6 May 11, 2022
0.2.5 Mar 30, 2022
0.1.0 Mar 29, 2022

#394 in Data structures

Download history 132/week @ 2022-03-27 24/week @ 2022-04-03 5/week @ 2022-04-10 3/week @ 2022-04-17 7/week @ 2022-04-24 16/week @ 2022-05-01 68/week @ 2022-05-08

94 downloads per month

MIT/Apache

90KB
2.5K SLoC

B-Tree range map

CI Crate informations License Documentation

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

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.

Dependencies

~390KB