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