| // This file is part of ICU4X. For terms of use, please see the file |
| // called LICENSE at the top level of the ICU4X source tree |
| // (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). |
| |
| use crate::store::*; |
| use alloc::borrow::Borrow; |
| use alloc::boxed::Box; |
| use alloc::vec::Vec; |
| use core::cmp::Ordering; |
| use core::iter::FromIterator; |
| use core::marker::PhantomData; |
| use core::mem; |
| use core::ops::{Index, IndexMut, Range}; |
| |
| /// A simple "flat" map based on a sorted vector |
| /// |
| /// See the [module level documentation][super] for why one should use this. |
| /// |
| /// The API is roughly similar to that of [`std::collections::BTreeMap`]. |
| #[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] |
| #[cfg_attr(feature = "yoke", derive(yoke::Yokeable))] |
| pub struct LiteMap<K: ?Sized, V: ?Sized, S = alloc::vec::Vec<(K, V)>> { |
| pub(crate) values: S, |
| pub(crate) _key_type: PhantomData<K>, |
| pub(crate) _value_type: PhantomData<V>, |
| } |
| |
| impl<K, V> LiteMap<K, V> { |
| /// Construct a new [`LiteMap`] backed by Vec |
| pub const fn new_vec() -> Self { |
| Self { |
| values: alloc::vec::Vec::new(), |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| } |
| |
| impl<K, V, S> LiteMap<K, V, S> { |
| /// Construct a new [`LiteMap`] using the given values |
| /// |
| /// The store must be sorted and have no duplicate keys. |
| pub const fn from_sorted_store_unchecked(values: S) -> Self { |
| Self { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| } |
| |
| impl<K, V> LiteMap<K, V, Vec<(K, V)>> { |
| /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`. |
| #[inline] |
| pub fn into_tuple_vec(self) -> Vec<(K, V)> { |
| self.values |
| } |
| } |
| |
| impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
| where |
| S: StoreConstEmpty<K, V>, |
| { |
| /// Create a new empty [`LiteMap`] |
| pub const fn new() -> Self { |
| Self { |
| values: S::EMPTY, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| } |
| |
| impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
| where |
| S: Store<K, V>, |
| { |
| /// The number of elements in the [`LiteMap`] |
| pub fn len(&self) -> usize { |
| self.values.lm_len() |
| } |
| |
| /// Whether the [`LiteMap`] is empty |
| pub fn is_empty(&self) -> bool { |
| self.values.lm_is_empty() |
| } |
| |
| /// Get the key-value pair residing at a particular index |
| /// |
| /// In most cases, prefer [`LiteMap::get()`] over this method. |
| #[inline] |
| pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> { |
| self.values.lm_get(index) |
| } |
| |
| /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = |
| /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]); |
| /// |
| /// assert_eq!(map.first(), Some((&1, &"uno"))); |
| /// ``` |
| #[inline] |
| pub fn first(&self) -> Option<(&K, &V)> { |
| self.values.lm_get(0) |
| } |
| |
| /// Get the highest-rank key/value pair from the `LiteMap`, if it exists. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = |
| /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]); |
| /// |
| /// assert_eq!(map.last(), Some((&3, &"tres"))); |
| /// ``` |
| #[inline] |
| pub fn last(&self) -> Option<(&K, &V)> { |
| self.values.lm_get(self.len() - 1) |
| } |
| |
| /// Returns a new [`LiteMap`] with owned keys and values. |
| /// |
| /// The trait bounds allow transforming most slice and string types. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map: LiteMap<&str, &str> = LiteMap::new_vec(); |
| /// map.insert("one", "uno"); |
| /// map.insert("two", "dos"); |
| /// |
| /// let boxed_map: LiteMap<Box<str>, Box<str>> = map.to_boxed_keys_values(); |
| /// |
| /// assert_eq!(boxed_map.get("one"), Some(&Box::from("uno"))); |
| /// ``` |
| pub fn to_boxed_keys_values<KB: ?Sized, VB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, Box<VB>, SB> |
| where |
| SB: StoreMut<Box<KB>, Box<VB>>, |
| K: Borrow<KB>, |
| V: Borrow<VB>, |
| Box<KB>: for<'a> From<&'a KB>, |
| Box<VB>: for<'a> From<&'a VB>, |
| { |
| let mut values = SB::lm_with_capacity(self.len()); |
| for i in 0..self.len() { |
| #[allow(clippy::unwrap_used)] // iterating over our own length |
| let (k, v) = self.values.lm_get(i).unwrap(); |
| values.lm_push(Box::from(k.borrow()), Box::from(v.borrow())) |
| } |
| LiteMap { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| |
| /// Returns a new [`LiteMap`] with owned keys and cloned values. |
| /// |
| /// The trait bounds allow transforming most slice and string types. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map: LiteMap<&str, usize> = LiteMap::new_vec(); |
| /// map.insert("one", 11); |
| /// map.insert("two", 22); |
| /// |
| /// let boxed_map: LiteMap<Box<str>, usize> = map.to_boxed_keys(); |
| /// |
| /// assert_eq!(boxed_map.get("one"), Some(&11)); |
| /// ``` |
| pub fn to_boxed_keys<KB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, V, SB> |
| where |
| V: Clone, |
| SB: StoreMut<Box<KB>, V>, |
| K: Borrow<KB>, |
| Box<KB>: for<'a> From<&'a KB>, |
| { |
| let mut values = SB::lm_with_capacity(self.len()); |
| for i in 0..self.len() { |
| #[allow(clippy::unwrap_used)] // iterating over our own length |
| let (k, v) = self.values.lm_get(i).unwrap(); |
| values.lm_push(Box::from(k.borrow()), v.clone()) |
| } |
| LiteMap { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| |
| /// Returns a new [`LiteMap`] with cloned keys and owned values. |
| /// |
| /// The trait bounds allow transforming most slice and string types. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map: LiteMap<usize, &str> = LiteMap::new_vec(); |
| /// map.insert(11, "uno"); |
| /// map.insert(22, "dos"); |
| /// |
| /// let boxed_map: LiteMap<usize, Box<str>> = map.to_boxed_values(); |
| /// |
| /// assert_eq!(boxed_map.get(&11), Some(&Box::from("uno"))); |
| /// ``` |
| pub fn to_boxed_values<VB: ?Sized, SB>(&self) -> LiteMap<K, Box<VB>, SB> |
| where |
| K: Clone, |
| SB: StoreMut<K, Box<VB>>, |
| V: Borrow<VB>, |
| Box<VB>: for<'a> From<&'a VB>, |
| { |
| let mut values = SB::lm_with_capacity(self.len()); |
| for i in 0..self.len() { |
| #[allow(clippy::unwrap_used)] // iterating over our own length |
| let (k, v) = self.values.lm_get(i).unwrap(); |
| values.lm_push(k.clone(), Box::from(v.borrow())) |
| } |
| LiteMap { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| } |
| |
| impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
| where |
| K: Ord, |
| S: Store<K, V>, |
| { |
| /// Get the value associated with `key`, if it exists. |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// assert_eq!(map.get(&1), Some(&"one")); |
| /// assert_eq!(map.get(&3), None); |
| /// ``` |
| pub fn get<Q>(&self, key: &Q) -> Option<&V> |
| where |
| K: Borrow<Q>, |
| Q: Ord + ?Sized, |
| { |
| match self.find_index(key) { |
| #[allow(clippy::unwrap_used)] // find_index returns a valid index |
| Ok(found) => Some(self.values.lm_get(found).unwrap().1), |
| Err(_) => None, |
| } |
| } |
| |
| /// Binary search the map with `predicate` to find a key, returning the value. |
| pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> { |
| let index = self.values.lm_binary_search_by(predicate).ok()?; |
| self.values.lm_get(index).map(|(_, v)| v) |
| } |
| |
| /// Returns whether `key` is contained in this map |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// assert!(map.contains_key(&1)); |
| /// assert!(!map.contains_key(&3)); |
| /// ``` |
| pub fn contains_key<Q>(&self, key: &Q) -> bool |
| where |
| K: Borrow<Q>, |
| Q: Ord + ?Sized, |
| { |
| self.find_index(key).is_ok() |
| } |
| |
| /// Obtain the index for a given key, or if the key is not found, the index |
| /// at which it would be inserted. |
| /// |
| /// (The return value works equivalently to [`slice::binary_search_by()`]) |
| /// |
| /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using |
| /// [`Self::get()`] directly where possible. |
| #[inline] |
| pub fn find_index<Q>(&self, key: &Q) -> Result<usize, usize> |
| where |
| K: Borrow<Q>, |
| Q: Ord + ?Sized, |
| { |
| self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) |
| } |
| } |
| |
| impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> |
| where |
| S: StoreSlice<K, V>, |
| { |
| /// Creates a new [`LiteMap`] from a range of the current [`LiteMap`]. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// map.insert(3, "three"); |
| /// |
| /// let mut sub_map = map.get_indexed_range(1..3).expect("valid range"); |
| /// assert_eq!(sub_map.get(&1), None); |
| /// assert_eq!(sub_map.get(&2), Some(&"two")); |
| /// assert_eq!(sub_map.get(&3), Some(&"three")); |
| /// ``` |
| pub fn get_indexed_range(&self, range: Range<usize>) -> Option<LiteMap<K, V, &S::Slice>> { |
| let subslice = self.values.lm_get_range(range)?; |
| Some(LiteMap { |
| values: subslice, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| }) |
| } |
| |
| /// Borrows this [`LiteMap`] as one of its slice type. |
| /// |
| /// This can be useful in situations where you need a `LiteMap` by value but do not want |
| /// to clone the owned version. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// |
| /// let borrowed_map = map.as_sliced(); |
| /// assert_eq!(borrowed_map.get(&1), Some(&"one")); |
| /// assert_eq!(borrowed_map.get(&2), Some(&"two")); |
| /// ``` |
| pub fn as_sliced(&self) -> LiteMap<K, V, &S::Slice> { |
| // Won't panic: 0..self.len() is within range |
| #[allow(clippy::unwrap_used)] |
| let subslice = self.values.lm_get_range(0..self.len()).unwrap(); |
| LiteMap { |
| values: subslice, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| |
| /// Borrows the backing buffer of this [`LiteMap`] as its slice type. |
| /// |
| /// The slice will be sorted. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// |
| /// let slice = map.as_slice(); |
| /// assert_eq!(slice, &[(1, "one"), (2, "two")]); |
| /// ``` |
| pub fn as_slice(&self) -> &S::Slice { |
| // Won't panic: 0..self.len() is within range |
| #[allow(clippy::unwrap_used)] |
| self.values.lm_get_range(0..self.len()).unwrap() |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
| where |
| S: Store<K, V>, |
| { |
| /// Returns a new [`LiteMap`] with keys and values borrowed from this one. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); |
| /// map.insert(Box::new(1), "one".to_string()); |
| /// map.insert(Box::new(2), "two".to_string()); |
| /// |
| /// let borrowed_map: LiteMap<&usize, &str> = map.to_borrowed_keys_values(); |
| /// |
| /// assert_eq!(borrowed_map.get(&1), Some(&"one")); |
| /// ``` |
| pub fn to_borrowed_keys_values<KB: ?Sized, VB: ?Sized, SB>( |
| &'a self, |
| ) -> LiteMap<&'a KB, &'a VB, SB> |
| where |
| K: Borrow<KB>, |
| V: Borrow<VB>, |
| SB: StoreMut<&'a KB, &'a VB>, |
| { |
| let mut values = SB::lm_with_capacity(self.len()); |
| for i in 0..self.len() { |
| #[allow(clippy::unwrap_used)] // iterating over our own length |
| let (k, v) = self.values.lm_get(i).unwrap(); |
| values.lm_push(k.borrow(), v.borrow()) |
| } |
| LiteMap { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| |
| /// Returns a new [`LiteMap`] with keys borrowed from this one and cloned values. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); |
| /// map.insert(Box::new(1), "one".to_string()); |
| /// map.insert(Box::new(2), "two".to_string()); |
| /// |
| /// let borrowed_map: LiteMap<&usize, String> = map.to_borrowed_keys(); |
| /// |
| /// assert_eq!(borrowed_map.get(&1), Some(&"one".to_string())); |
| /// ``` |
| pub fn to_borrowed_keys<KB: ?Sized, SB>(&'a self) -> LiteMap<&'a KB, V, SB> |
| where |
| K: Borrow<KB>, |
| V: Clone, |
| SB: StoreMut<&'a KB, V>, |
| { |
| let mut values = SB::lm_with_capacity(self.len()); |
| for i in 0..self.len() { |
| #[allow(clippy::unwrap_used)] // iterating over our own length |
| let (k, v) = self.values.lm_get(i).unwrap(); |
| values.lm_push(k.borrow(), v.clone()) |
| } |
| LiteMap { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| |
| /// Returns a new [`LiteMap`] with values borrowed from this one and cloned keys. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); |
| /// map.insert(Box::new(1), "one".to_string()); |
| /// map.insert(Box::new(2), "two".to_string()); |
| /// |
| /// let borrowed_map: LiteMap<Box<usize>, &str> = map.to_borrowed_values(); |
| /// |
| /// assert_eq!(borrowed_map.get(&1), Some(&"one")); |
| /// ``` |
| pub fn to_borrowed_values<VB: ?Sized, SB>(&'a self) -> LiteMap<K, &'a VB, SB> |
| where |
| K: Clone, |
| V: Borrow<VB>, |
| SB: StoreMut<K, &'a VB>, |
| { |
| let mut values = SB::lm_with_capacity(self.len()); |
| for i in 0..self.len() { |
| #[allow(clippy::unwrap_used)] // iterating over our own length |
| let (k, v) = self.values.lm_get(i).unwrap(); |
| values.lm_push(k.clone(), v.borrow()) |
| } |
| LiteMap { |
| values, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| } |
| |
| impl<K, V, S> LiteMap<K, V, S> |
| where |
| S: StoreMut<K, V>, |
| { |
| /// Construct a new [`LiteMap`] with a given capacity |
| pub fn with_capacity(capacity: usize) -> Self { |
| Self { |
| values: S::lm_with_capacity(capacity), |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| |
| /// Remove all elements from the [`LiteMap`] |
| pub fn clear(&mut self) { |
| self.values.lm_clear() |
| } |
| |
| /// Reserve capacity for `additional` more elements to be inserted into |
| /// the [`LiteMap`] to avoid frequent reallocations. |
| /// |
| /// See [`Vec::reserve()`] for more information. |
| /// |
| /// [`Vec::reserve()`]: alloc::vec::Vec::reserve |
| pub fn reserve(&mut self, additional: usize) { |
| self.values.lm_reserve(additional) |
| } |
| } |
| |
| impl<K, V, S> LiteMap<K, V, S> |
| where |
| K: Ord, |
| S: StoreMut<K, V>, |
| { |
| /// Get the value associated with `key`, if it exists, as a mutable reference. |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// if let Some(mut v) = map.get_mut(&1) { |
| /// *v = "uno"; |
| /// } |
| /// assert_eq!(map.get(&1), Some(&"uno")); |
| /// ``` |
| pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V> |
| where |
| K: Borrow<Q>, |
| Q: Ord + ?Sized, |
| { |
| match self.find_index(key) { |
| #[allow(clippy::unwrap_used)] // find_index returns a valid index |
| Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1), |
| Err(_) => None, |
| } |
| } |
| |
| /// Appends `value` with `key` to the end of the underlying vector, returning |
| /// `key` and `value` _if it failed_. Useful for extending with an existing |
| /// sorted list. |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// assert!(map.try_append(1, "uno").is_none()); |
| /// assert!(map.try_append(3, "tres").is_none()); |
| /// |
| /// assert!( |
| /// matches!(map.try_append(3, "tres-updated"), Some((3, "tres-updated"))), |
| /// "append duplicate of last key", |
| /// ); |
| /// |
| /// assert!( |
| /// matches!(map.try_append(2, "dos"), Some((2, "dos"))), |
| /// "append out of order" |
| /// ); |
| /// |
| /// assert_eq!(map.get(&1), Some(&"uno")); |
| /// |
| /// // contains the original value for the key: 3 |
| /// assert_eq!(map.get(&3), Some(&"tres")); |
| /// |
| /// // not appended since it wasn't in order |
| /// assert_eq!(map.get(&2), None); |
| /// ``` |
| #[must_use] |
| pub fn try_append(&mut self, key: K, value: V) -> Option<(K, V)> { |
| if let Some(last) = self.values.lm_last() { |
| if last.0 >= &key { |
| return Some((key, value)); |
| } |
| } |
| |
| self.values.lm_push(key, value); |
| None |
| } |
| |
| /// Insert `value` with `key`, returning the existing value if it exists. |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// assert_eq!(map.get(&1), Some(&"one")); |
| /// assert_eq!(map.get(&3), None); |
| /// ``` |
| pub fn insert(&mut self, key: K, value: V) -> Option<V> { |
| self.insert_save_key(key, value).map(|(_, v)| v) |
| } |
| |
| /// Version of [`Self::insert()`] that returns both the key and the old value. |
| fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> { |
| match self.values.lm_binary_search_by(|k| k.cmp(&key)) { |
| #[allow(clippy::unwrap_used)] // Index came from binary_search |
| Ok(found) => Some(( |
| key, |
| mem::replace(self.values.lm_get_mut(found).unwrap().1, value), |
| )), |
| Err(ins) => { |
| self.values.lm_insert(ins, key, value); |
| None |
| } |
| } |
| } |
| |
| /// Attempts to insert a unique entry into the map. |
| /// |
| /// If `key` is not already in the map, inserts it with the corresponding `value` |
| /// and returns `None`. |
| /// |
| /// If `key` is already in the map, no change is made to the map, and the key and value |
| /// are returned back to the caller. |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(3, "three"); |
| /// |
| /// // 2 is not yet in the map... |
| /// assert_eq!(map.try_insert(2, "two"), None); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// // ...but now it is. |
| /// assert_eq!(map.try_insert(2, "TWO"), Some((2, "TWO"))); |
| /// assert_eq!(map.len(), 3); |
| /// ``` |
| pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> { |
| match self.values.lm_binary_search_by(|k| k.cmp(&key)) { |
| Ok(_) => Some((key, value)), |
| Err(ins) => { |
| self.values.lm_insert(ins, key, value); |
| None |
| } |
| } |
| } |
| |
| /// Attempts to insert a unique entry into the map. |
| /// |
| /// If `key` is not already in the map, invokes the closure to compute `value`, inserts |
| /// the pair into the map, and returns a reference to the value. The closure is passed |
| /// a reference to the `key` argument. |
| /// |
| /// If `key` is already in the map, a reference to the existing value is returned. |
| /// |
| /// Additionally, the index of the value in the map is returned. If it is not desirable |
| /// to hold on to the mutable reference's lifetime, the index can be used to access the |
| /// element via [`LiteMap::get_indexed()`]. |
| /// |
| /// The closure returns a `Result` to allow for a fallible insertion function. If the |
| /// creation of `value` is infallible, you can use [`core::convert::Infallible`]. |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// /// Helper function to unwrap an `Infallible` result from the insertion function |
| /// fn unwrap_infallible<T>(result: Result<T, core::convert::Infallible>) -> T { |
| /// result.unwrap_or_else(|never| match never {}) |
| /// } |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(3, "three"); |
| /// |
| /// // 2 is not yet in the map... |
| /// let result1 = unwrap_infallible( |
| /// map.try_get_or_insert(2, |_| Ok("two")) |
| /// ); |
| /// assert_eq!(result1.1, &"two"); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// // ...but now it is. |
| /// let result1 = unwrap_infallible( |
| /// map.try_get_or_insert(2, |_| Ok("TWO")) |
| /// ); |
| /// assert_eq!(result1.1, &"two"); |
| /// assert_eq!(map.len(), 3); |
| /// ``` |
| pub fn try_get_or_insert<E>( |
| &mut self, |
| key: K, |
| value: impl FnOnce(&K) -> Result<V, E>, |
| ) -> Result<(usize, &V), E> { |
| let idx = match self.values.lm_binary_search_by(|k| k.cmp(&key)) { |
| Ok(idx) => idx, |
| Err(idx) => { |
| let value = value(&key)?; |
| self.values.lm_insert(idx, key, value); |
| idx |
| } |
| }; |
| #[allow(clippy::unwrap_used)] // item at idx found or inserted above |
| Ok((idx, self.values.lm_get(idx).unwrap().1)) |
| } |
| |
| /// Remove the value at `key`, returning it if it exists. |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// assert_eq!(map.remove(&1), Some("one")); |
| /// assert_eq!(map.get(&1), None); |
| /// ``` |
| pub fn remove<Q>(&mut self, key: &Q) -> Option<V> |
| where |
| K: Borrow<Q>, |
| Q: Ord + ?Sized, |
| { |
| match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) { |
| Ok(found) => Some(self.values.lm_remove(found).1), |
| Err(_) => None, |
| } |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
| where |
| K: Ord, |
| S: StoreIntoIterator<K, V> + StoreFromIterator<K, V>, |
| { |
| /// Insert all elements from `other` into this `LiteMap`. |
| /// |
| /// If `other` contains keys that already exist in `self`, the values in `other` replace the |
| /// corresponding ones in `self`, and the rejected items from `self` are returned as a new |
| /// `LiteMap`. Otherwise, `None` is returned. |
| /// |
| /// The implementation of this function is optimized if `self` and `other` have no overlap. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map1 = LiteMap::new_vec(); |
| /// map1.insert(1, "one"); |
| /// map1.insert(2, "two"); |
| /// |
| /// let mut map2 = LiteMap::new_vec(); |
| /// map2.insert(2, "TWO"); |
| /// map2.insert(4, "FOUR"); |
| /// |
| /// let leftovers = map1.extend_from_litemap(map2); |
| /// |
| /// assert_eq!(map1.len(), 3); |
| /// assert_eq!(map1.get(&1), Some("one").as_ref()); |
| /// assert_eq!(map1.get(&2), Some("TWO").as_ref()); |
| /// assert_eq!(map1.get(&4), Some("FOUR").as_ref()); |
| /// |
| /// let map3 = leftovers.expect("Duplicate keys"); |
| /// assert_eq!(map3.len(), 1); |
| /// assert_eq!(map3.get(&2), Some("two").as_ref()); |
| /// ``` |
| pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> { |
| if self.is_empty() { |
| self.values = other.values; |
| return None; |
| } |
| if other.is_empty() { |
| return None; |
| } |
| if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) { |
| // append other to self |
| self.values.lm_extend_end(other.values); |
| None |
| } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) { |
| // prepend other to self |
| self.values.lm_extend_start(other.values); |
| None |
| } else { |
| // insert every element |
| let leftover_tuples = other |
| .values |
| .lm_into_iter() |
| .filter_map(|(k, v)| self.insert_save_key(k, v)) |
| .collect(); |
| let ret = LiteMap { |
| values: leftover_tuples, |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| }; |
| if ret.is_empty() { |
| None |
| } else { |
| Some(ret) |
| } |
| } |
| } |
| } |
| |
| impl<K, V, S> Default for LiteMap<K, V, S> |
| where |
| S: Store<K, V> + Default, |
| { |
| fn default() -> Self { |
| Self { |
| values: S::default(), |
| _key_type: PhantomData, |
| _value_type: PhantomData, |
| } |
| } |
| } |
| impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S> |
| where |
| K: Ord, |
| S: Store<K, V>, |
| { |
| type Output = V; |
| fn index(&self, key: &K) -> &V { |
| #[allow(clippy::panic)] // documented |
| match self.get(key) { |
| Some(v) => v, |
| None => panic!("no entry found for key"), |
| } |
| } |
| } |
| impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S> |
| where |
| K: Ord, |
| S: StoreMut<K, V>, |
| { |
| fn index_mut(&mut self, key: &K) -> &mut V { |
| #[allow(clippy::panic)] // documented |
| match self.get_mut(key) { |
| Some(v) => v, |
| None => panic!("no entry found for key"), |
| } |
| } |
| } |
| impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S> |
| where |
| K: Ord, |
| S: StoreFromIterable<K, V>, |
| { |
| fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { |
| let values = S::lm_sort_from_iter(iter); |
| Self::from_sorted_store_unchecked(values) |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
| where |
| S: StoreIterable<'a, K, V>, |
| { |
| /// Produce an ordered iterator over key-value pairs |
| pub fn iter(&'a self) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)> { |
| self.values.lm_iter() |
| } |
| |
| /// Produce an ordered iterator over keys |
| pub fn iter_keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> { |
| self.values.lm_iter().map(|val| val.0) |
| } |
| |
| /// Produce an iterator over values, ordered by their keys |
| pub fn iter_values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> { |
| self.values.lm_iter().map(|val| val.1) |
| } |
| } |
| |
| impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> |
| where |
| S: StoreIterableMut<'a, K, V>, |
| { |
| /// Produce an ordered mutable iterator over key-value pairs |
| pub fn iter_mut(&'a mut self) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)> { |
| self.values.lm_iter_mut() |
| } |
| } |
| |
| impl<K, V, S> IntoIterator for LiteMap<K, V, S> |
| where |
| S: StoreIntoIterator<K, V>, |
| { |
| type Item = (K, V); |
| type IntoIter = S::KeyValueIntoIter; |
| |
| fn into_iter(self) -> Self::IntoIter { |
| self.values.lm_into_iter() |
| } |
| } |
| |
| impl<K, V, S> LiteMap<K, V, S> |
| where |
| S: StoreMut<K, V>, |
| { |
| /// Retains only the elements specified by the predicate. |
| /// |
| /// In other words, remove all elements such that `f((&k, &v))` returns `false`. |
| /// |
| /// # Example |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// let mut map = LiteMap::new_vec(); |
| /// map.insert(1, "one"); |
| /// map.insert(2, "two"); |
| /// map.insert(3, "three"); |
| /// |
| /// // Retain elements with odd keys |
| /// map.retain(|k, _| k % 2 == 1); |
| /// |
| /// assert_eq!(map.get(&1), Some(&"one")); |
| /// assert_eq!(map.get(&2), None); |
| /// ``` |
| #[inline] |
| pub fn retain<F>(&mut self, predicate: F) |
| where |
| F: FnMut(&K, &V) -> bool, |
| { |
| self.values.lm_retain(predicate) |
| } |
| } |
| |
| impl<'a, K, V> LiteMap<K, V, &'a [(K, V)]> { |
| /// Const version of [`LiteMap::len()`] for a slice store. |
| /// |
| /// Note: This function will no longer be needed if const trait behavior is stabilized. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
| /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]); |
| /// static len: usize = map.const_len(); |
| /// assert_eq!(len, 2); |
| /// ``` |
| #[inline] |
| pub const fn const_len(&self) -> usize { |
| self.values.len() |
| } |
| |
| /// Const version of [`LiteMap::is_empty()`] for a slice store. |
| /// |
| /// Note: This function will no longer be needed if const trait behavior is stabilized. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
| /// LiteMap::from_sorted_store_unchecked(&[]); |
| /// static is_empty: bool = map.const_is_empty(); |
| /// assert!(is_empty); |
| /// ``` |
| #[inline] |
| pub const fn const_is_empty(&self) -> bool { |
| self.values.is_empty() |
| } |
| |
| /// Const version of [`LiteMap::get_indexed()`] for a slice store. |
| /// |
| /// Note: This function will no longer be needed if const trait behavior is stabilized. |
| /// |
| /// # Panics |
| /// |
| /// Panics if the index is out of bounds. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
| /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]); |
| /// static t: &(&str, usize) = map.const_get_indexed_or_panic(0); |
| /// assert_eq!(t.0, "a"); |
| /// assert_eq!(t.1, 11); |
| /// ``` |
| #[inline] |
| #[allow(clippy::indexing_slicing)] // documented |
| pub const fn const_get_indexed_or_panic(&self, index: usize) -> &'a (K, V) { |
| &self.values[index] |
| } |
| } |
| |
| const fn const_cmp_bytes(a: &[u8], b: &[u8]) -> Ordering { |
| let (max, default) = if a.len() == b.len() { |
| (a.len(), Ordering::Equal) |
| } else if a.len() < b.len() { |
| (a.len(), Ordering::Less) |
| } else { |
| (b.len(), Ordering::Greater) |
| }; |
| let mut i = 0; |
| #[allow(clippy::indexing_slicing)] // indexes in range by above checks |
| while i < max { |
| if a[i] == b[i] { |
| i += 1; |
| continue; |
| } else if a[i] < b[i] { |
| return Ordering::Less; |
| } else { |
| return Ordering::Greater; |
| } |
| } |
| default |
| } |
| |
| impl<'a, V> LiteMap<&'a str, V, &'a [(&'a str, V)]> { |
| /// Const function to get the value associated with a `&str` key, if it exists. |
| /// |
| /// Also returns the index of the value. |
| /// |
| /// Note: This function will no longer be needed if const trait behavior is stabilized. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// static map: LiteMap<&str, usize, &[(&str, usize)]> = |
| /// LiteMap::from_sorted_store_unchecked(&[ |
| /// ("abc", 11), |
| /// ("bcd", 22), |
| /// ("cde", 33), |
| /// ("def", 44), |
| /// ("efg", 55), |
| /// ]); |
| /// |
| /// static d: Option<(usize, &usize)> = map.const_get_with_index("def"); |
| /// assert_eq!(d, Some((3, &44))); |
| /// |
| /// static n: Option<(usize, &usize)> = map.const_get_with_index("dng"); |
| /// assert_eq!(n, None); |
| /// ``` |
| pub const fn const_get_with_index(&self, key: &str) -> Option<(usize, &'a V)> { |
| let mut i = 0; |
| let mut j = self.const_len(); |
| while i < j { |
| let mid = (i + j) / 2; |
| #[allow(clippy::indexing_slicing)] // in range |
| let x = &self.values[mid]; |
| match const_cmp_bytes(key.as_bytes(), x.0.as_bytes()) { |
| Ordering::Equal => return Some((mid, &x.1)), |
| Ordering::Greater => i = mid + 1, |
| Ordering::Less => j = mid, |
| }; |
| } |
| None |
| } |
| } |
| |
| impl<'a, V> LiteMap<&'a [u8], V, &'a [(&'a [u8], V)]> { |
| /// Const function to get the value associated with a `&[u8]` key, if it exists. |
| /// |
| /// Also returns the index of the value. |
| /// |
| /// Note: This function will no longer be needed if const trait behavior is stabilized. |
| /// |
| /// # Examples |
| /// |
| /// ```rust |
| /// use litemap::LiteMap; |
| /// |
| /// static map: LiteMap<&[u8], usize, &[(&[u8], usize)]> = |
| /// LiteMap::from_sorted_store_unchecked(&[ |
| /// (b"abc", 11), |
| /// (b"bcd", 22), |
| /// (b"cde", 33), |
| /// (b"def", 44), |
| /// (b"efg", 55), |
| /// ]); |
| /// |
| /// static d: Option<(usize, &usize)> = map.const_get_with_index(b"def"); |
| /// assert_eq!(d, Some((3, &44))); |
| /// |
| /// static n: Option<(usize, &usize)> = map.const_get_with_index(b"dng"); |
| /// assert_eq!(n, None); |
| /// ``` |
| pub const fn const_get_with_index(&self, key: &[u8]) -> Option<(usize, &'a V)> { |
| let mut i = 0; |
| let mut j = self.const_len(); |
| while i < j { |
| let mid = (i + j) / 2; |
| #[allow(clippy::indexing_slicing)] // in range |
| let x = &self.values[mid]; |
| match const_cmp_bytes(key, x.0) { |
| Ordering::Equal => return Some((mid, &x.1)), |
| Ordering::Greater => i = mid + 1, |
| Ordering::Less => j = mid, |
| }; |
| } |
| None |
| } |
| } |
| |
| macro_rules! impl_const_get_with_index_for_integer { |
| ($integer:ty) => { |
| impl<'a, V> LiteMap<$integer, V, &'a [($integer, V)]> { |
| /// Const function to get the value associated with an integer key, if it exists. |
| /// |
| /// Note: This function will no longer be needed if const trait behavior is stabilized. |
| /// |
| /// Also returns the index of the value. |
| pub const fn const_get_with_index(&self, key: $integer) -> Option<(usize, &'a V)> { |
| let mut i = 0; |
| let mut j = self.const_len(); |
| while i < j { |
| let mid = (i + j) / 2; |
| #[allow(clippy::indexing_slicing)] // in range |
| let x = &self.values[mid]; |
| if key == x.0 { |
| return Some((mid, &x.1)); |
| } else if key > x.0 { |
| i = mid + 1; |
| } else { |
| j = mid; |
| } |
| } |
| return None; |
| } |
| } |
| }; |
| } |
| |
| impl_const_get_with_index_for_integer!(u8); |
| impl_const_get_with_index_for_integer!(u16); |
| impl_const_get_with_index_for_integer!(u32); |
| impl_const_get_with_index_for_integer!(u64); |
| impl_const_get_with_index_for_integer!(u128); |
| impl_const_get_with_index_for_integer!(usize); |
| impl_const_get_with_index_for_integer!(i8); |
| impl_const_get_with_index_for_integer!(i16); |
| impl_const_get_with_index_for_integer!(i32); |
| impl_const_get_with_index_for_integer!(i64); |
| impl_const_get_with_index_for_integer!(i128); |
| impl_const_get_with_index_for_integer!(isize); |
| |
| #[cfg(test)] |
| mod test { |
| use super::*; |
| |
| #[test] |
| fn from_iterator() { |
| let mut expected = LiteMap::with_capacity(4); |
| expected.insert(1, "updated-one"); |
| expected.insert(2, "original-two"); |
| expected.insert(3, "original-three"); |
| expected.insert(4, "updated-four"); |
| |
| let actual = [ |
| (1, "original-one"), |
| (2, "original-two"), |
| (4, "original-four"), |
| (4, "updated-four"), |
| (1, "updated-one"), |
| (3, "original-three"), |
| ] |
| .into_iter() |
| .collect::<LiteMap<_, _>>(); |
| |
| assert_eq!(expected, actual); |
| } |
| fn make_13() -> LiteMap<usize, &'static str> { |
| let mut result = LiteMap::new(); |
| result.insert(1, "one"); |
| result.insert(3, "three"); |
| result |
| } |
| |
| fn make_24() -> LiteMap<usize, &'static str> { |
| let mut result = LiteMap::new(); |
| result.insert(2, "TWO"); |
| result.insert(4, "FOUR"); |
| result |
| } |
| |
| fn make_46() -> LiteMap<usize, &'static str> { |
| let mut result = LiteMap::new(); |
| result.insert(4, "four"); |
| result.insert(6, "six"); |
| result |
| } |
| |
| #[test] |
| fn extend_from_litemap_append() { |
| let mut map = LiteMap::new(); |
| map.extend_from_litemap(make_13()) |
| .ok_or(()) |
| .expect_err("Append to empty map"); |
| map.extend_from_litemap(make_46()) |
| .ok_or(()) |
| .expect_err("Append to lesser map"); |
| assert_eq!(map.len(), 4); |
| } |
| |
| #[test] |
| fn extend_from_litemap_prepend() { |
| let mut map = LiteMap::new(); |
| map.extend_from_litemap(make_46()) |
| .ok_or(()) |
| .expect_err("Prepend to empty map"); |
| map.extend_from_litemap(make_13()) |
| .ok_or(()) |
| .expect_err("Prepend to lesser map"); |
| assert_eq!(map.len(), 4); |
| } |
| |
| #[test] |
| fn extend_from_litemap_insert() { |
| let mut map = LiteMap::new(); |
| map.extend_from_litemap(make_13()) |
| .ok_or(()) |
| .expect_err("Append to empty map"); |
| map.extend_from_litemap(make_24()) |
| .ok_or(()) |
| .expect_err("Insert with no conflict"); |
| map.extend_from_litemap(make_46()) |
| .ok_or(()) |
| .expect("Insert with conflict"); |
| assert_eq!(map.len(), 5); |
| } |
| |
| #[test] |
| fn test_const_cmp_bytes() { |
| let strs = &["a", "aa", "abc", "abde", "bcd", "bcde"]; |
| for i in 0..strs.len() { |
| for j in 0..strs.len() { |
| let a = strs[i].as_bytes(); |
| let b = strs[j].as_bytes(); |
| assert_eq!(a.cmp(b), const_cmp_bytes(a, b)); |
| } |
| } |
| } |
| |
| #[test] |
| fn into_iterator() { |
| let mut map = LiteMap::<_, _, Vec<(_, _)>>::new(); |
| map.insert(4, "four"); |
| map.insert(6, "six"); |
| let mut reference = vec![(6, "six"), (4, "four")]; |
| |
| for i in map { |
| let r = reference.pop().unwrap(); |
| assert_eq!(r, i); |
| } |
| assert!(reference.is_empty()); |
| } |
| } |
