Skip to main content

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}