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> dynZeroMapKV<'c> + ?Sized,
631 K1: for<'c> dynZeroMapKV<'c> + ?Sized,
632 V: for<'c> dynZeroMapKV<'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&mut DebugStruct<'_, '_>.debug_struct("ZeroMap2d")
656 .field("keys0", &self.keys0)
657 .field("joiner", &self.joiner)
658 .field("keys1", &self.keys1)
659 .field(name:"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: ::IntoIter = iter.into_iter();
697 let mut map: ZeroMap2d<'_, K0, K1, V> = match iter.size_hint() {
698 (_, Some(upper: usize)) => Self::with_capacity(upper),
699 (lower: usize, None) => Self::with_capacity(lower),
700 };
701
702 for (key0: A, key1: B, value: C) in iter {
703 if let Some((key0: &K0, key1: &K1, value: &V)) =
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}
875