btree_range_map/
lib.rs

1//! A *range map* is a map where keys are aggregated into ranges of keys for
2//! efficient storage. Every time you need to store a large number numeric-keyed
3//! items in a map or set, a range map (or range set) should be used.
4//!
5//! This library provides a range map implementation based on
6//! [`btree-slab`](https://crates.io/crates/btree-slab)'s B-tree.
7//! It defines three basic types `RangeSet<T>`, `RangeMap<K, V>` and
8//! `RangeMultiMap<K, S>`.
9//!
10//! ## Usage
11//!
12//! The `RangeSet<T>` and `RangeMap<K, V>` behave similarly to the standard
13//! `BTreeSet<T>` and `BTreeMap<K, V>` types.
14//! However in addition to `PartialOrd`, the key type must also implement the
15//! `Measure` trait defining how keys are merged into ranges.
16//! This trait is implemented by default for `char`, integer types and float
17//! types.
18//!
19//! ```
20//! use btree_range_map::RangeMap;
21//!
22//! let mut range_map: RangeMap<i32, bool> = RangeMap::new();
23//! range_map.insert(00..=05, true);
24//! range_map.insert(4, false);
25//! assert_eq!(range_map.range_count(), 3);
26//! assert_eq!(range_map.get(03), Some(&true));
27//! assert_eq!(range_map.get(04), Some(&false));
28//! assert_eq!(range_map.get(05), Some(&true));
29//! ```
30//!
31//! This library supports included and excluded bounds:
32//!
33//! ```
34//! # use btree_range_map::RangeMap;
35//! # let mut range_map: RangeMap<i32, bool> = RangeMap::new();
36//! range_map.insert(..1, true);
37//! range_map.insert(..=1, true);
38//! range_map.insert(2, true);
39//! range_map.insert(3..5, true);
40//! range_map.insert(5..=7, true);
41//! range_map.insert(7.., true);
42//! assert_eq!(range_map.range_count(), 1);
43//! ```
44//!
45//! It also supports non standard ranges with excluded start bounds:
46//!
47//! ```
48//! # use btree_range_map::RangeMap;
49//! # let mut range_map: RangeMap<i32, bool> = RangeMap::new();
50//! use btree_range_map::{
51//!   RangeFromExcluded,
52//!   RangeFromExcludedTo,
53//!   RangeFromExcludedToIncluded
54//! };
55//!
56//! // same as       `4..`
57//! range_map.insert(RangeFromExcluded::new(3), true);
58//!
59//! // same as       `3`
60//! range_map.insert(RangeFromExcludedTo::new(2, 4), true);
61//!
62//! // same as       `1..=2`
63//! range_map.insert(RangeFromExcludedToIncluded::new(0, 2), true);
64//!
65//! assert_eq!(range_map.range_count(), 1);
66//! ```
67//!
68//! ### Floats
69//!
70//! Floating point numbers `f32` and `f64` are handled as one might expect.
71//!
72//! ```
73//! use btree_range_map::{RangeMap, RangeFromExcluded};
74//! let mut range_map: RangeMap<f32, bool> = RangeMap::new();
75//!
76//! // sets all `f32` below zero to `false`.
77//! range_map.insert(..0.0, false);
78//!
79//! // sets all `f32` above zero to `true`.
80//! range_map.insert(RangeFromExcluded::new(0.0), true);
81//!
82//! assert_eq!(range_map.range_count(), 2);
83//! assert_eq!(range_map.get(0.0), None); // only `0.0` is unmapped.
84//! ```
85pub mod generic;
86mod range;
87
88#[cfg(feature = "serde")]
89mod serde;
90
91pub use range::*;
92
93pub type DefaultSetContainer<K> = slab::Slab<generic::Node<AnyRange<K>, ()>>;
94pub type DefaultMapContainer<K, V> = slab::Slab<generic::Node<AnyRange<K>, V>>;
95
96pub type RangeSet<K> = generic::RangeSet<K, DefaultSetContainer<K>>;
97pub type RangeMap<K, V> = generic::RangeMap<K, V, DefaultMapContainer<K, V>>;
98pub type RangeMultiMap<K, S> = generic::RangeMultiMap<K, S, DefaultMapContainer<K, S>>;
btree_range_map/lib.rs

btree_range_map/
lib.rs
