iter-merge-sort 0.1.2

イテレーターをマージソート
Documentation 
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<_>>()
        );
    }
}