Skip to main content

static_mapset/
ordered_array_map.rs

1use core::{
2	array,
3	borrow::Borrow,
4	iter::FusedIterator,
5	ops::{Bound, Index, RangeBounds}
6};
7
8use crate::internal::ordered_map::{self as internal, order};
9
10/// An iterator over the entries of a `OrderedArrayMap`.
11///
12/// This `struct` is created by the [`iter`] method on [`OrderedArrayMap`]. See its
13/// documentation for more.
14///
15/// [`iter`]: OrderedArrayMap::iter
16pub type Iter<'a, K, V> = internal::Iter<'a, K, V>;
17
18/// An iterator over the keys of a `OrderedArrayMap`.
19///
20/// This `struct` is created by the [`keys`] method on [`OrderedArrayMap`]. See its
21/// documentation for more.
22///
23/// [`keys`]: OrderedArrayMap::keys
24pub type Keys<'a, K, V> = internal::Keys<'a, K, V>;
25
26/// An iterator over a sub-range of entries in a `OrderedArrayMap`.
27///
28/// This `struct` is created by the [`range`] method on [`OrderedArrayMap`]. See its
29/// documentation for more.
30///
31/// [`range`]: OrderedArrayMap::range
32pub type Range<'a, K, V> = internal::Iter<'a, K, V>;
33
34/// An iterator over the values of a `OrderedArrayMap`.
35///
36/// This `struct` is created by the [`values`] method on [`OrderedArrayMap`]. See its
37/// documentation for more.
38///
39/// [`values`]: OrderedArrayMap::values
40pub type Values<'a, K, V> = internal::Values<'a, K, V>;
41
42/// A cursor over a `OrderedArrayMap`.
43///
44/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
45///
46/// Cursors always point to a gap between two elements in the map, and can
47/// operate on the two immediately adjacent elements.
48///
49/// A `Cursor` is created with the [`OrderedArrayMap::lower_bound`] and [`OrderedArrayMap::upper_bound`] methods.
50pub type Cursor<'a, K, V> = internal::Cursor<'a, K, V>;
51
52/// A mutable iterator over the entries of a `OrderedArrayMap`.
53///
54/// This `struct` is created by the [`iter_mut`] method on [`OrderedArrayMap`]. See its
55/// documentation for more.
56///
57/// [`iter_mut`]: OrderedArrayMap::iter_mut
58pub type IterMut<'a, K, V> = internal::IterMut<'a, K, V>;
59
60/// A mutable iterator over a sub-range of entries in a `OrderedArrayMap`.
61///
62/// This `struct` is created by the [`range_mut`] method on [`OrderedArrayMap`]. See its
63/// documentation for more.
64///
65/// [`range_mut`]: OrderedArrayMap::range_mut
66pub type RangeMut<'a, K, V> = internal::IterMut<'a, K, V>;
67
68/// A mutable iterator over the values of a `OrderedArrayMap`.
69///
70/// This `struct` is created by the [`values_mut`] method on [`OrderedArrayMap`]. See its
71/// documentation for more.
72///
73/// [`values_mut`]: OrderedArrayMap::values_mut
74pub type ValuesMut<'a, K, V> = internal::ValuesMut<'a, K, V>;
75
76/// A cursor over a `OrderedArrayMap` with editing operations.
77///
78/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
79/// safely mutate the map during iteration. This is because the lifetime of its yielded
80/// references is tied to its own lifetime, instead of just the underlying map. This means
81/// cursors cannot yield multiple elements at once.
82///
83/// Cursors always point to a gap between two elements in the map, and can
84/// operate on the two immediately adjacent elements.
85///
86/// A `CursorMut` is created with the [`OrderedArrayMap::lower_bound_mut`] and [`OrderedArrayMap::upper_bound_mut`]
87/// methods.
88pub type CursorMut<'a, K, V> = internal::CursorMut<'a, K, V>;
89
90#[derive(Debug, Clone)]
91/// An owning iterator over the entries of a `OrderedArrayMap`, sorted by key.
92///
93/// This `struct` is created by the [`into_iter`] method on [`OrderedArrayMap`]
94/// (provided by the [`IntoIterator`] trait). See its documentation for more.
95///
96/// [`into_iter`]: IntoIterator::into_iter
97pub struct IntoIter<K, V, const S: usize>(array::IntoIter<(K, V), S>);
98
99impl<K, V, const S: usize> Iterator for IntoIter<K, V, S> {
100	type Item = (K, V);
101
102	fn next(&mut self) -> Option<Self::Item> {
103		self.0.next()
104	}
105
106	fn size_hint(&self) -> (usize, Option<usize>) {
107		self.0.size_hint()
108	}
109}
110
111impl<K, V, const S: usize> DoubleEndedIterator for IntoIter<K, V, S> {
112	fn next_back(&mut self) -> Option<Self::Item> {
113		self.0.next_back()
114	}
115}
116
117impl<K, V, const S: usize> ExactSizeIterator for IntoIter<K, V, S> {}
118impl<K, V, const S: usize> FusedIterator for IntoIter<K, V, S> {}
119
120#[derive(Debug, Clone)]
121/// An owning iterator over the keys of a `OrderedArrayMap`.
122///
123/// This `struct` is created by the [`into_keys`] method on [`OrderedArrayMap`].
124/// See its documentation for more.
125///
126/// [`into_keys`]: OrderedArrayMap::into_keys
127pub struct IntoKeys<K, V, const S: usize>(IntoIter<K, V, S>);
128
129impl<K, V, const S: usize> IntoKeys<K, V, S> {
130	/// Creates a new owning iterator over keys.
131	///
132	/// # Complexity
133	///
134	/// Constant.
135	pub fn new(iter: IntoIter<K, V, S>) -> Self {
136		IntoKeys(iter)
137	}
138}
139
140impl<K, V, const S: usize> Iterator for IntoKeys<K, V, S> {
141	type Item = K;
142
143	fn next(&mut self) -> Option<Self::Item> {
144		self.0.next().map(|(k, _)| k)
145	}
146
147	fn size_hint(&self) -> (usize, Option<usize>) {
148		self.0.size_hint()
149	}
150}
151
152impl<K, V, const S: usize> DoubleEndedIterator for IntoKeys<K, V, S> {
153	fn next_back(&mut self) -> Option<Self::Item> {
154		self.0.next_back().map(|(k, _)| k)
155	}
156}
157
158impl<K, V, const S: usize> ExactSizeIterator for IntoKeys<K, V, S> {}
159impl<K, V, const S: usize> FusedIterator for IntoKeys<K, V, S> {}
160
161#[derive(Debug, Clone)]
162/// An owning iterator over the values of a `OrderedArrayMap`.
163///
164/// This `struct` is created by the [`into_values`] method on [`OrderedArrayMap`].
165/// See its documentation for more.
166///
167/// [`into_values`]: OrderedArrayMap::into_values
168pub struct IntoValues<K, V, const S: usize>(IntoIter<K, V, S>);
169
170impl<K, V, const S: usize> Iterator for IntoValues<K, V, S> {
171	type Item = V;
172
173	fn next(&mut self) -> Option<Self::Item> {
174		self.0.next().map(|(_, v)| v)
175	}
176
177	fn size_hint(&self) -> (usize, Option<usize>) {
178		self.0.size_hint()
179	}
180}
181
182impl<K, V, const S: usize> DoubleEndedIterator for IntoValues<K, V, S> {
183	fn next_back(&mut self) -> Option<Self::Item> {
184		self.0.next_back().map(|(_, v)| v)
185	}
186}
187
188impl<K, V, const S: usize> ExactSizeIterator for IntoValues<K, V, S> {}
189impl<K, V, const S: usize> FusedIterator for IntoValues<K, V, S> {}
190
191#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
192/// An ordered map based on an ordered array.
193/// This structures provides a subset of the methods offered by the standard library's
194/// `BTreeMap`.
195///
196/// # Examples
197///
198/// ```
199/// use static_mapset::OrderedArrayMap;
200///
201/// let movie_reviews = OrderedArrayMap::new([
202///     ("Office Space", "Deals with real issues in the workplace."),
203///     ("Pulp Fiction", "Masterpiece."),
204///     ("The Godfather", "Very enjoyable."),
205///     ("The Blues Brothers", "Eye lyked it a lot.")
206/// ]);
207///
208/// // check for a specific one.
209/// if !movie_reviews.contains_key("Les Misérables") {
210///     println!("We've got {} reviews, but Les Misérables ain't one.",
211///              movie_reviews.len());
212/// }
213///
214/// // look up the values associated with some keys.
215/// let to_find = ["Up!", "Office Space"];
216/// for movie in &to_find {
217///     match movie_reviews.get(movie) {
218///        Some(review) => println!("{movie}: {review}"),
219///        None => println!("{movie} is unreviewed.")
220///     }
221/// }
222///
223/// // Look up the value for a key (will panic if the key is not found).
224/// println!("Movie review: {}", movie_reviews[&"Office Space"]);
225///
226/// // iterate over everything.
227/// for (movie, review) in &movie_reviews {
228///     println!("{movie}: \"{review}\"");
229/// }
230/// ```
231pub struct OrderedArrayMap<K, V, const S: usize> {
232	inner: [(K, V); S],
233	len: usize
234}
235
236impl<K, V, const S: usize> OrderedArrayMap<K, V, S> {
237	/// Sorts the array and creates an `OrderedArrayMap`.
238	/// Duplicate keys are removed, keeping the last occurrence.
239	///
240	/// # Complexity
241	///
242	/// Linearithmic in `self.len()`.
243	///
244	/// # Examples
245	///
246	/// ```
247	/// use static_mapset::OrderedArrayMap;
248	///
249	/// let map = OrderedArrayMap::new([(2, "b"), (1, "a"), (2, "c")]);
250	/// assert_eq!(map.first_key_value(), Some((&1, &"a")));
251	/// assert_eq!(map.get(&2), Some(&"c"));
252	/// ```
253	pub fn new(mut items: [(K, V); S]) -> Self
254	where
255		K: Ord
256	{
257		let len = order(&mut items);
258		OrderedArrayMap { inner: items, len }
259	}
260
261	/// Creates an `OrderedArrayMap` from an owned array without sorting.
262	///
263	/// The array must be sorted in ascending order with no duplicate keys.
264	///
265	/// # Complexity
266	///
267	/// Constant.
268	///
269	/// # Examples
270	///
271	/// ```
272	/// use static_mapset::OrderedArrayMap;
273	///
274	/// static MAP: OrderedArrayMap<i32, &str, 2> = OrderedArrayMap::new_unchecked([(1, "a"), (2, "b")]);
275	/// assert_eq!(MAP.get(&2), Some(&"b"));
276	///
277	/// // Incorrect key order or duplicates cause undefined behavior:
278	/// // let map = OrderedArrayMap::new_unchecked([(2, "a"), (1, "b")]);
279	/// // let map = OrderedArrayMap::new_unchecked([(1, "a"), (1, "b")]);
280	/// ```
281	pub const fn new_unchecked(ordered_items: [(K, V); S]) -> Self {
282		OrderedArrayMap {
283			inner: ordered_items,
284			len: S
285		}
286	}
287
288	/// Returns `true` if the map is ordered correctly.
289	///
290	/// # Complexity
291	///
292	/// Linear in `self.len()`.
293	///
294	/// # Examples
295	///
296	/// ```
297	/// use static_mapset::OrderedArrayMap;
298	///
299	/// let map = OrderedArrayMap::new_unchecked([(1, "a"), (2, "b"), (3, "b")]);
300	/// assert!(map.is_valid());
301	///
302	/// let map = OrderedArrayMap::new_unchecked([(1, "a"), (2, "b"), (2, "c")]);
303	/// assert!(!map.is_valid());
304	/// let map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b"), (f64::NAN, "c")]);
305	/// assert!(!map.is_valid());
306	/// ```
307	pub fn is_valid(&self) -> bool
308	where
309		K: PartialOrd
310	{
311		internal::is_valid(&self.inner[..self.len])
312	}
313
314	/// Returns `true` if the map contains a value for the specified key.
315	///
316	/// The key may be any borrowed form of the map's key type, but the ordering
317	/// on the borrowed form *must* match the ordering on the key type.
318	/// If equal keys are present, this returns `true` if any matching key exists.
319	///
320	/// # Complexity
321	///
322	/// Logarithmic in `self.len()`.
323	///
324	/// # Examples
325	///
326	/// ```
327	/// use static_mapset::OrderedArrayMap;
328	///
329	/// let map = OrderedArrayMap::new([(1, "a")]);
330	/// assert_eq!(map.contains_key(&1), true);
331	/// assert_eq!(map.contains_key(&2), false);
332	///
333	/// let map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
334	/// // f64::NAN is incomparable, so key lookups by NaN never match.
335	/// assert_eq!(map.contains_key(&f64::NAN), false);
336	/// ```
337	pub fn contains_key<Q>(&self, key: &Q) -> bool
338	where
339		K: Borrow<Q>,
340		Q: PartialOrd + ?Sized
341	{
342		internal::contains_key(&self.inner[..self.len], key)
343	}
344
345	/// Returns the first key-value pair in the map.
346	/// The key in this pair is the minimum key in the map.
347	///
348	/// # Complexity
349	///
350	/// Constant.
351	///
352	/// # Examples
353	///
354	/// ```
355	/// use static_mapset::OrderedArrayMap;
356	///
357	/// let map: OrderedArrayMap<i32, &str, 0> = OrderedArrayMap::new([]);
358	/// assert_eq!(map.first_key_value(), None);
359	///
360	/// let map = OrderedArrayMap::new([(1, "b"), (2, "a")]);
361	/// assert_eq!(map.first_key_value(), Some((&1, &"b")));
362	/// ```
363	pub fn first_key_value(&self) -> Option<(&K, &V)> {
364		internal::first_key_value(&self.inner[..self.len])
365	}
366
367	/// Returns a reference to the value corresponding to the key.
368	///
369	/// The key may be any borrowed form of the map's key type, but the ordering
370	/// on the borrowed form *must* match the ordering on the key type.
371	///
372	/// # Complexity
373	///
374	/// Logarithmic in `self.len()`.
375	///
376	/// # Examples
377	///
378	/// ```
379	/// use static_mapset::OrderedArrayMap;
380	///
381	/// let map = OrderedArrayMap::new([(1, "a")]);
382	/// assert_eq!(map.get(&1), Some(&"a"));
383	/// assert_eq!(map.get(&2), None);
384	///
385	/// let map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
386	/// // f64::NAN is incomparable, so key lookups by NaN never match.
387	/// assert_eq!(map.get(&f64::NAN), None);
388	/// ```
389	pub fn get<Q>(&self, key: &Q) -> Option<&V>
390	where
391		K: Borrow<Q>,
392		Q: PartialOrd + ?Sized
393	{
394		internal::get(&self.inner[..self.len], key)
395	}
396
397	/// Returns the key-value pair corresponding to the supplied key.
398	///
399	/// The supplied key may be any borrowed form of the map's key type, but the ordering
400	/// on the borrowed form *must* match the ordering on the key type.
401	/// If equal keys are present, the first matching entry in key order is returned.
402	///
403	/// # Complexity
404	///
405	/// Logarithmic in `self.len()`.
406	///
407	/// # Examples
408	///
409	/// ```
410	/// use std::cmp::Ordering;
411	/// use static_mapset::OrderedArrayMap;
412	///
413	/// #[derive(Clone, Copy, Debug)]
414	/// struct S {
415	///     id: u32,
416	/// #   #[allow(unused)] // prevents a "field `name` is never read" error
417	///     name: &'static str, // ignored by equality and ordering operations
418	/// }
419	///
420	/// impl PartialEq for S {
421	///     fn eq(&self, other: &S) -> bool {
422	///         self.id == other.id
423	///     }
424	/// }
425	///
426	/// impl Eq for S {}
427	///
428	/// impl PartialOrd for S {
429	///     fn partial_cmp(&self, other: &S) -> Option<Ordering> {
430	///         self.id.partial_cmp(&other.id)
431	///     }
432	/// }
433	///
434	/// impl Ord for S {
435	///     fn cmp(&self, other: &S) -> Ordering {
436	///         self.id.cmp(&other.id)
437	///     }
438	/// }
439	///
440	/// let j_a = S { id: 1, name: "Jessica" };
441	/// let j_b = S { id: 1, name: "Jess" };
442	/// let p = S { id: 2, name: "Paul" };
443	/// assert_eq!(j_a, j_b);
444	///
445	/// let map = OrderedArrayMap::new([(j_a, "Paris")]);
446	/// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
447	/// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
448	/// assert_eq!(map.get_key_value(&p), None);
449	///
450	/// let map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
451	/// // f64::NAN is incomparable, so key lookups by NaN never match.
452	/// assert_eq!(map.get_key_value(&f64::NAN), None);
453	/// ```
454	pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
455	where
456		K: Borrow<Q>,
457		Q: PartialOrd + ?Sized
458	{
459		internal::get_key_value(&self.inner[..self.len], key)
460	}
461
462	/// Returns `true` if the map contains no elements.
463	///
464	/// # Complexity
465	///
466	/// Constant.
467	///
468	/// # Examples
469	///
470	/// ```
471	/// use static_mapset::OrderedArrayMap;
472	///
473	/// let mut a: OrderedArrayMap<i32, &str, 0> = OrderedArrayMap::new([]);
474	/// assert!(a.is_empty());
475	/// let a = OrderedArrayMap::new([(1, "a")]);
476	/// assert!(!a.is_empty());
477	/// ```
478	pub const fn is_empty(&self) -> bool {
479		self.len == 0
480	}
481
482	/// Gets an iterator over the entries of the map, sorted by key.
483	///
484	/// # Complexity
485	///
486	/// Linear in `self.len()` to iterate all elements.
487	///
488	/// # Examples
489	///
490	/// ```
491	/// use static_mapset::OrderedArrayMap;
492	///
493	/// let map = OrderedArrayMap::new([(2, "b"), (1, "a")]);
494	///
495	/// let (first_key, first_value) = map.iter().next().unwrap();
496	/// assert_eq!((*first_key, *first_value), (1, "a"));
497	/// ```
498	pub fn iter(&self) -> Iter<'_, K, V> {
499		internal::iter(&self.inner[..self.len])
500	}
501
502	/// Gets an iterator over the keys of the map, in sorted order.
503	///
504	/// # Complexity
505	///
506	/// Linear in `self.len()` to iterate all elements.
507	///
508	/// # Examples
509	///
510	/// ```
511	/// use static_mapset::OrderedArrayMap;
512	///
513	/// let map = OrderedArrayMap::new([(2, "b"), (1, "a")]);
514	///
515	/// let keys: Vec<_> = map.keys().cloned().collect();
516	/// assert_eq!(keys, [1, 2]);
517	/// ```
518	pub fn keys(&self) -> Keys<'_, K, V> {
519		internal::keys(&self.inner[..self.len])
520	}
521
522	/// Returns the last key-value pair in the map.
523	/// The key in this pair is the maximum key in the map.
524	///
525	/// # Complexity
526	///
527	/// Constant.
528	///
529	/// # Examples
530	///
531	/// ```
532	/// use static_mapset::OrderedArrayMap;
533	///
534	/// let map = OrderedArrayMap::new([(2, "a"), (1, "b")]);
535	/// assert_eq!(map.last_key_value(), Some((&2, &"a")));
536	/// ```
537	pub fn last_key_value(&self) -> Option<(&K, &V)> {
538		internal::last_key_value(&self.inner[..self.len])
539	}
540
541	/// Returns the number of elements in the map.
542	///
543	/// # Complexity
544	///
545	/// Constant.
546	pub const fn len(&self) -> usize {
547		self.len
548	}
549
550	/// Returns a [`Cursor`] pointing at the gap before the smallest key
551	/// greater than the given bound.
552	///
553	/// Passing `Bound::Included(x)` will return a cursor pointing to the
554	/// gap before the smallest key greater than or equal to `x`.
555	///
556	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
557	/// gap before the smallest key greater than `x`.
558	///
559	/// Passing `Bound::Unbounded` will return a cursor pointing to the
560	/// gap before the smallest key in the map.
561	/// With equal keys, `Included` points before the first equal key and `Excluded` points after the last equal key.
562	///
563	/// # Complexity
564	///
565	/// Logarithmic in `self.len()`.
566	///
567	/// # Examples
568	///
569	/// ```
570	/// use static_mapset::OrderedArrayMap;
571	/// use std::ops::Bound;
572	///
573	/// let map = OrderedArrayMap::from([
574	///     (1, "a"),
575	///     (2, "b"),
576	///     (3, "c"),
577	///     (4, "d"),
578	/// ]);
579	///
580	/// let cursor = map.lower_bound(Bound::Included(&2));
581	/// assert_eq!(cursor.peek_prev(), Some((&1, &"a")));
582	/// assert_eq!(cursor.peek_next(), Some((&2, &"b")));
583	///
584	/// let cursor = map.lower_bound(Bound::Excluded(&2));
585	/// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
586	/// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
587	///
588	/// let cursor = map.lower_bound(Bound::Unbounded);
589	/// assert_eq!(cursor.peek_prev(), None);
590	/// assert_eq!(cursor.peek_next(), Some((&1, &"a")));
591	///
592	/// let map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
593	/// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
594	/// let cursor = map.lower_bound(Bound::Included(&f64::NAN));
595	/// assert_eq!(cursor.peek_prev(), Some((&2.0, &"b")));
596	/// ```
597	pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
598	where
599		K: Borrow<Q>,
600		Q: PartialOrd + ?Sized
601	{
602		internal::lower_bound(&self.inner[..self.len], bound)
603	}
604
605	/// Constructs a double-ended iterator over a sub-range of elements in the map.
606	/// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
607	/// yield elements from min (inclusive) to max (exclusive).
608	/// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
609	/// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
610	/// range from 4 to 10.
611	///
612	/// # Panics
613	///
614	/// Panics if range `start > end`.
615	/// Panics if range `start == end` and both bounds are `Excluded`.
616	/// Panics if `start` (or `end`() is incomparable and `end` (or `start`) is bounded.
617	///
618	/// # Complexity
619	///
620	/// Logarithmic in `self.len()`.
621	///
622	/// # Examples
623	///
624	/// ```
625	/// use static_mapset::OrderedArrayMap;
626	/// use std::ops::Bound::Included;
627	///
628	/// let map = OrderedArrayMap::new([
629	///     (3, "a"),
630	///     (5, "b"),
631	///     (8, "c")
632	/// ]);
633	/// for (&key, &value) in map.range((Included(&4), Included(&8))) {
634	///     println!("{key}: {value}");
635	/// }
636	/// assert_eq!(Some((&5, &"b")), map.range(4..).next());
637	/// ```
638	pub fn range<Q, R>(&self, range: R) -> Range<'_, K, V>
639	where
640		K: Borrow<Q>,
641		Q: PartialOrd + ?Sized,
642		R: RangeBounds<Q>
643	{
644		internal::range(&self.inner[..self.len], range)
645	}
646
647	/// Returns a [`Cursor`] pointing at the gap after the greatest key
648	/// smaller than the given bound.
649	///
650	/// Passing `Bound::Included(x)` will return a cursor pointing to the
651	/// gap after the greatest key smaller than or equal to `x`.
652	///
653	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
654	/// gap after the greatest key smaller than `x`.
655	///
656	/// Passing `Bound::Unbounded` will return a cursor pointing to the
657	/// gap after the greatest key in the map.
658	/// With equal keys, `Excluded` points before the first equal key and `Included` points after the last equal key.
659	///
660	/// # Complexity
661	///
662	/// Logarithmic in `self.len()`.
663	///
664	/// # Examples
665	///
666	/// ```
667	///
668	/// use static_mapset::OrderedArrayMap;
669	/// use std::ops::Bound;
670	///
671	/// let map = OrderedArrayMap::from([
672	///     (1, "a"),
673	///     (2, "b"),
674	///     (3, "c"),
675	///     (4, "d"),
676	/// ]);
677	///
678	/// let cursor = map.upper_bound(Bound::Included(&3));
679	/// assert_eq!(cursor.peek_prev(), Some((&3, &"c")));
680	/// assert_eq!(cursor.peek_next(), Some((&4, &"d")));
681	///
682	/// let cursor = map.upper_bound(Bound::Excluded(&3));
683	/// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
684	/// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
685	///
686	/// let cursor = map.upper_bound(Bound::Unbounded);
687	/// assert_eq!(cursor.peek_prev(), Some((&4, &"d")));
688	/// assert_eq!(cursor.peek_next(), None);
689	///
690	/// let map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
691	/// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
692	/// let cursor = map.upper_bound(Bound::Included(&f64::NAN));
693	/// assert_eq!(cursor.peek_prev(), Some((&2.0, &"b")));
694	/// ```
695	pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
696	where
697		K: Borrow<Q>,
698		Q: PartialOrd + ?Sized
699	{
700		internal::upper_bound(&self.inner[..self.len], bound)
701	}
702
703	/// Gets an iterator over the values of the map, in order by key.
704	///
705	/// # Complexity
706	///
707	/// Linear in `self.len()` to iterate all elements.
708	///
709	/// # Examples
710	///
711	/// ```
712	/// use static_mapset::OrderedArrayMap;
713	///
714	/// let map = OrderedArrayMap::new([(2, "b"), (1, "a")]);
715	///
716	/// let values: Vec<_> = map.values().cloned().collect();
717	/// assert_eq!(values, ["a", "b"]);
718	/// ```
719	pub fn values(&self) -> Values<'_, K, V> {
720		internal::values(&self.inner[..self.len])
721	}
722
723	/// Returns a mutable reference to the value corresponding to the key.
724	///
725	/// The key may be any borrowed form of the map's key type, but the ordering
726	/// on the borrowed form *must* match the ordering on the key type.
727	/// If equal keys are present, the first matching entry in key order is returned.
728	///
729	/// # Complexity
730	///
731	/// Logarithmic in `self.len()`.
732	///
733	/// # Examples
734	///
735	/// ```
736	/// use static_mapset::OrderedArrayMap;
737	///
738	/// let mut map = OrderedArrayMap::new([(1, "a")]);
739	/// assert_eq!(map.get_mut(&1), Some(&mut "a"));
740	/// assert_eq!(map.get_mut(&2), None);
741	///
742	/// let mut map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
743	/// // f64::NAN is incomparable, so key lookups by NaN never match.
744	/// assert_eq!(map.get_mut(&f64::NAN), None);
745	/// ```
746	pub fn get_mut<'a, Q>(&'a mut self, key: &Q) -> Option<&'a mut V>
747	where
748		K: Borrow<Q>,
749		Q: PartialOrd + ?Sized
750	{
751		internal::get_mut(&mut self.inner[..self.len], key)
752	}
753
754	/// Gets a mutable iterator over the entries of the map, sorted by key.
755	///
756	/// # Complexity
757	///
758	/// Linear in `self.len()` to iterate all elements.
759	///
760	/// # Examples
761	///
762	/// ```
763	/// use static_mapset::OrderedArrayMap;
764	///
765	/// let mut map = OrderedArrayMap::from([
766	///    ("a", 1),
767	///    ("b", 2),
768	///    ("c", 3),
769	/// ]);
770	///
771	/// // add 10 to the value if the key isn't "a"
772	/// for (key, value) in map.iter_mut() {
773	///     if key != &"a" {
774	///         *value += 10;
775	///     }
776	/// }
777	///
778	/// let values: Vec<_> = map.values().cloned().collect();
779	/// assert_eq!(values, [1, 12, 13]);
780	/// ```
781	pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
782		internal::iter_mut(&mut self.inner[..self.len])
783	}
784
785	/// Returns a [`CursorMut`] pointing at the gap before the smallest key
786	/// greater than the given bound.
787	///
788	/// Passing `Bound::Included(x)` will return a cursor pointing to the
789	/// gap before the smallest key greater than or equal to `x`.
790	///
791	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
792	/// gap before the smallest key greater than `x`.
793	///
794	/// Passing `Bound::Unbounded` will return a cursor pointing to the
795	/// gap before the smallest key in the map.
796	///
797	/// # Complexity
798	///
799	/// Logarithmic in `self.len()`.
800	///
801	/// # Examples
802	///
803	/// ```
804	/// use static_mapset::OrderedArrayMap;
805	/// use std::ops::Bound;
806	///
807	/// let mut map = OrderedArrayMap::from([
808	///     (1, "a"),
809	///     (2, "b"),
810	///     (3, "c"),
811	///     (4, "d"),
812	/// ]);
813	///
814	/// let mut cursor = map.lower_bound_mut(Bound::Included(&2));
815	/// assert_eq!(cursor.peek_prev(), Some((&1, &mut "a")));
816	/// assert_eq!(cursor.peek_next(), Some((&2, &mut "b")));
817	///
818	/// let mut cursor = map.lower_bound_mut(Bound::Excluded(&2));
819	/// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b")));
820	/// assert_eq!(cursor.peek_next(), Some((&3, &mut "c")));
821	///
822	/// let mut cursor = map.lower_bound_mut(Bound::Unbounded);
823	/// assert_eq!(cursor.peek_prev(), None);
824	/// assert_eq!(cursor.peek_next(), Some((&1, &mut "a")));
825	///
826	/// let mut map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
827	/// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
828	/// let mut cursor = map.lower_bound_mut(Bound::Included(&f64::NAN));
829	/// assert_eq!(cursor.peek_prev(), Some((&2.0, &mut "b")));
830	/// ```
831	pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
832	where
833		K: Borrow<Q>,
834		Q: PartialOrd + ?Sized
835	{
836		internal::lower_bound_mut(&mut self.inner[..self.len], bound)
837	}
838
839	/// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
840	/// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
841	/// yield elements from min (inclusive) to max (exclusive).
842	/// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
843	/// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
844	/// range from 4 to 10.
845	///
846	/// # Panics
847	///
848	/// Panics if range `start > end`.
849	/// Panics if range `start == end` and both bounds are `Excluded`.
850	/// Panics if `start` (or `end`() is incomparable and `end` (or `start`) is bounded.
851	///
852	/// # Complexity
853	///
854	/// Logarithmic in `self.len()`.
855	///
856	/// # Examples
857	///
858	/// ```
859	/// use static_mapset::OrderedArrayMap;
860	///
861	/// let mut map = OrderedArrayMap::new([
862	///     ("Alice", 0),
863	///     ("Bob", 0),
864	///     ("Carol", 0),
865	///     ("Cheryl", 0)
866	/// ]);
867	/// for (_, balance) in map.range_mut("B".."Cheryl") {
868	///     *balance += 100;
869	/// }
870	/// for (name, balance) in &map {
871	///     println!("{name} => {balance}");
872	/// }
873	/// ```
874	pub fn range_mut<Q, R>(&mut self, range: R) -> RangeMut<'_, K, V>
875	where
876		K: Borrow<Q>,
877		Q: PartialOrd + ?Sized,
878		R: RangeBounds<Q>
879	{
880		internal::range_mut(&mut self.inner[..self.len], range)
881	}
882
883	/// Returns a [`CursorMut`] pointing at the gap after the greatest key
884	/// smaller than the given bound.
885	///
886	/// Passing `Bound::Included(x)` will return a cursor pointing to the
887	/// gap after the greatest key smaller than or equal to `x`.
888	///
889	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
890	/// gap after the greatest key smaller than `x`.
891	///
892	/// Passing `Bound::Unbounded` will return a cursor pointing to the
893	/// gap after the greatest key in the map.
894	///
895	/// # Complexity
896	///
897	/// Logarithmic in `self.len()`.
898	///
899	/// # Examples
900	///
901	/// ```
902	///
903	/// use static_mapset::OrderedArrayMap;
904	/// use std::ops::Bound;
905	///
906	/// let mut map = OrderedArrayMap::from([
907	///     (1, "a"),
908	///     (2, "b"),
909	///     (3, "c"),
910	///     (4, "d"),
911	/// ]);
912	///
913	/// let mut cursor = map.upper_bound_mut(Bound::Included(&3));
914	/// assert_eq!(cursor.peek_prev(), Some((&3, &mut "c")));
915	/// assert_eq!(cursor.peek_next(), Some((&4, &mut "d")));
916	///
917	/// let mut cursor = map.upper_bound_mut(Bound::Excluded(&3));
918	/// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b")));
919	/// assert_eq!(cursor.peek_next(), Some((&3, &mut "c")));
920	///
921	/// let mut cursor = map.upper_bound_mut(Bound::Unbounded);
922	/// assert_eq!(cursor.peek_prev(), Some((&4, &mut "d")));
923	/// assert_eq!(cursor.peek_next(), None);
924	///
925	/// let mut map = OrderedArrayMap::new_unchecked([(1.0, "a"), (2.0, "b")]);
926	/// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
927	/// let mut cursor = map.upper_bound_mut(Bound::Included(&f64::NAN));
928	/// assert_eq!(cursor.peek_prev(), Some((&2.0, &mut "b")));
929	/// ```
930	pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
931	where
932		K: Borrow<Q>,
933		Q: PartialOrd + ?Sized
934	{
935		internal::upper_bound_mut(&mut self.inner[..self.len], bound)
936	}
937
938	/// Gets a mutable iterator over the values of the map, in order by key.
939	///
940	/// # Complexity
941	///
942	/// Linear in `self.len()` to iterate all elements.
943	///
944	/// # Examples
945	///
946	/// ```
947	/// use static_mapset::OrderedArrayMap;
948	///
949	/// let mut a = OrderedArrayMap::new([
950	///     (1, String::from("hello")),
951	///     (2, String::from("goodbye"))
952	/// ]);
953	///
954	/// for value in a.values_mut() {
955	///     value.push_str("!");
956	/// }
957	///
958	/// let values: Vec<String> = a.values().cloned().collect();
959	/// assert_eq!(values, [String::from("hello!"),
960	///                     String::from("goodbye!")]);
961	/// ```
962	pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
963		internal::values_mut(&mut self.inner[..self.len])
964	}
965
966	/// Creates a consuming iterator visiting all the keys, in sorted order.
967	/// The map cannot be used after calling this.
968	/// The iterator element type is `K`.
969	///
970	/// # Complexity
971	///
972	/// Linear in `self.len()` to iterate all elements.
973	///
974	/// # Examples
975	///
976	/// ```
977	/// use static_mapset::OrderedArrayMap;
978	///
979	/// let a = OrderedArrayMap::new([(2, "b"), (1, "a")]);
980	///
981	/// let keys: Vec<i32> = a.into_keys().collect();
982	/// assert_eq!(keys, [1, 2]);
983	/// ```
984	pub fn into_keys(self) -> IntoKeys<K, V, S> {
985		IntoKeys(self.into_iter())
986	}
987
988	/// Creates a consuming iterator visiting all the values, in order by key.
989	/// The map cannot be used after calling this.
990	/// The iterator element type is `V`.
991	///
992	/// # Complexity
993	///
994	/// Linear in `self.len()` to iterate all elements.
995	///
996	/// # Examples
997	///
998	/// ```
999	/// use static_mapset::OrderedArrayMap;
1000	///
1001	/// let a = OrderedArrayMap::new([(1, "hello"), (2, "goodbye")]);
1002	///
1003	/// let values: Vec<&str> = a.into_values().collect();
1004	/// assert_eq!(values, ["hello", "goodbye"]);
1005	/// ```
1006	pub fn into_values(self) -> IntoValues<K, V, S> {
1007		IntoValues(self.into_iter())
1008	}
1009}
1010
1011impl<K, V, const S: usize> From<[(K, V); S]> for OrderedArrayMap<K, V, S>
1012where
1013	K: Ord
1014{
1015	fn from(value: [(K, V); S]) -> Self {
1016		OrderedArrayMap::new(value)
1017	}
1018}
1019
1020impl<K, V, Q, const S: usize> Index<&Q> for OrderedArrayMap<K, V, S>
1021where
1022	K: Borrow<Q>,
1023	Q: PartialOrd
1024{
1025	type Output = V;
1026
1027	fn index(&self, key: &Q) -> &Self::Output {
1028		self.get(key).expect("no entry found for key")
1029	}
1030}
1031
1032impl<K, V, const S: usize> IntoIterator for OrderedArrayMap<K, V, S> {
1033	type Item = (K, V);
1034	type IntoIter = IntoIter<K, V, S>;
1035
1036	fn into_iter(self) -> Self::IntoIter {
1037		let to_back = self.inner.len() - self.len;
1038		let mut inner = self.inner.into_iter();
1039		if to_back > 0 {
1040			inner.nth_back(to_back - 1);
1041		}
1042		IntoIter(inner)
1043	}
1044}
1045
1046impl<'a, K, V, const S: usize> IntoIterator for &'a OrderedArrayMap<K, V, S> {
1047	type Item = (&'a K, &'a V);
1048	type IntoIter = Iter<'a, K, V>;
1049
1050	fn into_iter(self) -> Self::IntoIter {
1051		self.iter()
1052	}
1053}
1054
1055impl<'a, K, V, const S: usize> IntoIterator for &'a mut OrderedArrayMap<K, V, S> {
1056	type Item = (&'a K, &'a mut V);
1057	type IntoIter = IterMut<'a, K, V>;
1058
1059	fn into_iter(self) -> Self::IntoIter {
1060		self.iter_mut()
1061	}
1062}
1063
1064#[cfg(test)]
1065mod tests {
1066	use core::ops::Bound;
1067
1068	use super::*;
1069
1070	#[test]
1071	fn test_new() {
1072		let set = OrderedArrayMap::new([(5, 1), (1, 2), (3, 3), (1, 4)]);
1073		assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![(1, 4), (3, 3), (5, 1)]);
1074	}
1075
1076	#[test]
1077	fn test_empty_map() {
1078		let target: OrderedArrayMap<i32, i32, 0> = OrderedArrayMap::new_unchecked([]);
1079		assert_eq!(target.get(&0), None);
1080		assert_eq!(target.lower_bound(Bound::Included(&0)).next(), None);
1081		assert_eq!(target.lower_bound(Bound::Included(&0)).prev(), None);
1082		assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), None);
1083		assert_eq!(target.lower_bound(Bound::Excluded(&0)).prev(), None);
1084		assert_eq!(target.lower_bound(Bound::Unbounded).next(), None);
1085		assert_eq!(target.lower_bound(Bound::Unbounded).prev(), None);
1086		assert_eq!(target.upper_bound(Bound::Included(&0)).next(), None);
1087		assert_eq!(target.upper_bound(Bound::Included(&0)).prev(), None);
1088		assert_eq!(target.upper_bound(Bound::Excluded(&0)).next(), None);
1089		assert_eq!(target.upper_bound(Bound::Excluded(&0)).prev(), None);
1090		assert_eq!(target.upper_bound(Bound::Unbounded).next(), None);
1091		assert_eq!(target.upper_bound(Bound::Unbounded).prev(), None);
1092	}
1093
1094	#[test]
1095	fn test_singleton_map() {
1096		let target = OrderedArrayMap::new_unchecked([(5, 25)]);
1097		assert_eq!(target.get(&4), None);
1098		assert_eq!(target.get(&5), Some(&25));
1099		assert_eq!(target.get(&6), None);
1100	}
1101
1102	#[test]
1103	fn test_map() {
1104		let target = OrderedArrayMap::new_unchecked([(1, 1), (2, 4), (4, 16)]);
1105		assert_eq!(target.get(&0), None);
1106		assert_eq!(target.get(&1), Some(&1));
1107		assert_eq!(target.get(&2), Some(&4));
1108		assert_eq!(target.get(&3), None);
1109		assert_eq!(target.get(&4), Some(&16));
1110		assert_eq!(target.get(&5), None);
1111	}
1112
1113	#[test]
1114	fn test_lower_bound_included() {
1115		let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25)]);
1116		assert_eq!(target.lower_bound(Bound::Included(&0)).next(), Some((&1, &1)));
1117		assert_eq!(target.lower_bound(Bound::Included(&1)).next(), Some((&1, &1)));
1118		assert_eq!(target.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
1119		assert_eq!(target.lower_bound(Bound::Included(&3)).next(), Some((&3, &9)));
1120		assert_eq!(target.lower_bound(Bound::Included(&4)).next(), Some((&5, &25)));
1121		assert_eq!(target.lower_bound(Bound::Included(&5)).next(), Some((&5, &25)));
1122		assert_eq!(target.lower_bound(Bound::Included(&6)).next(), None);
1123
1124		let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25), (7, 49)]);
1125		assert_eq!(target.lower_bound(Bound::Included(&0)).next(), Some((&1, &1)));
1126		assert_eq!(target.lower_bound(Bound::Included(&1)).next(), Some((&1, &1)));
1127		assert_eq!(target.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
1128		assert_eq!(target.lower_bound(Bound::Included(&3)).next(), Some((&3, &9)));
1129		assert_eq!(target.lower_bound(Bound::Included(&4)).next(), Some((&5, &25)));
1130		assert_eq!(target.lower_bound(Bound::Included(&5)).next(), Some((&5, &25)));
1131		assert_eq!(target.lower_bound(Bound::Included(&6)).next(), Some((&7, &49)));
1132		assert_eq!(target.lower_bound(Bound::Included(&7)).next(), Some((&7, &49)));
1133		assert_eq!(target.lower_bound(Bound::Included(&8)).next(), None);
1134
1135		let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (3, 16), (5, 25)]);
1136		assert_eq!(target.lower_bound(Bound::Included(&0)).next(), Some((&1, &1)));
1137		assert_eq!(target.lower_bound(Bound::Included(&1)).next(), Some((&1, &1)));
1138		assert_eq!(target.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
1139		assert_eq!(target.lower_bound(Bound::Included(&3)).next(), Some((&3, &9)));
1140		assert_eq!(target.lower_bound(Bound::Included(&4)).next(), Some((&5, &25)));
1141		assert_eq!(target.lower_bound(Bound::Included(&5)).next(), Some((&5, &25)));
1142		assert_eq!(target.lower_bound(Bound::Included(&6)).next(), None);
1143	}
1144
1145	#[test]
1146	fn test_lower_bound_excluded() {
1147		let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25)]);
1148		assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), Some((&1, &1)));
1149		assert_eq!(target.lower_bound(Bound::Excluded(&1)).next(), Some((&3, &9)));
1150		assert_eq!(target.lower_bound(Bound::Excluded(&2)).next(), Some((&3, &9)));
1151		assert_eq!(target.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
1152		assert_eq!(target.lower_bound(Bound::Excluded(&4)).next(), Some((&5, &25)));
1153		assert_eq!(target.lower_bound(Bound::Excluded(&5)).next(), None);
1154		assert_eq!(target.lower_bound(Bound::Excluded(&6)).next(), None);
1155
1156		let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25), (7, 49)]);
1157		assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), Some((&1, &1)));
1158		assert_eq!(target.lower_bound(Bound::Excluded(&1)).next(), Some((&3, &9)));
1159		assert_eq!(target.lower_bound(Bound::Excluded(&2)).next(), Some((&3, &9)));
1160		assert_eq!(target.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
1161		assert_eq!(target.lower_bound(Bound::Excluded(&4)).next(), Some((&5, &25)));
1162		assert_eq!(target.lower_bound(Bound::Excluded(&5)).next(), Some((&7, &49)));
1163		assert_eq!(target.lower_bound(Bound::Excluded(&6)).next(), Some((&7, &49)));
1164		assert_eq!(target.lower_bound(Bound::Excluded(&7)).next(), None);
1165		assert_eq!(target.lower_bound(Bound::Excluded(&8)).next(), None);
1166
1167		let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (3, 16), (5, 25)]);
1168		assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), Some((&1, &1)));
1169		assert_eq!(target.lower_bound(Bound::Excluded(&1)).next(), Some((&3, &9)));
1170		assert_eq!(target.lower_bound(Bound::Excluded(&2)).next(), Some((&3, &9)));
1171		assert_eq!(target.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
1172		assert_eq!(target.lower_bound(Bound::Excluded(&4)).next(), Some((&5, &25)));
1173		assert_eq!(target.lower_bound(Bound::Excluded(&5)).next(), None);
1174		assert_eq!(target.lower_bound(Bound::Excluded(&6)).next(), None);
1175	}
1176}