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 ).
7 use alloc
::borrow
::Borrow
;
8 use core
::cmp
::Ordering
;
9 use core
::convert
::TryFrom
;
11 use core
::iter
::FromIterator
;
15 use crate::map
::ZeroMapKV
;
16 use crate::map
::{MutableZeroVecLike, ZeroVecLike}
;
18 /// A zero-copy, two-dimensional map datastructure .
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:
24 /// # use zerovec::ZeroMap2d;
25 /// let _: ZeroMap2d<u32, str, [u8]> = unimplemented!();
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.
34 /// use zerovec::ZeroMap2d;
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,
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"));
50 /// [`VarZeroVec`]: crate::VarZeroVec
51 /// [`ZeroMap`]: crate::ZeroMap
52 // ZeroMap2d contains 4 fields:
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)
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.
62 // Required Invariants:
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
69 // Optional Invariants:
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)
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.
77 pub struct ZeroMap2d
<'a
, K0
, K1
, V
>
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
,
92 impl<'a
, K0
, K1
, V
> Default
for ZeroMap2d
<'a
, K0
, K1
, V
>
101 fn default() -> Self {
106 impl<'a
, K0
, K1
, V
> ZeroMap2d
<'a
, K0
, K1
, V
>
115 /// Creates a new, empty `ZeroMap2d`.
120 /// use zerovec::ZeroMap2d;
122 /// let zm: ZeroMap2d<u16, str, str> = ZeroMap2d::new();
123 /// assert!(zm.is_empty());
125 pub fn new() -> 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),
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
,
149 /// Construct a new [`ZeroMap2d`] with a given capacity
150 pub fn with_capacity(capacity
: usize) -> 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
),
159 /// Obtain a borrowed version of this map
160 pub fn as_borrowed(&'a
self) -> ZeroMap2dBorrowed
<'a
, K0
, K1
, V
> {
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(),
169 /// The number of values in the [`ZeroMap2d`]
170 pub fn len(&self) -> usize {
171 self.values
.zvl_len()
174 /// Whether the [`ZeroMap2d`] is empty
175 pub fn is_empty(&self) -> bool
{
176 self.values
.zvl_len() == 0
179 /// Remove all elements from the [`ZeroMap2d`]
180 pub fn clear(&mut self) {
181 self.keys0
.zvl_clear();
183 self.keys1
.zvl_clear();
184 self.values
.zvl_clear();
187 /// Reserve capacity for `additional` more elements to be inserted into
188 /// the [`ZeroMap2d`] to avoid frequent reallocations.
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
);
198 /// Produce an ordered iterator over keys0, which can then be used to get an iterator
199 /// over keys1 for a particular key0.
203 /// Loop over all elements of a ZeroMap2d:
206 /// use zerovec::ZeroMap2d;
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");
213 /// let mut total_value = 0;
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();
224 /// assert_eq!(total_value, 22);
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
))
230 // INTERNAL ROUTINES FOLLOW //
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()
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
));
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
250 .for_each(|ref mut v
| {
251 // TODO(#1410): Make this fallible
255 .expect("Attempted to add more than 2^32 elements to a ZeroMap2d")
260 /// Shifts all joiner ranges from key0_index onward one index down
261 fn joiner_shrink(&mut self, key0_index
: usize) {
266 .for_each(|ref mut v
| **v
= (v
.as_unsigned_int() - 1).to_unaligned())
270 impl<'a
, K0
, K1
, V
> ZeroMap2d
<'a
, K0
, K1
, V
>
272 K0
: ZeroMapKV
<'a
> + Ord
,
273 K1
: ZeroMapKV
<'a
> + Ord
,
279 /// Get the value associated with `key0` and `key1`, if it exists.
281 /// For more fine-grained error handling, use [`ZeroMap2d::get0`].
284 /// use zerovec::ZeroMap2d;
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);
296 pub fn get_2d(&self, key0
: &K0
, key1
: &K1
) -> Option
<&V
::GetType
> {
297 self.get0(key0
)?
.get1(key1
)
300 /// Insert `value` with `key`, returning the existing value if it exists.
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
)),
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();
321 /// Remove the value at `key`, returning it if it exists.
324 /// use zerovec::ZeroMap2d;
326 /// let mut map = ZeroMap2d::new();
327 /// map.insert(&1, "one", "foo");
328 /// map.insert(&2, "two", "bar");
330 /// map.remove(&1, "one"),
331 /// Some("foo".to_owned().into_boxed_str())
333 /// assert_eq!(map.get_2d(&1, "one"), None);
334 /// assert_eq!(map.remove(&1, "one"), None);
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
346 .zvl_binary_search_in_range(key1
, range
)
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
);
355 #[cfg(debug_assertions)]
356 self.check_invariants();
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
365 /// use zerovec::ZeroMap2d;
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());
371 /// let unsuccessful = map.try_append(&3, "three", "tres-updated");
372 /// assert!(unsuccessful.is_some(), "append duplicate of last key");
374 /// let unsuccessful = map.try_append(&2, "two", "dos");
375 /// assert!(unsuccessful.is_some(), "append out of order");
377 /// assert_eq!(map.get_2d(&1, "one"), Some("uno"));
379 /// // contains the original value for the key: 3
380 /// assert_eq!(map.get_2d(&3, "three"), Some("tres"));
382 /// // not appended since it wasn't in order
383 /// assert_eq!(map.get_2d(&2, "two"), None);
386 pub fn try_append
<'b
>(
391 ) -> Option
<(&'b K0
, &'b K1
, &'b V
)> {
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
);
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
);
408 // Check for error case (out of order)
412 return Some((key0
, key1
, value
));
416 Ordering
::Less
| Ordering
::Equal
=> {
418 return Some((key0
, key1
, value
));
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");
431 #[allow(clippy::unwrap_used)]
432 if key0_cmp
== Ordering
::Greater
{
433 self.keys0
.zvl_push(key0
);
435 .with_mut(|v
| v
.push(joiner_value
.to_unaligned()));
437 // This unwrap is protected because we are not empty
438 *self.joiner
.to_mut_slice().last_mut().unwrap() = joiner_value
.to_unaligned();
440 self.keys1
.zvl_push(key1
);
441 self.values
.zvl_push(value
);
443 #[cfg(debug_assertions)]
444 self.check_invariants();
449 // INTERNAL ROUTINES FOLLOW //
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());
461 for i
in 0..self.joiner
.len() {
465 self.joiner
.get(i
- 1).unwrap() as usize
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
));
478 impl<'a
, K0
, K1
, V
> ZeroMap2d
<'a
, K0
, K1
, V
>
480 K0
: ZeroMapKV
<'a
> + Ord
,
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.
491 /// use zerovec::ZeroMap2d;
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);
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
))
509 /// Binary search the map for `key0`, returning a cursor.
512 /// use zerovec::maps::ZeroMap2dBorrowed;
513 /// use zerovec::ZeroMap2d;
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));
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
))
529 /// Returns whether `key0` is contained in this map
532 /// use zerovec::ZeroMap2d;
534 /// let mut map = ZeroMap2d::new();
535 /// map.insert(&1, "one", "foo");
536 /// map.insert(&2, "two", "bar");
537 /// assert_eq!(map.contains_key0(&1), true);
538 /// assert_eq!(map.contains_key0(&3), false);
540 pub fn contains_key0(&self, key0
: &K0
) -> bool
{
541 self.keys0
.zvl_binary_search(key0
).is_ok()
544 // INTERNAL ROUTINES FOLLOW //
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
)),
551 // Add an entry to self.keys0 and self.joiner
552 let joiner_value
= if key0_index
== 0 {
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()
560 self.keys0
.zvl_insert(key0_index
, key0
);
562 .with_mut(|v
| v
.insert(key0_index
, joiner_value
.to_unaligned()));
563 (key0_index
, (joiner_value
as usize)..(joiner_value
as usize))
569 impl<'a
, K0
, K1
, V
> ZeroMap2d
<'a
, K0
, K1
, V
>
571 K0
: ZeroMapKV
<'a
> + Ord
,
572 K1
: ZeroMapKV
<'a
> + Ord
,
578 /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`
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);
589 /// assert_eq!(map.get_copied_2d(&6, &7), Some(8));
592 pub fn get_copied_2d(&self, key0
: &K0
, key1
: &K1
) -> Option
<V
> {
593 self.get0(key0
)?
.get1_copied(key1
)
597 impl<'a
, K0
, K1
, V
> From
<ZeroMap2dBorrowed
<'a
, K0
, K1
, V
>> for ZeroMap2d
<'a
, K0
, K1
, V
>
606 fn from(other
: ZeroMap2dBorrowed
<'a
, K0
, K1
, V
>) -> 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
),
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
619 impl<'a
, 'b
, K0
, K1
, V
> PartialEq
<ZeroMap2d
<'b
, K0
, K1
, V
>> for ZeroMap2d
<'a
, K0
, K1
, V
>
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
>,
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
)
636 impl<'a
, K0
, K1
, V
> fmt
::Debug
for ZeroMap2d
<'a
, K0
, K1
, V
>
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
,
645 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> Result
<(), fmt
::Error
> {
646 f
.debug_struct("ZeroMap2d")
647 .field("keys0", &self.keys0
)
648 .field("joiner", &self.joiner
)
649 .field("keys1", &self.keys1
)
650 .field("values", &self.values
)
655 impl<'a
, K0
, K1
, V
> Clone
for ZeroMap2d
<'a
, K0
, K1
, V
>
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
,
664 fn clone(&self) -> Self {
666 keys0
: self.keys0
.clone(),
667 joiner
: self.joiner
.clone(),
668 keys1
: self.keys1
.clone(),
669 values
: self.values
.clone(),
674 impl<'a
, A
, B
, C
, K0
, K1
, V
> FromIterator
<(A
, B
, C
)> for ZeroMap2d
<'a
, K0
, K1
, V
>
679 K0
: ZeroMapKV
<'a
> + ?Sized
+ Ord
,
680 K1
: ZeroMapKV
<'a
> + ?Sized
+ Ord
,
681 V
: ZeroMapKV
<'a
> + ?Sized
,
683 fn from_iter
<T
>(iter
: T
) -> Self
685 T
: IntoIterator
<Item
= (A
, B
, C
)>,
687 let iter
= iter
.into_iter();
688 let mut map
= match iter
.size_hint() {
689 (_
, Some(upper
)) => Self::with_capacity(upper
),
690 (lower
, None
) => Self::with_capacity(lower
),
693 for (key0
, key1
, value
) in iter
{
694 if let Some((key0
, key1
, value
)) =
695 map
.try_append(key0
.borrow(), key1
.borrow(), value
.borrow())
697 map
.insert(key0
, key1
, value
);
710 let mut zm2d
= ZeroMap2d
::<u16, str, str>::new();
713 format
!("{:?}", zm2d
),
714 "ZeroMap2d { keys0: ZeroVec([]), joiner: ZeroVec([]), keys1: [], values: [] }"
716 assert_eq
!(zm2d
.get0(&0), None
);
718 let result
= zm2d
.try_append(&3, "ccc", "CCC");
719 assert
!(matches
!(result
, None
));
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
);
727 let result
= zm2d
.try_append(&3, "eee", "EEE");
728 assert
!(matches
!(result
, None
));
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
);
739 let result
= zm2d
.try_append(&3, "ddd", "DD0");
740 assert
!(matches
!(result
, Some(_
)));
742 // Append a few more elements
743 let result
= zm2d
.try_append(&5, "ddd", "DD1");
744 assert
!(matches
!(result
, None
));
745 let result
= zm2d
.try_append(&7, "ddd", "DD2");
746 assert
!(matches
!(result
, None
));
747 let result
= zm2d
.try_append(&7, "eee", "EEE");
748 assert
!(matches
!(result
, None
));
749 let result
= zm2d
.try_append(&7, "www", "WWW");
750 assert
!(matches
!(result
, None
));
751 let result
= zm2d
.try_append(&9, "yyy", "YYY");
752 assert
!(matches
!(result
, None
));
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
);
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");
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
);
815 // Remove some elements
816 let result
= zm2d
.remove(&3, "ccc"); // first element
817 assert_eq
!(result
, Some(String
::from("CCC").into_boxed_str()));
818 let result
= zm2d
.remove(&3, "mmm"); // middle element
819 assert_eq
!(result
, Some(String
::from("MM0").into_boxed_str()));
820 let result
= zm2d
.remove(&5, "ddd"); // singleton K0
821 assert_eq
!(result
, Some(String
::from("DD1").into_boxed_str()));
822 let result
= zm2d
.remove(&9, "yyy"); // last element
823 assert_eq
!(result
, Some(String
::from("YYY").into_boxed_str()));
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\"] }");