zerovec/map2d/
map.rs

Help
1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5use crate::ule::AsULE;
6use crate::ZeroVec;
7use alloc::borrow::Borrow;
8use core::cmp::Ordering;
9use core::convert::TryFrom;
10use core::fmt;
11use core::iter::FromIterator;
12use core::ops::Range;
13
14use super::*;
15use crate::map::ZeroMapKV;
16use crate::map::{MutableZeroVecLike, ZeroVecLike};
17
18/// A zero-copy, two-dimensional map datastructure .
19///
20/// This is an extension of [`ZeroMap`] that supports two layers of keys. For example,
21/// to map a pair of an integer and a string to a buffer, you can write:
22///
23/// ```no_run
24/// # use zerovec::ZeroMap2d;
25/// let _: ZeroMap2d<u32, str, [u8]> = unimplemented!();
26/// ```
27///
28/// Internally, `ZeroMap2d` stores four zero-copy vectors, one for each type argument plus
29/// one more to match between the two vectors of keys.
30///
31/// # Examples
32///
33/// ```
34/// use zerovec::ZeroMap2d;
35///
36/// // Example byte buffer representing the map { 1: {2: "three" } }
37/// let BINCODE_BYTES: &[u8; 51] = &[
38///     2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0,
39///     0, 0, 0, 0, 0, 0, 2, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116,
40///     104, 114, 101, 101,
41/// ];
42///
43/// // Deserializing to ZeroMap requires no heap allocations.
44/// let zero_map: ZeroMap2d<u16, u16, str> =
45///     bincode::deserialize(BINCODE_BYTES)
46///         .expect("Should deserialize successfully");
47/// assert_eq!(zero_map.get_2d(&1, &2), Some("three"));
48/// ```
49///
50/// [`VarZeroVec`]: crate::VarZeroVec
51/// [`ZeroMap`]: crate::ZeroMap
52// ZeroMap2d contains 4 fields:
53//
54// - keys0 = sorted list of all K0 in the map
55// - joiner = helper vec that maps from a K0 to a range of keys1
56// - keys1 = list of all K1 in the map, sorted in ranges for each K0
57// - values = list of all values in the map, sorted by (K0, K1)
58//
59// For a particular K0 at index i, the range of keys1 corresponding to K0 is
60// (joiner[i-1]..joiner[i]), where the first range starts at 0.
61//
62// Required Invariants:
63//
64// 1. len(keys0) == len(joiner)
65// 2. len(keys1) == len(values)
66// 3. joiner is sorted
67// 4. the last element of joiner is the length of keys1
68//
69// Optional Invariants:
70//
71// 5. keys0 is sorted (for binary_search)
72// 6. ranges within keys1 are sorted (for binary_search)
73// 7. every K0 is associated with at least one K1 (no empty ranges)
74//
75// During deserialization, these three invariants are not checked, because they put the
76// ZeroMap2d in a deterministic state, even though it may have unexpected behavior.
77pub struct ZeroMap2d<'a, K0, K1, V>
78where
79    K0: ZeroMapKV<'a>,
80    K1: ZeroMapKV<'a>,
81    V: ZeroMapKV<'a>,
82    K0: ?Sized,
83    K1: ?Sized,
84    V: ?Sized,
85{
86    pub(crate) keys0: K0::Container,
87    pub(crate) joiner: ZeroVec<'a, u32>,
88    pub(crate) keys1: K1::Container,
89    pub(crate) values: V::Container,
90}
91
92impl<'a, K0, K1, V> Default for ZeroMap2d<'a, K0, K1, V>
93where
94    K0: ZeroMapKV<'a>,
95    K1: ZeroMapKV<'a>,
96    V: ZeroMapKV<'a>,
97    K0: ?Sized,
98    K1: ?Sized,
99    V: ?Sized,
100{
101    fn default() -> Self {
102        Self::new()
103    }
104}
105
106impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
107where
108    K0: ZeroMapKV<'a>,
109    K1: ZeroMapKV<'a>,
110    V: ZeroMapKV<'a>,
111    K0: ?Sized,
112    K1: ?Sized,
113    V: ?Sized,
114{
115    /// Creates a new, empty `ZeroMap2d`.
116    ///
117    /// # Examples
118    ///
119    /// ```
120    /// use zerovec::ZeroMap2d;
121    ///
122    /// let zm: ZeroMap2d<u16, str, str> = ZeroMap2d::new();
123    /// assert!(zm.is_empty());
124    /// ```
125    pub fn new() -> Self {
126        Self {
127            keys0: K0::Container::zvl_with_capacity(0),
128            joiner: ZeroVec::new(),
129            keys1: K1::Container::zvl_with_capacity(0),
130            values: V::Container::zvl_with_capacity(0),
131        }
132    }
133
134    #[doc(hidden)] // databake internal
135    pub const unsafe fn from_parts_unchecked(
136        keys0: K0::Container,
137        joiner: ZeroVec<'a, u32>,
138        keys1: K1::Container,
139        values: V::Container,
140    ) -> Self {
141        Self {
142            keys0,
143            joiner,
144            keys1,
145            values,
146        }
147    }
148
149    /// Construct a new [`ZeroMap2d`] with a given capacity
150    pub fn with_capacity(capacity: usize) -> Self {
151        Self {
152            keys0: K0::Container::zvl_with_capacity(capacity),
153            joiner: ZeroVec::with_capacity(capacity),
154            keys1: K1::Container::zvl_with_capacity(capacity),
155            values: V::Container::zvl_with_capacity(capacity),
156        }
157    }
158
159    /// Obtain a borrowed version of this map
160    pub fn as_borrowed(&'a self) -> ZeroMap2dBorrowed<'a, K0, K1, V> {
161        ZeroMap2dBorrowed {
162            keys0: self.keys0.zvl_as_borrowed(),
163            joiner: &self.joiner,
164            keys1: self.keys1.zvl_as_borrowed(),
165            values: self.values.zvl_as_borrowed(),
166        }
167    }
168
169    /// The number of values in the [`ZeroMap2d`]
170    pub fn len(&self) -> usize {
171        self.values.zvl_len()
172    }
173
174    /// Whether the [`ZeroMap2d`] is empty
175    pub fn is_empty(&self) -> bool {
176        self.values.zvl_len() == 0
177    }
178
179    /// Remove all elements from the [`ZeroMap2d`]
180    pub fn clear(&mut self) {
181        self.keys0.zvl_clear();
182        self.joiner.clear();
183        self.keys1.zvl_clear();
184        self.values.zvl_clear();
185    }
186
187    /// Reserve capacity for `additional` more elements to be inserted into
188    /// the [`ZeroMap2d`] to avoid frequent reallocations.
189    ///
190    /// See [`Vec::reserve()`](alloc::vec::Vec::reserve) for more information.
191    pub fn reserve(&mut self, additional: usize) {
192        self.keys0.zvl_reserve(additional);
193        self.joiner.zvl_reserve(additional);
194        self.keys1.zvl_reserve(additional);
195        self.values.zvl_reserve(additional);
196    }
197
198    /// Produce an ordered iterator over keys0, which can then be used to get an iterator
199    /// over keys1 for a particular key0.
200    ///
201    /// # Example
202    ///
203    /// Loop over all elements of a ZeroMap2d:
204    ///
205    /// ```
206    /// use zerovec::ZeroMap2d;
207    ///
208    /// let mut map: ZeroMap2d<u16, u16, str> = ZeroMap2d::new();
209    /// map.insert(&1, &1, "foo");
210    /// map.insert(&2, &3, "bar");
211    /// map.insert(&2, &4, "baz");
212    ///
213    /// let mut total_value = 0;
214    ///
215    /// for cursor in map.iter0() {
216    ///     for (key1, value) in cursor.iter1() {
217    ///         // This code runs for every (key0, key1) pair
218    ///         total_value += cursor.key0().as_unsigned_int() as usize;
219    ///         total_value += key1.as_unsigned_int() as usize;
220    ///         total_value += value.len();
221    ///     }
222    /// }
223    ///
224    /// assert_eq!(total_value, 22);
225    /// ```
226    pub fn iter0<'l>(&'l self) -> impl Iterator<Item = ZeroMap2dCursor<'l, 'a, K0, K1, V>> + 'l {
227        (0..self.keys0.zvl_len()).map(move |idx| ZeroMap2dCursor::from_cow(self, idx))
228    }
229
230    // INTERNAL ROUTINES FOLLOW //
231
232    /// Given an index into the joiner array, returns the corresponding range of keys1
233    fn get_range_for_key0_index(&self, key0_index: usize) -> Range<usize> {
234        ZeroMap2dCursor::from_cow(self, key0_index).get_range()
235    }
236
237    /// Removes key0_index from the keys0 array and the joiner array
238    fn remove_key0_index(&mut self, key0_index: usize) {
239        self.keys0.zvl_remove(key0_index);
240        self.joiner.with_mut(|v| v.remove(key0_index));
241    }
242
243    /// Shifts all joiner ranges from key0_index onward one index up
244    fn joiner_expand(&mut self, key0_index: usize) {
245        #[allow(clippy::expect_used)] // slice overflow
246        self.joiner
247            .to_mut_slice()
248            .iter_mut()
249            .skip(key0_index)
250            .for_each(|ref mut v| {
251                // TODO(#1410): Make this fallible
252                **v = v
253                    .as_unsigned_int()
254                    .checked_add(1)
255                    .expect("Attempted to add more than 2^32 elements to a ZeroMap2d")
256                    .to_unaligned()
257            })
258    }
259
260    /// Shifts all joiner ranges from key0_index onward one index down
261    fn joiner_shrink(&mut self, key0_index: usize) {
262        self.joiner
263            .to_mut_slice()
264            .iter_mut()
265            .skip(key0_index)
266            .for_each(|ref mut v| **v = (v.as_unsigned_int() - 1).to_unaligned())
267    }
268}
269
270impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
271where
272    K0: ZeroMapKV<'a> + Ord,
273    K1: ZeroMapKV<'a> + Ord,
274    V: ZeroMapKV<'a>,
275    K0: ?Sized,
276    K1: ?Sized,
277    V: ?Sized,
278{
279    /// Get the value associated with `key0` and `key1`, if it exists.
280    ///
281    /// For more fine-grained error handling, use [`ZeroMap2d::get0`].
282    ///
283    /// ```rust
284    /// use zerovec::ZeroMap2d;
285    ///
286    /// let mut map = ZeroMap2d::new();
287    /// map.insert(&1, "one", "foo");
288    /// map.insert(&2, "one", "bar");
289    /// map.insert(&2, "two", "baz");
290    /// assert_eq!(map.get_2d(&1, "one"), Some("foo"));
291    /// assert_eq!(map.get_2d(&1, "two"), None);
292    /// assert_eq!(map.get_2d(&2, "one"), Some("bar"));
293    /// assert_eq!(map.get_2d(&2, "two"), Some("baz"));
294    /// assert_eq!(map.get_2d(&3, "three"), None);
295    /// ```
296    pub fn get_2d(&self, key0: &K0, key1: &K1) -> Option<&V::GetType> {
297        self.get0(key0)?.get1(key1)
298    }
299
300    /// Insert `value` with `key`, returning the existing value if it exists.
301    ///
302    /// ```rust
303    /// use zerovec::ZeroMap2d;
304    ///
305    /// let mut map = ZeroMap2d::new();
306    /// assert_eq!(map.insert(&0, "zero", "foo"), None,);
307    /// assert_eq!(map.insert(&1, "one", "bar"), None,);
308    /// assert_eq!(map.insert(&1, "one", "baz").as_deref(), Some("bar"),);
309    /// assert_eq!(map.get_2d(&1, "one").as_deref(), Some("baz"));
310    /// assert_eq!(map.len(), 2);
311    /// ```
312    pub fn insert(&mut self, key0: &K0, key1: &K1, value: &V) -> Option<V::OwnedType> {
313        let (key0_index, range) = self.get_or_insert_range_for_key0(key0);
314        debug_assert!(range.start <= range.end); // '<=' because we may have inserted a new key0
315        debug_assert!(range.end <= self.keys1.zvl_len());
316        let range_start = range.start;
317        #[allow(clippy::unwrap_used)] // by debug_assert! invariants
318        let index = range_start
319            + match self.keys1.zvl_binary_search_in_range(key1, range).unwrap() {
320                Ok(index) => return Some(self.values.zvl_replace(range_start + index, value)),
321                Err(index) => index,
322            };
323        self.keys1.zvl_insert(index, key1);
324        self.values.zvl_insert(index, value);
325        self.joiner_expand(key0_index);
326        #[cfg(debug_assertions)]
327        self.check_invariants();
328        None
329    }
330
331    /// Remove the value at `key`, returning it if it exists.
332    ///
333    /// ```rust
334    /// use zerovec::ZeroMap2d;
335    ///
336    /// let mut map = ZeroMap2d::new();
337    /// map.insert(&1, "one", "foo");
338    /// map.insert(&2, "two", "bar");
339    /// assert_eq!(
340    ///     map.remove(&1, "one"),
341    ///     Some("foo".to_owned().into_boxed_str())
342    /// );
343    /// assert_eq!(map.get_2d(&1, "one"), None);
344    /// assert_eq!(map.remove(&1, "one"), None);
345    /// ```
346    pub fn remove(&mut self, key0: &K0, key1: &K1) -> Option<V::OwnedType> {
347        let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
348        let range = self.get_range_for_key0_index(key0_index);
349        debug_assert!(range.start < range.end); // '<' because every key0 should have a key1
350        debug_assert!(range.end <= self.keys1.zvl_len());
351        let is_singleton_range = range.start + 1 == range.end;
352        #[allow(clippy::unwrap_used)] // by debug_assert invariants
353        let index = range.start
354            + self
355                .keys1
356                .zvl_binary_search_in_range(key1, range)
357                .unwrap()
358                .ok()?;
359        self.keys1.zvl_remove(index);
360        let removed = self.values.zvl_remove(index);
361        self.joiner_shrink(key0_index);
362        if is_singleton_range {
363            self.remove_key0_index(key0_index);
364        }
365        #[cfg(debug_assertions)]
366        self.check_invariants();
367        Some(removed)
368    }
369
370    /// Appends `value` with `key` to the end of the underlying vector, returning
371    /// `key` and `value` _if it failed_. Useful for extending with an existing
372    /// sorted list.
373    ///
374    /// ```rust
375    /// use zerovec::ZeroMap2d;
376    ///
377    /// let mut map = ZeroMap2d::new();
378    /// assert!(map.try_append(&1, "one", "uno").is_none());
379    /// assert!(map.try_append(&3, "three", "tres").is_none());
380    ///
381    /// let unsuccessful = map.try_append(&3, "three", "tres-updated");
382    /// assert!(unsuccessful.is_some(), "append duplicate of last key");
383    ///
384    /// let unsuccessful = map.try_append(&2, "two", "dos");
385    /// assert!(unsuccessful.is_some(), "append out of order");
386    ///
387    /// assert_eq!(map.get_2d(&1, "one"), Some("uno"));
388    ///
389    /// // contains the original value for the key: 3
390    /// assert_eq!(map.get_2d(&3, "three"), Some("tres"));
391    ///
392    /// // not appended since it wasn't in order
393    /// assert_eq!(map.get_2d(&2, "two"), None);
394    /// ```
395    #[must_use]
396    pub fn try_append<'b>(
397        &mut self,
398        key0: &'b K0,
399        key1: &'b K1,
400        value: &'b V,
401    ) -> Option<(&'b K0, &'b K1, &'b V)> {
402        if self.is_empty() {
403            self.keys0.zvl_push(key0);
404            self.joiner.with_mut(|v| v.push(1u32.to_unaligned()));
405            self.keys1.zvl_push(key1);
406            self.values.zvl_push(value);
407            return None;
408        }
409
410        // The unwraps are protected by the fact that we are not empty
411        #[allow(clippy::unwrap_used)]
412        let last_key0 = self.keys0.zvl_get(self.keys0.zvl_len() - 1).unwrap();
413        let key0_cmp = K0::Container::t_cmp_get(key0, last_key0);
414        #[allow(clippy::unwrap_used)]
415        let last_key1 = self.keys1.zvl_get(self.keys1.zvl_len() - 1).unwrap();
416        let key1_cmp = K1::Container::t_cmp_get(key1, last_key1);
417
418        // Check for error case (out of order)
419        match key0_cmp {
420            Ordering::Less => {
421                // Error case
422                return Some((key0, key1, value));
423            }
424            Ordering::Equal => {
425                match key1_cmp {
426                    Ordering::Less | Ordering::Equal => {
427                        // Error case
428                        return Some((key0, key1, value));
429                    }
430                    _ => {}
431                }
432            }
433            _ => {}
434        }
435
436        #[allow(clippy::expect_used)] // slice overflow
437        let joiner_value = u32::try_from(self.keys1.zvl_len() + 1)
438            .expect("Attempted to add more than 2^32 elements to a ZeroMap2d");
439
440        // All OK to append
441        #[allow(clippy::unwrap_used)]
442        if key0_cmp == Ordering::Greater {
443            self.keys0.zvl_push(key0);
444            self.joiner
445                .with_mut(|v| v.push(joiner_value.to_unaligned()));
446        } else {
447            // This unwrap is protected because we are not empty
448            *self.joiner.to_mut_slice().last_mut().unwrap() = joiner_value.to_unaligned();
449        }
450        self.keys1.zvl_push(key1);
451        self.values.zvl_push(value);
452
453        #[cfg(debug_assertions)]
454        self.check_invariants();
455
456        None
457    }
458
459    // INTERNAL ROUTINES FOLLOW //
460
461    #[cfg(debug_assertions)]
462    #[allow(clippy::unwrap_used)] // this is an assertion function
463    pub(crate) fn check_invariants(&self) {
464        debug_assert_eq!(self.keys0.zvl_len(), self.joiner.len());
465        debug_assert_eq!(self.keys1.zvl_len(), self.values.zvl_len());
466        debug_assert!(self.keys0.zvl_is_ascending());
467        debug_assert!(self.joiner.zvl_is_ascending());
468        if let Some(last_joiner) = self.joiner.last() {
469            debug_assert_eq!(last_joiner as usize, self.keys1.zvl_len());
470        }
471        for i in 0..self.joiner.len() {
472            let j0 = if i == 0 {
473                0
474            } else {
475                self.joiner.get(i - 1).unwrap() as usize
476            };
477            let j1 = self.joiner.get(i).unwrap() as usize;
478            debug_assert_ne!(j0, j1);
479            for j in (j0 + 1)..j1 {
480                let m0 = self.keys1.zvl_get(j - 1).unwrap();
481                let m1 = self.keys1.zvl_get(j).unwrap();
482                debug_assert_eq!(Ordering::Less, K1::Container::get_cmp_get(m0, m1));
483            }
484        }
485    }
486}
487
488impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
489where
490    K0: ZeroMapKV<'a> + Ord,
491    K1: ZeroMapKV<'a>,
492    V: ZeroMapKV<'a>,
493    K0: ?Sized,
494    K1: ?Sized,
495    V: ?Sized,
496{
497    /// Gets a cursor for `key0`. If `None`, then `key0` is not in the map. If `Some`,
498    /// then `key0` is in the map, and `key1` can be queried.
499    ///
500    /// ```rust
501    /// use zerovec::ZeroMap2d;
502    ///
503    /// let mut map = ZeroMap2d::new();
504    /// map.insert(&1u32, "one", "foo");
505    /// map.insert(&2, "one", "bar");
506    /// map.insert(&2, "two", "baz");
507    /// assert_eq!(map.get0(&1).unwrap().get1("one").unwrap(), "foo");
508    /// assert_eq!(map.get0(&1).unwrap().get1("two"), None);
509    /// assert_eq!(map.get0(&2).unwrap().get1("one").unwrap(), "bar");
510    /// assert_eq!(map.get0(&2).unwrap().get1("two").unwrap(), "baz");
511    /// assert_eq!(map.get0(&3), None);
512    /// ```
513    #[inline]
514    pub fn get0<'l>(&'l self, key0: &K0) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> {
515        let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
516        Some(ZeroMap2dCursor::from_cow(self, key0_index))
517    }
518
519    /// Binary search the map for `key0`, returning a cursor.
520    ///
521    /// ```rust
522    /// use zerovec::ZeroMap2d;
523    ///
524    /// let mut map = ZeroMap2d::new();
525    /// map.insert(&1, "one", "foo");
526    /// map.insert(&2, "two", "bar");
527    /// assert!(matches!(map.get0_by(|probe| probe.cmp(&1)), Some(_)));
528    /// assert!(matches!(map.get0_by(|probe| probe.cmp(&3)), None));
529    /// ```
530    pub fn get0_by<'l>(
531        &'l self,
532        predicate: impl FnMut(&K0) -> Ordering,
533    ) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> {
534        let key0_index = self.keys0.zvl_binary_search_by(predicate).ok()?;
535        Some(ZeroMap2dCursor::from_cow(self, key0_index))
536    }
537
538    /// Returns whether `key0` is contained in this map
539    ///
540    /// ```rust
541    /// use zerovec::ZeroMap2d;
542    ///
543    /// let mut map = ZeroMap2d::new();
544    /// map.insert(&1, "one", "foo");
545    /// map.insert(&2, "two", "bar");
546    /// assert!(map.contains_key0(&1));
547    /// assert!(!map.contains_key0(&3));
548    /// ```
549    pub fn contains_key0(&self, key0: &K0) -> bool {
550        self.keys0.zvl_binary_search(key0).is_ok()
551    }
552
553    // INTERNAL ROUTINES FOLLOW //
554
555    /// Same as `get_range_for_key0`, but creates key0 if it doesn't already exist
556    fn get_or_insert_range_for_key0(&mut self, key0: &K0) -> (usize, Range<usize>) {
557        match self.keys0.zvl_binary_search(key0) {
558            Ok(key0_index) => (key0_index, self.get_range_for_key0_index(key0_index)),
559            Err(key0_index) => {
560                // Add an entry to self.keys0 and self.joiner
561                let joiner_value = if key0_index == 0 {
562                    0
563                } else {
564                    debug_assert!(key0_index <= self.joiner.len());
565                    // The unwrap is protected by the debug_assert above and key0_index != 0
566                    #[allow(clippy::unwrap_used)]
567                    self.joiner.get(key0_index - 1).unwrap()
568                };
569                self.keys0.zvl_insert(key0_index, key0);
570                self.joiner
571                    .with_mut(|v| v.insert(key0_index, joiner_value.to_unaligned()));
572                (key0_index, (joiner_value as usize)..(joiner_value as usize))
573            }
574        }
575    }
576}
577
578impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
579where
580    K0: ZeroMapKV<'a> + Ord,
581    K1: ZeroMapKV<'a> + Ord,
582    V: ZeroMapKV<'a>,
583    V: Copy,
584    K0: ?Sized,
585    K1: ?Sized,
586{
587    /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
588    ///
589    /// # Examples
590    ///
591    /// ```
592    /// # use zerovec::ZeroMap2d;
593    /// let mut map: ZeroMap2d<u16, u16, u16> = ZeroMap2d::new();
594    /// map.insert(&1, &2, &3);
595    /// map.insert(&1, &4, &5);
596    /// map.insert(&6, &7, &8);
597    ///
598    /// assert_eq!(map.get_copied_2d(&6, &7), Some(8));
599    /// ```
600    #[inline]
601    pub fn get_copied_2d(&self, key0: &K0, key1: &K1) -> Option<V> {
602        self.get0(key0)?.get1_copied(key1)
603    }
604}
605
606impl<'a, K0, K1, V> From<ZeroMap2dBorrowed<'a, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>
607where
608    K0: ZeroMapKV<'a>,
609    K1: ZeroMapKV<'a>,
610    V: ZeroMapKV<'a>,
611    K0: ?Sized,
612    K1: ?Sized,
613    V: ?Sized,
614{
615    fn from(other: ZeroMap2dBorrowed<'a, K0, K1, V>) -> Self {
616        Self {
617            keys0: K0::Container::zvl_from_borrowed(other.keys0),
618            joiner: other.joiner.as_zerovec(),
619            keys1: K1::Container::zvl_from_borrowed(other.keys1),
620            values: V::Container::zvl_from_borrowed(other.values),
621        }
622    }
623}
624
625// We can't use the default PartialEq because ZeroMap2d is invariant
626// so otherwise rustc will not automatically allow you to compare ZeroMaps
627// with different lifetimes
628impl<'a, 'b, K0, K1, V> PartialEq<ZeroMap2d<'b, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>
629where
630    K0: for<'c> ZeroMapKV<'c> + ?Sized,
631    K1: for<'c> ZeroMapKV<'c> + ?Sized,
632    V: for<'c> ZeroMapKV<'c> + ?Sized,
633    <K0 as ZeroMapKV<'a>>::Container: PartialEq<<K0 as ZeroMapKV<'b>>::Container>,
634    <K1 as ZeroMapKV<'a>>::Container: PartialEq<<K1 as ZeroMapKV<'b>>::Container>,
635    <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>,
636{
637    fn eq(&self, other: &ZeroMap2d<'b, K0, K1, V>) -> bool {
638        self.keys0.eq(&other.keys0)
639            && self.joiner.eq(&other.joiner)
640            && self.keys1.eq(&other.keys1)
641            && self.values.eq(&other.values)
642    }
643}
644
645impl<'a, K0, K1, V> fmt::Debug for ZeroMap2d<'a, K0, K1, V>
646where
647    K0: ZeroMapKV<'a> + ?Sized,
648    K1: ZeroMapKV<'a> + ?Sized,
649    V: ZeroMapKV<'a> + ?Sized,
650    <K0 as ZeroMapKV<'a>>::Container: fmt::Debug,
651    <K1 as ZeroMapKV<'a>>::Container: fmt::Debug,
652    <V as ZeroMapKV<'a>>::Container: fmt::Debug,
653{
654    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
655        f.debug_struct("ZeroMap2d")
656            .field("keys0", &self.keys0)
657            .field("joiner", &self.joiner)
658            .field("keys1", &self.keys1)
659            .field("values", &self.values)
660            .finish()
661    }
662}
663
664impl<'a, K0, K1, V> Clone for ZeroMap2d<'a, K0, K1, V>
665where
666    K0: ZeroMapKV<'a> + ?Sized,
667    K1: ZeroMapKV<'a> + ?Sized,
668    V: ZeroMapKV<'a> + ?Sized,
669    <K0 as ZeroMapKV<'a>>::Container: Clone,
670    <K1 as ZeroMapKV<'a>>::Container: Clone,
671    <V as ZeroMapKV<'a>>::Container: Clone,
672{
673    fn clone(&self) -> Self {
674        Self {
675            keys0: self.keys0.clone(),
676            joiner: self.joiner.clone(),
677            keys1: self.keys1.clone(),
678            values: self.values.clone(),
679        }
680    }
681}
682
683impl<'a, A, B, C, K0, K1, V> FromIterator<(A, B, C)> for ZeroMap2d<'a, K0, K1, V>
684where
685    A: Borrow<K0>,
686    B: Borrow<K1>,
687    C: Borrow<V>,
688    K0: ZeroMapKV<'a> + ?Sized + Ord,
689    K1: ZeroMapKV<'a> + ?Sized + Ord,
690    V: ZeroMapKV<'a> + ?Sized,
691{
692    fn from_iter<T>(iter: T) -> Self
693    where
694        T: IntoIterator<Item = (A, B, C)>,
695    {
696        let iter = iter.into_iter();
697        let mut map = match iter.size_hint() {
698            (_, Some(upper)) => Self::with_capacity(upper),
699            (lower, None) => Self::with_capacity(lower),
700        };
701
702        for (key0, key1, value) in iter {
703            if let Some((key0, key1, value)) =
704                map.try_append(key0.borrow(), key1.borrow(), value.borrow())
705            {
706                map.insert(key0, key1, value);
707            }
708        }
709        #[cfg(debug_assertions)]
710        map.check_invariants();
711        map
712    }
713}
714
715#[cfg(test)]
716mod test {
717    use super::*;
718    use alloc::collections::BTreeMap;
719
720    #[test]
721    fn stress_test() {
722        let mut zm2d = ZeroMap2d::<u16, str, str>::new();
723
724        assert_eq!(
725            format!("{zm2d:?}"),
726            "ZeroMap2d { keys0: ZeroVec([]), joiner: ZeroVec([]), keys1: [], values: [] }"
727        );
728        assert_eq!(zm2d.get0(&0), None);
729
730        let result = zm2d.try_append(&3, "ccc", "CCC");
731        assert!(result.is_none());
732
733        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([1]), keys1: [\"ccc\"], values: [\"CCC\"] }");
734        assert_eq!(zm2d.get0(&0), None);
735        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
736        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
737        assert_eq!(zm2d.get0(&99), None);
738
739        let result = zm2d.try_append(&3, "eee", "EEE");
740        assert!(result.is_none());
741
742        assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([2]), keys1: [\"ccc\", \"eee\"], values: [\"CCC\", \"EEE\"] }");
743        assert_eq!(zm2d.get0(&0), None);
744        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
745        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
746        assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
747        assert_eq!(zm2d.get0(&3).unwrap().get1("five"), None);
748        assert_eq!(zm2d.get0(&99), None);
749
750        // Out of order
751        let result = zm2d.try_append(&3, "ddd", "DD0");
752        assert!(result.is_some());
753
754        // Append a few more elements
755        let result = zm2d.try_append(&5, "ddd", "DD1");
756        assert!(result.is_none());
757        let result = zm2d.try_append(&7, "ddd", "DD2");
758        assert!(result.is_none());
759        let result = zm2d.try_append(&7, "eee", "EEE");
760        assert!(result.is_none());
761        let result = zm2d.try_append(&7, "www", "WWW");
762        assert!(result.is_none());
763        let result = zm2d.try_append(&9, "yyy", "YYY");
764        assert!(result.is_none());
765
766        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\"] }");
767        assert_eq!(zm2d.get0(&0), None);
768        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
769        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
770        assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
771        assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None);
772        assert_eq!(zm2d.get0(&4), None);
773        assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None);
774        assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1"));
775        assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None);
776        assert_eq!(zm2d.get0(&6), None);
777        assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None);
778        assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2"));
779        assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE"));
780        assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW"));
781        assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None);
782        assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None);
783        assert_eq!(zm2d.get0(&8), None);
784        assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None);
785        assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None);
786        assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY"));
787        assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None);
788        assert_eq!(zm2d.get0(&10), None);
789        assert_eq!(zm2d.get0(&99), None);
790
791        // Insert some elements
792        zm2d.insert(&3, "mmm", "MM0");
793        zm2d.insert(&6, "ddd", "DD3");
794        zm2d.insert(&6, "mmm", "MM1");
795        zm2d.insert(&6, "nnn", "NNN");
796
797        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\"] }");
798        assert_eq!(zm2d.get0(&0), None);
799        assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
800        assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
801        assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
802        assert_eq!(zm2d.get_2d(&3, "mmm"), Some("MM0"));
803        assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None);
804        assert_eq!(zm2d.get0(&4), None);
805        assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None);
806        assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1"));
807        assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None);
808        assert_eq!(zm2d.get0(&6).unwrap().get1("aaa"), None);
809        assert_eq!(zm2d.get_2d(&6, "ddd"), Some("DD3"));
810        assert_eq!(zm2d.get_2d(&6, "mmm"), Some("MM1"));
811        assert_eq!(zm2d.get_2d(&6, "nnn"), Some("NNN"));
812        assert_eq!(zm2d.get0(&6).unwrap().get1("zzz"), None);
813        assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None);
814        assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2"));
815        assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE"));
816        assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW"));
817        assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None);
818        assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None);
819        assert_eq!(zm2d.get0(&8), None);
820        assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None);
821        assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None);
822        assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY"));
823        assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None);
824        assert_eq!(zm2d.get0(&10), None);
825        assert_eq!(zm2d.get0(&99), None);
826
827        // Remove some elements
828        let result = zm2d.remove(&3, "ccc"); // first element
829        assert_eq!(result.as_deref(), Some("CCC"));
830        let result = zm2d.remove(&3, "mmm"); // middle element
831        assert_eq!(result.as_deref(), Some("MM0"));
832        let result = zm2d.remove(&5, "ddd"); // singleton K0
833        assert_eq!(result.as_deref(), Some("DD1"));
834        let result = zm2d.remove(&9, "yyy"); // last element
835        assert_eq!(result.as_deref(), Some("YYY"));
836
837        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\"] }");
838    }
839
840    #[test]
841    fn zeromap2d_metazone() {
842        let source_data = [
843            (*b"aedxb", 0, Some(*b"gulf")),
844            (*b"afkbl", 0, Some(*b"afgh")),
845            (*b"ushnl", 0, None),
846            (*b"ushnl", 7272660, Some(*b"haal")),
847            (*b"ushnl", 0, None),
848            (*b"ushnl", 7272660, Some(*b"haal")),
849        ];
850
851        let btreemap: BTreeMap<([u8; 5], i32), Option<[u8; 4]>> = source_data
852            .iter()
853            .copied()
854            .map(|(a, b, c)| ((a, b), c))
855            .collect();
856
857        let zeromap2d: ZeroMap2d<[u8; 5], i32, Option<[u8; 4]>> =
858            source_data.iter().copied().collect();
859
860        let mut btreemap_iter = btreemap.iter();
861
862        for cursor in zeromap2d.iter0() {
863            for (key1, value) in cursor.iter1() {
864                // This code runs for every (key0, key1) pair in order
865                let expected = btreemap_iter.next().unwrap();
866                assert_eq!(
867                    (expected.0 .0, expected.0 .1, expected.1),
868                    (*cursor.key0(), key1.as_unsigned_int() as i32, &value.get())
869                );
870            }
871        }
872        assert!(btreemap_iter.next().is_none());
873    }
874}
zerovec/map2d/map.rs

zerovec/map2d/
map.rs
