radix_rust/iterators/
overlaying_iterator.rs

1use crate::prelude::*;
2use core::cmp::*;
3use core::iter::*;
4
5/// An iterator overlaying a "change on a value" (coming from the [`overlaying`] iterator) over a
6/// "base value" (coming from the [`underlying`] iterator).
7/// The one is matched to another by a `K` part (of the iterated tuple `(K, V)`), which both
8/// iterators are assumed to be ordered by.
9pub struct OverlayingIterator<U, O>
10where
11    U: Iterator,
12    O: Iterator,
13{
14    underlying: Peekable<U>,
15    overlaying: Peekable<O>,
16}
17
18impl<K, V, U, O> OverlayingIterator<U, O>
19where
20    K: Ord,
21    U: Iterator<Item = (K, V)>,
22    O: Iterator<Item = (K, Option<V>)>,
23{
24    /// Creates an overlaying iterator.
25    /// The [`underlying`] iterator provides the "base values".
26    /// The [`overlaying`] one provides the "changes" to those values, represented as `Option<V>`:
27    /// - A [`Some`] is an upsert, i.e. it may override an existing base value, or "insert" a
28    ///   completely new one to the iterated results.
29    /// - A [`None`] is a delete, which causes the base value to be omitted in the iterated results.
30    #[allow(clippy::new_ret_no_self)]
31    pub fn new(underlying: U, overlaying: O) -> impl Iterator<Item = (K, V)> {
32        Self {
33            underlying: underlying.peekable(),
34            overlaying: overlaying.peekable(),
35        }
36    }
37}
38
39impl<K, V, U, O> Iterator for OverlayingIterator<U, O>
40where
41    K: Ord,
42    U: Iterator<Item = (K, V)>,
43    O: Iterator<Item = (K, Option<V>)>,
44{
45    type Item = (K, V);
46
47    fn next(&mut self) -> Option<Self::Item> {
48        loop {
49            if let Some(overlaying_key) = self.overlaying.peek_key() {
50                if let Some(underlying_key) = self.underlying.peek_key() {
51                    match underlying_key.cmp(overlaying_key) {
52                        Ordering::Less => {
53                            return self.underlying.next(); // return and move it forward
54                        }
55                        Ordering::Equal => {
56                            self.underlying.next(); // only move it forward
57                        }
58                        Ordering::Greater => {
59                            // leave it as-is
60                        }
61                    };
62                }
63                let (overlaying_key, overlaying_change) = self.overlaying.next().unwrap();
64                match overlaying_change {
65                    Some(value) => return Some((overlaying_key, value)),
66                    None => continue, // we may need to skip over an unbounded number of deletes
67                }
68            } else {
69                return self.underlying.next();
70            }
71        }
72    }
73}
radix_rust/iterators/overlaying_iterator.rs

radix_rust/iterators/
overlaying_iterator.rs
