iter_merge_sort/
lib.rs

1pub trait MergeSortImpl<T>
2where
3    T: Iterator,
4    T::Item: Ord + Clone,
5{
6    fn merge_sort(self, desc: bool) -> MergeSort<T>;
7}
8
9impl<T> MergeSortImpl<T> for Vec<T>
10where
11    T: Iterator,
12    T::Item: Ord + Clone,
13{
14    fn merge_sort(self, desc: bool) -> MergeSort<T> {
15        MergeSort {
16            iters: self.into_iter()
17                .map(|iter| (iter, None))
18                .collect::<Vec<_>>(),
19            desc: desc,
20        }
21    }
22}
23
24pub struct MergeSort<T>
25where
26    T: Iterator,
27    T::Item: Ord + Clone,
28{
29    iters: Vec<(T, Option<T::Item>)>,
30    desc: bool,
31}
32
33impl<T> Iterator for MergeSort<T>
34where
35    T: Iterator,
36    T::Item: Ord + Clone,
37{
38    type Item = T::Item;
39    fn next(&mut self) -> Option<T::Item> {
40        //None埋め
41        for i in 0..self.iters.len() {
42            match self.iters[i].1 {
43                Option::None => self.iters[i].1 = self.iters[i].0.next(),
44                _ => {}
45            }
46        }
47        if let Some((i, item)) = {
48            let it = self.iters
49                .iter()
50                .enumerate()
51                .filter_map(|(i, x)| match x.1.clone() {
52                    Option::Some(item) => Some((i, item)),
53                    Option::None => None,
54                });
55            if self.desc {
56                it.max_by_key(|x| x.1.clone())
57            } else {
58                it.min_by_key(|x| x.1.clone())
59            }
60        } {
61            self.iters[i].1 = None;
62            Some(item)
63        } else {
64            None
65        }
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn emepy() {
75        let vec1: Vec<i32> = Vec::new();
76        let vec2: Vec<std::vec::IntoIter<i32>> = Vec::new();
77
78        assert_eq!(vec1, vec2.merge_sort(true).collect::<Vec<_>>());
79    }
80
81    #[test]
82    fn one_desc() {
83        assert_eq!(
84            vec![3, 2, 1],
85            vec![vec![3, 2, 1].into_iter()]
86                .merge_sort(true)
87                .collect::<Vec<_>>()
88        );
89    }
90
91    #[test]
92    fn one_not_desc() {
93        assert_eq!(
94            vec![1, 2, 3],
95            vec![vec![1, 2, 3].into_iter()]
96                .merge_sort(false)
97                .collect::<Vec<_>>()
98        );
99    }
100
101    #[test]
102    fn desc() {
103        assert_eq!(
104            vec![5, 3, 2, 1],
105            vec![
106                vec![5, 1].into_iter(),
107                vec![].into_iter(),
108                vec![3, 2].into_iter(),
109                vec![].into_iter(),
110            ].merge_sort(true)
111                .collect::<Vec<_>>()
112        );
113    }
114
115    #[test]
116    fn not_desc() {
117        assert_eq!(
118            vec![1, 2, 2, 3, 4, 4],
119            vec![
120                vec![2, 4].into_iter(),
121                vec![1, 3].into_iter(),
122                vec![2, 4].into_iter(),
123            ].merge_sort(false)
124                .collect::<Vec<_>>()
125        );
126    }
127
128    #[test]
129    fn infinite_not_desc() {
130        assert_eq!(
131            vec![1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7],
132            vec![(3..), (4..), (1..)]
133                .merge_sort(false)
134                .take(15)
135                .collect::<Vec<_>>()
136        );
137    }
138}
iter_merge_sort/lib.rs

iter_merge_sort/
lib.rs
