diff options
Diffstat (limited to 'vendor/zerovec/src/map2d/map.rs')
| -rw-r--r-- | vendor/zerovec/src/map2d/map.rs | 827 |
1 files changed, 827 insertions, 0 deletions
diff --git a/vendor/zerovec/src/map2d/map.rs b/vendor/zerovec/src/map2d/map.rs new file mode 100644 index 000000000..ab6eded4e --- /dev/null +++ b/vendor/zerovec/src/map2d/map.rs @@ -0,0 +1,827 @@ +// 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::ule::AsULE; +use crate::ZeroVec; +use alloc::borrow::Borrow; +use core::cmp::Ordering; +use core::convert::TryFrom; +use core::fmt; +use core::iter::FromIterator; +use core::ops::Range; + +use super::*; +use crate::map::ZeroMapKV; +use crate::map::{MutableZeroVecLike, ZeroVecLike}; + +/// A zero-copy, two-dimensional map datastructure . +/// +/// This is an extension of [`ZeroMap`] that supports two layers of keys. For example, +/// to map a pair of an integer and a string to a buffer, you can write: +/// +/// ```no_run +/// # use zerovec::ZeroMap2d; +/// let _: ZeroMap2d<u32, str, [u8]> = unimplemented!(); +/// ``` +/// +/// Internally, `ZeroMap2d` stores four zero-copy vectors, one for each type argument plus +/// one more to match between the two vectors of keys. +/// +/// # Examples +/// +/// ``` +/// use zerovec::ZeroMap2d; +/// +/// // Example byte buffer representing the map { 1: {2: "three" } } +/// let BINCODE_BYTES: &[u8; 51] = &[ +/// 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, +/// 0, 0, 0, 0, 0, 0, 2, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116, +/// 104, 114, 101, 101, +/// ]; +/// +/// // Deserializing to ZeroMap requires no heap allocations. +/// let zero_map: ZeroMap2d<u16, u16, str> = +/// bincode::deserialize(BINCODE_BYTES) +/// .expect("Should deserialize successfully"); +/// assert_eq!(zero_map.get_2d(&1, &2), Some("three")); +/// ``` +/// +/// [`VarZeroVec`]: crate::VarZeroVec +/// [`ZeroMap`]: crate::ZeroMap +// ZeroMap2d contains 4 fields: +// +// - keys0 = sorted list of all K0 in the map +// - joiner = helper vec that maps from a K0 to a range of keys1 +// - keys1 = list of all K1 in the map, sorted in ranges for each K0 +// - values = list of all values in the map, sorted by (K0, K1) +// +// For a particular K0 at index i, the range of keys1 corresponding to K0 is +// (joiner[i-1]..joiner[i]), where the first range starts at 0. +// +// Required Invariants: +// +// 1. len(keys0) == len(joiner) +// 2. len(keys1) == len(values) +// 3. joiner is sorted +// 4. the last element of joiner is the length of keys1 +// +// Optional Invariants: +// +// 5. keys0 is sorted (for binary_search) +// 6. ranges within keys1 are sorted (for binary_search) +// 7. every K0 is associated with at least one K1 (no empty ranges) +// +// During deserialization, these three invariants are not checked, because they put the +// ZeroMap2d in a deterministic state, even though it may have unexpected behavior. +pub struct ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a>, + K1: ZeroMapKV<'a>, + V: ZeroMapKV<'a>, + K0: ?Sized, + K1: ?Sized, + V: ?Sized, +{ + pub(crate) keys0: K0::Container, + pub(crate) joiner: ZeroVec<'a, u32>, + pub(crate) keys1: K1::Container, + pub(crate) values: V::Container, +} + +impl<'a, K0, K1, V> Default for ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a>, + K1: ZeroMapKV<'a>, + V: ZeroMapKV<'a>, + K0: ?Sized, + K1: ?Sized, + V: ?Sized, +{ + fn default() -> Self { + Self::new() + } +} + +impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a>, + K1: ZeroMapKV<'a>, + V: ZeroMapKV<'a>, + K0: ?Sized, + K1: ?Sized, + V: ?Sized, +{ + /// Creates a new, empty `ZeroMap2d`. + /// + /// # Examples + /// + /// ``` + /// use zerovec::ZeroMap2d; + /// + /// let zm: ZeroMap2d<u16, str, str> = ZeroMap2d::new(); + /// assert!(zm.is_empty()); + /// ``` + pub fn new() -> Self { + Self { + keys0: K0::Container::zvl_with_capacity(0), + joiner: ZeroVec::new(), + keys1: K1::Container::zvl_with_capacity(0), + values: V::Container::zvl_with_capacity(0), + } + } + + #[doc(hidden)] // databake internal + pub const unsafe fn from_parts_unchecked( + keys0: K0::Container, + joiner: ZeroVec<'a, u32>, + keys1: K1::Container, + values: V::Container, + ) -> Self { + Self { + keys0, + joiner, + keys1, + values, + } + } + + /// Construct a new [`ZeroMap2d`] with a given capacity + pub fn with_capacity(capacity: usize) -> Self { + Self { + keys0: K0::Container::zvl_with_capacity(capacity), + joiner: ZeroVec::with_capacity(capacity), + keys1: K1::Container::zvl_with_capacity(capacity), + values: V::Container::zvl_with_capacity(capacity), + } + } + + /// Obtain a borrowed version of this map + pub fn as_borrowed(&'a self) -> ZeroMap2dBorrowed<'a, K0, K1, V> { + ZeroMap2dBorrowed { + keys0: self.keys0.zvl_as_borrowed(), + joiner: &*self.joiner, + keys1: self.keys1.zvl_as_borrowed(), + values: self.values.zvl_as_borrowed(), + } + } + + /// The number of values in the [`ZeroMap2d`] + pub fn len(&self) -> usize { + self.values.zvl_len() + } + + /// Whether the [`ZeroMap2d`] is empty + pub fn is_empty(&self) -> bool { + self.values.zvl_len() == 0 + } + + /// Remove all elements from the [`ZeroMap2d`] + pub fn clear(&mut self) { + self.keys0.zvl_clear(); + self.joiner.clear(); + self.keys1.zvl_clear(); + self.values.zvl_clear(); + } + + /// Reserve capacity for `additional` more elements to be inserted into + /// the [`ZeroMap2d`] to avoid frequent reallocations. + /// + /// See [`Vec::reserve()`](alloc::vec::Vec::reserve) for more information. + pub fn reserve(&mut self, additional: usize) { + self.keys0.zvl_reserve(additional); + self.joiner.zvl_reserve(additional); + self.keys1.zvl_reserve(additional); + self.values.zvl_reserve(additional); + } + + /// Produce an ordered iterator over keys0, which can then be used to get an iterator + /// over keys1 for a particular key0. + /// + /// # Example + /// + /// Loop over all elements of a ZeroMap2d: + /// + /// ``` + /// use zerovec::ZeroMap2d; + /// + /// let mut map: ZeroMap2d<u16, u16, str> = ZeroMap2d::new(); + /// map.insert(&1, &1, "foo"); + /// map.insert(&2, &3, "bar"); + /// map.insert(&2, &4, "baz"); + /// + /// let mut total_value = 0; + /// + /// for cursor in map.iter0() { + /// for (key1, value) in cursor.iter1() { + /// // This code runs for every (key0, key1) pair + /// total_value += cursor.key0().as_unsigned_int() as usize; + /// total_value += key1.as_unsigned_int() as usize; + /// total_value += value.len(); + /// } + /// } + /// + /// assert_eq!(total_value, 22); + /// ``` + pub fn iter0<'l>(&'l self) -> impl Iterator<Item = ZeroMap2dCursor<'l, 'a, K0, K1, V>> + 'l { + (0..self.keys0.zvl_len()).map(move |idx| ZeroMap2dCursor::from_cow(self, idx)) + } + + // INTERNAL ROUTINES FOLLOW // + + /// Given an index into the joiner array, returns the corresponding range of keys1 + fn get_range_for_key0_index(&self, key0_index: usize) -> Range<usize> { + ZeroMap2dCursor::from_cow(self, key0_index).get_range() + } + + /// Removes key0_index from the keys0 array and the joiner array + fn remove_key0_index(&mut self, key0_index: usize) { + self.keys0.zvl_remove(key0_index); + self.joiner.with_mut(|v| v.remove(key0_index)); + } + + /// Shifts all joiner ranges from key0_index onward one index up + fn joiner_expand(&mut self, key0_index: usize) { + #[allow(clippy::expect_used)] // slice overflow + self.joiner + .to_mut_slice() + .iter_mut() + .skip(key0_index) + .for_each(|ref mut v| { + // TODO(#1410): Make this fallible + **v = v + .as_unsigned_int() + .checked_add(1) + .expect("Attempted to add more than 2^32 elements to a ZeroMap2d") + .to_unaligned() + }) + } + + /// Shifts all joiner ranges from key0_index onward one index down + fn joiner_shrink(&mut self, key0_index: usize) { + self.joiner + .to_mut_slice() + .iter_mut() + .skip(key0_index) + .for_each(|ref mut v| **v = (v.as_unsigned_int() - 1).to_unaligned()) + } +} + +impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a> + Ord, + K1: ZeroMapKV<'a> + Ord, + V: ZeroMapKV<'a>, + K0: ?Sized, + K1: ?Sized, + V: ?Sized, +{ + /// Get the value associated with `key0` and `key1`, if it exists. + /// + /// For more fine-grained error handling, use [`ZeroMap2d::get0`]. + /// + /// ```rust + /// use zerovec::ZeroMap2d; + /// + /// let mut map = ZeroMap2d::new(); + /// map.insert(&1, "one", "foo"); + /// map.insert(&2, "one", "bar"); + /// map.insert(&2, "two", "baz"); + /// assert_eq!(map.get_2d(&1, "one"), Some("foo")); + /// assert_eq!(map.get_2d(&1, "two"), None); + /// assert_eq!(map.get_2d(&2, "one"), Some("bar")); + /// assert_eq!(map.get_2d(&2, "two"), Some("baz")); + /// assert_eq!(map.get_2d(&3, "three"), None); + /// ``` + pub fn get_2d(&self, key0: &K0, key1: &K1) -> Option<&V::GetType> { + self.get0(key0)?.get1(key1) + } + + /// Insert `value` with `key`, returning the existing value if it exists. + /// + /// See example in [`Self::get_2d()`]. + pub fn insert(&mut self, key0: &K0, key1: &K1, value: &V) -> Option<V::OwnedType> { + let (key0_index, range) = self.get_or_insert_range_for_key0(key0); + debug_assert!(range.start <= range.end); // '<=' because we may have inserted a new key0 + debug_assert!(range.end <= self.keys1.zvl_len()); + #[allow(clippy::unwrap_used)] // by debug_assert! invariants + let index = range.start + + match self.keys1.zvl_binary_search_in_range(key1, range).unwrap() { + Ok(index) => return Some(self.values.zvl_replace(index, value)), + Err(index) => index, + }; + self.keys1.zvl_insert(index, key1); + self.values.zvl_insert(index, value); + self.joiner_expand(key0_index); + #[cfg(debug_assertions)] + self.check_invariants(); + None + } + + /// Remove the value at `key`, returning it if it exists. + /// + /// ```rust + /// use zerovec::ZeroMap2d; + /// + /// let mut map = ZeroMap2d::new(); + /// map.insert(&1, "one", "foo"); + /// map.insert(&2, "two", "bar"); + /// assert_eq!( + /// map.remove(&1, "one"), + /// Some("foo".to_owned().into_boxed_str()) + /// ); + /// assert_eq!(map.get_2d(&1, "one"), None); + /// assert_eq!(map.remove(&1, "one"), None); + /// ``` + pub fn remove(&mut self, key0: &K0, key1: &K1) -> Option<V::OwnedType> { + let key0_index = self.keys0.zvl_binary_search(key0).ok()?; + let range = self.get_range_for_key0_index(key0_index); + debug_assert!(range.start < range.end); // '<' because every key0 should have a key1 + debug_assert!(range.end <= self.keys1.zvl_len()); + let is_singleton_range = range.start + 1 == range.end; + #[allow(clippy::unwrap_used)] // by debug_assert invariants + let index = range.start + + self + .keys1 + .zvl_binary_search_in_range(key1, range) + .unwrap() + .ok()?; + self.keys1.zvl_remove(index); + let removed = self.values.zvl_remove(index); + self.joiner_shrink(key0_index); + if is_singleton_range { + self.remove_key0_index(key0_index); + } + #[cfg(debug_assertions)] + self.check_invariants(); + Some(removed) + } + + /// 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 zerovec::ZeroMap2d; + /// + /// let mut map = ZeroMap2d::new(); + /// assert!(map.try_append(&1, "one", "uno").is_none()); + /// assert!(map.try_append(&3, "three", "tres").is_none()); + /// + /// let unsuccessful = map.try_append(&3, "three", "tres-updated"); + /// assert!(unsuccessful.is_some(), "append duplicate of last key"); + /// + /// let unsuccessful = map.try_append(&2, "two", "dos"); + /// assert!(unsuccessful.is_some(), "append out of order"); + /// + /// assert_eq!(map.get_2d(&1, "one"), Some("uno")); + /// + /// // contains the original value for the key: 3 + /// assert_eq!(map.get_2d(&3, "three"), Some("tres")); + /// + /// // not appended since it wasn't in order + /// assert_eq!(map.get_2d(&2, "two"), None); + /// ``` + #[must_use] + pub fn try_append<'b>( + &mut self, + key0: &'b K0, + key1: &'b K1, + value: &'b V, + ) -> Option<(&'b K0, &'b K1, &'b V)> { + if self.is_empty() { + self.keys0.zvl_push(key0); + self.joiner.with_mut(|v| v.push(1u32.to_unaligned())); + self.keys1.zvl_push(key1); + self.values.zvl_push(value); + return None; + } + + // The unwraps are protected by the fact that we are not empty + #[allow(clippy::unwrap_used)] + let last_key0 = self.keys0.zvl_get(self.keys0.zvl_len() - 1).unwrap(); + let key0_cmp = K0::Container::t_cmp_get(key0, last_key0); + #[allow(clippy::unwrap_used)] + let last_key1 = self.keys1.zvl_get(self.keys1.zvl_len() - 1).unwrap(); + let key1_cmp = K1::Container::t_cmp_get(key1, last_key1); + + // Check for error case (out of order) + match key0_cmp { + Ordering::Less => { + // Error case + return Some((key0, key1, value)); + } + Ordering::Equal => { + match key1_cmp { + Ordering::Less | Ordering::Equal => { + // Error case + return Some((key0, key1, value)); + } + _ => {} + } + } + _ => {} + } + + #[allow(clippy::expect_used)] // slice overflow + let joiner_value = u32::try_from(self.keys1.zvl_len() + 1) + .expect("Attempted to add more than 2^32 elements to a ZeroMap2d"); + + // All OK to append + #[allow(clippy::unwrap_used)] + if key0_cmp == Ordering::Greater { + self.keys0.zvl_push(key0); + self.joiner + .with_mut(|v| v.push(joiner_value.to_unaligned())); + } else { + // This unwrap is protected because we are not empty + *self.joiner.to_mut_slice().last_mut().unwrap() = joiner_value.to_unaligned(); + } + self.keys1.zvl_push(key1); + self.values.zvl_push(value); + + #[cfg(debug_assertions)] + self.check_invariants(); + + None + } + + // INTERNAL ROUTINES FOLLOW // + + #[cfg(debug_assertions)] + #[allow(clippy::unwrap_used)] // this is an assertion function + pub(crate) fn check_invariants(&self) { + debug_assert_eq!(self.keys0.zvl_len(), self.joiner.len()); + debug_assert_eq!(self.keys1.zvl_len(), self.values.zvl_len()); + debug_assert!(self.keys0.zvl_is_ascending()); + debug_assert!(self.joiner.zvl_is_ascending()); + if let Some(last_joiner) = self.joiner.last() { + debug_assert_eq!(last_joiner as usize, self.keys1.zvl_len()); + } + for i in 0..self.joiner.len() { + let j0 = if i == 0 { + 0 + } else { + self.joiner.get(i - 1).unwrap() as usize + }; + let j1 = self.joiner.get(i).unwrap() as usize; + debug_assert_ne!(j0, j1); + for j in (j0 + 1)..j1 { + let m0 = self.keys1.zvl_get(j - 1).unwrap(); + let m1 = self.keys1.zvl_get(j).unwrap(); + debug_assert_eq!(Ordering::Less, K1::Container::get_cmp_get(m0, m1)); + } + } + } +} + +impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a> + Ord, + K1: ZeroMapKV<'a>, + V: ZeroMapKV<'a>, + K0: ?Sized, + K1: ?Sized, + V: ?Sized, +{ + /// Gets a cursor for `key0`. If `None`, then `key0` is not in the map. If `Some`, + /// then `key0` is in the map, and `key1` can be queried. + /// + /// ```rust + /// use zerovec::ZeroMap2d; + /// + /// let mut map = ZeroMap2d::new(); + /// map.insert(&1u32, "one", "foo"); + /// map.insert(&2, "one", "bar"); + /// map.insert(&2, "two", "baz"); + /// assert_eq!(map.get0(&1).unwrap().get1("one").unwrap(), "foo"); + /// assert_eq!(map.get0(&1).unwrap().get1("two"), None); + /// assert_eq!(map.get0(&2).unwrap().get1("one").unwrap(), "bar"); + /// assert_eq!(map.get0(&2).unwrap().get1("two").unwrap(), "baz"); + /// assert_eq!(map.get0(&3), None); + /// ``` + #[inline] + pub fn get0<'l>(&'l self, key0: &K0) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> { + let key0_index = self.keys0.zvl_binary_search(key0).ok()?; + Some(ZeroMap2dCursor::from_cow(self, key0_index)) + } + + /// Binary search the map for `key0`, returning a cursor. + /// + /// ```rust + /// use zerovec::maps::ZeroMap2dBorrowed; + /// use zerovec::ZeroMap2d; + /// + /// let mut map = ZeroMap2d::new(); + /// map.insert(&1, "one", "foo"); + /// map.insert(&2, "two", "bar"); + /// assert!(matches!(map.get0_by(|probe| probe.cmp(&1)), Some(_))); + /// assert!(matches!(map.get0_by(|probe| probe.cmp(&3)), None)); + /// ``` + pub fn get0_by<'l>( + &'l self, + predicate: impl FnMut(&K0) -> Ordering, + ) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> { + let key0_index = self.keys0.zvl_binary_search_by(predicate).ok()?; + Some(ZeroMap2dCursor::from_cow(self, key0_index)) + } + + /// Returns whether `key0` is contained in this map + /// + /// ```rust + /// use zerovec::ZeroMap2d; + /// + /// let mut map = ZeroMap2d::new(); + /// map.insert(&1, "one", "foo"); + /// map.insert(&2, "two", "bar"); + /// assert_eq!(map.contains_key0(&1), true); + /// assert_eq!(map.contains_key0(&3), false); + /// ``` + pub fn contains_key0(&self, key0: &K0) -> bool { + self.keys0.zvl_binary_search(key0).is_ok() + } + + // INTERNAL ROUTINES FOLLOW // + + /// Same as `get_range_for_key0`, but creates key0 if it doesn't already exist + fn get_or_insert_range_for_key0(&mut self, key0: &K0) -> (usize, Range<usize>) { + match self.keys0.zvl_binary_search(key0) { + Ok(key0_index) => (key0_index, self.get_range_for_key0_index(key0_index)), + Err(key0_index) => { + // Add an entry to self.keys0 and self.joiner + let joiner_value = if key0_index == 0 { + 0 + } else { + debug_assert!(key0_index <= self.joiner.len()); + // The unwrap is protected by the debug_assert above and key0_index != 0 + #[allow(clippy::unwrap_used)] + self.joiner.get(key0_index - 1).unwrap() + }; + self.keys0.zvl_insert(key0_index, key0); + self.joiner + .with_mut(|v| v.insert(key0_index, joiner_value.to_unaligned())); + (key0_index, (joiner_value as usize)..(joiner_value as usize)) + } + } + } +} + +impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a> + Ord, + K1: ZeroMapKV<'a> + Ord, + V: ZeroMapKV<'a>, + V: Copy, + K0: ?Sized, + K1: ?Sized, +{ + /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE` + /// + /// # Examples + /// + /// ``` + /// # use zerovec::ZeroMap2d; + /// let mut map: ZeroMap2d<u16, u16, u16> = ZeroMap2d::new(); + /// map.insert(&1, &2, &3); + /// map.insert(&1, &4, &5); + /// map.insert(&6, &7, &8); + /// + /// assert_eq!(map.get_copied_2d(&6, &7), Some(8)); + /// ``` + #[inline] + pub fn get_copied_2d(&self, key0: &K0, key1: &K1) -> Option<V> { + self.get0(key0)?.get1_copied(key1) + } +} + +impl<'a, K0, K1, V> From<ZeroMap2dBorrowed<'a, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a>, + K1: ZeroMapKV<'a>, + V: ZeroMapKV<'a>, + K0: ?Sized, + K1: ?Sized, + V: ?Sized, +{ + fn from(other: ZeroMap2dBorrowed<'a, K0, K1, V>) -> Self { + Self { + keys0: K0::Container::zvl_from_borrowed(other.keys0), + joiner: other.joiner.as_zerovec(), + keys1: K1::Container::zvl_from_borrowed(other.keys1), + values: V::Container::zvl_from_borrowed(other.values), + } + } +} + +// We can't use the default PartialEq because ZeroMap2d is invariant +// so otherwise rustc will not automatically allow you to compare ZeroMaps +// with different lifetimes +impl<'a, 'b, K0, K1, V> PartialEq<ZeroMap2d<'b, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V> +where + K0: for<'c> ZeroMapKV<'c> + ?Sized, + K1: for<'c> ZeroMapKV<'c> + ?Sized, + V: for<'c> ZeroMapKV<'c> + ?Sized, + <K0 as ZeroMapKV<'a>>::Container: PartialEq<<K0 as ZeroMapKV<'b>>::Container>, + <K1 as ZeroMapKV<'a>>::Container: PartialEq<<K1 as ZeroMapKV<'b>>::Container>, + <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>, +{ + fn eq(&self, other: &ZeroMap2d<'b, K0, K1, V>) -> bool { + self.keys0.eq(&other.keys0) + && self.joiner.eq(&other.joiner) + && self.keys1.eq(&other.keys1) + && self.values.eq(&other.values) + } +} + +impl<'a, K0, K1, V> fmt::Debug for ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a> + ?Sized, + K1: ZeroMapKV<'a> + ?Sized, + V: ZeroMapKV<'a> + ?Sized, + <K0 as ZeroMapKV<'a>>::Container: fmt::Debug, + <K1 as ZeroMapKV<'a>>::Container: fmt::Debug, + <V as ZeroMapKV<'a>>::Container: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> { + f.debug_struct("ZeroMap2d") + .field("keys0", &self.keys0) + .field("joiner", &self.joiner) + .field("keys1", &self.keys1) + .field("values", &self.values) + .finish() + } +} + +impl<'a, K0, K1, V> Clone for ZeroMap2d<'a, K0, K1, V> +where + K0: ZeroMapKV<'a> + ?Sized, + K1: ZeroMapKV<'a> + ?Sized, + V: ZeroMapKV<'a> + ?Sized, + <K0 as ZeroMapKV<'a>>::Container: Clone, + <K1 as ZeroMapKV<'a>>::Container: Clone, + <V as ZeroMapKV<'a>>::Container: Clone, +{ + fn clone(&self) -> Self { + Self { + keys0: self.keys0.clone(), + joiner: self.joiner.clone(), + keys1: self.keys1.clone(), + values: self.values.clone(), + } + } +} + +impl<'a, A, B, C, K0, K1, V> FromIterator<(A, B, C)> for ZeroMap2d<'a, K0, K1, V> +where + A: Borrow<K0>, + B: Borrow<K1>, + C: Borrow<V>, + K0: ZeroMapKV<'a> + ?Sized + Ord, + K1: ZeroMapKV<'a> + ?Sized + Ord, + V: ZeroMapKV<'a> + ?Sized, +{ + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = (A, B, C)>, + { + let iter = iter.into_iter(); + let mut map = match iter.size_hint() { + (_, Some(upper)) => Self::with_capacity(upper), + (lower, None) => Self::with_capacity(lower), + }; + + for (key0, key1, value) in iter { + if let Some((key0, key1, value)) = + map.try_append(key0.borrow(), key1.borrow(), value.borrow()) + { + map.insert(key0, key1, value); + } + } + map + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn stress_test() { + let mut zm2d = ZeroMap2d::<u16, str, str>::new(); + + assert_eq!( + format!("{:?}", zm2d), + "ZeroMap2d { keys0: ZeroVec([]), joiner: ZeroVec([]), keys1: [], values: [] }" + ); + assert_eq!(zm2d.get0(&0), None); + + let result = zm2d.try_append(&3, "ccc", "CCC"); + assert!(matches!(result, None)); + + assert_eq!(format!("{:?}", zm2d), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([1]), keys1: [\"ccc\"], values: [\"CCC\"] }"); + assert_eq!(zm2d.get0(&0), None); + assert_eq!(zm2d.get0(&3).unwrap().get1(""), None); + assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC")); + assert_eq!(zm2d.get0(&99), None); + + let result = zm2d.try_append(&3, "eee", "EEE"); + assert!(matches!(result, None)); + + assert_eq!(format!("{:?}", zm2d), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([2]), keys1: [\"ccc\", \"eee\"], values: [\"CCC\", \"EEE\"] }"); + assert_eq!(zm2d.get0(&0), None); + assert_eq!(zm2d.get0(&3).unwrap().get1(""), None); + assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC")); + assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE")); + assert_eq!(zm2d.get0(&3).unwrap().get1("five"), None); + assert_eq!(zm2d.get0(&99), None); + + // Out of order + let result = zm2d.try_append(&3, "ddd", "DD0"); + assert!(matches!(result, Some(_))); + + // Append a few more elements + let result = zm2d.try_append(&5, "ddd", "DD1"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&7, "ddd", "DD2"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&7, "eee", "EEE"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&7, "www", "WWW"); + assert!(matches!(result, None)); + let result = zm2d.try_append(&9, "yyy", "YYY"); + assert!(matches!(result, None)); + + assert_eq!(format!("{:?}", zm2d), "ZeroMap2d { keys0: ZeroVec([3, 5, 7, 9]), joiner: ZeroVec([2, 3, 6, 7]), keys1: [\"ccc\", \"eee\", \"ddd\", \"ddd\", \"eee\", \"www\", \"yyy\"], values: [\"CCC\", \"EEE\", \"DD1\", \"DD2\", \"EEE\", \"WWW\", \"YYY\"] }"); + assert_eq!(zm2d.get0(&0), None); + assert_eq!(zm2d.get0(&3).unwrap().get1(""), None); + assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC")); + assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE")); + assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&4), None); + assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1")); + assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&6), None); + assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2")); + assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE")); + assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW")); + assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None); + assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&8), None); + assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None); + assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY")); + assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&10), None); + assert_eq!(zm2d.get0(&99), None); + + // Insert some elements + zm2d.insert(&3, "mmm", "MM0"); + zm2d.insert(&6, "ddd", "DD3"); + zm2d.insert(&6, "mmm", "MM1"); + zm2d.insert(&6, "nnn", "NNN"); + + assert_eq!(format!("{:?}", zm2d), "ZeroMap2d { keys0: ZeroVec([3, 5, 6, 7, 9]), joiner: ZeroVec([3, 4, 7, 10, 11]), keys1: [\"ccc\", \"eee\", \"mmm\", \"ddd\", \"ddd\", \"mmm\", \"nnn\", \"ddd\", \"eee\", \"www\", \"yyy\"], values: [\"CCC\", \"EEE\", \"MM0\", \"DD1\", \"DD3\", \"MM1\", \"NNN\", \"DD2\", \"EEE\", \"WWW\", \"YYY\"] }"); + assert_eq!(zm2d.get0(&0), None); + assert_eq!(zm2d.get0(&3).unwrap().get1(""), None); + assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC")); + assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE")); + assert_eq!(zm2d.get_2d(&3, "mmm"), Some("MM0")); + assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&4), None); + assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1")); + assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&6).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get_2d(&6, "ddd"), Some("DD3")); + assert_eq!(zm2d.get_2d(&6, "mmm"), Some("MM1")); + assert_eq!(zm2d.get_2d(&6, "nnn"), Some("NNN")); + assert_eq!(zm2d.get0(&6).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2")); + assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE")); + assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW")); + assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None); + assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&8), None); + assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None); + assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None); + assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY")); + assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None); + assert_eq!(zm2d.get0(&10), None); + assert_eq!(zm2d.get0(&99), None); + + // Remove some elements + let result = zm2d.remove(&3, "ccc"); // first element + assert_eq!(result, Some(String::from("CCC").into_boxed_str())); + let result = zm2d.remove(&3, "mmm"); // middle element + assert_eq!(result, Some(String::from("MM0").into_boxed_str())); + let result = zm2d.remove(&5, "ddd"); // singleton K0 + assert_eq!(result, Some(String::from("DD1").into_boxed_str())); + let result = zm2d.remove(&9, "yyy"); // last element + assert_eq!(result, Some(String::from("YYY").into_boxed_str())); + + assert_eq!(format!("{:?}", zm2d), "ZeroMap2d { keys0: ZeroVec([3, 6, 7]), joiner: ZeroVec([1, 4, 7]), keys1: [\"eee\", \"ddd\", \"mmm\", \"nnn\", \"ddd\", \"eee\", \"www\"], values: [\"EEE\", \"DD3\", \"MM1\", \"NNN\", \"DD2\", \"EEE\", \"WWW\"] }"); + } +} |