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::*;
6use alloc::borrow::Borrow;
7use alloc::boxed::Box;
8use alloc::vec::Vec;
9use core::cmp::Ordering;
10use core::iter::FromIterator;
11use core::marker::PhantomData;
12use core::mem;
13use core::ops::{Index, IndexMut, Range};
14
15/// A simple "flat" map based on a sorted vector
16///
17/// See the [module level documentation][super] for why one should use this.
18///
19/// The API is roughly similar to that of [`std::collections::BTreeMap`].
20#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
21#[cfg_attr(feature = "yoke", derive(yoke::Yokeable))]
22pub struct LiteMap<K: ?Sized, V: ?Sized, S = alloc::vec::Vec<(K, V)>> {
23 pub(crate) values: S,
24 pub(crate) _key_type: PhantomData<K>,
25 pub(crate) _value_type: PhantomData<V>,
26}
27
28impl<K, V> LiteMap<K, V> {
29 /// Construct a new [`LiteMap`] backed by Vec
30 pub const fn new_vec() -> Self {
31 Self {
32 values: alloc::vec::Vec::new(),
33 _key_type: PhantomData,
34 _value_type: PhantomData,
35 }
36 }
37}
38
39impl<K, V, S> LiteMap<K, V, S> {
40 /// Construct a new [`LiteMap`] using the given values
41 ///
42 /// The store must be sorted and have no duplicate keys.
43 pub const fn from_sorted_store_unchecked(values: S) -> Self {
44 Self {
45 values,
46 _key_type: PhantomData,
47 _value_type: PhantomData,
48 }
49 }
50}
51
52impl<K, V> LiteMap<K, V, Vec<(K, V)>> {
53 /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`.
54 #[inline]
55 pub fn into_tuple_vec(self) -> Vec<(K, V)> {
56 self.values
57 }
58}
59
60impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
61where
62 S: StoreConstEmpty<K, V>,
63{
64 /// Create a new empty [`LiteMap`]
65 pub const fn new() -> Self {
66 Self {
67 values: S::EMPTY,
68 _key_type: PhantomData,
69 _value_type: PhantomData,
70 }
71 }
72}
73
74impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
75where
76 S: Store<K, V>,
77{
78 /// The number of elements in the [`LiteMap`]
79 pub fn len(&self) -> usize {
80 self.values.lm_len()
81 }
82
83 /// Whether the [`LiteMap`] is empty
84 pub fn is_empty(&self) -> bool {
85 self.values.lm_is_empty()
86 }
87
88 /// Get the key-value pair residing at a particular index
89 ///
90 /// In most cases, prefer [`LiteMap::get()`] over this method.
91 #[inline]
92 pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> {
93 self.values.lm_get(index)
94 }
95
96 /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists.
97 ///
98 /// # Examples
99 ///
100 /// ```rust
101 /// use litemap::LiteMap;
102 ///
103 /// let mut map =
104 /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]);
105 ///
106 /// assert_eq!(map.first(), Some((&1, &"uno")));
107 /// ```
108 #[inline]
109 pub fn first(&self) -> Option<(&K, &V)> {
110 self.values.lm_get(0)
111 }
112
113 /// Get the highest-rank key/value pair from the `LiteMap`, if it exists.
114 ///
115 /// # Examples
116 ///
117 /// ```rust
118 /// use litemap::LiteMap;
119 ///
120 /// let mut map =
121 /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]);
122 ///
123 /// assert_eq!(map.last(), Some((&3, &"tres")));
124 /// ```
125 #[inline]
126 pub fn last(&self) -> Option<(&K, &V)> {
127 self.values.lm_last()
128 }
129
130 /// Returns a new [`LiteMap`] with owned keys and values.
131 ///
132 /// The trait bounds allow transforming most slice and string types.
133 ///
134 /// # Examples
135 ///
136 /// ```
137 /// use litemap::LiteMap;
138 ///
139 /// let mut map: LiteMap<&str, &str> = LiteMap::new_vec();
140 /// map.insert("one", "uno");
141 /// map.insert("two", "dos");
142 ///
143 /// let boxed_map: LiteMap<Box<str>, Box<str>> = map.to_boxed_keys_values();
144 ///
145 /// assert_eq!(boxed_map.get("one"), Some(&Box::from("uno")));
146 /// ```
147 pub fn to_boxed_keys_values<KB: ?Sized, VB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, Box<VB>, SB>
148 where
149 SB: StoreMut<Box<KB>, Box<VB>>,
150 K: Borrow<KB>,
151 V: Borrow<VB>,
152 Box<KB>: for<'a> From<&'a KB>,
153 Box<VB>: for<'a> From<&'a VB>,
154 {
155 let mut values = SB::lm_with_capacity(self.len());
156 for i in 0..self.len() {
157 #[allow(clippy::unwrap_used)] // iterating over our own length
158 let (k, v) = self.values.lm_get(i).unwrap();
159 values.lm_push(Box::from(k.borrow()), Box::from(v.borrow()))
160 }
161 LiteMap {
162 values,
163 _key_type: PhantomData,
164 _value_type: PhantomData,
165 }
166 }
167
168 /// Returns a new [`LiteMap`] with owned keys and cloned values.
169 ///
170 /// The trait bounds allow transforming most slice and string types.
171 ///
172 /// # Examples
173 ///
174 /// ```
175 /// use litemap::LiteMap;
176 ///
177 /// let mut map: LiteMap<&str, usize> = LiteMap::new_vec();
178 /// map.insert("one", 11);
179 /// map.insert("two", 22);
180 ///
181 /// let boxed_map: LiteMap<Box<str>, usize> = map.to_boxed_keys();
182 ///
183 /// assert_eq!(boxed_map.get("one"), Some(&11));
184 /// ```
185 pub fn to_boxed_keys<KB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, V, SB>
186 where
187 V: Clone,
188 SB: StoreMut<Box<KB>, V>,
189 K: Borrow<KB>,
190 Box<KB>: for<'a> From<&'a KB>,
191 {
192 let mut values = SB::lm_with_capacity(self.len());
193 for i in 0..self.len() {
194 #[allow(clippy::unwrap_used)] // iterating over our own length
195 let (k, v) = self.values.lm_get(i).unwrap();
196 values.lm_push(Box::from(k.borrow()), v.clone())
197 }
198 LiteMap {
199 values,
200 _key_type: PhantomData,
201 _value_type: PhantomData,
202 }
203 }
204
205 /// Returns a new [`LiteMap`] with cloned keys and owned values.
206 ///
207 /// The trait bounds allow transforming most slice and string types.
208 ///
209 /// # Examples
210 ///
211 /// ```
212 /// use litemap::LiteMap;
213 ///
214 /// let mut map: LiteMap<usize, &str> = LiteMap::new_vec();
215 /// map.insert(11, "uno");
216 /// map.insert(22, "dos");
217 ///
218 /// let boxed_map: LiteMap<usize, Box<str>> = map.to_boxed_values();
219 ///
220 /// assert_eq!(boxed_map.get(&11), Some(&Box::from("uno")));
221 /// ```
222 pub fn to_boxed_values<VB: ?Sized, SB>(&self) -> LiteMap<K, Box<VB>, SB>
223 where
224 K: Clone,
225 SB: StoreMut<K, Box<VB>>,
226 V: Borrow<VB>,
227 Box<VB>: for<'a> From<&'a VB>,
228 {
229 let mut values = SB::lm_with_capacity(self.len());
230 for i in 0..self.len() {
231 #[allow(clippy::unwrap_used)] // iterating over our own length
232 let (k, v) = self.values.lm_get(i).unwrap();
233 values.lm_push(k.clone(), Box::from(v.borrow()))
234 }
235 LiteMap {
236 values,
237 _key_type: PhantomData,
238 _value_type: PhantomData,
239 }
240 }
241}
242
243impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
244where
245 K: Ord,
246 S: Store<K, V>,
247{
248 /// Get the value associated with `key`, if it exists.
249 ///
250 /// ```rust
251 /// use litemap::LiteMap;
252 ///
253 /// let mut map = LiteMap::new_vec();
254 /// map.insert(1, "one");
255 /// map.insert(2, "two");
256 /// assert_eq!(map.get(&1), Some(&"one"));
257 /// assert_eq!(map.get(&3), None);
258 /// ```
259 pub fn get<Q>(&self, key: &Q) -> Option<&V>
260 where
261 K: Borrow<Q>,
262 Q: Ord + ?Sized,
263 {
264 match self.find_index(key) {
265 #[allow(clippy::unwrap_used)] // find_index returns a valid index
266 Ok(found) => Some(self.values.lm_get(found).unwrap().1),
267 Err(_) => None,
268 }
269 }
270
271 /// Binary search the map with `predicate` to find a key, returning the value.
272 pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> {
273 let index = self.values.lm_binary_search_by(predicate).ok()?;
274 self.values.lm_get(index).map(|(_, v)| v)
275 }
276
277 /// Returns whether `key` is contained in this map
278 ///
279 /// ```rust
280 /// use litemap::LiteMap;
281 ///
282 /// let mut map = LiteMap::new_vec();
283 /// map.insert(1, "one");
284 /// map.insert(2, "two");
285 /// assert!(map.contains_key(&1));
286 /// assert!(!map.contains_key(&3));
287 /// ```
288 pub fn contains_key<Q>(&self, key: &Q) -> bool
289 where
290 K: Borrow<Q>,
291 Q: Ord + ?Sized,
292 {
293 self.find_index(key).is_ok()
294 }
295
296 /// Obtain the index for a given key, or if the key is not found, the index
297 /// at which it would be inserted.
298 ///
299 /// (The return value works equivalently to [`slice::binary_search_by()`])
300 ///
301 /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using
302 /// [`Self::get()`] directly where possible.
303 #[inline]
304 pub fn find_index<Q>(&self, key: &Q) -> Result<usize, usize>
305 where
306 K: Borrow<Q>,
307 Q: Ord + ?Sized,
308 {
309 self.values.lm_binary_search_by(|k| k.borrow().cmp(key))
310 }
311}
312
313impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S>
314where
315 S: StoreSlice<K, V>,
316{
317 /// Creates a new [`LiteMap`] from a range of the current [`LiteMap`].
318 ///
319 /// # Examples
320 ///
321 /// ```
322 /// use litemap::LiteMap;
323 ///
324 /// let mut map = LiteMap::new_vec();
325 /// map.insert(1, "one");
326 /// map.insert(2, "two");
327 /// map.insert(3, "three");
328 ///
329 /// let mut sub_map = map.get_indexed_range(1..3).expect("valid range");
330 /// assert_eq!(sub_map.get(&1), None);
331 /// assert_eq!(sub_map.get(&2), Some(&"two"));
332 /// assert_eq!(sub_map.get(&3), Some(&"three"));
333 /// ```
334 pub fn get_indexed_range(&self, range: Range<usize>) -> Option<LiteMap<K, V, &S::Slice>> {
335 let subslice = self.values.lm_get_range(range)?;
336 Some(LiteMap {
337 values: subslice,
338 _key_type: PhantomData,
339 _value_type: PhantomData,
340 })
341 }
342
343 /// Borrows this [`LiteMap`] as one of its slice type.
344 ///
345 /// This can be useful in situations where you need a `LiteMap` by value but do not want
346 /// to clone the owned version.
347 ///
348 /// # Examples
349 ///
350 /// ```
351 /// use litemap::LiteMap;
352 ///
353 /// let mut map = LiteMap::new_vec();
354 /// map.insert(1, "one");
355 /// map.insert(2, "two");
356 ///
357 /// let borrowed_map = map.as_sliced();
358 /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
359 /// assert_eq!(borrowed_map.get(&2), Some(&"two"));
360 /// ```
361 pub fn as_sliced(&self) -> LiteMap<K, V, &S::Slice> {
362 // Won't panic: 0..self.len() is within range
363 #[allow(clippy::unwrap_used)]
364 let subslice = self.values.lm_get_range(0..self.len()).unwrap();
365 LiteMap {
366 values: subslice,
367 _key_type: PhantomData,
368 _value_type: PhantomData,
369 }
370 }
371
372 /// Borrows the backing buffer of this [`LiteMap`] as its slice type.
373 ///
374 /// The slice will be sorted.
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 slice = map.as_slice();
386 /// assert_eq!(slice, &[(1, "one"), (2, "two")]);
387 /// ```
388 pub fn as_slice(&self) -> &S::Slice {
389 // Won't panic: 0..self.len() is within range
390 #[allow(clippy::unwrap_used)]
391 self.values.lm_get_range(0..self.len()).unwrap()
392 }
393}
394
395impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
396where
397 S: Store<K, V>,
398{
399 /// Returns a new [`LiteMap`] with keys and values borrowed from this one.
400 ///
401 /// # Examples
402 ///
403 /// ```
404 /// use litemap::LiteMap;
405 ///
406 /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
407 /// map.insert(Box::new(1), "one".to_string());
408 /// map.insert(Box::new(2), "two".to_string());
409 ///
410 /// let borrowed_map: LiteMap<&usize, &str> = map.to_borrowed_keys_values();
411 ///
412 /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
413 /// ```
414 pub fn to_borrowed_keys_values<KB: ?Sized, VB: ?Sized, SB>(
415 &'a self,
416 ) -> LiteMap<&'a KB, &'a VB, SB>
417 where
418 K: Borrow<KB>,
419 V: Borrow<VB>,
420 SB: StoreMut<&'a KB, &'a VB>,
421 {
422 let mut values = SB::lm_with_capacity(self.len());
423 for i in 0..self.len() {
424 #[allow(clippy::unwrap_used)] // iterating over our own length
425 let (k, v) = self.values.lm_get(i).unwrap();
426 values.lm_push(k.borrow(), v.borrow())
427 }
428 LiteMap {
429 values,
430 _key_type: PhantomData,
431 _value_type: PhantomData,
432 }
433 }
434
435 /// Returns a new [`LiteMap`] with keys borrowed from this one and cloned values.
436 ///
437 /// # Examples
438 ///
439 /// ```
440 /// use litemap::LiteMap;
441 ///
442 /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
443 /// map.insert(Box::new(1), "one".to_string());
444 /// map.insert(Box::new(2), "two".to_string());
445 ///
446 /// let borrowed_map: LiteMap<&usize, String> = map.to_borrowed_keys();
447 ///
448 /// assert_eq!(borrowed_map.get(&1), Some(&"one".to_string()));
449 /// ```
450 pub fn to_borrowed_keys<KB: ?Sized, SB>(&'a self) -> LiteMap<&'a KB, V, SB>
451 where
452 K: Borrow<KB>,
453 V: Clone,
454 SB: StoreMut<&'a KB, V>,
455 {
456 let mut values = SB::lm_with_capacity(self.len());
457 for i in 0..self.len() {
458 #[allow(clippy::unwrap_used)] // iterating over our own length
459 let (k, v) = self.values.lm_get(i).unwrap();
460 values.lm_push(k.borrow(), v.clone())
461 }
462 LiteMap {
463 values,
464 _key_type: PhantomData,
465 _value_type: PhantomData,
466 }
467 }
468
469 /// Returns a new [`LiteMap`] with values borrowed from this one and cloned keys.
470 ///
471 /// # Examples
472 ///
473 /// ```
474 /// use litemap::LiteMap;
475 ///
476 /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec();
477 /// map.insert(Box::new(1), "one".to_string());
478 /// map.insert(Box::new(2), "two".to_string());
479 ///
480 /// let borrowed_map: LiteMap<Box<usize>, &str> = map.to_borrowed_values();
481 ///
482 /// assert_eq!(borrowed_map.get(&1), Some(&"one"));
483 /// ```
484 pub fn to_borrowed_values<VB: ?Sized, SB>(&'a self) -> LiteMap<K, &'a VB, SB>
485 where
486 K: Clone,
487 V: Borrow<VB>,
488 SB: StoreMut<K, &'a VB>,
489 {
490 let mut values = SB::lm_with_capacity(self.len());
491 for i in 0..self.len() {
492 #[allow(clippy::unwrap_used)] // iterating over our own length
493 let (k, v) = self.values.lm_get(i).unwrap();
494 values.lm_push(k.clone(), v.borrow())
495 }
496 LiteMap {
497 values,
498 _key_type: PhantomData,
499 _value_type: PhantomData,
500 }
501 }
502}
503
504impl<K, V, S> LiteMap<K, V, S>
505where
506 S: StoreMut<K, V>,
507{
508 /// Construct a new [`LiteMap`] with a given capacity
509 pub fn with_capacity(capacity: usize) -> Self {
510 Self {
511 values: S::lm_with_capacity(capacity),
512 _key_type: PhantomData,
513 _value_type: PhantomData,
514 }
515 }
516
517 /// Remove all elements from the [`LiteMap`]
518 pub fn clear(&mut self) {
519 self.values.lm_clear()
520 }
521
522 /// Reserve capacity for `additional` more elements to be inserted into
523 /// the [`LiteMap`] to avoid frequent reallocations.
524 ///
525 /// See [`Vec::reserve()`] for more information.
526 ///
527 /// [`Vec::reserve()`]: alloc::vec::Vec::reserve
528 pub fn reserve(&mut self, additional: usize) {
529 self.values.lm_reserve(additional)
530 }
531}
532
533impl<K, V, S> LiteMap<K, V, S>
534where
535 K: Ord,
536 S: StoreMut<K, V>,
537{
538 /// Get the value associated with `key`, if it exists, as a mutable reference.
539 ///
540 /// ```rust
541 /// use litemap::LiteMap;
542 ///
543 /// let mut map = LiteMap::new_vec();
544 /// map.insert(1, "one");
545 /// map.insert(2, "two");
546 /// if let Some(mut v) = map.get_mut(&1) {
547 /// *v = "uno";
548 /// }
549 /// assert_eq!(map.get(&1), Some(&"uno"));
550 /// ```
551 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
552 where
553 K: Borrow<Q>,
554 Q: Ord + ?Sized,
555 {
556 match self.find_index(key) {
557 #[allow(clippy::unwrap_used)] // find_index returns a valid index
558 Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1),
559 Err(_) => None,
560 }
561 }
562
563 /// Appends `value` with `key` to the end of the underlying vector, returning
564 /// `key` and `value` _if it failed_. Useful for extending with an existing
565 /// sorted list.
566 /// ```rust
567 /// use litemap::LiteMap;
568 ///
569 /// let mut map = LiteMap::new_vec();
570 /// assert!(map.try_append(1, "uno").is_none());
571 /// assert!(map.try_append(3, "tres").is_none());
572 ///
573 /// assert!(
574 /// matches!(map.try_append(3, "tres-updated"), Some((3, "tres-updated"))),
575 /// "append duplicate of last key",
576 /// );
577 ///
578 /// assert!(
579 /// matches!(map.try_append(2, "dos"), Some((2, "dos"))),
580 /// "append out of order"
581 /// );
582 ///
583 /// assert_eq!(map.get(&1), Some(&"uno"));
584 ///
585 /// // contains the original value for the key: 3
586 /// assert_eq!(map.get(&3), Some(&"tres"));
587 ///
588 /// // not appended since it wasn't in order
589 /// assert_eq!(map.get(&2), None);
590 /// ```
591 #[must_use]
592 pub fn try_append(&mut self, key: K, value: V) -> Option<(K, V)> {
593 if let Some(last) = self.values.lm_last() {
594 if last.0 >= &key {
595 return Some((key, value));
596 }
597 }
598
599 self.values.lm_push(key, value);
600 None
601 }
602
603 /// Insert `value` with `key`, returning the existing value if it exists.
604 ///
605 /// ```rust
606 /// use litemap::LiteMap;
607 ///
608 /// let mut map = LiteMap::new_vec();
609 /// map.insert(1, "one");
610 /// map.insert(2, "two");
611 /// assert_eq!(map.get(&1), Some(&"one"));
612 /// assert_eq!(map.get(&3), None);
613 /// ```
614 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
615 self.insert_save_key(key, value).map(|(_, v)| v)
616 }
617
618 /// Version of [`Self::insert()`] that returns both the key and the old value.
619 fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> {
620 match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
621 #[allow(clippy::unwrap_used)] // Index came from binary_search
622 Ok(found) => Some((
623 key,
624 mem::replace(self.values.lm_get_mut(found).unwrap().1, value),
625 )),
626 Err(ins) => {
627 self.values.lm_insert(ins, key, value);
628 None
629 }
630 }
631 }
632
633 /// Attempts to insert a unique entry into the map.
634 ///
635 /// If `key` is not already in the map, inserts it with the corresponding `value`
636 /// and returns `None`.
637 ///
638 /// If `key` is already in the map, no change is made to the map, and the key and value
639 /// are returned back to the caller.
640 ///
641 /// ```
642 /// use litemap::LiteMap;
643 ///
644 /// let mut map = LiteMap::new_vec();
645 /// map.insert(1, "one");
646 /// map.insert(3, "three");
647 ///
648 /// // 2 is not yet in the map...
649 /// assert_eq!(map.try_insert(2, "two"), None);
650 /// assert_eq!(map.len(), 3);
651 ///
652 /// // ...but now it is.
653 /// assert_eq!(map.try_insert(2, "TWO"), Some((2, "TWO")));
654 /// assert_eq!(map.len(), 3);
655 /// ```
656 pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> {
657 match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
658 Ok(_) => Some((key, value)),
659 Err(ins) => {
660 self.values.lm_insert(ins, key, value);
661 None
662 }
663 }
664 }
665
666 /// Attempts to insert a unique entry into the map.
667 ///
668 /// If `key` is not already in the map, invokes the closure to compute `value`, inserts
669 /// the pair into the map, and returns a reference to the value. The closure is passed
670 /// a reference to the `key` argument.
671 ///
672 /// If `key` is already in the map, a reference to the existing value is returned.
673 ///
674 /// Additionally, the index of the value in the map is returned. If it is not desirable
675 /// to hold on to the mutable reference's lifetime, the index can be used to access the
676 /// element via [`LiteMap::get_indexed()`].
677 ///
678 /// The closure returns a `Result` to allow for a fallible insertion function. If the
679 /// creation of `value` is infallible, you can use [`core::convert::Infallible`].
680 ///
681 /// ```
682 /// use litemap::LiteMap;
683 ///
684 /// /// Helper function to unwrap an `Infallible` result from the insertion function
685 /// fn unwrap_infallible<T>(result: Result<T, core::convert::Infallible>) -> T {
686 /// result.unwrap_or_else(|never| match never {})
687 /// }
688 ///
689 /// let mut map = LiteMap::new_vec();
690 /// map.insert(1, "one");
691 /// map.insert(3, "three");
692 ///
693 /// // 2 is not yet in the map...
694 /// let result1 = unwrap_infallible(
695 /// map.try_get_or_insert(2, |_| Ok("two"))
696 /// );
697 /// assert_eq!(result1.1, &"two");
698 /// assert_eq!(map.len(), 3);
699 ///
700 /// // ...but now it is.
701 /// let result1 = unwrap_infallible(
702 /// map.try_get_or_insert(2, |_| Ok("TWO"))
703 /// );
704 /// assert_eq!(result1.1, &"two");
705 /// assert_eq!(map.len(), 3);
706 /// ```
707 pub fn try_get_or_insert<E>(
708 &mut self,
709 key: K,
710 value: impl FnOnce(&K) -> Result<V, E>,
711 ) -> Result<(usize, &V), E> {
712 let idx = match self.values.lm_binary_search_by(|k| k.cmp(&key)) {
713 Ok(idx) => idx,
714 Err(idx) => {
715 let value = value(&key)?;
716 self.values.lm_insert(idx, key, value);
717 idx
718 }
719 };
720 #[allow(clippy::unwrap_used)] // item at idx found or inserted above
721 Ok((idx, self.values.lm_get(idx).unwrap().1))
722 }
723
724 /// Remove the value at `key`, returning it if it exists.
725 ///
726 /// ```rust
727 /// use litemap::LiteMap;
728 ///
729 /// let mut map = LiteMap::new_vec();
730 /// map.insert(1, "one");
731 /// map.insert(2, "two");
732 /// assert_eq!(map.remove(&1), Some("one"));
733 /// assert_eq!(map.get(&1), None);
734 /// ```
735 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
736 where
737 K: Borrow<Q>,
738 Q: Ord + ?Sized,
739 {
740 match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) {
741 Ok(found) => Some(self.values.lm_remove(found).1),
742 Err(_) => None,
743 }
744 }
745}
746
747impl<K, V, S> LiteMap<K, V, S>
748where
749 K: Ord,
750 S: StoreIntoIterator<K, V> + StoreFromIterator<K, V>,
751{
752 /// Insert all elements from `other` into this `LiteMap`.
753 ///
754 /// If `other` contains keys that already exist in `self`, the values in `other` replace the
755 /// corresponding ones in `self`, and the rejected items from `self` are returned as a new
756 /// `LiteMap`. Otherwise, `None` is returned.
757 ///
758 /// The implementation of this function is optimized if `self` and `other` have no overlap.
759 ///
760 /// # Examples
761 ///
762 /// ```
763 /// use litemap::LiteMap;
764 ///
765 /// let mut map1 = LiteMap::new_vec();
766 /// map1.insert(1, "one");
767 /// map1.insert(2, "two");
768 ///
769 /// let mut map2 = LiteMap::new_vec();
770 /// map2.insert(2, "TWO");
771 /// map2.insert(4, "FOUR");
772 ///
773 /// let leftovers = map1.extend_from_litemap(map2);
774 ///
775 /// assert_eq!(map1.len(), 3);
776 /// assert_eq!(map1.get(&1), Some("one").as_ref());
777 /// assert_eq!(map1.get(&2), Some("TWO").as_ref());
778 /// assert_eq!(map1.get(&4), Some("FOUR").as_ref());
779 ///
780 /// let map3 = leftovers.expect("Duplicate keys");
781 /// assert_eq!(map3.len(), 1);
782 /// assert_eq!(map3.get(&2), Some("two").as_ref());
783 /// ```
784 pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> {
785 if self.is_empty() {
786 self.values = other.values;
787 return None;
788 }
789 if other.is_empty() {
790 return None;
791 }
792 if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) {
793 // append other to self
794 self.values.lm_extend_end(other.values);
795 None
796 } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) {
797 // prepend other to self
798 self.values.lm_extend_start(other.values);
799 None
800 } else {
801 // insert every element
802 let leftover_tuples = other
803 .values
804 .lm_into_iter()
805 .filter_map(|(k, v)| self.insert_save_key(k, v))
806 .collect();
807 let ret = LiteMap {
808 values: leftover_tuples,
809 _key_type: PhantomData,
810 _value_type: PhantomData,
811 };
812 if ret.is_empty() {
813 None
814 } else {
815 Some(ret)
816 }
817 }
818 }
819}
820
821impl<K, V, S> Default for LiteMap<K, V, S>
822where
823 S: Store<K, V> + Default,
824{
825 fn default() -> Self {
826 Self {
827 values: S::default(),
828 _key_type: PhantomData,
829 _value_type: PhantomData,
830 }
831 }
832}
833impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S>
834where
835 K: Ord,
836 S: Store<K, V>,
837{
838 type Output = V;
839 fn index(&self, key: &K) -> &V {
840 #[allow(clippy::panic)] // documented
841 match self.get(key) {
842 Some(v) => v,
843 None => panic!("no entry found for key"),
844 }
845 }
846}
847impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S>
848where
849 K: Ord,
850 S: StoreMut<K, V>,
851{
852 fn index_mut(&mut self, key: &K) -> &mut V {
853 #[allow(clippy::panic)] // documented
854 match self.get_mut(key) {
855 Some(v) => v,
856 None => panic!("no entry found for key"),
857 }
858 }
859}
860impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S>
861where
862 K: Ord,
863 S: StoreFromIterable<K, V>,
864{
865 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
866 let values = S::lm_sort_from_iter(iter);
867 Self::from_sorted_store_unchecked(values)
868 }
869}
870
871impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
872where
873 S: StoreIterable<'a, K, V>,
874{
875 /// Produce an ordered iterator over key-value pairs
876 pub fn iter(&'a self) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)> {
877 self.values.lm_iter()
878 }
879
880 /// Produce an ordered iterator over keys
881 pub fn iter_keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> {
882 self.values.lm_iter().map(|val| val.0)
883 }
884
885 /// Produce an iterator over values, ordered by their keys
886 pub fn iter_values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> {
887 self.values.lm_iter().map(|val| val.1)
888 }
889}
890
891impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S>
892where
893 S: StoreIterableMut<'a, K, V>,
894{
895 /// Produce an ordered mutable iterator over key-value pairs
896 pub fn iter_mut(&'a mut self) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)> {
897 self.values.lm_iter_mut()
898 }
899}
900
901impl<K, V, S> IntoIterator for LiteMap<K, V, S>
902where
903 S: StoreIntoIterator<K, V>,
904{
905 type Item = (K, V);
906 type IntoIter = S::KeyValueIntoIter;
907
908 fn into_iter(self) -> Self::IntoIter {
909 self.values.lm_into_iter()
910 }
911}
912
913impl<K, V, S> LiteMap<K, V, S>
914where
915 S: StoreMut<K, V>,
916{
917 /// Retains only the elements specified by the predicate.
918 ///
919 /// In other words, remove all elements such that `f((&k, &v))` returns `false`.
920 ///
921 /// # Example
922 ///
923 /// ```rust
924 /// use litemap::LiteMap;
925 ///
926 /// let mut map = LiteMap::new_vec();
927 /// map.insert(1, "one");
928 /// map.insert(2, "two");
929 /// map.insert(3, "three");
930 ///
931 /// // Retain elements with odd keys
932 /// map.retain(|k, _| k % 2 == 1);
933 ///
934 /// assert_eq!(map.get(&1), Some(&"one"));
935 /// assert_eq!(map.get(&2), None);
936 /// ```
937 #[inline]
938 pub fn retain<F>(&mut self, predicate: F)
939 where
940 F: FnMut(&K, &V) -> bool,
941 {
942 self.values.lm_retain(predicate)
943 }
944}
945
946impl<'a, K, V> LiteMap<K, V, &'a [(K, V)]> {
947 /// Const version of [`LiteMap::len()`] for a slice store.
948 ///
949 /// Note: This function will no longer be needed if const trait behavior is stabilized.
950 ///
951 /// # Examples
952 ///
953 /// ```rust
954 /// use litemap::LiteMap;
955 ///
956 /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
957 /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]);
958 /// static len: usize = map.const_len();
959 /// assert_eq!(len, 2);
960 /// ```
961 #[inline]
962 pub const fn const_len(&self) -> usize {
963 self.values.len()
964 }
965
966 /// Const version of [`LiteMap::is_empty()`] for a slice store.
967 ///
968 /// Note: This function will no longer be needed if const trait behavior is stabilized.
969 ///
970 /// # Examples
971 ///
972 /// ```rust
973 /// use litemap::LiteMap;
974 ///
975 /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
976 /// LiteMap::from_sorted_store_unchecked(&[]);
977 /// static is_empty: bool = map.const_is_empty();
978 /// assert!(is_empty);
979 /// ```
980 #[inline]
981 pub const fn const_is_empty(&self) -> bool {
982 self.values.is_empty()
983 }
984
985 /// Const version of [`LiteMap::get_indexed()`] for a slice store.
986 ///
987 /// Note: This function will no longer be needed if const trait behavior is stabilized.
988 ///
989 /// # Panics
990 ///
991 /// Panics if the index is out of bounds.
992 ///
993 /// # Examples
994 ///
995 /// ```rust
996 /// use litemap::LiteMap;
997 ///
998 /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
999 /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]);
1000 /// static t: &(&str, usize) = map.const_get_indexed_or_panic(0);
1001 /// assert_eq!(t.0, "a");
1002 /// assert_eq!(t.1, 11);
1003 /// ```
1004 #[inline]
1005 #[allow(clippy::indexing_slicing)] // documented
1006 pub const fn const_get_indexed_or_panic(&self, index: usize) -> &'a (K, V) {
1007 &self.values[index]
1008 }
1009}
1010
1011const fn const_cmp_bytes(a: &[u8], b: &[u8]) -> Ordering {
1012 let (max, default) = if a.len() == b.len() {
1013 (a.len(), Ordering::Equal)
1014 } else if a.len() < b.len() {
1015 (a.len(), Ordering::Less)
1016 } else {
1017 (b.len(), Ordering::Greater)
1018 };
1019 let mut i = 0;
1020 #[allow(clippy::indexing_slicing)] // indexes in range by above checks
1021 while i < max {
1022 if a[i] == b[i] {
1023 i += 1;
1024 continue;
1025 } else if a[i] < b[i] {
1026 return Ordering::Less;
1027 } else {
1028 return Ordering::Greater;
1029 }
1030 }
1031 default
1032}
1033
1034impl<'a, V> LiteMap<&'a str, V, &'a [(&'a str, V)]> {
1035 /// Const function to get the value associated with a `&str` key, if it exists.
1036 ///
1037 /// Also returns the index of the value.
1038 ///
1039 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1040 ///
1041 /// # Examples
1042 ///
1043 /// ```rust
1044 /// use litemap::LiteMap;
1045 ///
1046 /// static map: LiteMap<&str, usize, &[(&str, usize)]> =
1047 /// LiteMap::from_sorted_store_unchecked(&[
1048 /// ("abc", 11),
1049 /// ("bcd", 22),
1050 /// ("cde", 33),
1051 /// ("def", 44),
1052 /// ("efg", 55),
1053 /// ]);
1054 ///
1055 /// static d: Option<(usize, &usize)> = map.const_get_with_index("def");
1056 /// assert_eq!(d, Some((3, &44)));
1057 ///
1058 /// static n: Option<(usize, &usize)> = map.const_get_with_index("dng");
1059 /// assert_eq!(n, None);
1060 /// ```
1061 pub const fn const_get_with_index(&self, key: &str) -> Option<(usize, &'a V)> {
1062 let mut i = 0;
1063 let mut j = self.const_len();
1064 while i < j {
1065 let mid = (i + j) / 2;
1066 #[allow(clippy::indexing_slicing)] // in range
1067 let x = &self.values[mid];
1068 match const_cmp_bytes(key.as_bytes(), x.0.as_bytes()) {
1069 Ordering::Equal => return Some((mid, &x.1)),
1070 Ordering::Greater => i = mid + 1,
1071 Ordering::Less => j = mid,
1072 };
1073 }
1074 None
1075 }
1076}
1077
1078impl<'a, V> LiteMap<&'a [u8], V, &'a [(&'a [u8], V)]> {
1079 /// Const function to get the value associated with a `&[u8]` key, if it exists.
1080 ///
1081 /// Also returns the index of the value.
1082 ///
1083 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1084 ///
1085 /// # Examples
1086 ///
1087 /// ```rust
1088 /// use litemap::LiteMap;
1089 ///
1090 /// static map: LiteMap<&[u8], usize, &[(&[u8], usize)]> =
1091 /// LiteMap::from_sorted_store_unchecked(&[
1092 /// (b"abc", 11),
1093 /// (b"bcd", 22),
1094 /// (b"cde", 33),
1095 /// (b"def", 44),
1096 /// (b"efg", 55),
1097 /// ]);
1098 ///
1099 /// static d: Option<(usize, &usize)> = map.const_get_with_index(b"def");
1100 /// assert_eq!(d, Some((3, &44)));
1101 ///
1102 /// static n: Option<(usize, &usize)> = map.const_get_with_index(b"dng");
1103 /// assert_eq!(n, None);
1104 /// ```
1105 pub const fn const_get_with_index(&self, key: &[u8]) -> Option<(usize, &'a V)> {
1106 let mut i = 0;
1107 let mut j = self.const_len();
1108 while i < j {
1109 let mid = (i + j) / 2;
1110 #[allow(clippy::indexing_slicing)] // in range
1111 let x = &self.values[mid];
1112 match const_cmp_bytes(key, x.0) {
1113 Ordering::Equal => return Some((mid, &x.1)),
1114 Ordering::Greater => i = mid + 1,
1115 Ordering::Less => j = mid,
1116 };
1117 }
1118 None
1119 }
1120}
1121
1122macro_rules! impl_const_get_with_index_for_integer {
1123 ($integer:ty) => {
1124 impl<'a, V> LiteMap<$integer, V, &'a [($integer, V)]> {
1125 /// Const function to get the value associated with an integer key, if it exists.
1126 ///
1127 /// Note: This function will no longer be needed if const trait behavior is stabilized.
1128 ///
1129 /// Also returns the index of the value.
1130 pub const fn const_get_with_index(&self, key: $integer) -> Option<(usize, &'a V)> {
1131 let mut i = 0;
1132 let mut j = self.const_len();
1133 while i < j {
1134 let mid = (i + j) / 2;
1135 #[allow(clippy::indexing_slicing)] // in range
1136 let x = &self.values[mid];
1137 if key == x.0 {
1138 return Some((mid, &x.1));
1139 } else if key > x.0 {
1140 i = mid + 1;
1141 } else {
1142 j = mid;
1143 }
1144 }
1145 return None;
1146 }
1147 }
1148 };
1149}
1150
1151impl_const_get_with_index_for_integer!(u8);
1152impl_const_get_with_index_for_integer!(u16);
1153impl_const_get_with_index_for_integer!(u32);
1154impl_const_get_with_index_for_integer!(u64);
1155impl_const_get_with_index_for_integer!(u128);
1156impl_const_get_with_index_for_integer!(usize);
1157impl_const_get_with_index_for_integer!(i8);
1158impl_const_get_with_index_for_integer!(i16);
1159impl_const_get_with_index_for_integer!(i32);
1160impl_const_get_with_index_for_integer!(i64);
1161impl_const_get_with_index_for_integer!(i128);
1162impl_const_get_with_index_for_integer!(isize);
1163
1164#[cfg(test)]
1165mod test {
1166 use super::*;
1167
1168 #[test]
1169 fn from_iterator() {
1170 let mut expected = LiteMap::with_capacity(4);
1171 expected.insert(1, "updated-one");
1172 expected.insert(2, "original-two");
1173 expected.insert(3, "original-three");
1174 expected.insert(4, "updated-four");
1175
1176 let actual = [
1177 (1, "original-one"),
1178 (2, "original-two"),
1179 (4, "original-four"),
1180 (4, "updated-four"),
1181 (1, "updated-one"),
1182 (3, "original-three"),
1183 ]
1184 .into_iter()
1185 .collect::<LiteMap<_, _>>();
1186
1187 assert_eq!(expected, actual);
1188 }
1189 fn make_13() -> LiteMap<usize, &'static str> {
1190 let mut result = LiteMap::new();
1191 result.insert(1, "one");
1192 result.insert(3, "three");
1193 result
1194 }
1195
1196 fn make_24() -> LiteMap<usize, &'static str> {
1197 let mut result = LiteMap::new();
1198 result.insert(2, "TWO");
1199 result.insert(4, "FOUR");
1200 result
1201 }
1202
1203 fn make_46() -> LiteMap<usize, &'static str> {
1204 let mut result = LiteMap::new();
1205 result.insert(4, "four");
1206 result.insert(6, "six");
1207 result
1208 }
1209
1210 #[test]
1211 fn extend_from_litemap_append() {
1212 let mut map = LiteMap::new();
1213 map.extend_from_litemap(make_13())
1214 .ok_or(())
1215 .expect_err("Append to empty map");
1216 map.extend_from_litemap(make_46())
1217 .ok_or(())
1218 .expect_err("Append to lesser map");
1219 assert_eq!(map.len(), 4);
1220 }
1221
1222 #[test]
1223 fn extend_from_litemap_prepend() {
1224 let mut map = LiteMap::new();
1225 map.extend_from_litemap(make_46())
1226 .ok_or(())
1227 .expect_err("Prepend to empty map");
1228 map.extend_from_litemap(make_13())
1229 .ok_or(())
1230 .expect_err("Prepend to lesser map");
1231 assert_eq!(map.len(), 4);
1232 }
1233
1234 #[test]
1235 fn extend_from_litemap_insert() {
1236 let mut map = LiteMap::new();
1237 map.extend_from_litemap(make_13())
1238 .ok_or(())
1239 .expect_err("Append to empty map");
1240 map.extend_from_litemap(make_24())
1241 .ok_or(())
1242 .expect_err("Insert with no conflict");
1243 map.extend_from_litemap(make_46())
1244 .ok_or(())
1245 .expect("Insert with conflict");
1246 assert_eq!(map.len(), 5);
1247 }
1248
1249 #[test]
1250 fn test_const_cmp_bytes() {
1251 let strs = &["a", "aa", "abc", "abde", "bcd", "bcde"];
1252 for i in 0..strs.len() {
1253 for j in 0..strs.len() {
1254 let a = strs[i].as_bytes();
1255 let b = strs[j].as_bytes();
1256 assert_eq!(a.cmp(b), const_cmp_bytes(a, b));
1257 }
1258 }
1259 }
1260
1261 #[test]
1262 fn into_iterator() {
1263 let mut map = LiteMap::<_, _, Vec<(_, _)>>::new();
1264 map.insert(4, "four");
1265 map.insert(6, "six");
1266 let mut reference = vec![(6, "six"), (4, "four")];
1267
1268 for i in map {
1269 let r = reference.pop().unwrap();
1270 assert_eq!(r, i);
1271 }
1272 assert!(reference.is_empty());
1273 }
1274}