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 /// See example in [`Self::get_2d()`].
303 pub fn insert(&mut self, key0: &K0, key1: &K1, value: &V) -> Option<V::OwnedType> {
304 let (key0_index, range) = self.get_or_insert_range_for_key0(key0);
305 debug_assert!(range.start <= range.end); // '<=' because we may have inserted a new key0
306 debug_assert!(range.end <= self.keys1.zvl_len());
307 #[allow(clippy::unwrap_used)] // by debug_assert! invariants
308 let index = range.start
309 + match self.keys1.zvl_binary_search_in_range(key1, range).unwrap() {
310 Ok(index) => return Some(self.values.zvl_replace(index, value)),
311 Err(index) => index,
312 };
313 self.keys1.zvl_insert(index, key1);
314 self.values.zvl_insert(index, value);
315 self.joiner_expand(key0_index);
316 #[cfg(debug_assertions)]
317 self.check_invariants();
318 None
319 }
320
321 /// Remove the value at `key`, returning it if it exists.
322 ///
323 /// ```rust
324 /// use zerovec::ZeroMap2d;
325 ///
326 /// let mut map = ZeroMap2d::new();
327 /// map.insert(&1, "one", "foo");
328 /// map.insert(&2, "two", "bar");
329 /// assert_eq!(
330 /// map.remove(&1, "one"),
331 /// Some("foo".to_owned().into_boxed_str())
332 /// );
333 /// assert_eq!(map.get_2d(&1, "one"), None);
334 /// assert_eq!(map.remove(&1, "one"), None);
335 /// ```
336 pub fn remove(&mut self, key0: &K0, key1: &K1) -> Option<V::OwnedType> {
337 let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
338 let range = self.get_range_for_key0_index(key0_index);
339 debug_assert!(range.start < range.end); // '<' because every key0 should have a key1
340 debug_assert!(range.end <= self.keys1.zvl_len());
341 let is_singleton_range = range.start + 1 == range.end;
342 #[allow(clippy::unwrap_used)] // by debug_assert invariants
343 let index = range.start
344 + self
345 .keys1
346 .zvl_binary_search_in_range(key1, range)
347 .unwrap()
348 .ok()?;
349 self.keys1.zvl_remove(index);
350 let removed = self.values.zvl_remove(index);
351 self.joiner_shrink(key0_index);
352 if is_singleton_range {
353 self.remove_key0_index(key0_index);
354 }
355 #[cfg(debug_assertions)]
356 self.check_invariants();
357 Some(removed)
358 }
359
360 /// Appends `value` with `key` to the end of the underlying vector, returning
361 /// `key` and `value` _if it failed_. Useful for extending with an existing
362 /// sorted list.
363 ///
364 /// ```rust
365 /// use zerovec::ZeroMap2d;
366 ///
367 /// let mut map = ZeroMap2d::new();
368 /// assert!(map.try_append(&1, "one", "uno").is_none());
369 /// assert!(map.try_append(&3, "three", "tres").is_none());
370 ///
371 /// let unsuccessful = map.try_append(&3, "three", "tres-updated");
372 /// assert!(unsuccessful.is_some(), "append duplicate of last key");
373 ///
374 /// let unsuccessful = map.try_append(&2, "two", "dos");
375 /// assert!(unsuccessful.is_some(), "append out of order");
376 ///
377 /// assert_eq!(map.get_2d(&1, "one"), Some("uno"));
378 ///
379 /// // contains the original value for the key: 3
380 /// assert_eq!(map.get_2d(&3, "three"), Some("tres"));
381 ///
382 /// // not appended since it wasn't in order
383 /// assert_eq!(map.get_2d(&2, "two"), None);
384 /// ```
385 #[must_use]
386 pub fn try_append<'b>(
387 &mut self,
388 key0: &'b K0,
389 key1: &'b K1,
390 value: &'b V,
391 ) -> Option<(&'b K0, &'b K1, &'b V)> {
392 if self.is_empty() {
393 self.keys0.zvl_push(key0);
394 self.joiner.with_mut(|v| v.push(1u32.to_unaligned()));
395 self.keys1.zvl_push(key1);
396 self.values.zvl_push(value);
397 return None;
398 }
399
400 // The unwraps are protected by the fact that we are not empty
401 #[allow(clippy::unwrap_used)]
402 let last_key0 = self.keys0.zvl_get(self.keys0.zvl_len() - 1).unwrap();
403 let key0_cmp = K0::Container::t_cmp_get(key0, last_key0);
404 #[allow(clippy::unwrap_used)]
405 let last_key1 = self.keys1.zvl_get(self.keys1.zvl_len() - 1).unwrap();
406 let key1_cmp = K1::Container::t_cmp_get(key1, last_key1);
407
408 // Check for error case (out of order)
409 match key0_cmp {
410 Ordering::Less => {
411 // Error case
412 return Some((key0, key1, value));
413 }
414 Ordering::Equal => {
415 match key1_cmp {
416 Ordering::Less | Ordering::Equal => {
417 // Error case
418 return Some((key0, key1, value));
419 }
420 _ => {}
421 }
422 }
423 _ => {}
424 }
425
426 #[allow(clippy::expect_used)] // slice overflow
427 let joiner_value = u32::try_from(self.keys1.zvl_len() + 1)
428 .expect("Attempted to add more than 2^32 elements to a ZeroMap2d");
429
430 // All OK to append
431 #[allow(clippy::unwrap_used)]
432 if key0_cmp == Ordering::Greater {
433 self.keys0.zvl_push(key0);
434 self.joiner
435 .with_mut(|v| v.push(joiner_value.to_unaligned()));
436 } else {
437 // This unwrap is protected because we are not empty
438 *self.joiner.to_mut_slice().last_mut().unwrap() = joiner_value.to_unaligned();
439 }
440 self.keys1.zvl_push(key1);
441 self.values.zvl_push(value);
442
443 #[cfg(debug_assertions)]
444 self.check_invariants();
445
446 None
447 }
448
449 // INTERNAL ROUTINES FOLLOW //
450
451 #[cfg(debug_assertions)]
452 #[allow(clippy::unwrap_used)] // this is an assertion function
453 pub(crate) fn check_invariants(&self) {
454 debug_assert_eq!(self.keys0.zvl_len(), self.joiner.len());
455 debug_assert_eq!(self.keys1.zvl_len(), self.values.zvl_len());
456 debug_assert!(self.keys0.zvl_is_ascending());
457 debug_assert!(self.joiner.zvl_is_ascending());
458 if let Some(last_joiner) = self.joiner.last() {
459 debug_assert_eq!(last_joiner as usize, self.keys1.zvl_len());
460 }
461 for i in 0..self.joiner.len() {
462 let j0 = if i == 0 {
463 0
464 } else {
465 self.joiner.get(i - 1).unwrap() as usize
466 };
467 let j1 = self.joiner.get(i).unwrap() as usize;
468 debug_assert_ne!(j0, j1);
469 for j in (j0 + 1)..j1 {
470 let m0 = self.keys1.zvl_get(j - 1).unwrap();
471 let m1 = self.keys1.zvl_get(j).unwrap();
472 debug_assert_eq!(Ordering::Less, K1::Container::get_cmp_get(m0, m1));
473 }
474 }
475 }
476}
477
478impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
479where
480 K0: ZeroMapKV<'a> + Ord,
481 K1: ZeroMapKV<'a>,
482 V: ZeroMapKV<'a>,
483 K0: ?Sized,
484 K1: ?Sized,
485 V: ?Sized,
486{
487 /// Gets a cursor for `key0`. If `None`, then `key0` is not in the map. If `Some`,
488 /// then `key0` is in the map, and `key1` can be queried.
489 ///
490 /// ```rust
491 /// use zerovec::ZeroMap2d;
492 ///
493 /// let mut map = ZeroMap2d::new();
494 /// map.insert(&1u32, "one", "foo");
495 /// map.insert(&2, "one", "bar");
496 /// map.insert(&2, "two", "baz");
497 /// assert_eq!(map.get0(&1).unwrap().get1("one").unwrap(), "foo");
498 /// assert_eq!(map.get0(&1).unwrap().get1("two"), None);
499 /// assert_eq!(map.get0(&2).unwrap().get1("one").unwrap(), "bar");
500 /// assert_eq!(map.get0(&2).unwrap().get1("two").unwrap(), "baz");
501 /// assert_eq!(map.get0(&3), None);
502 /// ```
503 #[inline]
504 pub fn get0<'l>(&'l self, key0: &K0) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> {
505 let key0_index = self.keys0.zvl_binary_search(key0).ok()?;
506 Some(ZeroMap2dCursor::from_cow(self, key0_index))
507 }
508
509 /// Binary search the map for `key0`, returning a cursor.
510 ///
511 /// ```rust
512 /// use zerovec::maps::ZeroMap2dBorrowed;
513 /// use zerovec::ZeroMap2d;
514 ///
515 /// let mut map = ZeroMap2d::new();
516 /// map.insert(&1, "one", "foo");
517 /// map.insert(&2, "two", "bar");
518 /// assert!(matches!(map.get0_by(|probe| probe.cmp(&1)), Some(_)));
519 /// assert!(matches!(map.get0_by(|probe| probe.cmp(&3)), None));
520 /// ```
521 pub fn get0_by<'l>(
522 &'l self,
523 predicate: impl FnMut(&K0) -> Ordering,
524 ) -> Option<ZeroMap2dCursor<'l, 'a, K0, K1, V>> {
525 let key0_index = self.keys0.zvl_binary_search_by(predicate).ok()?;
526 Some(ZeroMap2dCursor::from_cow(self, key0_index))
527 }
528
529 /// Returns whether `key0` is contained in this map
530 ///
531 /// ```rust
532 /// use zerovec::ZeroMap2d;
533 ///
534 /// let mut map = ZeroMap2d::new();
535 /// map.insert(&1, "one", "foo");
536 /// map.insert(&2, "two", "bar");
537 /// assert!(map.contains_key0(&1));
538 /// assert!(!map.contains_key0(&3));
539 /// ```
540 pub fn contains_key0(&self, key0: &K0) -> bool {
541 self.keys0.zvl_binary_search(key0).is_ok()
542 }
543
544 // INTERNAL ROUTINES FOLLOW //
545
546 /// Same as `get_range_for_key0`, but creates key0 if it doesn't already exist
547 fn get_or_insert_range_for_key0(&mut self, key0: &K0) -> (usize, Range<usize>) {
548 match self.keys0.zvl_binary_search(key0) {
549 Ok(key0_index) => (key0_index, self.get_range_for_key0_index(key0_index)),
550 Err(key0_index) => {
551 // Add an entry to self.keys0 and self.joiner
552 let joiner_value = if key0_index == 0 {
553 0
554 } else {
555 debug_assert!(key0_index <= self.joiner.len());
556 // The unwrap is protected by the debug_assert above and key0_index != 0
557 #[allow(clippy::unwrap_used)]
558 self.joiner.get(key0_index - 1).unwrap()
559 };
560 self.keys0.zvl_insert(key0_index, key0);
561 self.joiner
562 .with_mut(|v| v.insert(key0_index, joiner_value.to_unaligned()));
563 (key0_index, (joiner_value as usize)..(joiner_value as usize))
564 }
565 }
566 }
567}
568
569impl<'a, K0, K1, V> ZeroMap2d<'a, K0, K1, V>
570where
571 K0: ZeroMapKV<'a> + Ord,
572 K1: ZeroMapKV<'a> + Ord,
573 V: ZeroMapKV<'a>,
574 V: Copy,
575 K0: ?Sized,
576 K1: ?Sized,
577{
578 /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
579 ///
580 /// # Examples
581 ///
582 /// ```
583 /// # use zerovec::ZeroMap2d;
584 /// let mut map: ZeroMap2d<u16, u16, u16> = ZeroMap2d::new();
585 /// map.insert(&1, &2, &3);
586 /// map.insert(&1, &4, &5);
587 /// map.insert(&6, &7, &8);
588 ///
589 /// assert_eq!(map.get_copied_2d(&6, &7), Some(8));
590 /// ```
591 #[inline]
592 pub fn get_copied_2d(&self, key0: &K0, key1: &K1) -> Option<V> {
593 self.get0(key0)?.get1_copied(key1)
594 }
595}
596
597impl<'a, K0, K1, V> From<ZeroMap2dBorrowed<'a, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>
598where
599 K0: ZeroMapKV<'a>,
600 K1: ZeroMapKV<'a>,
601 V: ZeroMapKV<'a>,
602 K0: ?Sized,
603 K1: ?Sized,
604 V: ?Sized,
605{
606 fn from(other: ZeroMap2dBorrowed<'a, K0, K1, V>) -> Self {
607 Self {
608 keys0: K0::Container::zvl_from_borrowed(other.keys0),
609 joiner: other.joiner.as_zerovec(),
610 keys1: K1::Container::zvl_from_borrowed(other.keys1),
611 values: V::Container::zvl_from_borrowed(other.values),
612 }
613 }
614}
615
616// We can't use the default PartialEq because ZeroMap2d is invariant
617// so otherwise rustc will not automatically allow you to compare ZeroMaps
618// with different lifetimes
619impl<'a, 'b, K0, K1, V> PartialEq<ZeroMap2d<'b, K0, K1, V>> for ZeroMap2d<'a, K0, K1, V>
620where
621 K0: for<'c> ZeroMapKV<'c> + ?Sized,
622 K1: for<'c> ZeroMapKV<'c> + ?Sized,
623 V: for<'c> ZeroMapKV<'c> + ?Sized,
624 <K0 as ZeroMapKV<'a>>::Container: PartialEq<<K0 as ZeroMapKV<'b>>::Container>,
625 <K1 as ZeroMapKV<'a>>::Container: PartialEq<<K1 as ZeroMapKV<'b>>::Container>,
626 <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>,
627{
628 fn eq(&self, other: &ZeroMap2d<'b, K0, K1, V>) -> bool {
629 self.keys0.eq(&other.keys0)
630 && self.joiner.eq(&other.joiner)
631 && self.keys1.eq(&other.keys1)
632 && self.values.eq(&other.values)
633 }
634}
635
636impl<'a, K0, K1, V> fmt::Debug for ZeroMap2d<'a, K0, K1, V>
637where
638 K0: ZeroMapKV<'a> + ?Sized,
639 K1: ZeroMapKV<'a> + ?Sized,
640 V: ZeroMapKV<'a> + ?Sized,
641 <K0 as ZeroMapKV<'a>>::Container: fmt::Debug,
642 <K1 as ZeroMapKV<'a>>::Container: fmt::Debug,
643 <V as ZeroMapKV<'a>>::Container: fmt::Debug,
644{
645 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
646 f&mut DebugStruct<'_, '_>.debug_struct("ZeroMap2d")
647 .field("keys0", &self.keys0)
648 .field("joiner", &self.joiner)
649 .field("keys1", &self.keys1)
650 .field(name:"values", &self.values)
651 .finish()
652 }
653}
654
655impl<'a, K0, K1, V> Clone for ZeroMap2d<'a, K0, K1, V>
656where
657 K0: ZeroMapKV<'a> + ?Sized,
658 K1: ZeroMapKV<'a> + ?Sized,
659 V: ZeroMapKV<'a> + ?Sized,
660 <K0 as ZeroMapKV<'a>>::Container: Clone,
661 <K1 as ZeroMapKV<'a>>::Container: Clone,
662 <V as ZeroMapKV<'a>>::Container: Clone,
663{
664 fn clone(&self) -> Self {
665 Self {
666 keys0: self.keys0.clone(),
667 joiner: self.joiner.clone(),
668 keys1: self.keys1.clone(),
669 values: self.values.clone(),
670 }
671 }
672}
673
674impl<'a, A, B, C, K0, K1, V> FromIterator<(A, B, C)> for ZeroMap2d<'a, K0, K1, V>
675where
676 A: Borrow<K0>,
677 B: Borrow<K1>,
678 C: Borrow<V>,
679 K0: ZeroMapKV<'a> + ?Sized + Ord,
680 K1: ZeroMapKV<'a> + ?Sized + Ord,
681 V: ZeroMapKV<'a> + ?Sized,
682{
683 fn from_iter<T>(iter: T) -> Self
684 where
685 T: IntoIterator<Item = (A, B, C)>,
686 {
687 let iter: ::IntoIter = iter.into_iter();
688 let mut map: ZeroMap2d<'_, K0, K1, V> = match iter.size_hint() {
689 (_, Some(upper: usize)) => Self::with_capacity(upper),
690 (lower: usize, None) => Self::with_capacity(lower),
691 };
692
693 for (key0: A, key1: B, value: C) in iter {
694 if let Some((key0: &K0, key1: &K1, value: &V)) =
695 map.try_append(key0:key0.borrow(), key1:key1.borrow(), value:value.borrow())
696 {
697 map.insert(key0, key1, value);
698 }
699 }
700 map
701 }
702}
703
704#[cfg(test)]
705mod test {
706 use super::*;
707
708 #[test]
709 fn stress_test() {
710 let mut zm2d = ZeroMap2d::<u16, str, str>::new();
711
712 assert_eq!(
713 format!("{zm2d:?}"),
714 "ZeroMap2d { keys0: ZeroVec([]), joiner: ZeroVec([]), keys1: [], values: [] }"
715 );
716 assert_eq!(zm2d.get0(&0), None);
717
718 let result = zm2d.try_append(&3, "ccc", "CCC");
719 assert!(result.is_none());
720
721 assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([1]), keys1: [\"ccc\"], values: [\"CCC\"] }");
722 assert_eq!(zm2d.get0(&0), None);
723 assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
724 assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
725 assert_eq!(zm2d.get0(&99), None);
726
727 let result = zm2d.try_append(&3, "eee", "EEE");
728 assert!(result.is_none());
729
730 assert_eq!(format!("{zm2d:?}"), "ZeroMap2d { keys0: ZeroVec([3]), joiner: ZeroVec([2]), keys1: [\"ccc\", \"eee\"], values: [\"CCC\", \"EEE\"] }");
731 assert_eq!(zm2d.get0(&0), None);
732 assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
733 assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
734 assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
735 assert_eq!(zm2d.get0(&3).unwrap().get1("five"), None);
736 assert_eq!(zm2d.get0(&99), None);
737
738 // Out of order
739 let result = zm2d.try_append(&3, "ddd", "DD0");
740 assert!(result.is_some());
741
742 // Append a few more elements
743 let result = zm2d.try_append(&5, "ddd", "DD1");
744 assert!(result.is_none());
745 let result = zm2d.try_append(&7, "ddd", "DD2");
746 assert!(result.is_none());
747 let result = zm2d.try_append(&7, "eee", "EEE");
748 assert!(result.is_none());
749 let result = zm2d.try_append(&7, "www", "WWW");
750 assert!(result.is_none());
751 let result = zm2d.try_append(&9, "yyy", "YYY");
752 assert!(result.is_none());
753
754 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\"] }");
755 assert_eq!(zm2d.get0(&0), None);
756 assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
757 assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
758 assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
759 assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None);
760 assert_eq!(zm2d.get0(&4), None);
761 assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None);
762 assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1"));
763 assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None);
764 assert_eq!(zm2d.get0(&6), None);
765 assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None);
766 assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2"));
767 assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE"));
768 assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW"));
769 assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None);
770 assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None);
771 assert_eq!(zm2d.get0(&8), None);
772 assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None);
773 assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None);
774 assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY"));
775 assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None);
776 assert_eq!(zm2d.get0(&10), None);
777 assert_eq!(zm2d.get0(&99), None);
778
779 // Insert some elements
780 zm2d.insert(&3, "mmm", "MM0");
781 zm2d.insert(&6, "ddd", "DD3");
782 zm2d.insert(&6, "mmm", "MM1");
783 zm2d.insert(&6, "nnn", "NNN");
784
785 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\"] }");
786 assert_eq!(zm2d.get0(&0), None);
787 assert_eq!(zm2d.get0(&3).unwrap().get1(""), None);
788 assert_eq!(zm2d.get_2d(&3, "ccc"), Some("CCC"));
789 assert_eq!(zm2d.get_2d(&3, "eee"), Some("EEE"));
790 assert_eq!(zm2d.get_2d(&3, "mmm"), Some("MM0"));
791 assert_eq!(zm2d.get0(&3).unwrap().get1("zzz"), None);
792 assert_eq!(zm2d.get0(&4), None);
793 assert_eq!(zm2d.get0(&5).unwrap().get1("aaa"), None);
794 assert_eq!(zm2d.get_2d(&5, "ddd"), Some("DD1"));
795 assert_eq!(zm2d.get0(&5).unwrap().get1("zzz"), None);
796 assert_eq!(zm2d.get0(&6).unwrap().get1("aaa"), None);
797 assert_eq!(zm2d.get_2d(&6, "ddd"), Some("DD3"));
798 assert_eq!(zm2d.get_2d(&6, "mmm"), Some("MM1"));
799 assert_eq!(zm2d.get_2d(&6, "nnn"), Some("NNN"));
800 assert_eq!(zm2d.get0(&6).unwrap().get1("zzz"), None);
801 assert_eq!(zm2d.get0(&7).unwrap().get1("aaa"), None);
802 assert_eq!(zm2d.get_2d(&7, "ddd"), Some("DD2"));
803 assert_eq!(zm2d.get_2d(&7, "eee"), Some("EEE"));
804 assert_eq!(zm2d.get_2d(&7, "www"), Some("WWW"));
805 assert_eq!(zm2d.get0(&7).unwrap().get1("yyy"), None);
806 assert_eq!(zm2d.get0(&7).unwrap().get1("zzz"), None);
807 assert_eq!(zm2d.get0(&8), None);
808 assert_eq!(zm2d.get0(&9).unwrap().get1("aaa"), None);
809 assert_eq!(zm2d.get0(&9).unwrap().get1("www"), None);
810 assert_eq!(zm2d.get_2d(&9, "yyy"), Some("YYY"));
811 assert_eq!(zm2d.get0(&9).unwrap().get1("zzz"), None);
812 assert_eq!(zm2d.get0(&10), None);
813 assert_eq!(zm2d.get0(&99), None);
814
815 // Remove some elements
816 let result = zm2d.remove(&3, "ccc"); // first element
817 assert_eq!(result.as_deref(), Some("CCC"));
818 let result = zm2d.remove(&3, "mmm"); // middle element
819 assert_eq!(result.as_deref(), Some("MM0"));
820 let result = zm2d.remove(&5, "ddd"); // singleton K0
821 assert_eq!(result.as_deref(), Some("DD1"));
822 let result = zm2d.remove(&9, "yyy"); // last element
823 assert_eq!(result.as_deref(), Some("YYY"));
824
825 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\"] }");
826 }
827}
828