1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

use core::iter::Peekable;

/// A iterator for deduping the key of a sorted iterator.
/// When encountering the duplicated key, only the last key-value pair is yielded.
///
/// Used by [`BTreeMap::bulk_build_from_sorted_iter`][1].
///
/// [1]: crate::collections::BTreeMap::bulk_build_from_sorted_iter
pub struct DedupSortedIter<K, V, I>
where
    I: Iterator<Item = (K, V)>,
{
    iter: Peekable<I>,
}

impl<K, V, I> DedupSortedIter<K, V, I>
where
    I: Iterator<Item = (K, V)>,
{
    pub fn new(iter: I) -> Self {
        Self { iter: iter.peekable() }
    }
}

impl<K, V, I> Iterator for DedupSortedIter<K, V, I>
where
    K: Eq,
    I: Iterator<Item = (K, V)>,
{
    type Item = (K, V);

    fn next(&mut self) -> Option<(K, V)> {
        loop {
            let next = match self.iter.next() {
                Some(next) => next,
                None => return None,
            };

            let peeked = match self.iter.peek() {
                Some(peeked) => peeked,
                None => return Some(next),
            };

            if next.0 != peeked.0 {
                return Some(next);
            }
        }
    }
}