rpds/map/red_black_tree_map/
mod.rs

1use super::entry::Entry;
2use archery::{ArcTK, RcK, SharedPointer, SharedPointerKind};
3use core::borrow::Borrow;
4use core::cmp::Ordering;
5use core::fmt::Display;
6use core::hash::{Hash, Hasher};
7use core::iter::FromIterator;
8use core::marker::PhantomData;
9use core::ops::{Index, RangeBounds, RangeFull};
10
11// TODO Use impl trait instead of this when available.
12pub type Iter<'a, K, V, P> =
13    core::iter::Map<IterPtr<'a, K, V, P>, fn(&'a SharedPointer<Entry<K, V>, P>) -> (&'a K, &'a V)>;
14pub type IterKeys<'a, K, V, P> = core::iter::Map<Iter<'a, K, V, P>, fn((&'a K, &V)) -> &'a K>;
15pub type IterValues<'a, K, V, P> = core::iter::Map<Iter<'a, K, V, P>, fn((&K, &'a V)) -> &'a V>;
16pub type RangeIter<'a, K, V, RB, Q, P> = core::iter::Map<
17    RangeIterPtr<'a, K, V, RB, Q, P>,
18    fn(&'a SharedPointer<Entry<K, V>, P>) -> (&'a K, &'a V),
19>;
20
21/// Creates a [`RedBlackTreeMap`](crate::RedBlackTreeMap) containing the given arguments:
22///
23/// ```
24/// # use rpds::*;
25/// #
26/// let m = RedBlackTreeMap::new()
27///     .insert(1, "one")
28///     .insert(2, "two")
29///     .insert(3, "three");
30///
31/// assert_eq!(rbt_map![1 => "one", 2 => "two", 3 => "three"], m);
32/// ```
33#[macro_export]
34macro_rules! rbt_map {
35    ($($k:expr => $v:expr),*) => {
36        {
37            #[allow(unused_mut)]
38            let mut m = $crate::RedBlackTreeMap::new();
39            $(
40                m.insert_mut($k, $v);
41            )*
42            m
43        }
44    };
45}
46
47/// Creates a [`RedBlackTreeMap`](crate::RedBlackTreeMap) that implements `Sync`, containing the
48/// given arguments:
49///
50/// ```
51/// # use rpds::*;
52/// #
53/// let m = RedBlackTreeMap::new_sync()
54///     .insert(1, "one")
55///     .insert(2, "two")
56///     .insert(3, "three");
57///
58/// assert_eq!(rbt_map_sync![1 => "one", 2 => "two", 3 => "three"], m);
59/// ```
60#[macro_export]
61macro_rules! rbt_map_sync {
62    ($($k:expr => $v:expr),*) => {
63        {
64            #[allow(unused_mut)]
65            let mut m = $crate::RedBlackTreeMap::new_sync();
66            $(
67                m.insert_mut($k, $v);
68            )*
69            m
70        }
71    };
72}
73
74/// A persistent map with structural sharing.  This implementation uses a
75/// [red-black tree](https://en.wikipedia.org/wiki/Red-Black_tree).
76///
77/// # Complexity
78///
79/// Let *n* be the number of elements in the map.
80///
81/// ## Temporal complexity
82///
83/// | Operation                  | Average   | Worst case  |
84/// |:-------------------------- | ---------:| -----------:|
85/// | `new()`                    |      Θ(1) |        Θ(1) |
86/// | `insert()`                 | Θ(log(n)) |   Θ(log(n)) |
87/// | `remove()`                 | Θ(log(n)) |   Θ(log(n)) |
88/// | `get()`                    | Θ(log(n)) |   Θ(log(n)) |
89/// | `contains_key()`           | Θ(log(n)) |   Θ(log(n)) |
90/// | `size()`                   |      Θ(1) |        Θ(1) |
91/// | `clone()`                  |      Θ(1) |        Θ(1) |
92/// | iterator creation          | Θ(log(n)) |   Θ(log(n)) |
93/// | iterator step              |      Θ(1) |   Θ(log(n)) |
94/// | iterator full              |      Θ(n) |        Θ(n) |
95///
96/// # Implementation details
97///
98/// This implementation uses a [red-black tree](https://en.wikipedia.org/wiki/Red-Black_tree) as
99/// described in "Purely Functional Data Structures" by Chris Okasaki, page 27.  Deletion is
100/// implemented according to the paper "Red-Black Trees with Types" by Stefan Kahrs
101/// ([reference implementation](https://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.hs))
102#[derive(Debug)]
103pub struct RedBlackTreeMap<K, V, P = RcK>
104where
105    P: SharedPointerKind,
106{
107    root: Option<SharedPointer<Node<K, V, P>, P>>,
108    size: usize,
109}
110
111pub type RedBlackTreeMapSync<K, V> = RedBlackTreeMap<K, V, ArcTK>;
112
113#[derive(Clone, Copy, Debug, PartialEq, Eq)]
114enum Color {
115    Red,
116    Black,
117}
118
119#[derive(Debug)]
120struct Node<K, V, P>
121where
122    P: SharedPointerKind,
123{
124    entry: SharedPointer<Entry<K, V>, P>,
125    color: Color,
126    left: Option<SharedPointer<Node<K, V, P>, P>>,
127    right: Option<SharedPointer<Node<K, V, P>, P>>,
128}
129
130impl<K, V, P> Clone for Node<K, V, P>
131where
132    P: SharedPointerKind,
133{
134    fn clone(&self) -> Node<K, V, P> {
135        Node {
136            entry: SharedPointer::clone(&self.entry),
137            color: self.color,
138            left: self.left.clone(),
139            right: self.right.clone(),
140        }
141    }
142}
143
144impl<K, V, P> Node<K, V, P>
145where
146    K: Ord,
147    P: SharedPointerKind,
148{
149    fn new_red(entry: Entry<K, V>) -> Node<K, V, P> {
150        Node { entry: SharedPointer::new(entry), color: Color::Red, left: None, right: None }
151    }
152
153    fn new_black(entry: Entry<K, V>) -> Node<K, V, P> {
154        Node { entry: SharedPointer::new(entry), color: Color::Black, left: None, right: None }
155    }
156
157    fn borrow(node: Option<&SharedPointer<Node<K, V, P>, P>>) -> Option<&Node<K, V, P>> {
158        node.map(Borrow::borrow)
159    }
160
161    fn left_color(&self) -> Option<Color> {
162        self.left.as_ref().map(|l| l.color)
163    }
164
165    fn right_color(&self) -> Option<Color> {
166        self.right.as_ref().map(|r| r.color)
167    }
168
169    fn get<Q: ?Sized>(&self, key: &Q) -> Option<&Entry<K, V>>
170    where
171        K: Borrow<Q>,
172        Q: Ord,
173    {
174        match key.cmp(self.entry.key.borrow()) {
175            Ordering::Less => self.left.as_ref().and_then(|l| l.get(key)),
176            Ordering::Equal => Some(&self.entry),
177            Ordering::Greater => self.right.as_ref().and_then(|r| r.get(key)),
178        }
179    }
180
181    fn first(&self) -> &Entry<K, V> {
182        match self.left {
183            Some(ref l) => l.first(),
184            None => &self.entry,
185        }
186    }
187
188    fn last(&self) -> &Entry<K, V> {
189        match self.right {
190            Some(ref r) => r.last(),
191            None => &self.entry,
192        }
193    }
194
195    /// Balances an unbalanced node.  This is a function is described in "Purely Functional
196    /// Data Structures" by Chris Okasaki, page 27.
197    ///
198    /// The transformation is done as the figure below shows.
199    ///
200    /// ```text
201    ///                                                                    ╭────────────────────╮
202    ///                                                                    │  ┌───┐             │
203    ///                                                                    │  │   │ Red node    │
204    ///                                                                    │  └───┘             │
205    ///            ┏━━━┓                                                   │                    │
206    ///            ┃ z ┃                                                   │  ┏━━━┓             │
207    ///            ┗━━━┛                                                   │  ┃   ┃ Black node  │
208    ///             ╱ ╲                                                    │  ┗━━━┛             │
209    ///        ┌───┐   d                                                   ╰────────────────────╯
210    ///        │ y │                      Case 1
211    ///        └───┘           ╭──────────────────────────────────────────────────╮
212    ///         ╱ ╲            ╰────────────────────────────────────────────────╮ │
213    ///     ┌───┐  c                                                            │ │
214    ///     │ x │                                                               │ │
215    ///     └───┘                                                               │ │
216    ///      ╱ ╲                                                                │ │
217    ///     a   b                                                               │ │
218    ///                                                                         │ │
219    ///                                                                         │ │
220    ///                                                                         │ │
221    ///            ┏━━━┓                                                        │ │
222    ///            ┃ z ┃                                                        │ │
223    ///            ┗━━━┛                                                        │ │
224    ///             ╱ ╲                                                         │ │
225    ///        ┌───┐   d                  Case 2                                │ │
226    ///        │ x │           ╭─────────────────────────────╲                  │ │
227    ///        └───┘           ╰────────────────────────────╲ ╲                 ╲ ╱
228    ///         ╱ ╲                                          ╲ ╲
229    ///        a  ┌───┐                                       ╲ ╲
230    ///           │ y │                                        ╲ ╲             ┌───┐
231    ///           └───┘                                         ╲ ╲            │ y │
232    ///            ╱ ╲                                           ╲  │          └───┘
233    ///           b   c                                          ───┘           ╱ ╲
234    ///                                                                        ╱   ╲
235    ///                                                                   ┏━━━┓     ┏━━━┓
236    ///                                                                   ┃ x ┃     ┃ z ┃
237    ///            ┏━━━┓                                                  ┗━━━┛     ┗━━━┛
238    ///            ┃ x ┃                                         ───┐      ╱ ╲       ╱ ╲
239    ///            ┗━━━┛                                         ╱  │     ╱   ╲     ╱   ╲
240    ///             ╱ ╲                                         ╱ ╱      a     b   c     d
241    ///            a  ┌───┐                                    ╱ ╱
242    ///               │ z │                                   ╱ ╱
243    ///               └───┘               Case 3             ╱ ╱                ╱ ╲
244    ///                ╱ ╲     ╭────────────────────────────╱ ╱                 │ │
245    ///            ┌───┐  d    ╰─────────────────────────────╱                  │ │
246    ///            │ y │                                                        │ │
247    ///            └───┘                                                        │ │
248    ///             ╱ ╲                                                         │ │
249    ///            b   c                                                        │ │
250    ///                                                                         │ │
251    ///                                                                         │ │
252    ///                                                                         │ │
253    ///            ┏━━━┓                                                        │ │
254    ///            ┃ x ┃                                                        │ │
255    ///            ┗━━━┛                                                        │ │
256    ///             ╱ ╲                                                         │ │
257    ///            a  ┌───┐               Case 4                                │ │
258    ///               │ y │    ╭────────────────────────────────────────────────┘ │
259    ///               └───┘    ╰──────────────────────────────────────────────────┘
260    ///                ╱ ╲
261    ///               b  ┌───┐
262    ///                  │ z │
263    ///                  └───┘
264    ///                   ╱ ╲
265    ///                  c   d
266    /// ```
267    fn balance(&mut self) {
268        use Color::Black as B;
269        use Color::Red as R;
270        use core::mem::swap;
271
272        match self.color {
273            B => {
274                let color_l: Option<Color> = self.left_color();
275                let color_l_l: Option<Color> = self.left.as_ref().and_then(|l| l.left_color());
276                let color_l_r: Option<Color> = self.left.as_ref().and_then(|l| l.right_color());
277                let color_r: Option<Color> = self.right_color();
278                let color_r_l: Option<Color> = self.right.as_ref().and_then(|r| r.left_color());
279                let color_r_r: Option<Color> = self.right.as_ref().and_then(|r| r.right_color());
280
281                match (color_l, color_l_l, color_l_r, color_r, color_r_l, color_r_r) {
282                    // Case 1
283                    (Some(R), Some(R), ..) => {
284                        let mut node_l_ptr = self.left.take().unwrap();
285                        let node_l: &mut Node<K, V, P> = SharedPointer::make_mut(&mut node_l_ptr);
286                        let mut node_l_l_ptr = node_l.left.take().unwrap();
287                        let node_l_l: &mut Node<K, V, P> =
288                            SharedPointer::make_mut(&mut node_l_l_ptr);
289
290                        self.color = Color::Red;
291                        node_l.color = Color::Black;
292                        node_l_l.color = Color::Black;
293
294                        swap(&mut self.entry, &mut node_l.entry);
295                        swap(&mut node_l.left, &mut node_l.right);
296                        swap(&mut self.right, &mut node_l.right);
297
298                        self.left = Some(node_l_l_ptr);
299                        self.right = Some(node_l_ptr);
300                    }
301
302                    // Case 2
303                    (Some(R), _, Some(R), ..) => {
304                        let mut node_l_ptr = self.left.take().unwrap();
305                        let node_l: &mut Node<K, V, P> = SharedPointer::make_mut(&mut node_l_ptr);
306                        let mut node_l_r_ptr = node_l.right.take().unwrap();
307                        let node_l_r: &mut Node<K, V, P> =
308                            SharedPointer::make_mut(&mut node_l_r_ptr);
309
310                        self.color = Color::Red;
311                        node_l.color = Color::Black;
312                        node_l_r.color = Color::Black;
313
314                        swap(&mut self.entry, &mut node_l_r.entry);
315                        swap(&mut node_l_r.left, &mut node_l_r.right);
316                        swap(&mut node_l.right, &mut node_l_r.right);
317                        swap(&mut self.right, &mut node_l_r.right);
318
319                        self.right = Some(node_l_r_ptr);
320                        self.left = Some(node_l_ptr);
321                    }
322
323                    // Case 3
324                    (.., Some(R), Some(R), _) => {
325                        let mut node_r_ptr = self.right.take().unwrap();
326                        let node_r: &mut Node<K, V, P> = SharedPointer::make_mut(&mut node_r_ptr);
327                        let mut node_r_l_ptr = node_r.left.take().unwrap();
328                        let node_r_l: &mut Node<K, V, P> =
329                            SharedPointer::make_mut(&mut node_r_l_ptr);
330
331                        self.color = Color::Red;
332                        node_r.color = Color::Black;
333                        node_r_l.color = Color::Black;
334
335                        swap(&mut self.entry, &mut node_r_l.entry);
336                        swap(&mut node_r.left, &mut node_r_l.right);
337                        swap(&mut node_r_l.left, &mut node_r_l.right);
338                        swap(&mut self.left, &mut node_r_l.left);
339
340                        self.left = Some(node_r_l_ptr);
341                        self.right = Some(node_r_ptr);
342                    }
343
344                    // Case 4
345                    (.., Some(R), _, Some(R)) => {
346                        let mut node_r_ptr = self.right.take().unwrap();
347                        let node_r: &mut Node<K, V, P> = SharedPointer::make_mut(&mut node_r_ptr);
348                        let mut node_r_r_ptr = node_r.right.take().unwrap();
349                        let node_r_r: &mut Node<K, V, P> =
350                            SharedPointer::make_mut(&mut node_r_r_ptr);
351
352                        self.color = Color::Red;
353                        node_r.color = Color::Black;
354                        node_r_r.color = Color::Black;
355
356                        swap(&mut self.entry, &mut node_r.entry);
357                        swap(&mut node_r.left, &mut node_r.right);
358                        swap(&mut self.left, &mut node_r.left);
359
360                        self.right = Some(node_r_r_ptr);
361                        self.left = Some(node_r_ptr);
362                    }
363
364                    _ => (),
365                }
366            }
367            R => (),
368        }
369    }
370
371    /// Inserts the entry and returns whether the key is new.
372    fn insert(root: &mut Option<SharedPointer<Node<K, V, P>, P>>, key: K, value: V) -> bool {
373        fn ins<K: Ord, V, P: SharedPointerKind>(
374            node: &mut Option<SharedPointer<Node<K, V, P>, P>>,
375            k: K,
376            v: V,
377            is_root: bool,
378        ) -> bool {
379            match node {
380                Some(node) => {
381                    let node = SharedPointer::make_mut(node);
382
383                    let ret = match k.cmp(&node.entry.key) {
384                        Ordering::Less => {
385                            let is_new_key = ins(&mut node.left, k, v, false);
386
387                            // Small optimization: avoid unnecessary calls to balance.
388                            if is_new_key {
389                                node.balance();
390                            }
391
392                            is_new_key
393                        }
394                        Ordering::Equal => {
395                            node.entry = SharedPointer::new(Entry::new(k, v));
396
397                            false
398                        }
399                        Ordering::Greater => {
400                            let is_new_key = ins(&mut node.right, k, v, false);
401
402                            // Small optimization: avoid unnecessary calls to balance.
403                            if is_new_key {
404                                node.balance();
405                            }
406
407                            is_new_key
408                        }
409                    };
410
411                    if is_root {
412                        node.color = Color::Black;
413                    }
414
415                    ret
416                }
417                None => {
418                    *node = if is_root {
419                        Some(SharedPointer::new(Node::new_black(Entry::new(k, v))))
420                    } else {
421                        Some(SharedPointer::new(Node::new_red(Entry::new(k, v))))
422                    };
423
424                    true
425                }
426            }
427        }
428
429        ins(root, key, value, true)
430    }
431
432    /// Returns `false` if node has no children to merge.
433    fn remove_fuse(
434        node: &mut Node<K, V, P>,
435        left: Option<SharedPointer<Node<K, V, P>, P>>,
436        right: Option<SharedPointer<Node<K, V, P>, P>>,
437    ) -> bool {
438        use Color::Black as B;
439        use Color::Red as R;
440
441        use core::mem::swap;
442
443        match (left, right) {
444            (None, None) => false,
445            (None, Some(r_ptr)) => {
446                crate::utils::replace(node, r_ptr);
447                true
448            }
449            (Some(l_ptr), None) => {
450                crate::utils::replace(node, l_ptr);
451                true
452            }
453            (Some(mut l_ptr), Some(mut r_ptr)) => {
454                match (l_ptr.color, r_ptr.color) {
455                    (B, R) => {
456                        let r = SharedPointer::make_mut(&mut r_ptr);
457                        let rl = r.left.take();
458
459                        // This will always return `true`.
460                        Node::remove_fuse(node, Some(l_ptr), rl);
461
462                        swap(node, r);
463
464                        node.left = Some(r_ptr);
465                    }
466                    (R, B) => {
467                        let l = SharedPointer::make_mut(&mut l_ptr);
468                        let lr = l.right.take();
469
470                        // This will always return `true`.
471                        Node::remove_fuse(node, lr, Some(r_ptr));
472
473                        swap(node, l);
474
475                        node.right = Some(l_ptr);
476                    }
477                    (R, R) => {
478                        let r = SharedPointer::make_mut(&mut r_ptr);
479                        let rl = r.left.take();
480                        let l = SharedPointer::make_mut(&mut l_ptr);
481                        let lr = l.right.take();
482
483                        let fused = Node::remove_fuse(node, lr, rl);
484
485                        match node.color {
486                            R if fused => {
487                                let fl = node.left.take();
488                                let fr = node.right.take();
489
490                                l.right = fl;
491                                r.left = fr;
492
493                                node.left = Some(l_ptr);
494                                node.right = Some(r_ptr);
495                            }
496                            _ => {
497                                swap(l, node);
498
499                                if fused {
500                                    r.left = Some(l_ptr);
501                                }
502
503                                node.right = Some(r_ptr);
504                            }
505                        }
506                    }
507                    (B, B) => {
508                        let r = SharedPointer::make_mut(&mut r_ptr);
509                        let rl = r.left.take();
510                        let l = SharedPointer::make_mut(&mut l_ptr);
511                        let lr = l.right.take();
512
513                        let fused = Node::remove_fuse(node, lr, rl);
514
515                        match node.color {
516                            R if fused => {
517                                let fl = node.left.take();
518                                let fr = node.right.take();
519
520                                l.right = fl;
521                                r.left = fr;
522
523                                node.left = Some(l_ptr);
524                                node.right = Some(r_ptr);
525                            }
526                            _ => {
527                                swap(l, node);
528
529                                if fused {
530                                    r.left = Some(l_ptr);
531                                }
532
533                                node.color = Color::Red;
534                                node.right = Some(r_ptr);
535
536                                node.remove_balance_left();
537                            }
538                        }
539                    }
540                }
541
542                true
543            }
544        }
545    }
546
547    fn remove_balance(&mut self) {
548        match (self.left_color(), self.right_color()) {
549            (Some(Color::Red), Some(Color::Red)) => {
550                SharedPointer::make_mut(self.left.as_mut().unwrap()).color = Color::Black;
551                SharedPointer::make_mut(self.right.as_mut().unwrap()).color = Color::Black;
552
553                self.color = Color::Red;
554            }
555            _ => {
556                // Our `balance()` does nothing unless the color is black, which the caller
557                // must ensure.
558                debug_assert_eq!(self.color, Color::Black);
559                self.balance();
560            }
561        }
562    }
563
564    fn remove_balance_left(&mut self) {
565        use Color::Black as B;
566        use Color::Red as R;
567
568        use core::mem::swap;
569
570        let color_l: Option<Color> = self.left_color();
571        let color_r: Option<Color> = self.right_color();
572        let color_r_l: Option<Color> = self.right.as_ref().and_then(|r| r.left_color());
573
574        match (color_l, color_r, color_r_l) {
575            (Some(R), ..) => {
576                let self_l = SharedPointer::make_mut(self.left.as_mut().unwrap());
577
578                self.color = Color::Red;
579                self_l.color = Color::Black;
580            }
581            (_, Some(B), _) => {
582                let self_r = SharedPointer::make_mut(self.right.as_mut().unwrap());
583
584                self.color = Color::Black;
585                self_r.color = Color::Red;
586
587                self.remove_balance();
588            }
589            (_, Some(R), Some(B)) => {
590                let self_r = SharedPointer::make_mut(self.right.as_mut().unwrap());
591
592                let mut self_r_l_ptr = self_r.left.take().unwrap();
593                let self_r_l = SharedPointer::make_mut(&mut self_r_l_ptr);
594                let new_r_l = self_r_l.right.take();
595
596                self_r.color = Color::Black;
597                self_r.left = new_r_l;
598                SharedPointer::make_mut(self_r.right.as_mut().unwrap()).color = Color::Red;
599
600                self_r.remove_balance();
601
602                self.color = Color::Red;
603
604                self_r_l.right = self_r_l.left.take();
605                self_r_l.left = self.left.take();
606
607                swap(&mut self.entry, &mut self_r_l.entry);
608
609                self.left = Some(self_r_l_ptr);
610            }
611            _ => unreachable!(),
612        }
613    }
614
615    fn remove_balance_right(&mut self) {
616        use Color::Black as B;
617        use Color::Red as R;
618
619        use core::mem::swap;
620
621        let color_r: Option<Color> = self.right_color();
622        let color_l: Option<Color> = self.left_color();
623        let color_l_r: Option<Color> = self.left.as_ref().and_then(|l| l.right_color());
624
625        match (color_l, color_l_r, color_r) {
626            (.., Some(R)) => {
627                let self_r = SharedPointer::make_mut(self.right.as_mut().unwrap());
628
629                self.color = Color::Red;
630                self_r.color = Color::Black;
631            }
632            (Some(B), ..) => {
633                let self_l = SharedPointer::make_mut(self.left.as_mut().unwrap());
634
635                self.color = Color::Black;
636                self_l.color = Color::Red;
637
638                self.remove_balance();
639            }
640            (Some(R), Some(B), _) => {
641                let self_l = SharedPointer::make_mut(self.left.as_mut().unwrap());
642
643                let mut self_l_r_ptr = self_l.right.take().unwrap();
644                let self_l_r = SharedPointer::make_mut(&mut self_l_r_ptr);
645                let new_l_r = self_l_r.left.take();
646
647                self_l.color = Color::Black;
648                self_l.right = new_l_r;
649                SharedPointer::make_mut(self_l.left.as_mut().unwrap()).color = Color::Red;
650
651                self_l.remove_balance();
652
653                self.color = Color::Red;
654
655                self_l_r.left = self_l_r.right.take();
656                self_l_r.right = self.right.take();
657
658                swap(&mut self.entry, &mut self_l_r.entry);
659
660                self.right = Some(self_l_r_ptr);
661            }
662            _ => unreachable!(),
663        }
664    }
665
666    /// Returns `true` if the key was present.
667    ///
668    /// If the node becomes empty `*root` will be set to `None`.
669    fn remove<Q: ?Sized>(root: &mut Option<SharedPointer<Node<K, V, P>, P>>, key: &Q) -> bool
670    where
671        K: Borrow<Q>,
672        Q: Ord,
673    {
674        fn del_left<K, V, Q: ?Sized, P>(node: &mut Node<K, V, P>, k: &Q) -> bool
675        where
676            K: Borrow<Q> + Ord,
677            Q: Ord,
678            P: SharedPointerKind,
679        {
680            let original_left_color = node.left_color();
681            let removed = del(&mut node.left, k, false);
682
683            node.color = Color::Red; // In case of rebalance the color does not matter.
684
685            if let Some(Color::Black) = original_left_color {
686                node.remove_balance_left();
687            }
688
689            removed
690        }
691
692        fn del_right<K, V, Q: ?Sized, P>(node: &mut Node<K, V, P>, k: &Q) -> bool
693        where
694            K: Borrow<Q> + Ord,
695            Q: Ord,
696            P: SharedPointerKind,
697        {
698            let original_right_color = node.right_color();
699
700            let removed = del(&mut node.right, k, false);
701
702            node.color = Color::Red; // In case of rebalance the color does not matter.
703
704            if let Some(Color::Black) = original_right_color {
705                node.remove_balance_right();
706            }
707
708            removed
709        }
710
711        fn del<K, V, Q: ?Sized, P>(
712            node: &mut Option<SharedPointer<Node<K, V, P>, P>>,
713            k: &Q,
714            is_root: bool,
715        ) -> bool
716        where
717            K: Borrow<Q> + Ord,
718            Q: Ord,
719            P: SharedPointerKind,
720        {
721            let (removed, make_node_none) = match *node {
722                Some(ref mut node) => {
723                    let node = SharedPointer::make_mut(node);
724
725                    let ret = match k.cmp(node.entry.key.borrow()) {
726                        Ordering::Less => (del_left(node, k), false),
727                        Ordering::Equal => {
728                            let left = node.left.take();
729                            let right = node.right.take();
730
731                            let make_node_none = !Node::remove_fuse(node, left, right);
732
733                            (true, make_node_none)
734                        }
735                        Ordering::Greater => (del_right(node, k), false),
736                    };
737
738                    if is_root {
739                        node.color = Color::Black;
740                    }
741
742                    ret
743                }
744                None => (false, false),
745            };
746
747            if make_node_none {
748                *node = None;
749            }
750
751            removed
752        }
753
754        del(root, key, true)
755    }
756}
757
758impl<K, V, P> Node<K, V, P>
759where
760    K: Ord + Clone,
761    V: Clone,
762    P: SharedPointerKind,
763{
764    fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut Entry<K, V>>
765    where
766        K: Borrow<Q>,
767        Q: Ord,
768    {
769        match key.cmp(self.entry.key.borrow()) {
770            Ordering::Less => {
771                self.left.as_mut().and_then(|l| SharedPointer::make_mut(l).get_mut(key))
772            }
773            Ordering::Equal => Some(SharedPointer::make_mut(&mut self.entry)),
774            Ordering::Greater => {
775                self.right.as_mut().and_then(|r| SharedPointer::make_mut(r).get_mut(key))
776            }
777        }
778    }
779}
780
781impl<K, V> RedBlackTreeMapSync<K, V>
782where
783    K: Ord,
784{
785    #[must_use]
786    pub fn new_sync() -> RedBlackTreeMapSync<K, V> {
787        RedBlackTreeMap::new_with_ptr_kind()
788    }
789}
790
791impl<K, V> RedBlackTreeMap<K, V>
792where
793    K: Ord,
794{
795    #[must_use]
796    pub fn new() -> RedBlackTreeMap<K, V> {
797        RedBlackTreeMap::new_with_ptr_kind()
798    }
799}
800
801impl<K, V, P> RedBlackTreeMap<K, V, P>
802where
803    K: Ord,
804    P: SharedPointerKind,
805{
806    #[must_use]
807    pub fn new_with_ptr_kind() -> RedBlackTreeMap<K, V, P> {
808        RedBlackTreeMap { root: None, size: 0 }
809    }
810
811    #[must_use]
812    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
813    where
814        K: Borrow<Q>,
815        Q: Ord,
816    {
817        self.root.as_ref().and_then(|r| r.get(key)).map(|e| &e.value)
818    }
819
820    #[must_use]
821    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
822    where
823        K: Borrow<Q>,
824        Q: Ord,
825    {
826        self.root.as_ref().and_then(|r| r.get(key)).map(|e| (&e.key, &e.value))
827    }
828
829    #[must_use]
830    pub fn first(&self) -> Option<(&K, &V)> {
831        self.root.as_ref().map(|r| r.first()).map(|e| (&e.key, &e.value))
832    }
833
834    #[must_use]
835    pub fn last(&self) -> Option<(&K, &V)> {
836        self.root.as_ref().map(|r| r.last()).map(|e| (&e.key, &e.value))
837    }
838
839    #[must_use]
840    pub fn insert(&self, key: K, value: V) -> RedBlackTreeMap<K, V, P> {
841        let mut new_map = self.clone();
842
843        new_map.insert_mut(key, value);
844
845        new_map
846    }
847
848    pub fn insert_mut(&mut self, key: K, value: V) {
849        let is_new_key = Node::insert(&mut self.root, key, value);
850
851        if is_new_key {
852            self.size += 1;
853        }
854    }
855
856    #[must_use]
857    pub fn remove<Q: ?Sized>(&self, key: &Q) -> RedBlackTreeMap<K, V, P>
858    where
859        K: Borrow<Q>,
860        Q: Ord,
861    {
862        let mut new_map = self.clone();
863
864        if new_map.remove_mut(key) {
865            new_map
866        } else {
867            // We want to keep maximum sharing so in case of no change we just `clone()` ourselves.
868            self.clone()
869        }
870    }
871
872    pub fn remove_mut<Q: ?Sized>(&mut self, key: &Q) -> bool
873    where
874        K: Borrow<Q>,
875        Q: Ord,
876    {
877        let removed = Node::remove(&mut self.root, key);
878
879        // Note that unfortunately, even if nothing was removed, we still might have cloned some
880        // part of the tree unnecessarily.
881
882        if removed {
883            self.size -= 1;
884        }
885
886        removed
887    }
888
889    #[must_use]
890    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
891    where
892        K: Borrow<Q>,
893        Q: Ord,
894    {
895        self.get(key).is_some()
896    }
897
898    /// Test whether the two maps refer to the same content in memory.
899    ///
900    /// This would return true if you’re comparing a map to itself,
901    /// or if you’re comparing a map to a fresh clone of itself.
902    pub(crate) fn ptr_eq<PO: SharedPointerKind>(&self, other: &RedBlackTreeMap<K, V, PO>) -> bool {
903        let a = self.root.as_ref().map_or(core::ptr::null(), SharedPointer::as_ptr);
904        // Note how we're casting the raw pointer changing from P to PO
905        // We cannot perform the equality in a type safe way because the root type depends
906        // on P/PO, and we can't pass different types to SharedPtr::same_ptr or std::ptr::eq.
907        let b = other
908            .root
909            .as_ref()
910            .map_or(core::ptr::null(), SharedPointer::as_ptr)
911            .cast::<Node<K, V, P>>();
912        core::ptr::eq(a, b)
913    }
914
915    #[must_use]
916    #[inline]
917    pub fn size(&self) -> usize {
918        self.size
919    }
920
921    #[must_use]
922    #[inline]
923    pub fn is_empty(&self) -> bool {
924        self.size() == 0
925    }
926
927    pub fn iter(&self) -> Iter<'_, K, V, P> {
928        self.iter_ptr().map(|e| (&e.key, &e.value))
929    }
930
931    #[must_use]
932    fn iter_ptr(&self) -> IterPtr<'_, K, V, P> {
933        IterPtr::new(self)
934    }
935
936    pub fn keys(&self) -> IterKeys<'_, K, V, P> {
937        self.iter().map(|(k, _)| k)
938    }
939
940    pub fn values(&self) -> IterValues<'_, K, V, P> {
941        self.iter().map(|(_, v)| v)
942    }
943
944    pub fn range<Q, RB>(&self, range: RB) -> RangeIter<'_, K, V, RB, Q, P>
945    where
946        K: Borrow<Q>,
947        Q: Ord + ?Sized,
948        RB: RangeBounds<Q>,
949    {
950        use core::ops::Bound::*;
951
952        match (range.start_bound(), range.end_bound()) {
953            (Excluded(s), Excluded(e)) if s == e => {
954                panic!("range start and end are equal and excluded")
955            }
956            (Included(s), Included(e))
957            | (Included(s), Excluded(e))
958            | (Excluded(s), Included(e))
959            | (Excluded(s), Excluded(e))
960                if s > e =>
961            {
962                panic!("range start is greater than range end")
963            }
964            (_, _) => RangeIterPtr::new(self, range).map(|e| (&e.key, &e.value)),
965        }
966    }
967}
968
969impl<K, V, P> RedBlackTreeMap<K, V, P>
970where
971    K: Ord + Clone,
972    V: Clone,
973    P: SharedPointerKind,
974{
975    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
976    where
977        K: Borrow<Q>,
978        Q: Ord,
979    {
980        // Note that unfortunately, even if nothing is found, we still might have cloned some
981        // part of the tree unnecessarily.
982        self.root
983            .as_mut()
984            .and_then(|r| SharedPointer::make_mut(r).get_mut(key).map(|e| &mut e.value))
985    }
986}
987
988impl<K, Q: ?Sized, V, P> Index<&Q> for RedBlackTreeMap<K, V, P>
989where
990    K: Ord + Borrow<Q>,
991    Q: Ord,
992    P: SharedPointerKind,
993{
994    type Output = V;
995
996    fn index(&self, key: &Q) -> &V {
997        self.get(key).expect("no entry found for key")
998    }
999}
1000
1001impl<K, V, P> Clone for RedBlackTreeMap<K, V, P>
1002where
1003    K: Ord,
1004    P: SharedPointerKind,
1005{
1006    fn clone(&self) -> RedBlackTreeMap<K, V, P> {
1007        RedBlackTreeMap { root: self.root.clone(), size: self.size }
1008    }
1009}
1010
1011impl<K, V, P> Default for RedBlackTreeMap<K, V, P>
1012where
1013    K: Ord,
1014    P: SharedPointerKind,
1015{
1016    fn default() -> RedBlackTreeMap<K, V, P> {
1017        RedBlackTreeMap::new_with_ptr_kind()
1018    }
1019}
1020
1021impl<K, V: PartialEq, P, PO> PartialEq<RedBlackTreeMap<K, V, PO>> for RedBlackTreeMap<K, V, P>
1022where
1023    K: Ord,
1024    P: SharedPointerKind,
1025    PO: SharedPointerKind,
1026{
1027    fn eq(&self, other: &RedBlackTreeMap<K, V, PO>) -> bool {
1028        if self.ptr_eq(other) {
1029            return true;
1030        }
1031        self.size() == other.size()
1032            && self.iter().all(|(key, value)| other.get(key).is_some_and(|v| *value == *v))
1033    }
1034}
1035
1036impl<K, V: Eq, P> Eq for RedBlackTreeMap<K, V, P>
1037where
1038    K: Ord,
1039    P: SharedPointerKind,
1040{
1041}
1042
1043impl<K: Ord, V: PartialOrd, P, PO> PartialOrd<RedBlackTreeMap<K, V, PO>>
1044    for RedBlackTreeMap<K, V, P>
1045where
1046    P: SharedPointerKind,
1047    PO: SharedPointerKind,
1048{
1049    fn partial_cmp(&self, other: &RedBlackTreeMap<K, V, PO>) -> Option<Ordering> {
1050        self.iter().partial_cmp(other.iter())
1051    }
1052}
1053
1054impl<K: Ord, V: Ord, P> Ord for RedBlackTreeMap<K, V, P>
1055where
1056    P: SharedPointerKind,
1057{
1058    fn cmp(&self, other: &RedBlackTreeMap<K, V, P>) -> Ordering {
1059        self.iter().cmp(other.iter())
1060    }
1061}
1062
1063impl<K: Hash, V: Hash, P: SharedPointerKind> Hash for RedBlackTreeMap<K, V, P>
1064where
1065    K: Ord,
1066{
1067    fn hash<H: Hasher>(&self, state: &mut H) {
1068        // Add the hash of length so that if two collections are added one after the other it
1069        // doesn't hash to the same thing as a single collection with the same elements in the same
1070        // order.
1071        self.size().hash(state);
1072
1073        for e in self {
1074            e.hash(state);
1075        }
1076    }
1077}
1078
1079impl<K, V, P> Display for RedBlackTreeMap<K, V, P>
1080where
1081    K: Ord + Display,
1082    V: Display,
1083    P: SharedPointerKind,
1084{
1085    fn fmt(&self, fmt: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1086        let mut first = true;
1087
1088        fmt.write_str("{")?;
1089
1090        for (k, v) in self {
1091            if !first {
1092                fmt.write_str(", ")?;
1093            }
1094            k.fmt(fmt)?;
1095            fmt.write_str(": ")?;
1096            v.fmt(fmt)?;
1097            first = false;
1098        }
1099
1100        fmt.write_str("}")
1101    }
1102}
1103
1104impl<'a, K, V, P> IntoIterator for &'a RedBlackTreeMap<K, V, P>
1105where
1106    K: Ord,
1107    P: SharedPointerKind,
1108{
1109    type Item = (&'a K, &'a V);
1110    type IntoIter = Iter<'a, K, V, P>;
1111
1112    fn into_iter(self) -> Iter<'a, K, V, P> {
1113        self.iter()
1114    }
1115}
1116
1117// TODO This can be improved to create a perfectly balanced tree.
1118impl<K, V, P> FromIterator<(K, V)> for RedBlackTreeMap<K, V, P>
1119where
1120    K: Ord,
1121    P: SharedPointerKind,
1122{
1123    fn from_iter<I: IntoIterator<Item = (K, V)>>(into_iter: I) -> RedBlackTreeMap<K, V, P> {
1124        let mut map = RedBlackTreeMap::new_with_ptr_kind();
1125
1126        for (k, v) in into_iter {
1127            map.insert_mut(k, v);
1128        }
1129
1130        map
1131    }
1132}
1133
1134mod iter_utils {
1135    use super::{Entry, Node, RedBlackTreeMap};
1136    use alloc::vec::Vec;
1137    use archery::{SharedPointer, SharedPointerKind};
1138    use core::borrow::Borrow;
1139    use core::ops::Bound;
1140
1141    // This is a stack for navigating through the tree. It can be used to go either forwards or
1142    // backwards: you choose the direction at construction time, and then every call to `advance`
1143    // goes in that direction.
1144    #[derive(Debug)]
1145    pub struct IterStack<'a, K, V, P>
1146    where
1147        P: SharedPointerKind,
1148    {
1149        // The invariant maintained by `stack` depends on whether we are moving forwards or backwards.
1150        // In either case, the current node is at the top of the stack. If we are moving forwards, the
1151        // rest of the stack consists of those ancestors of the current node that contain the current
1152        // node in their left subtree. In other words, the keys in the stack increase as we go from the
1153        // top of the stack to the bottom.
1154        stack: Vec<&'a Node<K, V, P>>,
1155        backwards: bool,
1156    }
1157
1158    impl<'a, K, V, P> IterStack<'a, K, V, P>
1159    where
1160        K: Ord,
1161        P: SharedPointerKind,
1162    {
1163        pub fn new<Q>(
1164            map: &'a RedBlackTreeMap<K, V, P>,
1165            start_bound: Bound<&Q>,
1166            end_bound: Bound<&Q>,
1167            backwards: bool,
1168        ) -> IterStack<'a, K, V, P>
1169        where
1170            K: Borrow<Q>,
1171            Q: Ord + ?Sized,
1172        {
1173            let size = conservative_height(map.size()) + 1;
1174
1175            let mut stack = IterStack { stack: Vec::with_capacity(size), backwards };
1176
1177            if let Some(ref root) = map.root {
1178                stack.dig_towards(root.borrow(), start_bound, end_bound);
1179            }
1180
1181            stack.clear_if_finished(start_bound, end_bound);
1182
1183            stack
1184        }
1185
1186        fn clear_if_finished<Q>(&mut self, start_bound: Bound<&Q>, end_bound: Bound<&Q>)
1187        where
1188            K: Borrow<Q>,
1189            Q: Ord + ?Sized,
1190        {
1191            use core::ops::Bound::*;
1192
1193            if let Some(entry) = self.current() {
1194                let in_range = if self.backwards {
1195                    match start_bound {
1196                        Included(v) => entry.key.borrow() >= v,
1197                        Excluded(v) => entry.key.borrow() > v,
1198                        Unbounded => true,
1199                    }
1200                } else {
1201                    match end_bound {
1202                        Included(v) => entry.key.borrow() <= v,
1203                        Excluded(v) => entry.key.borrow() < v,
1204                        Unbounded => true,
1205                    }
1206                };
1207
1208                if !in_range {
1209                    self.stack.clear();
1210                }
1211            }
1212        }
1213
1214        #[inline]
1215        pub fn current(&self) -> Option<&'a SharedPointer<Entry<K, V>, P>> {
1216            self.stack.last().map(|node| &node.entry)
1217        }
1218
1219        fn dig<Q>(&mut self)
1220        where
1221            K: Borrow<Q>,
1222            Q: Ord + ?Sized,
1223        {
1224            let child = self.stack.last().and_then(|node| {
1225                let c = if self.backwards { node.right.as_ref() } else { node.left.as_ref() };
1226                Node::borrow(c)
1227            });
1228
1229            if let Some(c) = child {
1230                self.stack.push(c);
1231                self.dig();
1232            }
1233        }
1234
1235        fn dig_towards<Q>(
1236            &mut self,
1237            node: &'a Node<K, V, P>,
1238            start_bound: Bound<&Q>,
1239            end_bound: Bound<&Q>,
1240        ) where
1241            K: Borrow<Q>,
1242            Q: Ord + ?Sized,
1243        {
1244            use core::ops::Bound::*;
1245
1246            let in_range = if self.backwards {
1247                match end_bound {
1248                    Included(v) => node.entry.key.borrow() <= v,
1249                    Excluded(v) => node.entry.key.borrow() < v,
1250                    Unbounded => true,
1251                }
1252            } else {
1253                match start_bound {
1254                    Included(v) => node.entry.key.borrow() >= v,
1255                    Excluded(v) => node.entry.key.borrow() > v,
1256                    Unbounded => true,
1257                }
1258            };
1259
1260            if in_range {
1261                self.stack.push(node);
1262            }
1263
1264            let child = match (self.backwards, in_range) {
1265                (false, true) => &node.left,
1266                (false, false) => &node.right,
1267                (true, true) => &node.right,
1268                (true, false) => &node.left,
1269            };
1270
1271            if let Some(c) = child {
1272                self.dig_towards(c.borrow(), start_bound, end_bound);
1273            }
1274        }
1275
1276        pub fn advance<Q>(&mut self, start_bound: Bound<&Q>, end_bound: Bound<&Q>)
1277        where
1278            K: Borrow<Q>,
1279            Q: Ord + ?Sized,
1280        {
1281            if let Some(node) = self.stack.pop() {
1282                let child = if self.backwards { node.left.as_ref() } else { node.right.as_ref() };
1283
1284                if let Some(c) = Node::borrow(child) {
1285                    self.stack.push(c);
1286                    self.dig();
1287                }
1288
1289                self.clear_if_finished(start_bound, end_bound);
1290            }
1291        }
1292    }
1293
1294    pub fn lg_floor(size: usize) -> usize {
1295        debug_assert!(size > 0);
1296
1297        let c: usize = usize::BITS as usize - size.leading_zeros() as usize;
1298
1299        c - 1
1300    }
1301
1302    pub fn conservative_height(size: usize) -> usize {
1303        if size > 0 { 2 * lg_floor(size + 1) } else { 0 }
1304    }
1305}
1306
1307#[derive(Debug)]
1308pub struct IterPtr<'a, K, V, P>
1309where
1310    P: SharedPointerKind,
1311{
1312    range_iter: RangeIterPtr<'a, K, V, RangeFull, K, P>,
1313
1314    // Number of elements left in the iterator.
1315    size: usize,
1316}
1317
1318impl<K, V, P> IterPtr<'_, K, V, P>
1319where
1320    K: Ord,
1321    P: SharedPointerKind,
1322{
1323    fn new(map: &RedBlackTreeMap<K, V, P>) -> IterPtr<'_, K, V, P> {
1324        IterPtr { range_iter: RangeIterPtr::new(map, ..), size: map.size }
1325    }
1326}
1327
1328impl<'a, K, V, P> Iterator for IterPtr<'a, K, V, P>
1329where
1330    K: Ord,
1331    P: SharedPointerKind,
1332{
1333    type Item = &'a SharedPointer<Entry<K, V>, P>;
1334
1335    fn next(&mut self) -> Option<&'a SharedPointer<Entry<K, V>, P>> {
1336        if self.size > 0 {
1337            self.size -= 1;
1338            self.range_iter.next()
1339        } else {
1340            None
1341        }
1342    }
1343
1344    fn size_hint(&self) -> (usize, Option<usize>) {
1345        (self.size, Some(self.size))
1346    }
1347}
1348
1349impl<'a, K, V, P> DoubleEndedIterator for IterPtr<'a, K, V, P>
1350where
1351    K: Ord,
1352    P: SharedPointerKind,
1353{
1354    fn next_back(&mut self) -> Option<&'a SharedPointer<Entry<K, V>, P>> {
1355        if self.size > 0 {
1356            self.size -= 1;
1357            self.range_iter.next_back()
1358        } else {
1359            None
1360        }
1361    }
1362}
1363
1364impl<K: Ord, V, P> ExactSizeIterator for IterPtr<'_, K, V, P> where P: SharedPointerKind {}
1365
1366#[derive(Debug)]
1367pub struct RangeIterPtr<'a, K, V, RB, Q: ?Sized, P>
1368where
1369    P: SharedPointerKind,
1370{
1371    map: &'a RedBlackTreeMap<K, V, P>,
1372
1373    stack_forward: Option<iter_utils::IterStack<'a, K, V, P>>,
1374    stack_backward: Option<iter_utils::IterStack<'a, K, V, P>>,
1375
1376    range: RB,
1377    _q: PhantomData<Q>,
1378}
1379
1380impl<'a, K, V, Q, RB, P> RangeIterPtr<'a, K, V, RB, Q, P>
1381where
1382    K: Ord + Borrow<Q>,
1383    Q: Ord + ?Sized,
1384    RB: RangeBounds<Q>,
1385    P: SharedPointerKind,
1386{
1387    fn new(map: &'a RedBlackTreeMap<K, V, P>, range: RB) -> RangeIterPtr<'a, K, V, RB, Q, P> {
1388        RangeIterPtr { map, stack_forward: None, stack_backward: None, range, _q: PhantomData }
1389    }
1390
1391    fn init_if_needed(&mut self, backwards: bool) {
1392        use iter_utils::IterStack;
1393
1394        let stack_field =
1395            if backwards { &mut self.stack_backward } else { &mut self.stack_forward };
1396
1397        if stack_field.is_none() {
1398            *stack_field = Some(IterStack::new(
1399                self.map,
1400                self.range.start_bound(),
1401                self.range.end_bound(),
1402                backwards,
1403            ));
1404        }
1405    }
1406
1407    fn is_remaining_range_empty(&self) -> bool {
1408        match (&self.stack_forward, &self.stack_backward) {
1409            (Some(stack_forward), Some(stack_backward)) => {
1410                match (stack_forward.current(), stack_backward.current()) {
1411                    (Some(left), Some(right)) => left.key > right.key,
1412                    (_, _) => true,
1413                }
1414            }
1415            (_, _) => false,
1416        }
1417    }
1418
1419    fn current_forward(&self) -> Option<&'a SharedPointer<Entry<K, V>, P>> {
1420        match self.is_remaining_range_empty() {
1421            true => None,
1422            false => self.stack_forward.as_ref().unwrap().current(),
1423        }
1424    }
1425
1426    fn advance_forward(&mut self) {
1427        self.stack_forward
1428            .as_mut()
1429            .unwrap()
1430            .advance(self.range.start_bound(), self.range.end_bound());
1431    }
1432
1433    fn current_backward(&self) -> Option<&'a SharedPointer<Entry<K, V>, P>> {
1434        match self.is_remaining_range_empty() {
1435            true => None,
1436            false => self.stack_backward.as_ref().unwrap().current(),
1437        }
1438    }
1439
1440    fn advance_backward(&mut self) {
1441        self.stack_backward
1442            .as_mut()
1443            .unwrap()
1444            .advance(self.range.start_bound(), self.range.end_bound());
1445    }
1446}
1447
1448impl<'a, K, V, RB, Q, P> Iterator for RangeIterPtr<'a, K, V, RB, Q, P>
1449where
1450    K: Ord + Borrow<Q>,
1451    Q: Ord + ?Sized,
1452    RB: RangeBounds<Q>,
1453    P: SharedPointerKind,
1454{
1455    type Item = &'a SharedPointer<Entry<K, V>, P>;
1456
1457    fn next(&mut self) -> Option<Self::Item> {
1458        self.init_if_needed(false);
1459
1460        let current = self.current_forward();
1461
1462        self.advance_forward();
1463
1464        current
1465    }
1466}
1467
1468impl<'a, K, V, RB, Q, P> DoubleEndedIterator for RangeIterPtr<'a, K, V, RB, Q, P>
1469where
1470    K: Ord + Borrow<Q>,
1471    Q: Ord + ?Sized,
1472    RB: RangeBounds<Q>,
1473    P: SharedPointerKind,
1474{
1475    fn next_back(&mut self) -> Option<&'a SharedPointer<Entry<K, V>, P>> {
1476        self.init_if_needed(true);
1477
1478        let current = self.current_backward();
1479
1480        self.advance_backward();
1481
1482        current
1483    }
1484}
1485
1486#[cfg(feature = "serde")]
1487pub mod serde {
1488    use super::*;
1489    use ::serde::de::{Deserialize, Deserializer, MapAccess, Visitor};
1490    use ::serde::ser::{Serialize, Serializer};
1491    use core::fmt;
1492    use core::marker::PhantomData;
1493
1494    impl<K, V, P> Serialize for RedBlackTreeMap<K, V, P>
1495    where
1496        K: Ord + Serialize,
1497        V: Serialize,
1498        P: SharedPointerKind,
1499    {
1500        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
1501            serializer.collect_map(self)
1502        }
1503    }
1504
1505    impl<'de, K, V, P> Deserialize<'de> for RedBlackTreeMap<K, V, P>
1506    where
1507        K: Ord + Deserialize<'de>,
1508        V: Deserialize<'de>,
1509        P: SharedPointerKind,
1510    {
1511        fn deserialize<D: Deserializer<'de>>(
1512            deserializer: D,
1513        ) -> Result<RedBlackTreeMap<K, V, P>, D::Error> {
1514            deserializer.deserialize_map(RedBlackTreeMapVisitor {
1515                _phantom_entry: PhantomData,
1516                _phantom_p: PhantomData,
1517            })
1518        }
1519    }
1520
1521    struct RedBlackTreeMapVisitor<K, V, P>
1522    where
1523        P: SharedPointerKind,
1524    {
1525        _phantom_entry: PhantomData<(K, V)>,
1526        _phantom_p: PhantomData<P>,
1527    }
1528
1529    impl<'de, K, V, P> Visitor<'de> for RedBlackTreeMapVisitor<K, V, P>
1530    where
1531        K: Ord + Deserialize<'de>,
1532        V: Deserialize<'de>,
1533        P: SharedPointerKind,
1534    {
1535        type Value = RedBlackTreeMap<K, V, P>;
1536
1537        fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
1538            formatter.write_str("a map")
1539        }
1540
1541        fn visit_map<A>(self, mut map: A) -> Result<RedBlackTreeMap<K, V, P>, A::Error>
1542        where
1543            A: MapAccess<'de>,
1544        {
1545            let mut rb_tree_map = RedBlackTreeMap::new_with_ptr_kind();
1546
1547            while let Some((k, v)) = map.next_entry()? {
1548                rb_tree_map.insert_mut(k, v);
1549            }
1550
1551            Ok(rb_tree_map)
1552        }
1553    }
1554}
1555
1556#[cfg(test)]
1557mod test;
rpds/map/red_black_tree_map/mod.rs

rpds/map/red_black_tree_map/
mod.rs
