1use crate::avl::{Iter, IterMut, Tree, WeakTree};
2pub use crate::chunk::DEFAULT_SIZE;
3use core::{
4 borrow::Borrow,
5 cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd},
6 default::Default,
7 fmt::{self, Debug, Formatter},
8 hash::{Hash, Hasher},
9 iter::FromIterator,
10 ops::{Index, IndexMut, RangeBounds, RangeFull},
11};
12
13#[cfg(feature = "serde")]
14use serde::{
15 de::{MapAccess, Visitor},
16 ser::SerializeMap,
17 Deserialize, Deserializer, Serialize, Serializer,
18};
19
20#[cfg(feature = "serde")]
21use core::marker::PhantomData;
22
23#[cfg(feature = "rayon")]
24use rayon::{
25 iter::{FromParallelIterator, IntoParallelIterator},
26 prelude::*,
27};
28
29/// This Map uses a similar strategy to BTreeMap to ensure cache
30/// efficient performance on modern hardware while still providing
31/// log(N) get, insert, and remove operations.
32///
33/// For good performance, it is very important to understand
34/// that clone is a fundamental operation, it needs to be fast
35/// for your key and data types, because it's going to be
36/// called a lot whenever you change the map.
37///
38/// # Why
39///
40/// 1. Multiple threads can read this structure even while one thread
41/// is updating it. Using a library like arc_swap you can avoid ever
42/// blocking readers.
43///
44/// 2. Snapshotting this structure is free.
45///
46/// # Examples
47/// ```
48/// # extern crate alloc;
49/// use alloc::string::String;
50/// use self::immutable_chunkmap::map::MapM;
51///
52/// let m =
53/// MapM::new()
54/// .insert(String::from("1"), 1).0
55/// .insert(String::from("2"), 2).0
56/// .insert(String::from("3"), 3).0;
57///
58/// assert_eq!(m.get("1"), Option::Some(&1));
59/// assert_eq!(m.get("2"), Option::Some(&2));
60/// assert_eq!(m.get("3"), Option::Some(&3));
61/// assert_eq!(m.get("4"), Option::None);
62///
63/// for (k, v) in &m {
64/// println!("key {}, val: {}", k, v)
65/// }
66/// ```
67#[derive(Clone)]
68pub struct Map<K: Ord + Clone, V: Clone, const SIZE: usize>(Tree<K, V, SIZE>);
69
70/// Map using a smaller chunk size, faster to update, slower to search
71pub type MapS<K, V> = Map<K, V, { DEFAULT_SIZE / 2 }>;
72
73/// Map using the default chunk size, a good balance of update and search
74pub type MapM<K, V> = Map<K, V, DEFAULT_SIZE>;
75
76/// Map using a larger chunk size, faster to search, slower to update
77pub type MapL<K, V> = Map<K, V, { DEFAULT_SIZE * 2 }>;
78
79/// A weak reference to a map.
80#[derive(Clone)]
81pub struct WeakMapRef<K: Ord + Clone, V: Clone, const SIZE: usize>(WeakTree<K, V, SIZE>);
82
83pub type WeakMapRefS<K, V> = WeakMapRef<K, V, { DEFAULT_SIZE / 2 }>;
84pub type WeakMapRefM<K, V> = WeakMapRef<K, V, DEFAULT_SIZE>;
85pub type WeakMapRefL<K, V> = WeakMapRef<K, V, { DEFAULT_SIZE * 2 }>;
86
87impl<K, V, const SIZE: usize> WeakMapRef<K, V, SIZE>
88where
89 K: Ord + Clone,
90 V: Clone,
91{
92 pub fn upgrade(&self) -> Option<Map<K, V, SIZE>> {
93 self.0.upgrade().map(Map)
94 }
95}
96
97impl<K, V, const SIZE: usize> Hash for Map<K, V, SIZE>
98where
99 K: Hash + Ord + Clone,
100 V: Hash + Clone,
101{
102 fn hash<H: Hasher>(&self, state: &mut H) {
103 self.0.hash(state)
104 }
105}
106
107impl<K, V, const SIZE: usize> Default for Map<K, V, SIZE>
108where
109 K: Ord + Clone,
110 V: Clone,
111{
112 fn default() -> Map<K, V, SIZE> {
113 Map::new()
114 }
115}
116
117impl<K, V, const SIZE: usize> PartialEq for Map<K, V, SIZE>
118where
119 K: PartialEq + Ord + Clone,
120 V: PartialEq + Clone,
121{
122 fn eq(&self, other: &Map<K, V, SIZE>) -> bool {
123 self.0 == other.0
124 }
125}
126
127impl<K, V, const SIZE: usize> Eq for Map<K, V, SIZE>
128where
129 K: Eq + Ord + Clone,
130 V: Eq + Clone,
131{
132}
133
134impl<K, V, const SIZE: usize> PartialOrd for Map<K, V, SIZE>
135where
136 K: Ord + Clone,
137 V: PartialOrd + Clone,
138{
139 fn partial_cmp(&self, other: &Map<K, V, SIZE>) -> Option<Ordering> {
140 self.0.partial_cmp(&other.0)
141 }
142}
143
144impl<K, V, const SIZE: usize> Ord for Map<K, V, SIZE>
145where
146 K: Ord + Clone,
147 V: Ord + Clone,
148{
149 fn cmp(&self, other: &Map<K, V, SIZE>) -> Ordering {
150 self.0.cmp(&other.0)
151 }
152}
153
154impl<K, V, const SIZE: usize> Debug for Map<K, V, SIZE>
155where
156 K: Debug + Ord + Clone,
157 V: Debug + Clone,
158{
159 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
160 self.0.fmt(f)
161 }
162}
163
164impl<'a, Q, K, V, const SIZE: usize> Index<&'a Q> for Map<K, V, SIZE>
165where
166 Q: Ord,
167 K: Ord + Clone + Borrow<Q>,
168 V: Clone,
169{
170 type Output = V;
171 fn index(&self, k: &Q) -> &V {
172 self.get(k).expect(msg:"element not found for key")
173 }
174}
175
176impl<'a, Q, K, V, const SIZE: usize> IndexMut<&'a Q> for Map<K, V, SIZE>
177where
178 Q: Ord,
179 K: Ord + Clone + Borrow<Q>,
180 V: Clone,
181{
182 fn index_mut(&mut self, k: &'a Q) -> &mut Self::Output {
183 self.get_mut_cow(k).expect(msg:"element not found for key")
184 }
185}
186
187impl<K, V, const SIZE: usize> FromIterator<(K, V)> for Map<K, V, SIZE>
188where
189 K: Ord + Clone,
190 V: Clone,
191{
192 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
193 Map::new().insert_many(elts:iter)
194 }
195}
196
197impl<'a, K, V, const SIZE: usize> IntoIterator for &'a Map<K, V, SIZE>
198where
199 K: 'a + Ord + Clone,
200 V: 'a + Clone,
201{
202 type Item = (&'a K, &'a V);
203 type IntoIter = Iter<'a, RangeFull, K, K, V, SIZE>;
204 fn into_iter(self) -> Self::IntoIter {
205 self.0.into_iter()
206 }
207}
208
209#[cfg(feature = "serde")]
210impl<K, V, const SIZE: usize> Serialize for Map<K, V, SIZE>
211where
212 K: Serialize + Clone + Ord,
213 V: Serialize + Clone,
214{
215 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
216 where
217 S: Serializer,
218 {
219 let mut map = serializer.serialize_map(Some(self.len()))?;
220 for (k, v) in self {
221 map.serialize_entry(k, v)?
222 }
223 map.end()
224 }
225}
226
227#[cfg(feature = "serde")]
228struct MapVisitor<K: Clone + Ord, V: Clone, const SIZE: usize> {
229 marker: PhantomData<fn() -> Map<K, V, SIZE>>,
230}
231
232#[cfg(feature = "serde")]
233impl<'a, K, V, const SIZE: usize> Visitor<'a> for MapVisitor<K, V, SIZE>
234where
235 K: Deserialize<'a> + Clone + Ord,
236 V: Deserialize<'a> + Clone,
237{
238 type Value = Map<K, V, SIZE>;
239
240 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
241 formatter.write_str("expected an immutable_chunkmap::Map")
242 }
243
244 fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
245 where
246 A: MapAccess<'a>,
247 {
248 let mut t = Map::<K, V, SIZE>::new();
249 while let Some((k, v)) = map.next_entry()? {
250 t.insert_cow(k, v);
251 }
252 Ok(t)
253 }
254}
255
256#[cfg(feature = "serde")]
257impl<'a, K, V, const SIZE: usize> Deserialize<'a> for Map<K, V, SIZE>
258where
259 K: Deserialize<'a> + Clone + Ord,
260 V: Deserialize<'a> + Clone,
261{
262 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
263 where
264 D: Deserializer<'a>,
265 {
266 deserializer.deserialize_map(MapVisitor {
267 marker: PhantomData,
268 })
269 }
270}
271
272#[cfg(feature = "rayon")]
273impl<'a, K, V, const SIZE: usize> IntoParallelIterator for &'a Map<K, V, SIZE>
274where
275 K: 'a + Ord + Clone + Send + Sync,
276 V: Clone + Send + Sync,
277{
278 type Item = (&'a K, &'a V);
279 type Iter = rayon::vec::IntoIter<(&'a K, &'a V)>;
280
281 fn into_par_iter(self) -> Self::Iter {
282 self.into_iter().collect::<Vec<_>>().into_par_iter()
283 }
284}
285
286#[cfg(feature = "rayon")]
287impl<K, V, const SIZE: usize> FromParallelIterator<(K, V)> for Map<K, V, SIZE>
288where
289 K: Ord + Clone + Send + Sync,
290 V: Clone + Send + Sync,
291{
292 fn from_par_iter<I>(i: I) -> Self
293 where
294 I: IntoParallelIterator<Item = (K, V)>,
295 {
296 i.into_par_iter()
297 .fold_with(Map::new(), |mut m, (k, v)| {
298 m.insert_cow(k, v);
299 m
300 })
301 .reduce_with(|m0, m1| m0.union(&m1, |_k, _v0, v1| Some(v1.clone())))
302 .unwrap_or_else(Map::new)
303 }
304}
305
306impl<K, V, const SIZE: usize> Map<K, V, SIZE>
307where
308 K: Ord + Clone,
309 V: Clone,
310{
311 /// Create a new empty map
312 pub fn new() -> Self {
313 Map(Tree::new())
314 }
315
316 /// Create a weak reference to this map
317 pub fn downgrade(&self) -> WeakMapRef<K, V, SIZE> {
318 WeakMapRef(self.0.downgrade())
319 }
320
321 /// Return the number of strong references to this map (see Arc)
322 pub fn strong_count(&self) -> usize {
323 self.0.strong_count()
324 }
325
326 /// Return the number of weak references to this map (see Arc)
327 pub fn weak_count(&self) -> usize {
328 self.0.weak_count()
329 }
330
331 /// This will insert many elements at once, and is
332 /// potentially a lot faster than inserting one by one,
333 /// especially if the data is sorted. It is just a wrapper
334 /// around the more general update_many method.
335 ///
336 /// #Examples
337 ///```
338 /// use self::immutable_chunkmap::map::MapM;
339 ///
340 /// let mut v = vec![(1, 3), (10, 1), (-12, 2), (44, 0), (50, -1)];
341 /// v.sort_unstable_by_key(|&(k, _)| k);
342 ///
343 /// let m = MapM::new().insert_many(v.iter().map(|(k, v)| (*k, *v)));
344 ///
345 /// for (k, v) in &v {
346 /// assert_eq!(m.get(k), Option::Some(v))
347 /// }
348 /// ```
349 pub fn insert_many<E: IntoIterator<Item = (K, V)>>(&self, elts: E) -> Self {
350 Map(self.0.insert_many(elts))
351 }
352
353 /// This will remove many elements at once, and is potentially a
354 /// lot faster than removing elements one by one, especially if
355 /// the data is sorted. It is just a wrapper around the more
356 /// general update_many method.
357 pub fn remove_many<Q, E>(&self, elts: E) -> Self
358 where
359 E: IntoIterator<Item = Q>,
360 Q: Ord,
361 K: Borrow<Q>,
362 {
363 self.update_many(elts.into_iter().map(|q| (q, ())), |_, _, _| None)
364 }
365
366 /// This method updates multiple bindings in one call. Given an
367 /// iterator of an arbitrary type (Q, D), where Q is any borrowed
368 /// form of K, an update function taking Q, D, the current binding
369 /// in the map, if any, and producing the new binding, if any,
370 /// this method will produce a new map with updated bindings of
371 /// many elements at once. It will skip intermediate node
372 /// allocations where possible. If the data in elts is sorted, it
373 /// will be able to skip many more intermediate allocations, and
374 /// can produce a speedup of about 10x compared to
375 /// inserting/updating one by one. In any case it should always be
376 /// faster than inserting elements one by one, even with random
377 /// unsorted keys.
378 ///
379 /// #Examples
380 /// ```
381 /// use core::iter::FromIterator;
382 /// use self::immutable_chunkmap::map::MapM;
383 ///
384 /// let m = MapM::from_iter((0..4).map(|k| (k, k)));
385 /// let m = m.update_many(
386 /// (0..4).map(|x| (x, ())),
387 /// |k, (), cur| cur.map(|(_, c)| (k, c + 1))
388 /// );
389 /// assert_eq!(
390 /// m.into_iter().map(|(k, v)| (*k, *v)).collect::<Vec<_>>(),
391 /// vec![(0, 1), (1, 2), (2, 3), (3, 4)]
392 /// );
393 /// ```
394 pub fn update_many<Q, D, E, F>(&self, elts: E, mut f: F) -> Self
395 where
396 E: IntoIterator<Item = (Q, D)>,
397 Q: Ord,
398 K: Borrow<Q>,
399 F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
400 {
401 Map(self.0.update_many(elts, &mut f))
402 }
403
404 /// return a new map with (k, v) inserted into it. If k
405 /// already exists in the old map, the old binding will be
406 /// returned, and the new map will contain the new
407 /// binding. In fact this method is just a wrapper around
408 /// update.
409 pub fn insert(&self, k: K, v: V) -> (Self, Option<V>) {
410 let (root, prev) = self.0.insert(k, v);
411 (Map(root), prev)
412 }
413
414 /// insert in place using copy on write semantics if self is not a
415 /// unique reference to the map. see `update_cow`.
416 pub fn insert_cow(&mut self, k: K, v: V) -> Option<V> {
417 self.0.insert_cow(k, v)
418 }
419
420 /// return a new map with the binding for q, which can be any
421 /// borrowed form of k, updated to the result of f. If f returns
422 /// None, the binding will be removed from the new map, otherwise
423 /// it will be inserted. This function is more efficient than
424 /// calling `get` and then `insert`, since it makes only one tree
425 /// traversal instead of two. This method runs in log(N) time and
426 /// space where N is the size of the map.
427 ///
428 /// # Examples
429 /// ```
430 /// use self::immutable_chunkmap::map::MapM;
431 ///
432 /// let (m, _) = MapM::new().update(0, 0, |k, d, _| Some((k, d)));
433 /// let (m, _) = m.update(1, 1, |k, d, _| Some((k, d)));
434 /// let (m, _) = m.update(2, 2, |k, d, _| Some((k, d)));
435 /// assert_eq!(m.get(&0), Some(&0));
436 /// assert_eq!(m.get(&1), Some(&1));
437 /// assert_eq!(m.get(&2), Some(&2));
438 ///
439 /// let (m, _) = m.update(0, (), |k, (), v| v.map(move |(_, v)| (k, v + 1)));
440 /// assert_eq!(m.get(&0), Some(&1));
441 /// assert_eq!(m.get(&1), Some(&1));
442 /// assert_eq!(m.get(&2), Some(&2));
443 ///
444 /// let (m, _) = m.update(1, (), |_, (), _| None);
445 /// assert_eq!(m.get(&0), Some(&1));
446 /// assert_eq!(m.get(&1), None);
447 /// assert_eq!(m.get(&2), Some(&2));
448 /// ```
449 pub fn update<Q, D, F>(&self, q: Q, d: D, mut f: F) -> (Self, Option<V>)
450 where
451 Q: Ord,
452 K: Borrow<Q>,
453 F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
454 {
455 let (root, prev) = self.0.update(q, d, &mut f);
456 (Map(root), prev)
457 }
458
459 /// Perform a copy on write update to the map. In the case that
460 /// self is a unique reference to the map, then the update will be
461 /// performed completly in place. self will be mutated, and no
462 /// previous version will be available. In the case that self has
463 /// a clone, or clones, then only the parts of the map that need
464 /// to be mutated will be copied before the update is
465 /// performed. self will reference the mutated copy, and previous
466 /// versions of the map will not be modified. self will still
467 /// share all the parts of the map that did not need to be mutated
468 /// with any pre existing clones.
469 ///
470 /// COW semantics are a flexible middle way between full
471 /// peristance and full mutability. Needless to say in the case
472 /// where you have a unique reference to the map, using update_cow
473 /// is a lot faster than using update, and a lot more flexible
474 /// than update_many.
475 ///
476 /// Other than copy on write the semanics of this method are
477 /// identical to those of update.
478 ///
479 /// #Examples
480 ///```
481 /// use self::immutable_chunkmap::map::MapM;
482 ///
483 /// let mut m = MapM::new().update(0, 0, |k, d, _| Some((k, d))).0;
484 /// let orig = m.clone();
485 /// m.update_cow(1, 1, |k, d, _| Some((k, d))); // copies the original chunk
486 /// m.update_cow(2, 2, |k, d, _| Some((k, d))); // doesn't copy anything
487 /// assert_eq!(m.len(), 3);
488 /// assert_eq!(orig.len(), 1);
489 /// assert_eq!(m.get(&0), Some(&0));
490 /// assert_eq!(m.get(&1), Some(&1));
491 /// assert_eq!(m.get(&2), Some(&2));
492 /// assert_eq!(orig.get(&0), Some(&0));
493 /// assert_eq!(orig.get(&1), None);
494 /// assert_eq!(orig.get(&2), None);
495 ///```
496 pub fn update_cow<Q, D, F>(&mut self, q: Q, d: D, mut f: F) -> Option<V>
497 where
498 Q: Ord,
499 K: Borrow<Q>,
500 F: FnMut(Q, D, Option<(&K, &V)>) -> Option<(K, V)>,
501 {
502 self.0.update_cow(q, d, &mut f)
503 }
504
505 /// Merge two maps together. Bindings that exist in both maps will
506 /// be passed to f, which may elect to remove the binding by
507 /// returning None. This function runs in O(log(n) + m) time and
508 /// space, where n is the size of the largest map, and m is the
509 /// number of intersecting chunks. It will never be slower than
510 /// calling update_many on the first map with an iterator over the
511 /// second, and will be significantly faster if the intersection
512 /// is minimal or empty.
513 ///
514 /// # Examples
515 /// ```
516 /// use core::iter::FromIterator;
517 /// use self::immutable_chunkmap::map::MapM;
518 ///
519 /// let m0 = MapM::from_iter((0..10).map(|k| (k, 1)));
520 /// let m1 = MapM::from_iter((10..20).map(|k| (k, 1)));
521 /// let m2 = m0.union(&m1, |_k, _v0, _v1| panic!("no intersection expected"));
522 ///
523 /// for i in 0..20 {
524 /// assert!(m2.get(&i).is_some())
525 /// }
526 ///
527 /// let m3 = MapM::from_iter((5..9).map(|k| (k, 1)));
528 /// let m4 = m3.union(&m2, |_k, v0, v1| Some(v0 + v1));
529 ///
530 /// for i in 0..20 {
531 /// assert!(
532 /// *m4.get(&i).unwrap() ==
533 /// *m3.get(&i).unwrap_or(&0) + *m2.get(&i).unwrap_or(&0)
534 /// )
535 /// }
536 /// ```
537 pub fn union<F>(&self, other: &Map<K, V, SIZE>, mut f: F) -> Self
538 where
539 F: FnMut(&K, &V, &V) -> Option<V>,
540 {
541 Map(Tree::union(&self.0, &other.0, &mut f))
542 }
543
544 /// Produce a map containing the mapping over F of the
545 /// intersection (by key) of two maps. The function f runs on each
546 /// intersecting element, and has the option to omit elements from
547 /// the intersection by returning None, or change the value any
548 /// way it likes. Runs in O(log(N) + M) time and space where N is
549 /// the size of the smallest map, and M is the number of
550 /// intersecting chunks.
551 ///
552 /// # Examples
553 ///```
554 /// use core::iter::FromIterator;
555 /// use self::immutable_chunkmap::map::MapM;
556 ///
557 /// let m0 = MapM::from_iter((0..100000).map(|k| (k, 1)));
558 /// let m1 = MapM::from_iter((50..30000).map(|k| (k, 1)));
559 /// let m2 = m0.intersect(&m1, |_k, v0, v1| Some(v0 + v1));
560 ///
561 /// for i in 0..100000 {
562 /// if i >= 30000 || i < 50 {
563 /// assert!(m2.get(&i).is_none());
564 /// } else {
565 /// assert!(*m2.get(&i).unwrap() == 2);
566 /// }
567 /// }
568 /// ```
569 pub fn intersect<F>(&self, other: &Map<K, V, SIZE>, mut f: F) -> Self
570 where
571 F: FnMut(&K, &V, &V) -> Option<V>,
572 {
573 Map(Tree::intersect(&self.0, &other.0, &mut f))
574 }
575
576 /// Produce a map containing the second map subtracted from the
577 /// first. The function F is called for each intersecting element,
578 /// and ultimately decides whether it appears in the result, for
579 /// example, to compute a classical set diff, the function should
580 /// always return None.
581 ///
582 /// # Examples
583 ///```
584 /// use core::iter::FromIterator;
585 /// use self::immutable_chunkmap::map::MapM;
586 ///
587 /// let m0 = MapM::from_iter((0..10000).map(|k| (k, 1)));
588 /// let m1 = MapM::from_iter((50..3000).map(|k| (k, 1)));
589 /// let m2 = m0.diff(&m1, |_k, _v0, _v1| None);
590 ///
591 /// m2.invariant();
592 /// dbg!(m2.len());
593 /// assert!(m2.len() == 10000 - 2950);
594 /// for i in 0..10000 {
595 /// if i >= 3000 || i < 50 {
596 /// assert!(*m2.get(&i).unwrap() == 1);
597 /// } else {
598 /// assert!(m2.get(&i).is_none());
599 /// }
600 /// }
601 /// ```
602 pub fn diff<F>(&self, other: &Map<K, V, SIZE>, mut f: F) -> Self
603 where
604 F: FnMut(&K, &V, &V) -> Option<V>,
605 K: Debug,
606 V: Debug,
607 {
608 Map(Tree::diff(&self.0, &other.0, &mut f))
609 }
610
611 /// lookup the mapping for k. If it doesn't exist return
612 /// None. Runs in log(N) time and constant space. where N
613 /// is the size of the map.
614 pub fn get<'a, Q: ?Sized + Ord>(&'a self, k: &Q) -> Option<&'a V>
615 where
616 K: Borrow<Q>,
617 {
618 self.0.get(k)
619 }
620
621 /// lookup the mapping for k. Return the key. If it doesn't exist
622 /// return None. Runs in log(N) time and constant space. where N
623 /// is the size of the map.
624 pub fn get_key<'a, Q: ?Sized + Ord>(&'a self, k: &Q) -> Option<&'a K>
625 where
626 K: Borrow<Q>,
627 {
628 self.0.get_key(k)
629 }
630
631 /// lookup the mapping for k. Return both the key and the
632 /// value. If it doesn't exist return None. Runs in log(N) time
633 /// and constant space. where N is the size of the map.
634 pub fn get_full<'a, Q: ?Sized + Ord>(&'a self, k: &Q) -> Option<(&'a K, &'a V)>
635 where
636 K: Borrow<Q>,
637 {
638 self.0.get_full(k)
639 }
640
641 /// Get a mutable reference to the value mapped to `k` using copy on write semantics.
642 /// This works as `Arc::make_mut`, it will only clone the parts of the tree that are,
643 /// - required to reach `k`
644 /// - have a strong count > 1
645 ///
646 /// This operation is also triggered by mut indexing on the map, e.g. `&mut m[k]`
647 /// calls `get_mut_cow` on `m`
648 ///
649 /// # Example
650 /// ```
651 /// use core::iter::FromIterator;
652 /// use self::immutable_chunkmap::map::MapM as Map;
653 ///
654 /// let mut m = Map::from_iter((0..100).map(|k| (k, Map::from_iter((0..100).map(|k| (k, 1))))));
655 /// let orig = m.clone();
656 ///
657 /// if let Some(inner) = m.get_mut_cow(&0) {
658 /// if let Some(v) = inner.get_mut_cow(&0) {
659 /// *v += 1
660 /// }
661 /// }
662 ///
663 /// assert_eq!(m.get(&0).and_then(|m| m.get(&0)), Some(&2));
664 /// assert_eq!(orig.get(&0).and_then(|m| m.get(&0)), Some(&1));
665 /// ```
666 pub fn get_mut_cow<'a, Q: ?Sized + Ord>(&'a mut self, k: &Q) -> Option<&'a mut V>
667 where
668 K: Borrow<Q>,
669 {
670 self.0.get_mut_cow(k)
671 }
672
673 /// Same as `get_mut_cow` except if the value is not in the map it will
674 /// first be inserted by calling `f`
675 pub fn get_or_insert_cow<'a, F>(&'a mut self, k: K, f: F) -> &'a mut V
676 where
677 F: FnOnce() -> V,
678 {
679 self.0.get_or_insert_cow(k, f)
680 }
681
682 /// return a new map with the mapping under k removed. If
683 /// the binding existed in the old map return it. Runs in
684 /// log(N) time and log(N) space, where N is the size of
685 /// the map.
686 pub fn remove<Q: Sized + Ord>(&self, k: &Q) -> (Self, Option<V>)
687 where
688 K: Borrow<Q>,
689 {
690 let (t, prev) = self.0.remove(k);
691 (Map(t), prev)
692 }
693
694 /// remove in place using copy on write semantics if self is not a
695 /// unique reference to the map. see `update_cow`.
696 pub fn remove_cow<Q: Sized + Ord>(&mut self, k: &Q) -> Option<V>
697 where
698 K: Borrow<Q>,
699 {
700 self.0.remove_cow(k)
701 }
702
703 /// get the number of elements in the map O(1) time and space
704 pub fn len(&self) -> usize {
705 self.0.len()
706 }
707
708 /// return an iterator over the subset of elements in the
709 /// map that are within the specified range.
710 ///
711 /// The returned iterator runs in O(log(N) + M) time, and
712 /// constant space. N is the number of elements in the
713 /// tree, and M is the number of elements you examine.
714 ///
715 /// if lbound >= ubound the returned iterator will be empty
716 pub fn range<'a, Q, R>(&'a self, r: R) -> Iter<'a, R, Q, K, V, SIZE>
717 where
718 Q: Ord + ?Sized + 'a,
719 K: Borrow<Q>,
720 R: RangeBounds<Q> + 'a,
721 {
722 self.0.range(r)
723 }
724
725 /// return a mutable iterator over the subset of elements in the
726 /// map that are within the specified range. The iterator will
727 /// copy on write the part of the tree that it visits,
728 /// specifically it will be as if you ran get_mut_cow on every
729 /// element you visit.
730 ///
731 /// The returned iterator runs in O(log(N) + M) time, and
732 /// constant space. N is the number of elements in the
733 /// tree, and M is the number of elements you examine.
734 ///
735 /// if lbound >= ubound the returned iterator will be empty
736 pub fn range_mut_cow<'a, Q, R>(&'a mut self, r: R) -> IterMut<'a, R, Q, K, V, SIZE>
737 where
738 Q: Ord + ?Sized + 'a,
739 K: Borrow<Q>,
740 R: RangeBounds<Q> + 'a,
741 {
742 self.0.range_mut_cow(r)
743 }
744
745 /// return a mutable iterator over the entire map. The iterator
746 /// will copy on write every element in the tree, specifically it
747 /// will be as if you ran get_mut_cow on every element.
748 ///
749 /// The returned iterator runs in O(log(N) + M) time, and
750 /// constant space. N is the number of elements in the
751 /// tree, and M is the number of elements you examine.
752 pub fn iter_mut_cow<'a>(&'a mut self) -> IterMut<'a, RangeFull, K, K, V, SIZE> {
753 self.0.iter_mut_cow()
754 }
755}
756
757impl<K, V, const SIZE: usize> Map<K, V, SIZE>
758where
759 K: Ord + Clone,
760 V: Clone + Default,
761{
762 /// Same as `get_mut_cow` except if the value isn't in the map it will
763 /// be added by calling `V::default`
764 pub fn get_or_default_cow<'a>(&'a mut self, k: K) -> &'a mut V {
765 self.get_or_insert_cow(k, V::default)
766 }
767}
768
769impl<K, V, const SIZE: usize> Map<K, V, SIZE>
770where
771 K: Ord + Clone + Debug,
772 V: Clone + Debug,
773{
774 #[allow(dead_code)]
775 pub fn invariant(&self) -> () {
776 self.0.invariant()
777 }
778}
779