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
50
51
52
53
54

//! ソート済み配列の線形時間マージ

use std::iter::Peekable;

pub trait Merge: Iterator
where
    Self::Item: Ord,
    Self: Sized,
{
    /// ソート済み配列をマージする
    ///
    /// - 時間計算量: $`O(N + M)`$
    fn merge_linear(self, other: Self) -> MergeIterator<Self::Item, Self, Self> {
        MergeIterator {
            itr_a: self.peekable(),
            itr_b: other.peekable(),
        }
    }
}

impl<I: Iterator> Merge for I where I::Item: Ord {}

/// 2つのソート済みイテレータを，整列順に返す
pub struct MergeIterator<T, I, J>
where
    T: Ord,
    I: Iterator<Item = T>,
    J: Iterator<Item = T>,
{
    itr_a: Peekable<I>,
    itr_b: Peekable<J>,
}

impl<T, I, J> Iterator for MergeIterator<T, I, J>
where
    T: Ord,
    I: Iterator<Item = T>,
    J: Iterator<Item = T>,
{
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        match (self.itr_a.peek(), self.itr_b.peek()) {
            (Some(a), Some(b)) => {
                if a <= b {
                    self.itr_a.next()
                } else {
                    self.itr_b.next()
                }
            }
            (Some(_), _) => self.itr_a.next(),
            _ => self.itr_b.next(),
        }
    }
}