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}