litemap/map.rs
1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5use crate::store::*;
6#[cfg(feature = "alloc")]
7use alloc::boxed::Box;
8#[cfg(feature = "alloc")]
9use alloc::vec::Vec;
10use core::borrow::Borrow;
11use core::cmp::Ordering;
12use core::fmt::Debug;
13use core::iter::FromIterator;
14use core::marker::PhantomData;
15use core::mem;
16use core::ops::{Index, IndexMut, Range};
17
18macro_rules! litemap_impl(
19 ($cfg:meta, $store:ident $(=$defaultty:ty)?) => {
20 /// A simple "flat" map based on a sorted vector
21 ///
22 /// See the [module level documentation][super] for why one should use this.
23 ///
24 /// The API is roughly similar to that of [`std::collections::BTreeMap`].
25 #[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
26 #[cfg_attr(feature = "yoke", derive(yoke::Yokeable))]
27 #[cfg($cfg)]
28 pub struct LiteMap<K: ?Sized, V: ?Sized, $store $(= $defaultty)?> {
29 pub(crate) values: $store,
30 pub(crate) _key_type: PhantomData<K>,
31 pub(crate) _value_type: PhantomData<V>,
32 }
33 };
34
35);
36// You can't `cfg()` a default generic parameter, and we don't want to write this type twice
37// and keep them in sync so we use a small macro
38litemap_impl!(feature = "alloc", S = alloc::vec::Vec<(K, V)>);
39litemap_impl!(not(feature = "alloc"), S);
40
41#[cfg(feature = "alloc")]
42impl<K, V> LiteMap<K, V> {
43 /// Construct a new [`LiteMap`] backed by Vec
44 ///
45 /// ✨ *Enabled with the `alloc` Cargo feature.*
46 pub const fn new_vec() -> Self {
47 Self {
48 values: alloc::vec::Vec::new(),
49 _key_type: PhantomData,
50 _value_type: PhantomData,
51 }
52 }
53}
54
55impl<K, V, S> LiteMap<K, V, S> {
56 /// Construct a new [`LiteMap`] using the given values
57 ///
58 /// The store must be sorted and have no duplicate keys.
59 pub const fn from_sorted_store_unchecked(values: S) -> Self {
60 Self {
61 values,
62 _key_type: PhantomData,
63 _value_type: PhantomData,
64 }
65 }
66}
67
68#[cfg(feature = "alloc")]
69impl<K, V> LiteMap<K, V, Vec<(K, V)>> {
70 /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`.
71 ///
72 /// ✨ *Enabled with the `alloc` Cargo feature.*
73 #[inline]
74 pub fn into_tuple_vec(self) -> Vec<(K, V)> {
75 self.values
76 }
77}
78
79impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
80where
81 S: StoreConstEmpty<K, V>,
82{
83 /// Create a new empty [`LiteMap`]
84 pub const fn new() -> Self {
85 Self {
86 values: S::EMPTY,
87 _key_type: PhantomData,
88 _value_type: PhantomData,
89 }
90 }
91}
92
93impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
94where
95 S: Store<K, V>,
96{
97 /// The number of elements in the [`LiteMap`]
98 pub fn len(&self) -> usize {
99 self.values.lm_len()
100 }
101
102 /// Whether the [`LiteMap`] is empty
103 pub fn is_empty(&self) -> bool {
104 self.values.lm_is_empty()
105 }
106
107 /// Get the key-value pair residing at a particular index
108 ///
109 /// In most cases, prefer [`LiteMap::get()`] over this method.
110 #[inline]
111 pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> {
112 self.values.lm_get(index)
113 }
114
115 /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists.
116 ///
117 /// # Examples
118 ///
119 /// ```rust
120 /// use litemap::LiteMap;
121 ///
122 /// let mut map =
123 /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]);
124 ///
125 /// assert_eq!(map.first(), Some((&1, &"uno")));
126 /// ```
127 #[inline]
128 pub fn first(&self) -> Option<(&K, &V)> {
129 self.values.lm_get(0)
130 }
131
132 /// Get the highest-rank key/value pair from the `LiteMap`, if it exists.
133 ///
134 /// # Examples
135 ///
136 /// ```rust
137 /// use litemap::LiteMap;
138 ///
139 /// let mut map =
140 /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]);
141 ///
142 /// assert_eq!(map.last(), Some((&3, &"tres")));
143 /// ```
144 #[inline]
145 pub fn last(&self) -> Option<(&K, &V)> {
146 self.values.lm_last()
147 }
148
149 /// Returns a new [`LiteMap`] with owned keys and values.
150 ///
151 /// The trait bounds allow transforming most slice and string types.
152 ///
153 /// ✨ *Enabled with the `alloc` Cargo feature.*
154 ///
155 /// # Examples
156 ///
157 /// ```
158 /// use litemap::LiteMap;
159 ///
160 /// let mut map: LiteMap<&str, &str> = LiteMap::new_vec();
161 /// map.insert("one", "uno");
162 /// map.insert("two", "dos");
163 ///
164 /// let boxed_map: LiteMap<Box<str>, Box<str>> = map.to_boxed_keys_values();
165 ///
166 /// assert_eq!(boxed_map.get("one"), Some(&Box::from("uno")));
167 /// ```
168 #[cfg(feature = "alloc")]
169 pub fn to_boxed_keys_values<KB: ?Sized, VB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, Box<VB>, SB>
170 where
171 SB: StoreMut<Box<KB>, Box<VB>>,
172 K: Borrow<KB>,
173 V: Borrow<VB>,
174 Box<KB>: for<'a> From<&'a KB>,
175 Box<VB>: for<'a> From<&'a VB>,
176 {
177 let mut values = SB::lm_with_capacity(self.len());
178 for i in 0..self.len() {
179 #[expect(clippy::unwrap_used)] // iterating over our own length
180 let (k, v) = self.values.lm_get(i).unwrap();
181 values.lm_push(Box::from(k.borrow()), Box::from(v.borrow()))
182 }
183 LiteMap {
184 values,
185 _key_type: PhantomData,
186 _value_type: PhantomData,
187 }
188 }
189
190 /// Returns a new [`LiteMap`] with owned keys and cloned values.
191 ///
192 /// The trait bounds allow transforming most slice and string types.
193 ///
194 /// ✨ *Enabled with the `alloc` Cargo feature.*
195 ///
196 /// # Examples
197 ///
198 /// ```
199 /// use litemap::LiteMap;
200 ///
201 /// let mut map: LiteMap<&str, usize> = LiteMap::new_vec();
202 /// map.insert("one", 11);
203 /// map.insert("two", 22);
204 ///
205 /// let boxed_map: LiteMap<Box<str>, usize> = map.to_boxed_keys();
206 ///
207 /// assert_eq!(boxed_map.get("one"), Some(&11));
208 /// ```
209 #[cfg(feature = "alloc")]
210 pub fn to_boxed_keys<KB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, V, SB>
211 where
212 V: Clone,
213 SB: StoreMut<Box<KB>, V>,
214 K: Borrow<KB>,
215 Box<KB>: for<'a> From<&'a KB>,
216 {
217 let mut values = SB::lm_with_capacity(self.len());
218 for i in 0..self.len() {
219 #[expect(clippy::unwrap_used)] // iterating over our own length
220 let (k, v) = self.values.lm_get(i).unwrap();
221 values.lm_push(Box::from(k.borrow()), v.clone())
222 }
223 LiteMap {
224 values,
225 _key_type: PhantomData,
226 _value_type: PhantomData,
227 }
228 }
229
230 /// Returns a new [`LiteMap`] with cloned keys and owned values.
231 ///
232 /// The trait bounds allow transforming most slice and string types.
233 ///
234 /// ✨ *Enabled with the `alloc` Cargo feature.*
235 ///
236 /// # Examples
237 ///
238 /// ```
239 /// use litemap::LiteMap;
240 ///
241 /// let mut map: LiteMap<usize, &str> = LiteMap::new_vec();
242 /// map.insert(11, "uno");
243 /// map.insert(22, "dos");
244 ///
245 /// let boxed_map: LiteMap<usize, Box<str>> = map.to_boxed_values();
246 ///
247 /// assert_eq!(boxed_map.get(&11), Some(&Box::from("uno")));
248 /// ```
249 #[cfg(feature = "alloc")]
250 pub fn to_boxed_values<VB: ?Sized, SB>(&self) -> LiteMap<K, Box<VB>, SB>
251 where
252 K: Clone,
253 SB: StoreMut<K, Box<VB>>,
254 V: Borrow<VB>,
255 Box<VB>: for<'a> From<&'a VB>,
256 {
257 let mut values = SB::lm_with_capacity(self.len());
258 for i in 0..self.len() {
259 #[expect(clippy::unwrap_used)] // iterating over our own length
260 let (k, v) = self.values.lm_get(i).unwrap();
261 values.lm_push(k.clone(), Box::from(v.borrow()))
262 }
263 LiteMap {
264 values,
265 _key_type: PhantomData,
266 _value_type: PhantomData,
267 }
268 }
269}
270
271impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
272where
273 K: Ord,
274 S: Store<K, V>,
275{
276 /// Get the value associated with `key`, if it exists.
277 ///
278 /// ```rust
279 /// use litemap::LiteMap;
280 ///
281 /// let mut map = LiteMap::new_vec();
282 /// map.insert(1, "one");
283 /// map.insert(2, "two");
284 /// assert_eq!(map.get(&1), Some(&"one"));
285 /// assert_eq!(map.get(&3), None);
286 /// ```
287 pub fn get<Q>(&self, key: &Q) -> Option<&V>
288 where
289 K: Borrow<Q>,
290 Q: Ord + ?Sized,
291 {
292 match self.find_index(key) {
293 #[expect(clippy::unwrap_used)] // find_index returns a valid index
294 Ok(found) => Some(self.values.lm_get(found).unwrap().1),
295 Err(_) => None,
296 }
297 }
298
299 /// Binary search the map with `predicate` to find a key, returning the value.
300 pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> {
301 let index = self.values.lm_binary_search_by(predicate).ok()?;
302 self.values.lm_get(index).map(|(_, v)| v)
303 }
304
305 /// Returns whether `key` is contained in this map
306 ///
307 /// ```rust
308 /// use litemap::LiteMap;
309 ///
310 /// let mut map = LiteMap::new_vec();
311 /// map.insert(1, "one");
312 /// map.insert(2, "two");
313 /// assert!(map.contains_key(&1));
314 /// assert!(!map.contains_key(&3));
315 /// ```
316 pub fn contains_key<Q>(&self, key: &Q) -> bool
317 where
318 K: Borrow<Q>,
319 Q: Ord + ?Sized,
320 {
321 self.find_index(key).is_ok()
322 }
323
324 /// Obtain the index for a given key, or if the key is not found, the index
325 /// at which it would be inserted.
326 ///
327 /// (The return value works equivalently to [`slice::binary_search_by()`])
328 ///
329 /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using
330 /// [`Self::get()`] directly where possible.
331 #[inline]
332 pub fn find_index<Q>(&self, key: &Q) -> Result<usize, usize>
333 where
334 K: Borrow<Q>,
335 Q: Ord + ?Sized,
336 {
337 self.values.lm_binary_search_by(|k| k.borrow().cmp(key))
338 }
339}
340
341impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
342where
343 S: StoreSlice<K, V>,
344{
345 /// Creates a new [`LiteMap`] from a range of the current [`LiteMap`].
346 ///
347 /// # Examples
348 ///
349 /// ```
350 /// use litemap::LiteMap;
351 ///
352 /// let mut map = LiteMap::new_vec();
353 /// map.insert(1, "one");
354 /// map.insert(2, "two");
355 /// map.insert(3, "three");
356 ///
357 /// let mut sub_map = map.get_indexed_range(1..3).expect("valid range");
358 /// assert_eq!(sub_map.get(&1), None);
359 /// assert_eq!(sub_map.get(&2), Some(&"two"));
360 /// assert_eq!(sub_map.get(&3), Some(&"three"));
361 /// ```
362 pub fn get_indexed_range(&self, range: Range<usize>) -> Option<LiteMap<K, V, &S::Slice>> {
363 let subslice = self.values.lm_get_range(range)?;
364 Some(LiteMap {
365 values: subslice,
366 _key_type: PhantomData,
367 _value_type: PhantomData,
368 })
369 }
370
371 /// Borrows this [`LiteMap`] as one of its slice type.
372 ///
373 /// This can be useful in situations where you need a `LiteMap` by value but do not want
374 /// to clone the owned version.
375 ///
376 /// # Examples
377 ///
378 /// ```
379 /// use litemap::LiteMap;
380 ///
381 /// let mut map = LiteMap::new_vec();
382 /// map.insert(1, "one");
383 /// map.insert(2, "two");
384 ///
385 /// let borrowed_map = map.as_sliced();
386 /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
387 /// assert_eq!(borrowed_map.get(&2), Some(&"two"));
388 /// ```
389 pub fn as_sliced(&self) -> LiteMap<K, V, &S::Slice> {
390 // Won't panic: 0..self.len() is within range
391 #[expect(clippy::unwrap_used)]
392 let subslice = self.values.lm_get_range(0..self.len()).unwrap();
393 LiteMap {
394 values: subslice,
395 _key_type: PhantomData,
396 _value_type: PhantomData,
397 }
398 }
399
400 /// Borrows the backing buffer of this [`LiteMap`] as its slice type.
401 ///
402 /// The slice will be sorted.
403 ///
404 /// # Examples
405 ///
406 /// ```
407 /// use litemap::LiteMap;
408 ///
409 /// let mut map = LiteMap::new_vec();
410 /// map.insert(1, "one");
411 /// map.insert(2, "two");
412 ///
413 /// let slice = map.as_slice();
414 /// assert_eq!(slice, &[(1, "one"), (2, "two")]);
415 /// ```
416 pub fn as_slice(&self) -> &S::Slice {
417 // Won't panic: 0..self.len() is within range
418 #[expect(clippy::unwrap_used)]
419 self.values.lm_get_range(0..self.len()).unwrap()
420 }
421}
422
423impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
424where
425 S: Store<K, V>,
426{
427 /// Returns a new [`LiteMap`] with keys and values borrowed from this one.
428 ///
429 /// # Examples
430 ///
431 /// ```
432 /// use litemap::LiteMap;
433 ///
434 /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
435 /// map.insert(Box::new(1), "one".to_string());
436 /// map.insert(Box::new(2), "two".to_string());
437 ///
438 /// let borrowed_map: LiteMap<&usize, &str> = map.to_borrowed_keys_values();
439 ///
440 /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
441 /// ```
442 pub fn to_borrowed_keys_values<KB: ?Sized, VB: ?Sized, SB>(
443 &'a self,
444 ) -> LiteMap<&'a KB, &'a VB, SB>
445 where
446 K: Borrow<KB>,
447 V: Borrow<VB>,
448 SB: StoreMut<&'a KB, &'a VB>,
449 {
450 let mut values = SB::lm_with_capacity(self.len());
451 for i in 0..self.len() {
452 #[expect(clippy::unwrap_used)] // iterating over our own length
453 let (k, v) = self.values.lm_get(i).unwrap();
454 values.lm_push(k.borrow(), v.borrow())
455 }
456 LiteMap {
457 values,
458 _key_type: PhantomData,
459 _value_type: PhantomData,
460 }
461 }
462
463 /// Returns a new [`LiteMap`] with keys borrowed from this one and cloned values.
464 ///
465 /// # Examples
466 ///
467 /// ```
468 /// use litemap::LiteMap;
469 ///
470 /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
471 /// map.insert(Box::new(1), "one".to_string());
472 /// map.insert(Box::new(2), "two".to_string());
473 ///
474 /// let borrowed_map: LiteMap<&usize, String> = map.to_borrowed_keys();
475 ///
476 /// assert_eq!(borrowed_map.get(&1), Some(&"one".to_string()));
477 /// ```
478 pub fn to_borrowed_keys<KB: ?Sized, SB>(&'a self) -> LiteMap<&'a KB, V, SB>
479 where
480 K: Borrow<KB>,
481 V: Clone,
482 SB: StoreMut<&'a KB, V>,
483 {
484 let mut values = SB::lm_with_capacity(self.len());
485 for i in 0..self.len() {
486 #[expect(clippy::unwrap_used)] // iterating over our own length
487 let (k, v) = self.values.lm_get(i).unwrap();
488 values.lm_push(k.borrow(), v.clone())
489 }
490 LiteMap {
491 values,
492 _key_type: PhantomData,
493 _value_type: PhantomData,
494 }
495 }
496
497 /// Returns a new [`LiteMap`] with values borrowed from this one and cloned keys.
498 ///
499 /// # Examples
500 ///
501 /// ```
502 /// use litemap::LiteMap;
503 ///
504 /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
505 /// map.insert(Box::new(1), "one".to_string());
506 /// map.insert(Box::new(2), "two".to_string());
507 ///
508 /// let borrowed_map: LiteMap<Box<usize>, &str> = map.to_borrowed_values();
509 ///
510 /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
511 /// ```
512 pub fn to_borrowed_values<VB: ?Sized, SB>(&'a self) -> LiteMap<K, &'a VB, SB>
513 where
514 K: Clone,
515 V: Borrow<VB>,
516 SB: StoreMut<K, &'a VB>,
517 {
518 let mut values = SB::lm_with_capacity(self.len());
519 for i in 0..self.len() {
520 #[expect(clippy::unwrap_used)] // iterating over our own length
521 let (k, v) = self.values.lm_get(i).unwrap();
522 values.lm_push(k.clone(), v.borrow())
523 }
524 LiteMap {
525 values,
526 _key_type: PhantomData,
527 _value_type: PhantomData,
528 }
529 }
530}
531
532impl<K, V, S> LiteMap<K, V, S>
533where
534 S: StoreMut<K, V>,
535{
536 /// Construct a new [`LiteMap`] with a given capacity
537 pub fn with_capacity(capacity: usize) -> Self {
538 Self {
539 values: S::lm_with_capacity(capacity),
540 _key_type: PhantomData,
541 _value_type: PhantomData,
542 }
543 }
544
545 /// Remove all elements from the [`LiteMap`]
546 pub fn clear(&mut self) {
547 self.values.lm_clear()
548 }
549
550 /// Reserve capacity for `additional` more elements to be inserted into
551 /// the [`LiteMap`] to avoid frequent reallocations.
552 ///
553 /// See [`Vec::reserve()`] for more information.
554 ///
555 /// [`Vec::reserve()`]: alloc::vec::Vec::reserve
556 pub fn reserve(&mut self, additional: usize) {
557 self.values.lm_reserve(additional)
558 }
559}
560
561impl<K, V, S> LiteMap<K, V, S>
562where
563 K: Ord,
564 S: StoreMut<K, V>,
565{
566 /// Get the value associated with `key`, if it exists, as a mutable reference.
567 ///
568 /// ```rust
569 /// use litemap::LiteMap;
570 ///
571 /// let mut map = LiteMap::new_vec();
572 /// map.insert(1, "one");
573 /// map.insert(2, "two");
574 /// if let Some(mut v) = map.get_mut(&1) {
575 /// *v = "uno";
576 /// }
577 /// assert_eq!(map.get(&1), Some(&"uno"));
578 /// ```
579 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
580 where
581 K: Borrow<Q>,
582 Q: Ord + ?Sized,
583 {
584 match self.find_index(key) {
585 #[expect(clippy::unwrap_used)] // find_index returns a valid index
586 Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1),
587 Err(_) => None,
588 }
589 }
590
591 /// Appends `value` with `key` to the end of the underlying vector, returning
592 /// `key` and `value` _if it failed_. Useful for extending with an existing
593 /// sorted list.
594 /// ```rust
595 /// use litemap::LiteMap;
596 ///
597 /// let mut map = LiteMap::new_vec();
598 /// assert!(map.try_append(1, "uno").is_none());
599 /// assert!(map.try_append(3, "tres").is_none());
600 ///
601 /// assert!(
602 /// matches!(map.try_append(3, "tres-updated"), Some((3, "tres-updated"))),
603 /// "append duplicate of last key",
604 /// );
605 ///
606 /// assert!(
607 /// matches!(map.try_append(2, "dos"), Some((2, "dos"))),
608 /// "append out of order"
609 /// );
610 ///
611 /// assert_eq!(map.get(&1), Some(&"uno"));
612 ///
613 /// // contains the original value for the key: 3
614 /// assert_eq!(map.get(&3), Some(&"tres"));
615 ///
616 /// // not appended since it wasn't in order
617 /// assert_eq!(map.get(&2), None);
618 /// ```
619 #[must_use]
620 pub fn try_append(&mut self, key: K, value: V) -> Option<(K, V)> {
621 if let Some(last) = self.values.lm_last() {
622 if last.0 >= &key {
623 return Some((key, value));
624 }
625 }
626
627 self.values.lm_push(key, value);
628 None
629 }
630
631 /// Insert `value` with `key`, returning the existing value if it exists.
632 ///
633 /// ```rust
634 /// use litemap::LiteMap;
635 ///
636 /// let mut map = LiteMap::new_vec();
637 /// map.insert(1, "one");
638 /// map.insert(2, "two");
639 /// assert_eq!(map.get(&1), Some(&"one"));
640 /// assert_eq!(map.get(&3), None);
641 /// ```
642 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
643 self.insert_save_key(key, value).map(|(_, v)| v)
644 }
645
646 /// Version of [`Self::insert()`] that returns both the key and the old value.
647 fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> {
648 match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
649 #[expect(clippy::unwrap_used)] // Index came from binary_search
650 Ok(found) => Some((
651 key,
652 mem::replace(self.values.lm_get_mut(found).unwrap().1, value),
653 )),
654 Err(ins) => {
655 self.values.lm_insert(ins, key, value);
656 None
657 }
658 }
659 }
660
661 /// Attempts to insert a unique entry into the map.
662 ///
663 /// If `key` is not already in the map, inserts it with the corresponding `value`
664 /// and returns `None`.
665 ///
666 /// If `key` is already in the map, no change is made to the map, and the key and value
667 /// are returned back to the caller.
668 ///
669 /// ```
670 /// use litemap::LiteMap;
671 ///
672 /// let mut map = LiteMap::new_vec();
673 /// map.insert(1, "one");
674 /// map.insert(3, "three");
675 ///
676 /// // 2 is not yet in the map...
677 /// assert_eq!(map.try_insert(2, "two"), None);
678 /// assert_eq!(map.len(), 3);
679 ///
680 /// // ...but now it is.
681 /// assert_eq!(map.try_insert(2, "TWO"), Some((2, "TWO")));
682 /// assert_eq!(map.len(), 3);
683 /// ```
684 pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> {
685 match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
686 Ok(_) => Some((key, value)),
687 Err(ins) => {
688 self.values.lm_insert(ins, key, value);
689 None
690 }
691 }
692 }
693
694 /// Attempts to insert a unique entry into the map.
695 ///
696 /// If `key` is not already in the map, invokes the closure to compute `value`, inserts
697 /// the pair into the map, and returns a reference to the value. The closure is passed
698 /// a reference to the `key` argument.
699 ///
700 /// If `key` is already in the map, a reference to the existing value is returned.
701 ///
702 /// Additionally, the index of the value in the map is returned. If it is not desirable
703 /// to hold on to the mutable reference's lifetime, the index can be used to access the
704 /// element via [`LiteMap::get_indexed()`].
705 ///
706 /// The closure returns a `Result` to allow for a fallible insertion function. If the
707 /// creation of `value` is infallible, you can use [`core::convert::Infallible`].
708 ///
709 /// ```
710 /// use litemap::LiteMap;
711 ///
712 /// /// Helper function to unwrap an `Infallible` result from the insertion function
713 /// fn unwrap_infallible<T>(result: Result<T, core::convert::Infallible>) -> T {
714 /// result.unwrap_or_else(|never| match never {})
715 /// }
716 ///
717 /// let mut map = LiteMap::new_vec();
718 /// map.insert(1, "one");
719 /// map.insert(3, "three");
720 ///
721 /// // 2 is not yet in the map...
722 /// let result1 = unwrap_infallible(
723 /// map.try_get_or_insert(2, |_| Ok("two"))
724 /// );
725 /// assert_eq!(result1.1, &"two");
726 /// assert_eq!(map.len(), 3);
727 ///
728 /// // ...but now it is.
729 /// let result1 = unwrap_infallible(
730 /// map.try_get_or_insert(2, |_| Ok("TWO"))
731 /// );
732 /// assert_eq!(result1.1, &"two");
733 /// assert_eq!(map.len(), 3);
734 /// ```
735 pub fn try_get_or_insert<E>(
736 &mut self,
737 key: K,
738 value: impl FnOnce(&K) -> Result<V, E>,
739 ) -> Result<(usize, &V), E> {
740 let idx = match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
741 Ok(idx) => idx,
742 Err(idx) => {
743 let value = value(&key)?;
744 self.values.lm_insert(idx, key, value);
745 idx
746 }
747 };
748 #[expect(clippy::unwrap_used)] // item at idx found or inserted above
749 Ok((idx, self.values.lm_get(idx).unwrap().1))
750 }
751
752 /// Remove the value at `key`, returning it if it exists.
753 ///
754 /// ```rust
755 /// use litemap::LiteMap;
756 ///
757 /// let mut map = LiteMap::new_vec();
758 /// map.insert(1, "one");
759 /// map.insert(2, "two");
760 /// assert_eq!(map.remove(&1), Some("one"));
761 /// assert_eq!(map.get(&1), None);
762 /// ```
763 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
764 where
765 K: Borrow<Q>,
766 Q: Ord + ?Sized,
767 {
768 match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) {
769 Ok(found) => Some(self.values.lm_remove(found).1),
770 Err(_) => None,
771 }
772 }
773}
774
775impl<K, V, S> LiteMap<K, V, S>
776where
777 K: Ord,
778 S: StoreIntoIterator<K, V> + StoreFromIterator<K, V>,
779{
780 /// Insert all elements from `other` into this `LiteMap`.
781 ///
782 /// If `other` contains keys that already exist in `self`, the values in `other` replace the
783 /// corresponding ones in `self`, and the rejected items from `self` are returned as a new
784 /// `LiteMap`. Otherwise, `None` is returned.
785 ///
786 /// The implementation of this function is optimized if `self` and `other` have no overlap.
787 ///
788 /// # Examples
789 ///
790 /// ```
791 /// use litemap::LiteMap;
792 ///
793 /// let mut map1 = LiteMap::new_vec();
794 /// map1.insert(1, "one");
795 /// map1.insert(2, "two");
796 ///
797 /// let mut map2 = LiteMap::new_vec();
798 /// map2.insert(2, "TWO");
799 /// map2.insert(4, "FOUR");
800 ///
801 /// let leftovers = map1.extend_from_litemap(map2);
802 ///
803 /// assert_eq!(map1.len(), 3);
804 /// assert_eq!(map1.get(&1), Some("one").as_ref());
805 /// assert_eq!(map1.get(&2), Some("TWO").as_ref());
806 /// assert_eq!(map1.get(&4), Some("FOUR").as_ref());
807 ///
808 /// let map3 = leftovers.expect("Duplicate keys");
809 /// assert_eq!(map3.len(), 1);
810 /// assert_eq!(map3.get(&2), Some("two").as_ref());
811 /// ```
812 pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> {
813 if self.is_empty() {
814 self.values = other.values;
815 return None;
816 }
817 if other.is_empty() {
818 return None;
819 }
820 if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) {
821 // append other to self
822 self.values.lm_extend_end(other.values);
823 None
824 } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) {
825 // prepend other to self
826 self.values.lm_extend_start(other.values);
827 None
828 } else {
829 // insert every element
830 let leftover_tuples = other
831 .values
832 .lm_into_iter()
833 .filter_map(|(k, v)| self.insert_save_key(k, v))
834 .collect();
835 let ret = LiteMap {
836 values: leftover_tuples,
837 _key_type: PhantomData,
838 _value_type: PhantomData,
839 };
840 if ret.is_empty() {
841 None
842 } else {
843 Some(ret)
844 }
845 }
846 }
847}
848
849impl<K, V, S> Default for LiteMap<K, V, S>
850where
851 S: Store<K, V> + Default,
852{
853 fn default() -> Self {
854 Self {
855 values: S::default(),
856 _key_type: PhantomData,
857 _value_type: PhantomData,
858 }
859 }
860}
861impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S>
862where
863 K: Ord,
864 S: Store<K, V>,
865{
866 type Output = V;
867 fn index(&self, key: &K) -> &V {
868 #[expect(clippy::panic)] // documented
869 match self.get(key) {
870 Some(v) => v,
871 None => panic!("no entry found for key"),
872 }
873 }
874}
875impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S>
876where
877 K: Ord,
878 S: StoreMut<K, V>,
879{
880 fn index_mut(&mut self, key: &K) -> &mut V {
881 #[expect(clippy::panic)] // documented
882 match self.get_mut(key) {
883 Some(v) => v,
884 None => panic!("no entry found for key"),
885 }
886 }
887}
888impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S>
889where
890 K: Ord,
891 S: StoreFromIterable<K, V>,
892{
893 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
894 let values = S::lm_sort_from_iter(iter);
895 Self::from_sorted_store_unchecked(values)
896 }
897}
898
899impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
900where
901 S: StoreIterable<'a, K, V>,
902{
903 /// Produce an ordered iterator over key-value pairs
904 pub fn iter(&'a self) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)> {
905 self.values.lm_iter()
906 }
907
908 /// Produce an ordered iterator over keys
909 #[deprecated = "use keys() instead"]
910 pub fn iter_keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> {
911 self.values.lm_iter().map(|val| val.0)
912 }
913
914 /// Produce an iterator over values, ordered by their keys
915 #[deprecated = "use values() instead"]
916 pub fn iter_values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> {
917 self.values.lm_iter().map(|val| val.1)
918 }
919
920 /// Produce an ordered iterator over keys
921 pub fn keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> {
922 self.values.lm_iter().map(|val| val.0)
923 }
924
925 /// Produce an iterator over values, ordered by their keys
926 pub fn values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> {
927 self.values.lm_iter().map(|val| val.1)
928 }
929}
930
931impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
932where
933 S: StoreIterableMut<'a, K, V>,
934{
935 /// Produce an ordered mutable iterator over key-value pairs
936 pub fn iter_mut(&'a mut self) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)> {
937 self.values.lm_iter_mut()
938 }
939}
940
941impl<K, V, S> IntoIterator for LiteMap<K, V, S>
942where
943 S: StoreIntoIterator<K, V>,
944{
945 type Item = (K, V);
946 type IntoIter = S::KeyValueIntoIter;
947
948 fn into_iter(self) -> Self::IntoIter {
949 self.values.lm_into_iter()
950 }
951}
952
953impl<'a, K, V, S> IntoIterator for &'a LiteMap<K, V, S>
954where
955 S: StoreIterable<'a, K, V>,
956{
957 type Item = (&'a K, &'a V);
958 type IntoIter = S::KeyValueIter;
959
960 fn into_iter(self) -> Self::IntoIter {
961 self.values.lm_iter()
962 }
963}
964
965impl<'a, K, V, S> IntoIterator for &'a mut LiteMap<K, V, S>
966where
967 S: StoreIterableMut<'a, K, V>,
968{
969 type Item = (&'a K, &'a mut V);
970 type IntoIter = S::KeyValueIterMut;
971
972 fn into_iter(self) -> Self::IntoIter {
973 self.values.lm_iter_mut()
974 }
975}
976
977impl<K, V, S> LiteMap<K, V, S>
978where
979 S: StoreBulkMut<K, V>,
980{
981 /// Retains only the elements specified by the predicate.
982 ///
983 /// In other words, remove all elements such that `f((&k, &v))` returns `false`.
984 ///
985 /// # Example
986 ///
987 /// ```rust
988 /// use litemap::LiteMap;
989 ///
990 /// let mut map = LiteMap::new_vec();
991 /// map.insert(1, "one");
992 /// map.insert(2, "two");
993 /// map.insert(3, "three");
994 ///
995 /// // Retain elements with odd keys
996 /// map.retain(|k, _| k % 2 == 1);
997 ///
998 /// assert_eq!(map.get(&1), Some(&"one"));
999 /// assert_eq!(map.get(&2), None);
1000 /// ```
1001 #[inline]
1002 pub fn retain<F>(&mut self, predicate: F)
1003 where
1004 F: FnMut(&K, &V) -> bool,
1005 {
1006 self.values.lm_retain(predicate)
1007 }
1008}
1009
1010impl<'a, K, V> LiteMap<K, V, &'a [(K, V)]> {
1011 /// Const version of [`LiteMap::len()`] for a slice store.
1012 ///
1013 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1014 ///
1015 /// # Examples
1016 ///
1017 /// ```rust
1018 /// use litemap::LiteMap;
1019 ///
1020 /// const MAP: LiteMap<&str, usize, &[(&str, usize)]> =
1021 /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]);
1022 /// assert_eq!(const { MAP.const_len() }, 2);
1023 /// ```
1024 #[inline]
1025 pub const fn const_len(&self) -> usize {
1026 self.values.len()
1027 }
1028
1029 /// Const version of [`LiteMap::is_empty()`] for a slice store.
1030 ///
1031 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1032 ///
1033 /// # Examples
1034 ///
1035 /// ```rust
1036 /// use litemap::LiteMap;
1037 ///
1038 /// const MAP: LiteMap<&str, usize, &[(&str, usize)]> =
1039 /// LiteMap::from_sorted_store_unchecked(&[]);
1040 /// assert!(const { MAP.const_is_empty() });
1041 /// ```
1042 #[inline]
1043 pub const fn const_is_empty(&self) -> bool {
1044 self.values.is_empty()
1045 }
1046
1047 /// Const version of [`LiteMap::get_indexed()`] for a slice store.
1048 ///
1049 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1050 ///
1051 /// # Panics
1052 ///
1053 /// Panics if the index is out of bounds.
1054 ///
1055 /// # Examples
1056 ///
1057 /// ```rust
1058 /// use litemap::LiteMap;
1059 ///
1060 /// const MAP: LiteMap<&str, usize, &[(&str, usize)]> =
1061 /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]);
1062 /// assert_eq!(const { *MAP.const_get_indexed_or_panic(0) }, ("a", 11));
1063 /// ```
1064 #[inline]
1065 #[expect(clippy::indexing_slicing)] // documented
1066 pub const fn const_get_indexed_or_panic(&self, index: usize) -> &'a (K, V) {
1067 &self.values[index]
1068 }
1069}
1070
1071const fn const_cmp_bytes(a: &[u8], b: &[u8]) -> Ordering {
1072 let (max, default) = if a.len() == b.len() {
1073 (a.len(), Ordering::Equal)
1074 } else if a.len() < b.len() {
1075 (a.len(), Ordering::Less)
1076 } else {
1077 (b.len(), Ordering::Greater)
1078 };
1079 let mut i = 0;
1080 #[expect(clippy::indexing_slicing)] // indexes in range by above checks
1081 while i < max {
1082 if a[i] == b[i] {
1083 i += 1;
1084 continue;
1085 } else if a[i] < b[i] {
1086 return Ordering::Less;
1087 } else {
1088 return Ordering::Greater;
1089 }
1090 }
1091 default
1092}
1093
1094impl<'a, V> LiteMap<&'a str, V, &'a [(&'a str, V)]> {
1095 /// Const function to get the value associated with a `&str` key, if it exists.
1096 ///
1097 /// Also returns the index of the value.
1098 ///
1099 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1100 ///
1101 /// # Examples
1102 ///
1103 /// ```rust
1104 /// use litemap::LiteMap;
1105 ///
1106 /// const MAP: LiteMap<&str, usize, &[(&str, usize)]> =
1107 /// LiteMap::from_sorted_store_unchecked(&[
1108 /// ("abc", 11),
1109 /// ("bcd", 22),
1110 /// ("cde", 33),
1111 /// ("def", 44),
1112 /// ("efg", 55),
1113 /// ]);
1114 ///
1115 /// assert_eq!(const { MAP.const_get_with_index("def") }, Some((3, &44)));
1116 ///
1117 /// assert_eq!(const { MAP.const_get_with_index("dng") }, None);
1118 /// ```
1119 pub const fn const_get_with_index(&self, key: &str) -> Option<(usize, &'a V)> {
1120 let mut i = 0;
1121 let mut j = self.const_len();
1122 while i < j {
1123 let mid = (i + j) / 2;
1124 #[expect(clippy::indexing_slicing)] // in range
1125 let x = &self.values[mid];
1126 match const_cmp_bytes(key.as_bytes(), x.0.as_bytes()) {
1127 Ordering::Equal => return Some((mid, &x.1)),
1128 Ordering::Greater => i = mid + 1,
1129 Ordering::Less => j = mid,
1130 };
1131 }
1132 None
1133 }
1134}
1135
1136impl<'a, V> LiteMap<&'a [u8], V, &'a [(&'a [u8], V)]> {
1137 /// Const function to get the value associated with a `&[u8]` key, if it exists.
1138 ///
1139 /// Also returns the index of the value.
1140 ///
1141 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1142 ///
1143 /// # Examples
1144 ///
1145 /// ```rust
1146 /// use litemap::LiteMap;
1147 ///
1148 /// const MAP: LiteMap<&[u8], usize, &[(&[u8], usize)]> =
1149 /// LiteMap::from_sorted_store_unchecked(&[
1150 /// (b"abc", 11),
1151 /// (b"bcd", 22),
1152 /// (b"cde", 33),
1153 /// (b"def", 44),
1154 /// (b"efg", 55),
1155 /// ]);
1156 ///
1157 /// assert_eq!(const { MAP.const_get_with_index(b"def") }, Some((3, &44)));
1158 ///
1159 /// assert_eq!(const { MAP.const_get_with_index(b"dng") }, None);
1160 /// ```
1161 pub const fn const_get_with_index(&self, key: &[u8]) -> Option<(usize, &'a V)> {
1162 let mut i = 0;
1163 let mut j = self.const_len();
1164 while i < j {
1165 let mid = (i + j) / 2;
1166 #[expect(clippy::indexing_slicing)] // in range
1167 let x = &self.values[mid];
1168 match const_cmp_bytes(key, x.0) {
1169 Ordering::Equal => return Some((mid, &x.1)),
1170 Ordering::Greater => i = mid + 1,
1171 Ordering::Less => j = mid,
1172 };
1173 }
1174 None
1175 }
1176}
1177
1178macro_rules! impl_const_get_with_index_for_integer {
1179 ($integer:ty) => {
1180 impl<'a, V> LiteMap<$integer, V, &'a [($integer, V)]> {
1181 /// Const function to get the value associated with an integer key, if it exists.
1182 ///
1183 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1184 ///
1185 /// Also returns the index of the value.
1186 pub const fn const_get_with_index(&self, key: $integer) -> Option<(usize, &'a V)> {
1187 let mut i = 0;
1188 let mut j = self.const_len();
1189 while i < j {
1190 let mid = (i + j) / 2;
1191 #[expect(clippy::indexing_slicing)] // in range
1192 let x = &self.values[mid];
1193 if key == x.0 {
1194 return Some((mid, &x.1));
1195 } else if key > x.0 {
1196 i = mid + 1;
1197 } else {
1198 j = mid;
1199 }
1200 }
1201 return None;
1202 }
1203 }
1204 };
1205}
1206
1207impl_const_get_with_index_for_integer!(u8);
1208impl_const_get_with_index_for_integer!(u16);
1209impl_const_get_with_index_for_integer!(u32);
1210impl_const_get_with_index_for_integer!(u64);
1211impl_const_get_with_index_for_integer!(u128);
1212impl_const_get_with_index_for_integer!(usize);
1213impl_const_get_with_index_for_integer!(i8);
1214impl_const_get_with_index_for_integer!(i16);
1215impl_const_get_with_index_for_integer!(i32);
1216impl_const_get_with_index_for_integer!(i64);
1217impl_const_get_with_index_for_integer!(i128);
1218impl_const_get_with_index_for_integer!(isize);
1219
1220/// An entry in a `LiteMap`, which may be either occupied or vacant.
1221#[allow(clippy::exhaustive_enums)]
1222pub enum Entry<'a, K, V, S> {
1223 Occupied(OccupiedEntry<'a, K, V, S>),
1224 Vacant(VacantEntry<'a, K, V, S>),
1225}
1226
1227impl<K, V, S> Debug for Entry<'_, K, V, S> {
1228 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1229 match self {
1230 Self::Occupied(arg0) => f.debug_tuple("Occupied").field(arg0).finish(),
1231 Self::Vacant(arg0) => f.debug_tuple("Vacant").field(arg0).finish(),
1232 }
1233 }
1234}
1235
1236/// A view into an occupied entry in a `LiteMap`.
1237pub struct OccupiedEntry<'a, K, V, S> {
1238 map: &'a mut LiteMap<K, V, S>,
1239 index: usize,
1240}
1241
1242impl<K, V, S> Debug for OccupiedEntry<'_, K, V, S> {
1243 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1244 f.debug_struct("OccupiedEntry")
1245 .field("index", &self.index)
1246 .finish()
1247 }
1248}
1249
1250/// A view into a vacant entry in a `LiteMap`.
1251pub struct VacantEntry<'a, K, V, S> {
1252 map: &'a mut LiteMap<K, V, S>,
1253 key: K,
1254 index: usize,
1255}
1256
1257impl<K, V, S> Debug for VacantEntry<'_, K, V, S> {
1258 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1259 f.debug_struct("VacantEntry")
1260 .field("index", &self.index)
1261 .finish()
1262 }
1263}
1264
1265impl<'a, K, V, S> Entry<'a, K, V, S>
1266where
1267 K: Ord,
1268 S: StoreMut<K, V>,
1269{
1270 /// Ensures a value is in the entry by inserting the default value if empty,
1271 /// and returns a mutable reference to the value in the entry.
1272 pub fn or_insert(self, default: V) -> &'a mut V {
1273 match self {
1274 Entry::Occupied(entry) => entry.into_mut(),
1275 Entry::Vacant(entry) => entry.insert(default),
1276 }
1277 }
1278
1279 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1280 /// and returns a mutable reference to the value in the entry.
1281 pub fn or_default(self) -> &'a mut V
1282 where
1283 V: Default,
1284 {
1285 self.or_insert(V::default())
1286 }
1287
1288 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1289 /// and returns a mutable reference to the value in the entry.
1290 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1291 match self {
1292 Entry::Occupied(entry) => entry.into_mut(),
1293 Entry::Vacant(entry) => entry.insert(default()),
1294 }
1295 }
1296
1297 /// Provides in-place mutable access to an occupied entry before any
1298 /// potential inserts into the map.
1299 pub fn and_modify<F>(self, f: F) -> Self
1300 where
1301 F: FnOnce(&mut V),
1302 {
1303 match self {
1304 Entry::Occupied(mut entry) => {
1305 f(entry.get_mut());
1306 Entry::Occupied(entry)
1307 }
1308 Entry::Vacant(entry) => Entry::Vacant(entry),
1309 }
1310 }
1311}
1312
1313impl<'a, K, V, S> OccupiedEntry<'a, K, V, S>
1314where
1315 K: Ord,
1316 S: StoreMut<K, V>,
1317{
1318 /// Gets a reference to the key in the entry.
1319 pub fn key(&self) -> &K {
1320 #[expect(clippy::unwrap_used)] // index is valid while we have a reference to the map
1321 self.map.values.lm_get(self.index).unwrap().0
1322 }
1323
1324 /// Gets a reference to the value in the entry.
1325 pub fn get(&self) -> &V {
1326 #[expect(clippy::unwrap_used)] // index is valid while we have a reference to the map
1327 self.map.values.lm_get(self.index).unwrap().1
1328 }
1329
1330 /// Gets a mutable reference to the value in the entry.
1331 pub fn get_mut(&mut self) -> &mut V {
1332 #[expect(clippy::unwrap_used)] // index is valid while we have a reference to the map
1333 self.map.values.lm_get_mut(self.index).unwrap().1
1334 }
1335
1336 /// Converts the entry into a mutable reference to the value in the entry with a lifetime bound to the map.
1337 pub fn into_mut(self) -> &'a mut V {
1338 #[expect(clippy::unwrap_used)] // index is valid while we have a reference to the map
1339 self.map.values.lm_get_mut(self.index).unwrap().1
1340 }
1341
1342 /// Sets the value of the entry, and returns the entry's old value.
1343 pub fn insert(&mut self, value: V) -> V {
1344 mem::replace(self.get_mut(), value)
1345 }
1346
1347 /// Takes the value out of the entry, and returns it.
1348 pub fn remove(self) -> V {
1349 self.map.values.lm_remove(self.index).1
1350 }
1351}
1352
1353impl<'a, K, V, S> VacantEntry<'a, K, V, S>
1354where
1355 K: Ord,
1356 S: StoreMut<K, V>,
1357{
1358 /// Gets a reference to the key that would be used when inserting a value through the `VacantEntry`.
1359 pub fn key(&self) -> &K {
1360 &self.key
1361 }
1362
1363 /// Sets the value of the entry with the `VacantEntry`'s key, and returns a mutable reference to it.
1364 pub fn insert(self, value: V) -> &'a mut V {
1365 // index is valid insert index that was found via binary search
1366 // it's valid while we have a reference to the map
1367 self.map.values.lm_insert(self.index, self.key, value);
1368 #[expect(clippy::unwrap_used)] // we inserted at self.index above
1369 self.map.values.lm_get_mut(self.index).unwrap().1
1370 }
1371}
1372
1373impl<K, V, S> LiteMap<K, V, S>
1374where
1375 K: Ord,
1376 S: StoreMut<K, V>,
1377{
1378 /// Gets the entry for the given key in the map for in-place manipulation.
1379 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S> {
1380 match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
1381 Ok(index) => Entry::Occupied(OccupiedEntry { map: self, index }),
1382 Err(index) => Entry::Vacant(VacantEntry {
1383 map: self,
1384 key,
1385 index,
1386 }),
1387 }
1388 }
1389}
1390
1391impl<K, V, S> Extend<(K, V)> for LiteMap<K, V, S>
1392where
1393 K: Ord,
1394 S: StoreBulkMut<K, V>,
1395{
1396 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
1397 self.values.lm_extend(iter)
1398 }
1399}
1400
1401#[cfg(test)]
1402mod test {
1403 use super::*;
1404
1405 #[test]
1406 fn from_iterator() {
1407 let mut expected = LiteMap::with_capacity(4);
1408 expected.insert(1, "updated-one");
1409 expected.insert(2, "original-two");
1410 expected.insert(3, "original-three");
1411 expected.insert(4, "updated-four");
1412
1413 let actual = [
1414 (1, "original-one"),
1415 (2, "original-two"),
1416 (4, "original-four"),
1417 (4, "updated-four"),
1418 (1, "updated-one"),
1419 (3, "original-three"),
1420 ]
1421 .into_iter()
1422 .collect::<LiteMap<_, _>>();
1423
1424 assert_eq!(expected, actual);
1425 }
1426
1427 #[test]
1428 fn extend() {
1429 let mut expected: LiteMap<i32, &str> = LiteMap::with_capacity(4);
1430 expected.insert(1, "updated-one");
1431 expected.insert(2, "original-two");
1432 expected.insert(3, "original-three");
1433 expected.insert(4, "updated-four");
1434
1435 let mut actual: LiteMap<i32, &str> = LiteMap::new();
1436 actual.insert(1, "original-one");
1437 actual.extend([
1438 (2, "original-two"),
1439 (4, "original-four"),
1440 (4, "updated-four"),
1441 (1, "updated-one"),
1442 (3, "original-three"),
1443 ]);
1444
1445 assert_eq!(expected, actual);
1446 }
1447
1448 #[test]
1449 fn extend2() {
1450 let mut map: LiteMap<usize, &str> = LiteMap::new();
1451 map.extend(make_13());
1452 map.extend(make_24());
1453 map.extend(make_24());
1454 map.extend(make_46());
1455 map.extend(make_13());
1456 map.extend(make_46());
1457 assert_eq!(map.len(), 5);
1458 }
1459
1460 fn make_13() -> LiteMap<usize, &'static str> {
1461 let mut result = LiteMap::new();
1462 result.insert(1, "one");
1463 result.insert(3, "three");
1464 result
1465 }
1466
1467 fn make_24() -> LiteMap<usize, &'static str> {
1468 let mut result = LiteMap::new();
1469 result.insert(2, "TWO");
1470 result.insert(4, "FOUR");
1471 result
1472 }
1473
1474 fn make_46() -> LiteMap<usize, &'static str> {
1475 let mut result = LiteMap::new();
1476 result.insert(4, "four");
1477 result.insert(6, "six");
1478 result
1479 }
1480
1481 #[test]
1482 fn extend_from_litemap_append() {
1483 let mut map = LiteMap::new();
1484 map.extend_from_litemap(make_13())
1485 .ok_or(())
1486 .expect_err("Append to empty map");
1487 map.extend_from_litemap(make_46())
1488 .ok_or(())
1489 .expect_err("Append to lesser map");
1490 assert_eq!(map.len(), 4);
1491 }
1492
1493 #[test]
1494 fn extend_from_litemap_prepend() {
1495 let mut map = LiteMap::new();
1496 map.extend_from_litemap(make_46())
1497 .ok_or(())
1498 .expect_err("Prepend to empty map");
1499 map.extend_from_litemap(make_13())
1500 .ok_or(())
1501 .expect_err("Prepend to lesser map");
1502 assert_eq!(map.len(), 4);
1503 }
1504
1505 #[test]
1506 fn extend_from_litemap_insert() {
1507 let mut map = LiteMap::new();
1508 map.extend_from_litemap(make_13())
1509 .ok_or(())
1510 .expect_err("Append to empty map");
1511 map.extend_from_litemap(make_24())
1512 .ok_or(())
1513 .expect_err("Insert with no conflict");
1514 map.extend_from_litemap(make_46())
1515 .ok_or(())
1516 .expect("Insert with conflict");
1517 assert_eq!(map.len(), 5);
1518 }
1519
1520 #[test]
1521 fn test_const_cmp_bytes() {
1522 let strs = &["a", "aa", "abc", "abde", "bcd", "bcde"];
1523 for i in 0..strs.len() {
1524 for j in 0..strs.len() {
1525 let a = strs[i].as_bytes();
1526 let b = strs[j].as_bytes();
1527 assert_eq!(a.cmp(b), const_cmp_bytes(a, b));
1528 }
1529 }
1530 }
1531
1532 #[test]
1533 fn into_iterator() {
1534 let mut map = LiteMap::<_, _, Vec<(_, _)>>::new();
1535 map.insert(4, "four");
1536 map.insert(6, "six");
1537 let mut reference = vec![(6, "six"), (4, "four")];
1538
1539 for i in map {
1540 let r = reference.pop().unwrap();
1541 assert_eq!(r, i);
1542 }
1543 assert!(reference.is_empty());
1544 }
1545
1546 #[test]
1547 fn entry_insert() {
1548 let mut map: LiteMap<i32, &str> = LiteMap::new();
1549 assert!(matches!(map.entry(1), Entry::Vacant(_)));
1550 map.entry(1).or_insert("one");
1551 assert!(matches!(map.entry(1), Entry::Occupied(_)));
1552 assert_eq!(map.get(&1), Some(&"one"));
1553 }
1554
1555 #[test]
1556 fn entry_insert_with() {
1557 let mut map: LiteMap<i32, &str> = LiteMap::new();
1558 assert!(matches!(map.entry(1), Entry::Vacant(_)));
1559 map.entry(1).or_insert_with(|| "one");
1560 assert!(matches!(map.entry(1), Entry::Occupied(_)));
1561 assert_eq!(map.get(&1), Some(&"one"));
1562 }
1563
1564 #[test]
1565 fn entry_vacant_insert() {
1566 let mut map: LiteMap<i32, &str> = LiteMap::new();
1567 if let Entry::Vacant(entry) = map.entry(1) {
1568 entry.insert("one");
1569 }
1570 assert_eq!(map.get(&1), Some(&"one"));
1571 }
1572
1573 #[test]
1574 fn entry_occupied_get_mut() {
1575 let mut map: LiteMap<i32, &str> = LiteMap::new();
1576 map.insert(1, "one");
1577 if let Entry::Occupied(mut entry) = map.entry(1) {
1578 *entry.get_mut() = "uno";
1579 }
1580 assert_eq!(map.get(&1), Some(&"uno"));
1581 }
1582
1583 #[test]
1584 fn entry_occupied_remove() {
1585 let mut map: LiteMap<i32, &str> = LiteMap::new();
1586 map.insert(1, "one");
1587 if let Entry::Occupied(entry) = map.entry(1) {
1588 entry.remove();
1589 }
1590 assert_eq!(map.get(&1), None);
1591 }
1592
1593 #[test]
1594 fn entry_occupied_key() {
1595 let mut map: LiteMap<i32, &str> = LiteMap::new();
1596 map.insert(1, "one");
1597 if let Entry::Occupied(entry) = map.entry(1) {
1598 assert_eq!(entry.key(), &1);
1599 }
1600 }
1601
1602 #[test]
1603 fn entry_occupied_get() {
1604 let mut map: LiteMap<i32, &str> = LiteMap::new();
1605 map.insert(1, "one");
1606 if let Entry::Occupied(entry) = map.entry(1) {
1607 assert_eq!(entry.get(), &"one");
1608 }
1609 }
1610
1611 #[test]
1612 fn entry_occupied_insert() {
1613 let mut map: LiteMap<i32, &str> = LiteMap::new();
1614 map.insert(1, "one");
1615 if let Entry::Occupied(mut entry) = map.entry(1) {
1616 assert_eq!(entry.insert("uno"), "one");
1617 }
1618 assert_eq!(map.get(&1), Some(&"uno"));
1619 }
1620
1621 #[test]
1622 fn entry_vacant_key() {
1623 let mut map: LiteMap<i32, &str> = LiteMap::new();
1624 if let Entry::Vacant(entry) = map.entry(1) {
1625 assert_eq!(entry.key(), &1);
1626 }
1627 }
1628
1629 #[test]
1630 fn entry_or_insert() {
1631 let mut map: LiteMap<i32, &str> = LiteMap::new();
1632 map.entry(1).or_insert("one");
1633 assert_eq!(map.get(&1), Some(&"one"));
1634 map.entry(1).or_insert("uno");
1635 assert_eq!(map.get(&1), Some(&"one"));
1636 }
1637
1638 #[test]
1639 fn entry_or_insert_with() {
1640 let mut map: LiteMap<i32, &str> = LiteMap::new();
1641 map.entry(1).or_insert_with(|| "one");
1642 assert_eq!(map.get(&1), Some(&"one"));
1643 map.entry(1).or_insert_with(|| "uno");
1644 assert_eq!(map.get(&1), Some(&"one"));
1645 }
1646
1647 #[test]
1648 fn entry_or_default() {
1649 let mut map: LiteMap<i32, String> = LiteMap::new();
1650 map.entry(1).or_default();
1651 assert_eq!(map.get(&1), Some(&String::new()));
1652 }
1653
1654 #[test]
1655 fn entry_and_modify() {
1656 let mut map: LiteMap<i32, i32> = LiteMap::new();
1657 map.entry(1).or_insert(10);
1658 map.entry(1).and_modify(|v| *v += 5);
1659 assert_eq!(map.get(&1), Some(&15));
1660 map.entry(2).and_modify(|v| *v += 5).or_insert(20);
1661 assert_eq!(map.get(&2), Some(&20));
1662 }
1663}