diff options
Diffstat (limited to 'third_party/rust/litemap/src/map.rs')
| -rw-r--r-- | third_party/rust/litemap/src/map.rs | 1248 |
1 files changed, 1248 insertions, 0 deletions
diff --git a/third_party/rust/litemap/src/map.rs b/third_party/rust/litemap/src/map.rs new file mode 100644 index 0000000000..195a46d723 --- /dev/null +++ b/third_party/rust/litemap/src/map.rs @@ -0,0 +1,1248 @@ +// 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: ?Sized>(&self, key: &Q) -> Option<&V> + where + K: Borrow<Q>, + Q: Ord, + { + 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: ?Sized>(&self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Ord, + { + 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: ?Sized>(&self, key: &Q) -> Result<usize, usize> + where + K: Borrow<Q>, + Q: Ord, + { + 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: ?Sized>(&mut self, key: &Q) -> Option<&mut V> + where + K: Borrow<Q>, + Q: Ord, + { + 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: ?Sized>(&mut self, key: &Q) -> Option<V> + where + K: Borrow<Q>, + Q: Ord, + { + 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: StoreIterableMut<'a, 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> 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)); + } + } + } +} |