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 super::*;
6use crate::ule::{AsULE, EncodeAsVarULE, VarULE};
7use crate::{VarZeroVec, ZeroSlice, ZeroVec, ZeroVecError};
8use alloc::borrow::Borrow;
9use alloc::boxed::Box;
10use core::cmp::Ordering;
11use core::fmt;
12use core::iter::FromIterator;
13
14/// A zero-copy map datastructure, built on sorted binary-searchable [`ZeroVec`]
15/// and [`VarZeroVec`].
16///
17/// This type, like [`ZeroVec`] and [`VarZeroVec`], is able to zero-copy
18/// deserialize from appropriately formatted byte buffers. It is internally copy-on-write, so it can be mutated
19/// afterwards as necessary.
20///
21/// Internally, a `ZeroMap` is a zero-copy vector for keys paired with a zero-copy vector for
22/// values, sorted by the keys. Therefore, all types used in `ZeroMap` need to work with either
23/// [`ZeroVec`] or [`VarZeroVec`].
24///
25/// This does mean that for fixed-size data, one must use the regular type (`u32`, `u8`, `char`, etc),
26/// whereas for variable-size data, `ZeroMap` will use the dynamically sized version (`str` not `String`,
27/// `ZeroSlice` not `ZeroVec`, `FooULE` not `Foo` for custom types)
28///
29/// # Examples
30///
31/// ```
32/// use zerovec::ZeroMap;
33///
34/// #[derive(serde::Serialize, serde::Deserialize)]
35/// struct Data<'a> {
36/// #[serde(borrow)]
37/// map: ZeroMap<'a, u32, str>,
38/// }
39///
40/// let mut map = ZeroMap::new();
41/// map.insert(&1, "one");
42/// map.insert(&2, "two");
43/// map.insert(&4, "four");
44///
45/// let data = Data { map };
46///
47/// let bincode_bytes =
48/// bincode::serialize(&data).expect("Serialization should be successful");
49///
50/// // Will deserialize without any allocations
51/// let deserialized: Data = bincode::deserialize(&bincode_bytes)
52/// .expect("Deserialization should be successful");
53///
54/// assert_eq!(data.map.get(&1), Some("one"));
55/// assert_eq!(data.map.get(&2), Some("two"));
56/// ```
57///
58/// [`VarZeroVec`]: crate::VarZeroVec
59// ZeroMap has only one invariant: keys.len() == values.len()
60// It is also expected that the keys are sorted, but this is not an invariant. See #1433
61pub struct ZeroMap<'a, K, V>
62where
63 K: ZeroMapKV<'a> + ?Sized,
64 V: ZeroMapKV<'a> + ?Sized,
65{
66 pub(crate) keys: K::Container,
67 pub(crate) values: V::Container,
68}
69
70impl<'a, K, V> Default for ZeroMap<'a, K, V>
71where
72 K: ZeroMapKV<'a> + ?Sized,
73 V: ZeroMapKV<'a> + ?Sized,
74{
75 fn default() -> Self {
76 Self::new()
77 }
78}
79
80impl<'a, K, V> ZeroMap<'a, K, V>
81where
82 K: ZeroMapKV<'a> + ?Sized,
83 V: ZeroMapKV<'a> + ?Sized,
84{
85 /// Creates a new, empty `ZeroMap<K, V>`.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use zerovec::ZeroMap;
91 ///
92 /// let zm: ZeroMap<u16, str> = ZeroMap::new();
93 /// assert!(zm.is_empty());
94 /// ```
95 pub fn new() -> Self {
96 Self {
97 keys: K::Container::zvl_with_capacity(0),
98 values: V::Container::zvl_with_capacity(0),
99 }
100 }
101
102 #[doc(hidden)] // databake internal
103 pub const unsafe fn from_parts_unchecked(keys: K::Container, values: V::Container) -> Self {
104 Self { keys, values }
105 }
106
107 /// Construct a new [`ZeroMap`] with a given capacity
108 pub fn with_capacity(capacity: usize) -> Self {
109 Self {
110 keys: K::Container::zvl_with_capacity(capacity),
111 values: V::Container::zvl_with_capacity(capacity),
112 }
113 }
114
115 /// Obtain a borrowed version of this map
116 pub fn as_borrowed(&'a self) -> ZeroMapBorrowed<'a, K, V> {
117 ZeroMapBorrowed {
118 keys: self.keys.zvl_as_borrowed(),
119 values: self.values.zvl_as_borrowed(),
120 }
121 }
122
123 /// The number of elements in the [`ZeroMap`]
124 pub fn len(&self) -> usize {
125 self.values.zvl_len()
126 }
127
128 /// Whether the [`ZeroMap`] is empty
129 pub fn is_empty(&self) -> bool {
130 self.values.zvl_len() == 0
131 }
132
133 /// Remove all elements from the [`ZeroMap`]
134 pub fn clear(&mut self) {
135 self.keys.zvl_clear();
136 self.values.zvl_clear();
137 }
138
139 /// Reserve capacity for `additional` more elements to be inserted into
140 /// the [`ZeroMap`] to avoid frequent reallocations.
141 ///
142 /// See [`Vec::reserve()`](alloc::vec::Vec::reserve) for more information.
143 pub fn reserve(&mut self, additional: usize) {
144 self.keys.zvl_reserve(additional);
145 self.values.zvl_reserve(additional);
146 }
147}
148impl<'a, K, V> ZeroMap<'a, K, V>
149where
150 K: ZeroMapKV<'a> + ?Sized + Ord,
151 V: ZeroMapKV<'a> + ?Sized,
152{
153 /// Get the value associated with `key`, if it exists.
154 ///
155 /// For fixed-size ([`AsULE`]) `V` types, this _will_ return
156 /// their corresponding [`AsULE::ULE`] type. If you wish to work with the `V`
157 /// type directly, [`Self::get_copied()`] exists for convenience.
158 ///
159 /// ```rust
160 /// use zerovec::ZeroMap;
161 ///
162 /// let mut map = ZeroMap::new();
163 /// map.insert(&1, "one");
164 /// map.insert(&2, "two");
165 /// assert_eq!(map.get(&1), Some("one"));
166 /// assert_eq!(map.get(&3), None);
167 /// ```
168 pub fn get(&self, key: &K) -> Option<&V::GetType> {
169 let index = self.keys.zvl_binary_search(key).ok()?;
170 self.values.zvl_get(index)
171 }
172
173 /// Binary search the map with `predicate` to find a key, returning the value.
174 ///
175 /// ```rust
176 /// use zerovec::ZeroMap;
177 ///
178 /// let mut map = ZeroMap::new();
179 /// map.insert(&1, "one");
180 /// map.insert(&2, "two");
181 /// assert_eq!(map.get_by(|probe| probe.cmp(&1)), Some("one"));
182 /// assert_eq!(map.get_by(|probe| probe.cmp(&3)), None);
183 /// ```
184 pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V::GetType> {
185 let index = self.keys.zvl_binary_search_by(predicate).ok()?;
186 self.values.zvl_get(index)
187 }
188
189 /// Returns whether `key` is contained in this map
190 ///
191 /// ```rust
192 /// use zerovec::ZeroMap;
193 ///
194 /// let mut map = ZeroMap::new();
195 /// map.insert(&1, "one");
196 /// map.insert(&2, "two");
197 /// assert!(map.contains_key(&1));
198 /// assert!(!map.contains_key(&3));
199 /// ```
200 pub fn contains_key(&self, key: &K) -> bool {
201 self.keys.zvl_binary_search(key).is_ok()
202 }
203
204 /// Insert `value` with `key`, returning the existing value if it exists.
205 ///
206 /// ```rust
207 /// use zerovec::ZeroMap;
208 ///
209 /// let mut map = ZeroMap::new();
210 /// map.insert(&1, "one");
211 /// map.insert(&2, "two");
212 /// assert_eq!(map.get(&1), Some("one"));
213 /// assert_eq!(map.get(&3), None);
214 /// ```
215 pub fn insert(&mut self, key: &K, value: &V) -> Option<V::OwnedType> {
216 match self.keys.zvl_binary_search(key) {
217 Ok(index) => Some(self.values.zvl_replace(index, value)),
218 Err(index) => {
219 self.keys.zvl_insert(index, key);
220 self.values.zvl_insert(index, value);
221 None
222 }
223 }
224 }
225
226 /// Remove the value at `key`, returning it if it exists.
227 ///
228 /// ```rust
229 /// use zerovec::ZeroMap;
230 ///
231 /// let mut map = ZeroMap::new();
232 /// map.insert(&1, "one");
233 /// map.insert(&2, "two");
234 /// assert_eq!(map.remove(&1), Some("one".to_owned().into_boxed_str()));
235 /// assert_eq!(map.get(&1), None);
236 /// ```
237 pub fn remove(&mut self, key: &K) -> Option<V::OwnedType> {
238 let idx = self.keys.zvl_binary_search(key).ok()?;
239 self.keys.zvl_remove(idx);
240 Some(self.values.zvl_remove(idx))
241 }
242
243 /// Appends `value` with `key` to the end of the underlying vector, returning
244 /// `key` and `value` _if it failed_. Useful for extending with an existing
245 /// sorted list.
246 /// ```rust
247 /// use zerovec::ZeroMap;
248 ///
249 /// let mut map = ZeroMap::new();
250 /// assert!(map.try_append(&1, "uno").is_none());
251 /// assert!(map.try_append(&3, "tres").is_none());
252 ///
253 /// let unsuccessful = map.try_append(&3, "tres-updated");
254 /// assert!(unsuccessful.is_some(), "append duplicate of last key");
255 ///
256 /// let unsuccessful = map.try_append(&2, "dos");
257 /// assert!(unsuccessful.is_some(), "append out of order");
258 ///
259 /// assert_eq!(map.get(&1), Some("uno"));
260 ///
261 /// // contains the original value for the key: 3
262 /// assert_eq!(map.get(&3), Some("tres"));
263 ///
264 /// // not appended since it wasn't in order
265 /// assert_eq!(map.get(&2), None);
266 /// ```
267 #[must_use]
268 pub fn try_append<'b>(&mut self, key: &'b K, value: &'b V) -> Option<(&'b K, &'b V)> {
269 if self.keys.zvl_len() != 0 {
270 if let Some(last) = self.keys.zvl_get(self.keys.zvl_len() - 1) {
271 if K::Container::t_cmp_get(key, last) != Ordering::Greater {
272 return Some((key, value));
273 }
274 }
275 }
276
277 self.keys.zvl_push(key);
278 self.values.zvl_push(value);
279 None
280 }
281}
282
283impl<'a, K, V> ZeroMap<'a, K, V>
284where
285 K: ZeroMapKV<'a> + ?Sized,
286 V: ZeroMapKV<'a> + ?Sized,
287{
288 /// Produce an ordered iterator over key-value pairs
289 pub fn iter<'b>(
290 &'b self,
291 ) -> impl ExactSizeIterator<
292 Item = (
293 &'b <K as ZeroMapKV<'a>>::GetType,
294 &'b <V as ZeroMapKV<'a>>::GetType,
295 ),
296 > {
297 (0..self.keys.zvl_len()).map(move |idx| {
298 (
299 #[allow(clippy::unwrap_used)] // idx is in-range
300 self.keys.zvl_get(idx).unwrap(),
301 #[allow(clippy::unwrap_used)] // idx is in-range
302 self.values.zvl_get(idx).unwrap(),
303 )
304 })
305 }
306
307 /// Produce an ordered iterator over keys
308 pub fn iter_keys<'b>(
309 &'b self,
310 ) -> impl ExactSizeIterator<Item = &'b <K as ZeroMapKV<'a>>::GetType> {
311 #[allow(clippy::unwrap_used)] // idx is in-range
312 (0..self.keys.zvl_len()).map(move |idx| self.keys.zvl_get(idx).unwrap())
313 }
314
315 /// Produce an iterator over values, ordered by keys
316 pub fn iter_values<'b>(
317 &'b self,
318 ) -> impl ExactSizeIterator<Item = &'b <V as ZeroMapKV<'a>>::GetType> {
319 #[allow(clippy::unwrap_used)] // idx is in-range
320 (0..self.values.zvl_len()).map(move |idx| self.values.zvl_get(idx).unwrap())
321 }
322}
323
324impl<'a, K, V> ZeroMap<'a, K, V>
325where
326 K: ZeroMapKV<'a, Container = ZeroVec<'a, K>> + ?Sized,
327 V: ZeroMapKV<'a> + ?Sized,
328 K: AsULE,
329{
330 /// Cast a `ZeroMap<K, V>` to `ZeroMap<P, V>` where `K` and `P` are [`AsULE`] types
331 /// with the same representation.
332 ///
333 /// # Unchecked Invariants
334 ///
335 /// If `K` and `P` have different ordering semantics, unexpected behavior may occur.
336 pub fn cast_zv_k_unchecked<P>(self) -> ZeroMap<'a, P, V>
337 where
338 P: AsULE<ULE = K::ULE> + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,
339 {
340 ZeroMap {
341 keys: self.keys.cast(),
342 values: self.values,
343 }
344 }
345
346 /// Convert a `ZeroMap<K, V>` to `ZeroMap<P, V>` where `K` and `P` are [`AsULE`] types
347 /// with the same size.
348 ///
349 /// # Unchecked Invariants
350 ///
351 /// If `K` and `P` have different ordering semantics, unexpected behavior may occur.
352 ///
353 /// # Panics
354 ///
355 /// Panics if `K::ULE` and `P::ULE` are not the same size.
356 pub fn try_convert_zv_k_unchecked<P>(self) -> Result<ZeroMap<'a, P, V>, ZeroVecError>
357 where
358 P: AsULE + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,
359 {
360 Ok(ZeroMap {
361 keys: self.keys.try_into_converted()?,
362 values: self.values,
363 })
364 }
365}
366
367impl<'a, K, V> ZeroMap<'a, K, V>
368where
369 K: ZeroMapKV<'a> + ?Sized,
370 V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized,
371 V: AsULE,
372{
373 /// Cast a `ZeroMap<K, V>` to `ZeroMap<K, P>` where `V` and `P` are [`AsULE`] types
374 /// with the same representation.
375 ///
376 /// # Unchecked Invariants
377 ///
378 /// If `V` and `P` have different ordering semantics, unexpected behavior may occur.
379 pub fn cast_zv_v_unchecked<P>(self) -> ZeroMap<'a, K, P>
380 where
381 P: AsULE<ULE = V::ULE> + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,
382 {
383 ZeroMap {
384 keys: self.keys,
385 values: self.values.cast(),
386 }
387 }
388
389 /// Convert a `ZeroMap<K, V>` to `ZeroMap<K, P>` where `V` and `P` are [`AsULE`] types
390 /// with the same size.
391 ///
392 /// # Unchecked Invariants
393 ///
394 /// If `V` and `P` have different ordering semantics, unexpected behavior may occur.
395 ///
396 /// # Panics
397 ///
398 /// Panics if `V::ULE` and `P::ULE` are not the same size.
399 pub fn try_convert_zv_v_unchecked<P>(self) -> Result<ZeroMap<'a, K, P>, ZeroVecError>
400 where
401 P: AsULE + ZeroMapKV<'a, Container = ZeroVec<'a, P>> + ?Sized,
402 {
403 Ok(ZeroMap {
404 keys: self.keys,
405 values: self.values.try_into_converted()?,
406 })
407 }
408}
409
410impl<'a, K, V> ZeroMap<'a, K, V>
411where
412 K: ZeroMapKV<'a> + ?Sized + Ord,
413 V: ZeroMapKV<'a, Container = VarZeroVec<'a, V>> + ?Sized,
414 V: VarULE,
415{
416 /// Same as `insert()`, but allows using [EncodeAsVarULE](crate::ule::EncodeAsVarULE)
417 /// types with the value to avoid an extra allocation when dealing with custom ULE types.
418 ///
419 /// ```rust
420 /// use std::borrow::Cow;
421 /// use zerovec::ZeroMap;
422 ///
423 /// #[zerovec::make_varule(PersonULE)]
424 /// #[derive(Clone, Eq, PartialEq, Ord, PartialOrd)]
425 /// struct Person<'a> {
426 /// age: u8,
427 /// name: Cow<'a, str>,
428 /// }
429 ///
430 /// let mut map: ZeroMap<u32, PersonULE> = ZeroMap::new();
431 /// map.insert_var_v(
432 /// &1,
433 /// &Person {
434 /// age: 20,
435 /// name: "Joseph".into(),
436 /// },
437 /// );
438 /// map.insert_var_v(
439 /// &1,
440 /// &Person {
441 /// age: 35,
442 /// name: "Carla".into(),
443 /// },
444 /// );
445 /// assert_eq!(&map.get(&1).unwrap().name, "Carla");
446 /// assert!(map.get(&3).is_none());
447 /// ```
448 pub fn insert_var_v<VE: EncodeAsVarULE<V>>(&mut self, key: &K, value: &VE) -> Option<Box<V>> {
449 match self.keys.zvl_binary_search(key) {
450 Ok(index) => {
451 #[allow(clippy::unwrap_used)] // binary search
452 let ret = self.values.get(index).unwrap().to_boxed();
453 self.values.make_mut().replace(index, value);
454 Some(ret)
455 }
456 Err(index) => {
457 self.keys.zvl_insert(index, key);
458 self.values.make_mut().insert(index, value);
459 None
460 }
461 }
462 }
463
464 // insert_var_k, insert_var_kv are not possible since one cannot perform the binary search with EncodeAsVarULE
465 // though we might be able to do it in the future if we add a trait for cross-Ord requirements
466}
467
468impl<'a, K, V> ZeroMap<'a, K, V>
469where
470 K: ZeroMapKV<'a> + ?Sized + Ord,
471 V: ZeroMapKV<'a> + ?Sized,
472 V: Copy,
473{
474 /// For cases when `V` is fixed-size, obtain a direct copy of `V` instead of `V::ULE`.
475 ///
476 /// # Examples
477 ///
478 /// ```rust
479 /// use zerovec::ZeroMap;
480 ///
481 /// let mut map = ZeroMap::new();
482 /// map.insert(&1, &'a');
483 /// map.insert(&2, &'b');
484 /// assert_eq!(map.get_copied(&1), Some('a'));
485 /// assert_eq!(map.get_copied(&3), None);
486 #[inline]
487 pub fn get_copied(&self, key: &K) -> Option<V> {
488 let index = self.keys.zvl_binary_search(key).ok()?;
489 self.get_copied_at(index)
490 }
491
492 /// Binary search the map with `predicate` to find a key, returning the value.
493 ///
494 /// For cases when `V` is fixed-size, use this method to obtain a direct copy of `V`
495 /// instead of `V::ULE`.
496 ///
497 /// # Examples
498 ///
499 /// ```rust
500 /// use zerovec::ZeroMap;
501 ///
502 /// let mut map = ZeroMap::new();
503 /// map.insert(&1, &'a');
504 /// map.insert(&2, &'b');
505 /// assert_eq!(map.get_copied_by(|probe| probe.cmp(&1)), Some('a'));
506 /// assert_eq!(map.get_copied_by(|probe| probe.cmp(&3)), None);
507 /// ```
508 #[inline]
509 pub fn get_copied_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<V> {
510 let index = self.keys.zvl_binary_search_by(predicate).ok()?;
511 self.get_copied_at(index)
512 }
513
514 fn get_copied_at(&self, index: usize) -> Option<V> {
515 let ule = self.values.zvl_get(index)?;
516 let mut result = Option::<V>::None;
517 V::Container::zvl_get_as_t(ule, |v| result.replace(*v));
518 #[allow(clippy::unwrap_used)] // `zvl_get_as_t` guarantees that the callback is invoked
519 Some(result.unwrap())
520 }
521}
522
523impl<'a, K, V> ZeroMap<'a, K, V>
524where
525 K: ZeroMapKV<'a> + ?Sized,
526 V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized,
527 V: AsULE + Copy,
528{
529 /// Similar to [`Self::iter()`] except it returns a direct copy of the values instead of references
530 /// to `V::ULE`, in cases when `V` is fixed-size
531 pub fn iter_copied_values<'b>(
532 &'b self,
533 ) -> impl Iterator<Item = (&'b <K as ZeroMapKV<'a>>::GetType, V)> {
534 (0..self.keys.zvl_len()).map(move |idx: usize| {
535 (
536 #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
537 self.keys.zvl_get(index:idx).unwrap(),
538 #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
539 ZeroSlice::get(&*self.values, index:idx).unwrap(),
540 )
541 })
542 }
543}
544
545impl<'a, K, V> ZeroMap<'a, K, V>
546where
547 K: ZeroMapKV<'a, Container = ZeroVec<'a, K>> + ?Sized,
548 V: ZeroMapKV<'a, Container = ZeroVec<'a, V>> + ?Sized,
549 K: AsULE + Copy,
550 V: AsULE + Copy,
551{
552 /// Similar to [`Self::iter()`] except it returns a direct copy of the keys values instead of references
553 /// to `K::ULE` and `V::ULE`, in cases when `K` and `V` are fixed-size
554 #[allow(clippy::needless_lifetimes)] // Lifetime is necessary in impl Trait
555 pub fn iter_copied<'b>(&'b self) -> impl Iterator<Item = (K, V)> + 'b {
556 let keys: &ZeroVec<'a, K> = &self.keys;
557 let values: &ZeroVec<'a, V> = &self.values;
558 (0..keys.len()).map(move |idx: usize| {
559 (
560 #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len()
561 ZeroSlice::get(&**keys, index:idx).unwrap(),
562 #[allow(clippy::unwrap_used)] // idx in 0..keys.zvl_len() = values.zvl_len()
563 ZeroSlice::get(&**values, index:idx).unwrap(),
564 )
565 })
566 }
567}
568
569impl<'a, K, V> From<ZeroMapBorrowed<'a, K, V>> for ZeroMap<'a, K, V>
570where
571 K: ZeroMapKV<'a>,
572 V: ZeroMapKV<'a>,
573 K: ?Sized,
574 V: ?Sized,
575{
576 fn from(other: ZeroMapBorrowed<'a, K, V>) -> Self {
577 Self {
578 keys: K::Container::zvl_from_borrowed(other.keys),
579 values: V::Container::zvl_from_borrowed(other.values),
580 }
581 }
582}
583
584// We can't use the default PartialEq because ZeroMap is invariant
585// so otherwise rustc will not automatically allow you to compare ZeroMaps
586// with different lifetimes
587impl<'a, 'b, K, V> PartialEq<ZeroMap<'b, K, V>> for ZeroMap<'a, K, V>
588where
589 K: for<'c> dynZeroMapKV<'c> + ?Sized,
590 V: for<'c> dynZeroMapKV<'c> + ?Sized,
591 <K as ZeroMapKV<'a>>::Container: PartialEq<<K as ZeroMapKV<'b>>::Container>,
592 <V as ZeroMapKV<'a>>::Container: PartialEq<<V as ZeroMapKV<'b>>::Container>,
593{
594 fn eq(&self, other: &ZeroMap<'b, K, V>) -> bool {
595 self.keys.eq(&other.keys) && self.values.eq(&other.values)
596 }
597}
598
599impl<'a, K, V> fmt::Debug for ZeroMap<'a, K, V>
600where
601 K: ZeroMapKV<'a> + ?Sized,
602 V: ZeroMapKV<'a> + ?Sized,
603 <K as ZeroMapKV<'a>>::Container: fmt::Debug,
604 <V as ZeroMapKV<'a>>::Container: fmt::Debug,
605{
606 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
607 f&mut DebugStruct<'_, '_>.debug_struct("ZeroMap")
608 .field("keys", &self.keys)
609 .field(name:"values", &self.values)
610 .finish()
611 }
612}
613
614impl<'a, K, V> Clone for ZeroMap<'a, K, V>
615where
616 K: ZeroMapKV<'a> + ?Sized,
617 V: ZeroMapKV<'a> + ?Sized,
618 <K as ZeroMapKV<'a>>::Container: Clone,
619 <V as ZeroMapKV<'a>>::Container: Clone,
620{
621 fn clone(&self) -> Self {
622 Self {
623 keys: self.keys.clone(),
624 values: self.values.clone(),
625 }
626 }
627}
628
629impl<'a, A, B, K, V> FromIterator<(A, B)> for ZeroMap<'a, K, V>
630where
631 A: Borrow<K>,
632 B: Borrow<V>,
633 K: ZeroMapKV<'a> + ?Sized + Ord,
634 V: ZeroMapKV<'a> + ?Sized,
635{
636 fn from_iter<T>(iter: T) -> Self
637 where
638 T: IntoIterator<Item = (A, B)>,
639 {
640 let iter: ::IntoIter = iter.into_iter();
641 let mut map: ZeroMap<'_, K, V> = match iter.size_hint() {
642 (_, Some(upper: usize)) => Self::with_capacity(upper),
643 (lower: usize, None) => Self::with_capacity(lower),
644 };
645
646 for (key: A, value: B) in iter {
647 if let Some((key: &K, value: &V)) = map.try_append(key.borrow(), value.borrow()) {
648 map.insert(key, value);
649 }
650 }
651 map
652 }
653}
654