copse/liballoc/collections/btree/
dedup_sorted_iter.rs

1use core::iter::Peekable;
2
3use crate::{SortableBy, TotalOrder};
4
5/// A iterator for deduping the key of a sorted iterator.
6/// When encountering the duplicated key, only the last key-value pair is yielded.
7///
8/// Used by [`BTreeMap::bulk_build_from_sorted_iter`][1].
9///
10/// [1]: crate::collections::BTreeMap::bulk_build_from_sorted_iter
11pub struct DedupSortedIter<'a, K, V, O, I>
12where
13    I: Iterator<Item = (K, V)>,
14{
15    iter: Peekable<I>,
16    order: &'a O,
17}
18
19impl<'a, K, V, O, I> DedupSortedIter<'a, K, V, O, I>
20where
21    I: Iterator<Item = (K, V)>,
22{
23    pub fn new(iter: I, order: &'a O) -> Self {
24        Self { iter: iter.peekable(), order }
25    }
26}
27
28impl<K, V, O, I> Iterator for DedupSortedIter<'_, K, V, O, I>
29where
30    K: SortableBy<O>,
31    O: TotalOrder,
32    I: Iterator<Item = (K, V)>,
33{
34    type Item = (K, V);
35
36    fn next(&mut self) -> Option<(K, V)> {
37        loop {
38            let next = match self.iter.next() {
39                Some(next) => next,
40                None => return None,
41            };
42
43            let peeked = match self.iter.peek() {
44                Some(peeked) => peeked,
45                None => return Some(next),
46            };
47
48            if self.order.ne(&next.0, &peeked.0) {
49                return Some(next);
50            }
51        }
52    }
53}

copse/liballoc/collections/btree/dedup_sorted_iter.rs

copse/liballoc/collections/btree/
dedup_sorted_iter.rs