diff options
Diffstat (limited to 'third_party/rust/litemap/src')
| -rw-r--r-- | third_party/rust/litemap/src/databake.rs | 80 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/lib.rs | 67 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/map.rs | 1248 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/serde.rs | 213 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/serde_helpers.rs | 168 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/store/mod.rs | 178 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/store/slice_impl.rs | 63 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/store/vec_impl.rs | 181 | ||||
| -rw-r--r-- | third_party/rust/litemap/src/testing.rs | 240 |
9 files changed, 2438 insertions, 0 deletions
diff --git a/third_party/rust/litemap/src/databake.rs b/third_party/rust/litemap/src/databake.rs new file mode 100644 index 0000000000..d42085b9c6 --- /dev/null +++ b/third_party/rust/litemap/src/databake.rs @@ -0,0 +1,80 @@ +// 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::LiteMap; +use databake::*; + +/// Bakes a LiteMap into Rust code for fast runtime construction from data. Use this impl during +/// code generation, such as in a `build.rs` script. +/// +/// For the most efficient bake, bake the [`LiteMap`] with a slice store. Use functions such as +/// the following for converting an allocated [`LiteMap`] to a borrowing [`LiteMap`]: +/// +/// - [`LiteMap::to_borrowed_keys()`] +/// - [`LiteMap::to_borrowed_values()`] +/// - [`LiteMap::to_borrowed_keys_values()`] +/// - [`LiteMap::as_sliced()`] +/// +/// # Examples +/// +/// ``` +/// use databake::*; +/// use litemap::LiteMap; +/// +/// // Construct the LiteMap fully owned and allocated: +/// let mut litemap_alloc: LiteMap<usize, String, Vec<_>> = LiteMap::new_vec(); +/// litemap_alloc.insert(1usize, "one".to_string()); +/// litemap_alloc.insert(2usize, "two".to_string()); +/// litemap_alloc.insert(10usize, "ten".to_string()); +/// +/// // Convert to a borrowed type for baking: +/// let litemap_str: LiteMap<usize, &str, Vec<_>> = +/// litemap_alloc.to_borrowed_values(); +/// let litemap_slice: LiteMap<usize, &str, &[_]> = litemap_str.as_sliced(); +/// +/// // The bake will now work for const construction: +/// let mut ctx = Default::default(); +/// println!( +/// "const FOO: LiteMap<usize, &str, &[(usize, &str)]> = {};", +/// litemap_slice.bake(&mut ctx) +/// ); +/// ``` +impl<K, V, S> Bake for LiteMap<K, V, S> +where + S: Bake, +{ + fn bake(&self, env: &CrateEnv) -> TokenStream { + env.insert("litemap"); + let store = self.values.bake(env); + quote! { litemap::LiteMap::from_sorted_store_unchecked(#store) } + } +} + +#[test] +fn test_baked_map() { + // Const construction: + test_bake!( + LiteMap<usize, &str, &[(usize, &str)]>, + const: crate::LiteMap::from_sorted_store_unchecked( + &[ + (1usize, "one"), + (2usize, "two"), + (10usize, "ten") + ] + ), + litemap + ); + // Non-const construction: + test_bake!( + LiteMap<usize, String, Vec<(usize, String)>>, + crate::LiteMap::from_sorted_store_unchecked( + alloc::vec![ + (1usize, "one".to_owned()), + (2usize, "two".to_owned()), + (10usize, "ten".to_owned()), + ] + ), + litemap + ); +} diff --git a/third_party/rust/litemap/src/lib.rs b/third_party/rust/litemap/src/lib.rs new file mode 100644 index 0000000000..b6f4019a70 --- /dev/null +++ b/third_party/rust/litemap/src/lib.rs @@ -0,0 +1,67 @@ +// 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 ). + +//! # `litemap` +//! +//! `litemap` is a crate providing [`LiteMap`], a highly simplistic "flat" key-value map +//! based off of a single sorted vector. +//! +//! The goal of this crate is to provide a map that is good enough for small +//! sizes, and does not carry the binary size impact of [`HashMap`](std::collections::HashMap) +//! or [`BTreeMap`](alloc::collections::BTreeMap). +//! +//! If binary size is not a concern, [`std::collections::BTreeMap`] may be a better choice +//! for your use case. It behaves very similarly to [`LiteMap`] for less than 12 elements, +//! and upgrades itself gracefully for larger inputs. +//! +//! ## Pluggable Backends +//! +//! By default, [`LiteMap`] is backed by a [`Vec`]; however, it can be backed by any appropriate +//! random-access data store, giving that data store a map-like interface. See the [`store`] +//! module for more details. +//! +//! ## Const construction +//! +//! [`LiteMap`] supports const construction from any store that is const-constructible, such as a +//! static slice, via [`LiteMap::from_sorted_store_unchecked()`]. This also makes [`LiteMap`] +//! suitable for use with [`databake`]. See [`impl Bake for LiteMap`] for more details. +//! +//! [`impl Bake for LiteMap`]: ./struct.LiteMap.html#impl-Bake-for-LiteMap<K,+V,+S> +//! [`Vec`]: alloc::vec::Vec + +// https://github.com/unicode-org/icu4x/blob/main/docs/process/boilerplate.md#library-annotations +#![cfg_attr(not(test), no_std)] +#![cfg_attr( + not(test), + deny( + clippy::indexing_slicing, + clippy::unwrap_used, + clippy::expect_used, + clippy::panic, + clippy::exhaustive_structs, + clippy::exhaustive_enums, + missing_debug_implementations, + ) +)] + +// for intra doc links +#[cfg(doc)] +extern crate std; + +extern crate alloc; + +#[cfg(feature = "databake")] +#[path = "databake.rs"] // to not conflict with `databake` as used in the docs +mod databake_impls; +mod map; +#[cfg(feature = "serde")] +mod serde; +#[cfg(feature = "serde")] +mod serde_helpers; +pub mod store; + +#[cfg(any(test, feature = "testing"))] +pub mod testing; + +pub use map::LiteMap; 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)); + } + } + } +} diff --git a/third_party/rust/litemap/src/serde.rs b/third_party/rust/litemap/src/serde.rs new file mode 100644 index 0000000000..45e249ea8d --- /dev/null +++ b/third_party/rust/litemap/src/serde.rs @@ -0,0 +1,213 @@ +// 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 super::LiteMap; +use crate::store::*; +use core::fmt; +use core::marker::PhantomData; +use serde::de::{MapAccess, SeqAccess, Visitor}; +use serde::{Deserialize, Deserializer}; + +#[cfg(feature = "serde")] +use serde::{ser::SerializeMap, Serialize, Serializer}; + +#[cfg(feature = "serde")] +impl<K, V, R> Serialize for LiteMap<K, V, R> +where + K: Serialize, + V: Serialize, + R: Store<K, V> + Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + // Many human-readable formats don't support values other + // than numbers and strings as map keys. For them, we can serialize + // as a vec of tuples instead + if serializer.is_human_readable() { + if let Some((ref k, _)) = self.values.lm_get(0) { + if !super::serde_helpers::is_num_or_string(k) { + return self.values.serialize(serializer); + } + // continue to regular serialization + } + } + let mut map = serializer.serialize_map(Some(self.len()))?; + let mut i = 0; + while i < self.values.lm_len() { + #[allow(clippy::unwrap_used)] // i is in range + let (k, v) = self.values.lm_get(i).unwrap(); + map.serialize_entry(k, v)?; + i += 1; + } + map.end() + } +} + +/// Modified example from https://serde.rs/deserialize-map.html +#[allow(clippy::type_complexity)] +struct LiteMapVisitor<K, V, R> { + marker: PhantomData<fn() -> LiteMap<K, V, R>>, +} + +impl<K, V, R> LiteMapVisitor<K, V, R> { + fn new() -> Self { + Self { + marker: PhantomData, + } + } +} + +impl<'de, K, V, R> Visitor<'de> for LiteMapVisitor<K, V, R> +where + K: Deserialize<'de> + Ord, + V: Deserialize<'de>, + R: StoreMut<K, V> + StoreFromIterable<K, V>, +{ + type Value = LiteMap<K, V, R>; + + fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str("a map produced by LiteMap") + } + + fn visit_seq<S>(self, mut access: S) -> Result<Self::Value, S::Error> + where + S: SeqAccess<'de>, + { + let mut map = LiteMap::with_capacity(access.size_hint().unwrap_or(0)); + + // While there are entries remaining in the input, add them + // into our map. + while let Some((key, value)) = access.next_element()? { + // Try to append it at the end, hoping for a sorted map. + // If not sorted, insert as usual. + // This allows for arbitrary maps (e.g. from user JSON) + // to be deserialized into LiteMap + // without impacting performance in the case of deserializing + // a serialized map that came from another LiteMap + if let Some((key, value)) = map.try_append(key, value) { + // Note: this effectively selection sorts the map, + // which isn't efficient for large maps + map.insert(key, value); + } + } + + Ok(map) + } + + fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error> + where + M: MapAccess<'de>, + { + let mut map = LiteMap::with_capacity(access.size_hint().unwrap_or(0)); + + // While there are entries remaining in the input, add them + // into our map. + while let Some((key, value)) = access.next_entry()? { + // Try to append it at the end, hoping for a sorted map. + // If not sorted, insert as usual. + // This allows for arbitrary maps (e.g. from user JSON) + // to be deserialized into LiteMap + // without impacting performance in the case of deserializing + // a serialized map that came from another LiteMap + if let Some((key, value)) = map.try_append(key, value) { + // Note: this effectively selection sorts the map, + // which isn't efficient for large maps + map.insert(key, value); + } + } + + Ok(map) + } +} + +impl<'de, K, V, R> Deserialize<'de> for LiteMap<K, V, R> +where + K: Ord + Deserialize<'de>, + V: Deserialize<'de>, + R: StoreMut<K, V> + StoreFromIterable<K, V>, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + if deserializer.is_human_readable() { + // deserialize_any only works on self-describing (human-readable) + // formats + deserializer.deserialize_any(LiteMapVisitor::new()) + } else { + deserializer.deserialize_map(LiteMapVisitor::new()) + } + } +} + +#[cfg(test)] +mod test { + use crate::LiteMap; + use alloc::borrow::ToOwned; + use alloc::string::String; + + fn get_simple_map() -> LiteMap<u32, String> { + [ + (1, "one".to_owned()), + (2, "two".to_owned()), + (4, "four".to_owned()), + (5, "five".to_owned()), + ] + .into_iter() + .collect() + } + + fn get_tuple_map() -> LiteMap<(u32, String), String> { + [ + ((1, "en".to_owned()), "one".to_owned()), + ((1, "zh".to_owned()), "一".to_owned()), + ((2, "en".to_owned()), "two".to_owned()), + ((2, "zh".to_owned()), "二".to_owned()), + ((4, "en".to_owned()), "four".to_owned()), + ((5, "en".to_owned()), "five".to_owned()), + ((5, "zh".to_owned()), "五".to_owned()), + ((7, "zh".to_owned()), "七".to_owned()), + ] + .into_iter() + .collect() + } + + #[test] + fn test_roundtrip_json() { + let map = get_simple_map(); + let json = serde_json::to_string(&map).unwrap(); + assert_eq!( + json, + "{\"1\":\"one\",\"2\":\"two\",\"4\":\"four\",\"5\":\"five\"}" + ); + let deserialized: LiteMap<u32, String> = serde_json::from_str(&json).unwrap(); + assert_eq!(map, deserialized); + + let map = get_tuple_map(); + let json = serde_json::to_string(&map).unwrap(); + assert_eq!( + json, + "[[[1,\"en\"],\"one\"],[[1,\"zh\"],\"一\"],[[2,\"en\"],\"two\"],\ + [[2,\"zh\"],\"二\"],[[4,\"en\"],\"four\"],[[5,\"en\"],\"five\"],\ + [[5,\"zh\"],\"五\"],[[7,\"zh\"],\"七\"]]" + ); + let deserialized: LiteMap<(u32, String), String> = serde_json::from_str(&json).unwrap(); + assert_eq!(map, deserialized); + } + + #[test] + fn test_roundtrip_postcard() { + let map = get_simple_map(); + let postcard = postcard::to_stdvec(&map).unwrap(); + let deserialized: LiteMap<u32, String> = postcard::from_bytes(&postcard).unwrap(); + assert_eq!(map, deserialized); + + let map = get_tuple_map(); + let postcard = postcard::to_stdvec(&map).unwrap(); + let deserialized: LiteMap<(u32, String), String> = postcard::from_bytes(&postcard).unwrap(); + assert_eq!(map, deserialized); + } +} diff --git a/third_party/rust/litemap/src/serde_helpers.rs b/third_party/rust/litemap/src/serde_helpers.rs new file mode 100644 index 0000000000..b1ead938a0 --- /dev/null +++ b/third_party/rust/litemap/src/serde_helpers.rs @@ -0,0 +1,168 @@ +// 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 ). + +// @@@@@@@@@@@@@@@@ +// THIS FILE IS SHARED BETWEEN LITEMAP AND ZEROVEC. PLEASE KEEP IT IN SYNC FOR ALL EDITS +// @@@@@@@@@@@@@@@@ + +use serde::ser::{Impossible, Serialize, Serializer}; + +pub fn is_num_or_string<T: Serialize + ?Sized>(k: &T) -> bool { + // Serializer that errors in the same cases as serde_json::ser::MapKeySerializer + struct MapKeySerializerDryRun; + impl Serializer for MapKeySerializerDryRun { + type Ok = (); + // Singleton error type that implements serde::ser::Error + type Error = core::fmt::Error; + + type SerializeSeq = Impossible<(), Self::Error>; + type SerializeTuple = Impossible<(), Self::Error>; + type SerializeTupleStruct = Impossible<(), Self::Error>; + type SerializeTupleVariant = Impossible<(), Self::Error>; + type SerializeMap = Impossible<(), Self::Error>; + type SerializeStruct = Impossible<(), Self::Error>; + type SerializeStructVariant = Impossible<(), Self::Error>; + + fn serialize_str(self, _value: &str) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_unit_variant( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + ) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_newtype_struct<T: Serialize + ?Sized>( + self, + _name: &'static str, + value: &T, + ) -> Result<Self::Ok, Self::Error> { + // Recurse + value.serialize(self) + } + fn serialize_bool(self, _value: bool) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_i8(self, _value: i8) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_i16(self, _value: i16) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_i32(self, _value: i32) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_i64(self, _value: i64) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + serde::serde_if_integer128! { + fn serialize_i128(self, _value: i128) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + } + fn serialize_u8(self, _value: u8) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_u16(self, _value: u16) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_u32(self, _value: u32) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_u64(self, _value: u64) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + serde::serde_if_integer128! { + fn serialize_u128(self, _value: u128) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + } + fn serialize_f32(self, _value: f32) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_f64(self, _value: f64) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_char(self, _value: char) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_bytes(self, _value: &[u8]) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_unit(self) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_unit_struct(self, _name: &'static str) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_newtype_variant<T: Serialize + ?Sized>( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + _value: &T, + ) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_none(self) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_some<T: Serialize + ?Sized>( + self, + _value: &T, + ) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_seq(self, _len: Option<usize>) -> Result<Self::SerializeSeq, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_tuple(self, _len: usize) -> Result<Self::SerializeTuple, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_tuple_struct( + self, + _name: &'static str, + _len: usize, + ) -> Result<Self::SerializeTupleStruct, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_tuple_variant( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + _len: usize, + ) -> Result<Self::SerializeTupleVariant, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_map(self, _len: Option<usize>) -> Result<Self::SerializeMap, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_struct( + self, + _name: &'static str, + _len: usize, + ) -> Result<Self::SerializeStruct, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_struct_variant( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + _len: usize, + ) -> Result<Self::SerializeStructVariant, Self::Error> { + Err(core::fmt::Error) + } + fn collect_str<T: core::fmt::Display + ?Sized>( + self, + _value: &T, + ) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + } + k.serialize(MapKeySerializerDryRun).is_ok() +} diff --git a/third_party/rust/litemap/src/store/mod.rs b/third_party/rust/litemap/src/store/mod.rs new file mode 100644 index 0000000000..ca696a1afa --- /dev/null +++ b/third_party/rust/litemap/src/store/mod.rs @@ -0,0 +1,178 @@ +// 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 ). + +//! Traits for pluggable LiteMap backends. +//! +//! By default, LiteMap is backed by a `Vec`. However, in some environments, it may be desirable +//! to use a different data store while still using LiteMap to manage proper ordering of items. +//! +//! The general guidelines for a performant data store are: +//! +//! 1. Must support efficient random access for binary search +//! 2. Should support efficient append operations for deserialization +//! +//! To plug a custom data store into LiteMap, implement: +//! +//! - [`Store`] for most of the methods +//! - [`StoreIterable`] for methods that return iterators +//! - [`StoreFromIterator`] to enable `FromIterator` for LiteMap +//! +//! To test your implementation, enable the `"testing"` Cargo feature and use [`check_store()`]. +//! +//! [`check_store()`]: crate::testing::check_store + +mod slice_impl; +#[cfg(feature = "alloc")] +mod vec_impl; + +use core::cmp::Ordering; +use core::iter::DoubleEndedIterator; +use core::iter::FromIterator; +use core::iter::Iterator; +use core::ops::Range; + +/// Trait to enable const construction of empty store. +pub trait StoreConstEmpty<K: ?Sized, V: ?Sized> { + /// An empty store + const EMPTY: Self; +} + +/// Trait to enable pluggable backends for LiteMap. +/// +/// Some methods have default implementations provided for convenience; however, it is generally +/// better to implement all methods that your data store supports. +pub trait Store<K: ?Sized, V: ?Sized>: Sized { + /// Returns the number of elements in the store. + fn lm_len(&self) -> usize; + + /// Returns whether the store is empty (contains 0 elements). + fn lm_is_empty(&self) -> bool { + self.lm_len() == 0 + } + + /// Gets a key/value pair at the specified index. + fn lm_get(&self, index: usize) -> Option<(&K, &V)>; + + /// Gets the last element in the store, or `None` if the store is empty. + fn lm_last(&self) -> Option<(&K, &V)> { + let len = self.lm_len(); + if len == 0 { + None + } else { + self.lm_get(len - 1) + } + } + + /// Searches the store for a particular element with a comparator function. + /// + /// See the binary search implementation on `slice` for more information. + fn lm_binary_search_by<F>(&self, cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering; +} + +pub trait StoreFromIterable<K, V>: Store<K, V> { + /// Create a sorted store from `iter`. + fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self; +} + +pub trait StoreSlice<K: ?Sized, V: ?Sized>: Store<K, V> { + type Slice: ?Sized; + + fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice>; +} + +pub trait StoreMut<K, V>: Store<K, V> { + /// Creates a new store with the specified capacity hint. + /// + /// Implementations may ignore the argument if they do not support pre-allocating capacity. + fn lm_with_capacity(capacity: usize) -> Self; + + /// Reserves additional capacity in the store. + /// + /// Implementations may ignore the argument if they do not support pre-allocating capacity. + fn lm_reserve(&mut self, additional: usize); + + /// Gets a key/value pair at the specified index, with a mutable value. + fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>; + + /// Pushes one additional item onto the store. + fn lm_push(&mut self, key: K, value: V); + + /// Inserts an item at a specific index in the store. + /// + /// # Panics + /// + /// Panics if `index` is greater than the length. + fn lm_insert(&mut self, index: usize, key: K, value: V); + + /// Removes an item at a specific index in the store. + /// + /// # Panics + /// + /// Panics if `index` is greater than the length. + fn lm_remove(&mut self, index: usize) -> (K, V); + + /// Removes all items from the store. + fn lm_clear(&mut self); + + /// Retains items satisfying a predicate in this store. + fn lm_retain<F>(&mut self, mut predicate: F) + where + F: FnMut(&K, &V) -> bool, + { + let mut i = 0; + while i < self.lm_len() { + #[allow(clippy::unwrap_used)] // i is in range + let (k, v) = self.lm_get(i).unwrap(); + if predicate(k, v) { + i += 1; + } else { + self.lm_remove(i); + } + } + } +} + +/// Iterator methods for the LiteMap store. +pub trait StoreIterable<'a, K: 'a + ?Sized, V: 'a + ?Sized>: Store<K, V> { + type KeyValueIter: Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator + 'a; + + /// Returns an iterator over key/value pairs. + fn lm_iter(&'a self) -> Self::KeyValueIter; +} + +pub trait StoreIterableMut<'a, K: 'a, V: 'a>: StoreMut<K, V> + StoreIterable<'a, K, V> { + type KeyValueIterMut: Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator + 'a; + type KeyValueIntoIter: Iterator<Item = (K, V)>; + + /// Returns an iterator over key/value pairs, with a mutable value. + fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut; + + /// Returns an iterator that moves every item from this store. + fn lm_into_iter(self) -> Self::KeyValueIntoIter; + + /// Adds items from another store to the end of this store. + fn lm_extend_end(&mut self, other: Self) + where + Self: Sized, + { + for item in other.lm_into_iter() { + self.lm_push(item.0, item.1); + } + } + + /// Adds items from another store to the beginning of this store. + fn lm_extend_start(&mut self, other: Self) + where + Self: Sized, + { + for (i, item) in other.lm_into_iter().enumerate() { + self.lm_insert(i, item.0, item.1); + } + } +} + +/// A store that can be built from a tuple iterator. +pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {} diff --git a/third_party/rust/litemap/src/store/slice_impl.rs b/third_party/rust/litemap/src/store/slice_impl.rs new file mode 100644 index 0000000000..48f6ca40cf --- /dev/null +++ b/third_party/rust/litemap/src/store/slice_impl.rs @@ -0,0 +1,63 @@ +// 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 super::*; + +type MapF<K, V> = fn(&(K, V)) -> (&K, &V); + +#[inline] +fn map_f<K, V>(input: &(K, V)) -> (&K, &V) { + (&input.0, &input.1) +} + +impl<'a, K: 'a, V: 'a> StoreConstEmpty<K, V> for &'a [(K, V)] { + const EMPTY: &'a [(K, V)] = &[]; +} + +impl<'a, K: 'a, V: 'a> Store<K, V> for &'a [(K, V)] { + #[inline] + fn lm_len(&self) -> usize { + self.len() + } + + #[inline] + fn lm_is_empty(&self) -> bool { + self.is_empty() + } + + #[inline] + fn lm_get(&self, index: usize) -> Option<(&K, &V)> { + self.get(index).map(map_f) + } + + #[inline] + fn lm_last(&self) -> Option<(&K, &V)> { + self.last().map(map_f) + } + + #[inline] + fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering, + { + self.binary_search_by(|(k, _)| cmp(k)) + } +} + +impl<'a, K, V> StoreSlice<K, V> for &'a [(K, V)] { + type Slice = [(K, V)]; + + fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice> { + self.get(range) + } +} + +impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for &'a [(K, V)] { + type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>; + + #[inline] + fn lm_iter(&'a self) -> Self::KeyValueIter { + self.iter().map(map_f) + } +} diff --git a/third_party/rust/litemap/src/store/vec_impl.rs b/third_party/rust/litemap/src/store/vec_impl.rs new file mode 100644 index 0000000000..2205e8e8ff --- /dev/null +++ b/third_party/rust/litemap/src/store/vec_impl.rs @@ -0,0 +1,181 @@ +// 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 super::*; +use alloc::vec::Vec; + +type MapF<K, V> = fn(&(K, V)) -> (&K, &V); + +#[inline] +fn map_f<K, V>(input: &(K, V)) -> (&K, &V) { + (&input.0, &input.1) +} + +type MapFMut<K, V> = fn(&mut (K, V)) -> (&K, &mut V); + +#[inline] +fn map_f_mut<K, V>(input: &mut (K, V)) -> (&K, &mut V) { + (&input.0, &mut input.1) +} + +impl<K, V> StoreConstEmpty<K, V> for Vec<(K, V)> { + const EMPTY: Vec<(K, V)> = Vec::new(); +} + +impl<K, V> Store<K, V> for Vec<(K, V)> { + #[inline] + fn lm_len(&self) -> usize { + self.as_slice().len() + } + + #[inline] + fn lm_is_empty(&self) -> bool { + self.as_slice().is_empty() + } + + #[inline] + fn lm_get(&self, index: usize) -> Option<(&K, &V)> { + self.as_slice().get(index).map(map_f) + } + + #[inline] + fn lm_last(&self) -> Option<(&K, &V)> { + self.as_slice().last().map(map_f) + } + + #[inline] + fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering, + { + self.as_slice().binary_search_by(|(k, _)| cmp(k)) + } +} + +impl<K, V> StoreSlice<K, V> for Vec<(K, V)> { + type Slice = [(K, V)]; + + fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice> { + self.get(range) + } +} + +impl<K, V> StoreMut<K, V> for Vec<(K, V)> { + #[inline] + fn lm_with_capacity(capacity: usize) -> Self { + Self::with_capacity(capacity) + } + + #[inline] + fn lm_reserve(&mut self, additional: usize) { + self.reserve(additional) + } + + #[inline] + fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.as_mut_slice().get_mut(index).map(map_f_mut) + } + + #[inline] + fn lm_push(&mut self, key: K, value: V) { + self.push((key, value)) + } + + #[inline] + fn lm_insert(&mut self, index: usize, key: K, value: V) { + self.insert(index, (key, value)) + } + + #[inline] + fn lm_remove(&mut self, index: usize) -> (K, V) { + self.remove(index) + } + + #[inline] + fn lm_clear(&mut self) { + self.clear() + } + + #[inline] + fn lm_retain<F>(&mut self, mut predicate: F) + where + F: FnMut(&K, &V) -> bool, + { + self.retain(|(k, v)| predicate(k, v)) + } +} + +impl<K: Ord, V> StoreFromIterable<K, V> for Vec<(K, V)> { + fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { + let iter = iter.into_iter(); + let mut container = match iter.size_hint() { + (_, Some(upper)) => Self::with_capacity(upper), + (lower, None) => Self::with_capacity(lower), + }; + + for (key, value) in iter { + if let Some(last) = container.lm_last() { + if last.0 >= &key { + match container.lm_binary_search_by(|k| k.cmp(&key)) { + #[allow(clippy::unwrap_used)] // Index came from binary_search + Ok(found) => { + let _ = + core::mem::replace(container.lm_get_mut(found).unwrap().1, value); + } + Err(ins) => { + container.insert(ins, (key, value)); + } + } + } else { + container.push((key, value)) + } + } else { + container.push((key, value)) + } + } + + container + } +} + +impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for Vec<(K, V)> { + type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>; + + #[inline] + fn lm_iter(&'a self) -> Self::KeyValueIter { + self.as_slice().iter().map(map_f) + } +} + +impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for Vec<(K, V)> { + type KeyValueIterMut = core::iter::Map<core::slice::IterMut<'a, (K, V)>, MapFMut<K, V>>; + type KeyValueIntoIter = alloc::vec::IntoIter<(K, V)>; + + #[inline] + fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut { + self.as_mut_slice().iter_mut().map(map_f_mut) + } + + #[inline] + fn lm_into_iter(self) -> Self::KeyValueIntoIter { + IntoIterator::into_iter(self) + } + + #[inline] + fn lm_extend_end(&mut self, other: Self) { + self.extend(other) + } + + #[inline] + fn lm_extend_start(&mut self, other: Self) { + self.splice(0..0, other); + } +} + +impl<K, V> StoreFromIterator<K, V> for Vec<(K, V)> {} + +#[test] +fn test_vec_impl() { + crate::testing::check_store_full::<Vec<(u32, u64)>>(); +} diff --git a/third_party/rust/litemap/src/testing.rs b/third_party/rust/litemap/src/testing.rs new file mode 100644 index 0000000000..2fb8c522a4 --- /dev/null +++ b/third_party/rust/litemap/src/testing.rs @@ -0,0 +1,240 @@ +// 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 ). + +//! Test utilities, primarily targeted to custom LiteMap stores. + +use crate::store::*; +use crate::LiteMap; +use alloc::vec::Vec; +use core::fmt::Debug; + +// Test code +#[allow(clippy::expect_used)] +fn check_equivalence<'a, K, V, S0, S1>(mut a: S0, mut b: S1) +where + K: Ord + Debug + PartialEq + 'a, + V: Debug + PartialEq + 'a, + S0: StoreMut<K, V> + StoreIterable<'a, K, V>, + S1: StoreMut<K, V> + StoreIterable<'a, K, V>, +{ + let len = a.lm_len(); + assert_eq!(len, b.lm_len()); + if len == 0 { + assert!(a.lm_is_empty()); + assert!(b.lm_is_empty()); + } + for i in 0..len { + let a_kv = a.lm_get(i); + let b_kv = b.lm_get(i); + assert!(a_kv.is_some()); + assert_eq!(a_kv, b_kv); + let a_kv_mut = a.lm_get_mut(i); + let b_kv_mut = b.lm_get_mut(i); + assert!(a_kv_mut.is_some()); + assert_eq!(a_kv_mut, b_kv_mut); + } + for j in 0..len { + let needle = a.lm_get(j).expect("j is in range").0; + let a_binary = a.lm_binary_search_by(|k| k.cmp(needle)); + let b_binary = a.lm_binary_search_by(|k| k.cmp(needle)); + assert_eq!(Ok(j), a_binary); + assert_eq!(Ok(j), b_binary); + } + assert!(a.lm_get(len).is_none()); + assert!(b.lm_get(len).is_none()); + assert_eq!(a.lm_last(), b.lm_last()); +} + +// Test code +#[allow(clippy::expect_used)] +fn check_into_iter_equivalence<'a, K, V, S0, S1>(a: S0, b: S1) +where + K: Ord + Debug + PartialEq + 'a, + V: Debug + PartialEq + 'a, + S0: StoreIterableMut<'a, K, V>, + S1: StoreIterableMut<'a, K, V>, +{ + let a_vec = a.lm_into_iter().collect::<Vec<_>>(); + let b_vec = b.lm_into_iter().collect::<Vec<_>>(); + assert_eq!(a_vec, b_vec); +} + +const SORTED_DATA: &[(u32, u64)] = &[ + (106, 4816), + (147, 9864), + (188, 8588), + (252, 6031), + (434, 2518), + (574, 8500), + (607, 3756), + (619, 4965), + (663, 2669), + (724, 9211), +]; + +const RANDOM_DATA: &[(u32, u64)] = &[ + (546, 7490), + (273, 4999), + (167, 8078), + (176, 2101), + (373, 1304), + (339, 9613), + (561, 3620), + (301, 1214), + (483, 4453), + (704, 5359), +]; + +// Test code +#[allow(clippy::expect_used)] +#[allow(clippy::panic)] +fn populate_litemap<S>(map: &mut LiteMap<u32, u64, S>) +where + S: StoreMut<u32, u64> + Debug, +{ + assert_eq!(0, map.len()); + assert!(map.is_empty()); + for (k, v) in SORTED_DATA.iter() { + #[allow(clippy::single_match)] // for clarity + match map.try_append(*k, *v) { + Some(_) => panic!("appending sorted data: {k:?} to {map:?}"), + None => (), // OK + }; + } + assert_eq!(10, map.len()); + for (k, v) in RANDOM_DATA.iter() { + #[allow(clippy::single_match)] // for clarity + match map.try_append(*k, *v) { + Some(_) => (), // OK + None => panic!("cannot append random data: {k:?} to{map:?}"), + }; + } + assert_eq!(10, map.len()); + for (k, v) in RANDOM_DATA.iter() { + map.insert(*k, *v); + } + assert_eq!(20, map.len()); +} + +/// Tests that a litemap that uses the given store as backend has behavior consistent with the +/// reference impl. +/// +/// Call this function in a test with the store impl to test as a valid backend for LiteMap. +// Test code +#[allow(clippy::expect_used)] +pub fn check_store<'a, S>() +where + S: StoreConstEmpty<u32, u64> + + StoreMut<u32, u64> + + StoreIterable<'a, u32, u64> + + StoreFromIterator<u32, u64> + + Clone + + Debug + + PartialEq + + 'a, +{ + let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new(); + assert!(litemap_test.is_empty()); + let mut litemap_std = LiteMap::<u32, u64>::new(); + populate_litemap(&mut litemap_test); + populate_litemap(&mut litemap_std); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.retain(|_, v| v % 2 == 0); + litemap_std.retain(|_, v| v % 2 == 0); + assert_eq!(11, litemap_test.len()); + assert_eq!(11, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_test.remove(&147).ok_or(()).expect("exists"); + litemap_std + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_std.remove(&147).ok_or(()).expect("exists"); + + assert_eq!(10, litemap_test.len()); + assert_eq!(10, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.clear(); + litemap_std.clear(); + check_equivalence(litemap_test.values, litemap_std.values); +} + +/// Similar to [`check_store`] function, but also checks the validitiy of [`StoreIterableMut`] +/// trait. +// Test code +#[allow(clippy::expect_used)] +pub fn check_store_full<'a, S>() +where + S: StoreConstEmpty<u32, u64> + + StoreIterableMut<'a, u32, u64> + + StoreFromIterator<u32, u64> + + Clone + + Debug + + PartialEq + + 'a, +{ + let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new(); + assert!(litemap_test.is_empty()); + let mut litemap_std = LiteMap::<u32, u64>::new(); + populate_litemap(&mut litemap_test); + populate_litemap(&mut litemap_std); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + let extras_test = litemap_test.clone(); + let extras_test = litemap_test + .extend_from_litemap(extras_test) + .expect("duplicates"); + assert_eq!(extras_test, litemap_test); + let extras_std = litemap_std.clone(); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.retain(|_, v| v % 2 == 0); + litemap_std.retain(|_, v| v % 2 == 0); + assert_eq!(11, litemap_test.len()); + assert_eq!(11, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + let extras_test = litemap_test + .extend_from_litemap(extras_test) + .expect("duplicates"); + let extras_std = litemap_std + .extend_from_litemap(extras_std) + .expect("duplicates"); + assert_eq!(11, extras_test.len()); + assert_eq!(11, extras_std.len()); + assert_eq!(20, litemap_test.len()); + assert_eq!(20, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_test.remove(&176).ok_or(()).expect("exists"); + litemap_std + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_std.remove(&176).ok_or(()).expect("exists"); + assert_eq!(19, litemap_test.len()); + assert_eq!(19, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.clear(); + litemap_std.clear(); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.values, litemap_std.values); +} |