static_mapset/lib.rs
1//! This crate provides ordered maps and sets backed by sorted arrays or slices.
2//!
3//! The crate provides five structures with different internal data types and map/set distinctions:
4//!
5//! - [`OrderedArrayMap`] — owned fixed-size array-backed map
6//! - [`OrderedArraySet`] — owned fixed-size array-backed set
7//! - [`OrderedSliceMap`] — borrowed sorted slice-backed read-only map
8//! - [`OrderedSliceMapMut`] — borrowed sorted slice-backed map with mutable values
9//! - [`OrderedSliceSet`] — borrowed sorted slice-backed read-only set
10//!
11//! These structures provide a subset of the methods offered by the standard library's
12//! `BTreeMap` and `BTreeSet`. They use binary search for element lookup, resulting in
13//! logarithmic time complexity for most methods relative to the number of elements.
14//!
15//! The current version does not provide methods that change the size (such as `append` or `remove`).
16//! (no_std developers may need these. If you do, please let us know.)
17//!
18//! # Features
19//!
20//! ## Compile-time constants
21//!
22//! Each structure provides a `const` function called `new_unchecked`. This function takes a
23//! sorted array or slice as an argument and returns a map or set. It is the programmer's
24//! responsibility to ensure the input is sorted.
25//!
26//! Since `new_unchecked` is a `const` function, it can be used in compile-time constant definitions.
27//!
28//! ## no_std support
29//!
30//! The structures in this crate hold only arrays or slices as internal state.
31//! They work in `no_std` environments since they do not allocate memory dynamically.
32//!
33//! ## Support for `PartialOrd`
34//!
35//! The `new_unchecked` function assumes the programmer guarantees that the input is sorted
36//! (including that it contains no incomparable values like `f64::NAN`). This allows you to
37//! create maps and sets of types without a total order, such as `f32` and `f64`.
38//!
39//! Methods other than `new_unchecked` treat incomparable values as greater than all other values.
40//! Therefore, behavior is well-defined when incomparable values are passed to any method.
41//! Refer to the description of each method for details.
42//!
43//! ## Correspondence with the standard library
44//!
45//! Methods in these structures that share names with `BTreeMap` or `BTreeSet` in the standard
46//! library behave identically. Even for methods that return iterators, the returned iterator
47//! enumerates the same values.
48//!
49//! # Example
50//!
51//! ```
52//! use std::ops::Bound;
53//! use static_mapset::OrderedArrayMap;
54//!
55//! static MONTHS: OrderedArrayMap<i32, &str, 12> = OrderedArrayMap::new_unchecked([
56//! (31, "January"), (59, "February"), (90, "March"),
57//! (120, "April"), (151, "May"), (181, "June"),
58//! (212, "July"), (243, "August"), (273, "September"),
59//! (304, "October"), (334, "November"), (365, "December")
60//! ]);
61//!
62//! fn main() {
63//! println!(
64//! "The 200th day of a year is on {}.",
65//! MONTHS.upper_bound(Bound::Excluded(&200)).next().unwrap().1);
66//! }
67//!
68//! #[cfg(test)]
69//! mod tests {
70//! use super::*;
71//!
72//! #[test]
73//! fn test_order_of_month() {
74//! // You can use `is_valid` method for unit testing.
75//! assert!(MONTHS.is_valid(), "MONTHS is not ordered correctly");
76//! }
77//! }
78//! ```
79//!
80//! # Compatibility
81//!
82//! Except for `is_valid` method, the behavior when `new_unchecked` receives
83//! an unsorted collection is undefined. We do not plan to maintain compatibility in this case.
84//!
85//! # Copyright Notice
86//!
87//! The APIs of the types provided by this crate are modelled after Rust's `BTreeMap` and `BTreeSet`.
88//! Consequently, the documentation and tests of this crate incorporate work from the Rust standard library.
89//!
90//! > Copyright (c) The Rust Project Contributors
91//! >
92//! > Permission is hereby granted, free of charge, to any
93//! > person obtaining a copy of this software and associated
94//! > documentation files (the "Software"), to deal in the
95//! > Software without restriction, including without
96//! > limitation the rights to use, copy, modify, merge,
97//! > publish, distribute, sublicense, and/or sell copies of
98//! > the Software, and to permit persons to whom the Software
99//! > is furnished to do so, subject to the following
100//! > conditions:
101//! >
102//! > The above copyright notice and this permission notice
103//! > shall be included in all copies or substantial portions
104//! > of the Software.
105//! >
106//! > THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
107//! > ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
108//! > TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
109//! > PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
110//! > SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
111//! > CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
112//! > OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
113//! > IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
114//! > DEALINGS IN THE SOFTWARE.
115
116mod internal;
117pub mod ordered;
118pub mod ordered_array_map;
119pub mod ordered_array_set;
120pub mod ordered_slice_map;
121pub mod ordered_slice_map_mut;
122pub mod ordered_slice_set;
123
124pub use ordered_array_map::OrderedArrayMap;
125pub use ordered_array_set::OrderedArraySet;
126pub use ordered_slice_map::OrderedSliceMap;
127pub use ordered_slice_map_mut::OrderedSliceMapMut;
128pub use ordered_slice_set::OrderedSliceSet;