Source code
Revision control
Copy as Markdown
Other Tools
// 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
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.
///
/// ```rust
/// use zerovec::ZeroMap2d;
///
/// let mut map = ZeroMap2d::new();
/// assert_eq!(map.insert(&0, "zero", "foo"), None,);
/// assert_eq!(map.insert(&1, "one", "bar"), None,);
/// assert_eq!(map.insert(&1, "one", "baz").as_deref(), Some("bar"),);
/// assert_eq!(map.get_2d(&1, "one").as_deref(), Some("baz"));
/// assert_eq!(map.len(), 2);
/// ```
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());
let range_start = range.start;
#[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(range_start + 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::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!(map.contains_key0(&1));
/// assert!(!map.contains_key0(&3));
/// ```
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);
}
}
#[cfg(debug_assertions)]
map.check_invariants();
map
}
}
#[cfg(test)]
mod test {
use super::*;
use alloc::collections::BTreeMap;
#[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!(result.is_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!(result.is_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!(result.is_some());
// Append a few more elements
let result = zm2d.try_append(&5, "ddd", "DD1");
assert!(result.is_none());
let result = zm2d.try_append(&7, "ddd", "DD2");
assert!(result.is_none());
let result = zm2d.try_append(&7, "eee", "EEE");
assert!(result.is_none());
let result = zm2d.try_append(&7, "www", "WWW");
assert!(result.is_none());
let result = zm2d.try_append(&9, "yyy", "YYY");
assert!(result.is_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.as_deref(), Some("CCC"));
let result = zm2d.remove(&3, "mmm"); // middle element
assert_eq!(result.as_deref(), Some("MM0"));
let result = zm2d.remove(&5, "ddd"); // singleton K0
assert_eq!(result.as_deref(), Some("DD1"));
let result = zm2d.remove(&9, "yyy"); // last element
assert_eq!(result.as_deref(), Some("YYY"));
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\"] }");
}
#[test]
fn zeromap2d_metazone() {
let source_data = [
(*b"aedxb", 0, Some(*b"gulf")),
(*b"afkbl", 0, Some(*b"afgh")),
(*b"ushnl", 0, None),
(*b"ushnl", 7272660, Some(*b"haal")),
(*b"ushnl", 0, None),
(*b"ushnl", 7272660, Some(*b"haal")),
];
let btreemap: BTreeMap<([u8; 5], i32), Option<[u8; 4]>> = source_data
.iter()
.copied()
.map(|(a, b, c)| ((a, b), c))
.collect();
let zeromap2d: ZeroMap2d<[u8; 5], i32, Option<[u8; 4]>> =
source_data.iter().copied().collect();
let mut btreemap_iter = btreemap.iter();
for cursor in zeromap2d.iter0() {
for (key1, value) in cursor.iter1() {
// This code runs for every (key0, key1) pair in order
let expected = btreemap_iter.next().unwrap();
assert_eq!(
(expected.0 .0, expected.0 .1, expected.1),
(*cursor.key0(), key1.as_unsigned_int() as i32, &value.get())
);
}
}
assert!(btreemap_iter.next().is_none());
}
}