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