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