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
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

pub trait MergeSortImpl<T>
where
    T: Iterator,
    T::Item: Ord + Clone,
{
    fn merge_sort(self, desc: bool) -> MergeSort<T>;
}

impl<T> MergeSortImpl<T> for Vec<T>
where
    T: Iterator,
    T::Item: Ord + Clone,
{
    fn merge_sort(self, desc: bool) -> MergeSort<T> {
        MergeSort {
            iters: self.into_iter()
                .map(|iter| (iter, None))
                .collect::<Vec<_>>(),
            desc: desc,
        }
    }
}

pub struct MergeSort<T>
where
    T: Iterator,
    T::Item: Ord + Clone,
{
    iters: Vec<(T, Option<T::Item>)>,
    desc: bool,
}

impl<T> Iterator for MergeSort<T>
where
    T: Iterator,
    T::Item: Ord + Clone,
{
    type Item = T::Item;
    fn next(&mut self) -> Option<T::Item> {
        //None埋め
        for i in 0..self.iters.len() {
            match self.iters[i].1 {
                Option::None => self.iters[i].1 = self.iters[i].0.next(),
                _ => {}
            }
        }
        if let Some((i, item)) = {
            let it = self.iters
                .iter()
                .enumerate()
                .filter_map(|(i, x)| match x.1.clone() {
                    Option::Some(item) => Some((i, item)),
                    Option::None => None,
                });
            if self.desc {
                it.max_by_key(|x| x.1.clone())
            } else {
                it.min_by_key(|x| x.1.clone())
            }
        } {
            self.iters[i].1 = None;
            Some(item)
        } else {
            None
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn emepy() {
        let vec1: Vec<i32> = Vec::new();
        let vec2: Vec<std::vec::IntoIter<i32>> = Vec::new();

        assert_eq!(vec1, vec2.merge_sort(true).collect::<Vec<_>>());
    }

    #[test]
    fn one_desc() {
        assert_eq!(
            vec![3, 2, 1],
            vec![vec![3, 2, 1].into_iter()]
                .merge_sort(true)
                .collect::<Vec<_>>()
        );
    }

    #[test]
    fn one_not_desc() {
        assert_eq!(
            vec![1, 2, 3],
            vec![vec![1, 2, 3].into_iter()]
                .merge_sort(false)
                .collect::<Vec<_>>()
        );
    }

    #[test]
    fn desc() {
        assert_eq!(
            vec![5, 3, 2, 1],
            vec![
                vec![5, 1].into_iter(),
                vec![].into_iter(),
                vec![3, 2].into_iter(),
                vec![].into_iter(),
            ].merge_sort(true)
                .collect::<Vec<_>>()
        );
    }

    #[test]
    fn not_desc() {
        assert_eq!(
            vec![1, 2, 2, 3, 4, 4],
            vec![
                vec![2, 4].into_iter(),
                vec![1, 3].into_iter(),
                vec![2, 4].into_iter(),
            ].merge_sort(false)
                .collect::<Vec<_>>()
        );
    }

    #[test]
    fn infinite_not_desc() {
        assert_eq!(
            vec![1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7],
            vec![(3..), (4..), (1..)]
                .merge_sort(false)
                .take(15)
                .collect::<Vec<_>>()
        );
    }
}