sliding_window/
lib.rs

1use std::collections::VecDeque;
2
3/// 幅 `window_width` の区間すべてに対し最小値を求めます。
4///
5/// 配列 `a` に対し次で定める配列 `b` を求めます。
6///
7/// - `a` の長さ `a.len()` を `n` とする
8/// - `b[0]`: `min(a[0], a[1], ..., a[window_width - 1])`
9/// - `b[1]`: `min(a[1], a[2], ..., a[window_width])`
10/// - ...
11/// - `b[n - window_width]`: `min(a[n - window_width], ..., a[n - 2], a[n - 1])`
12///
13/// [実装の参考資料](https://qiita.com/kuuso1/items/318d42cd089a49eeb332)
14///
15/// # Panics
16///
17/// if `window_width` is zero or is greater than `a.len()`.
18///
19/// # Examples
20///
21/// ```
22/// use sliding_window::sliding_window_minimum;
23///
24/// let a = vec![4, 7, 7, 8, 5, 7, 6, 9, 9, 2, 8, 3];
25/// let minimums = sliding_window_minimum(&a, 6);
26/// assert_eq!(
27///     minimums,
28///     vec![
29///         &4, // 4 7 7 8 5 7
30///         &5, //   7 7 8 5 7 6
31///         &5, //     7 8 5 7 6 9
32///         &5, //       8 5 7 6 9 9
33///         &2, //         5 7 6 9 9 2
34///         &2, //           7 6 9 9 2 8
35///         &2, //             6 9 9 2 8 3
36///     ]
37/// );
38/// ```
39pub fn sliding_window_minimum<T>(a: &[T], window_width: usize) -> Vec<&T>
40where
41    T: Ord,
42{
43    sliding_window(a, window_width, |last, new| last >= new)
44}
45
46/// [`sliding_window_minimum`](fn.sliding_window_minimum.html) の最大値バージョンです。
47pub fn sliding_window_maximum<T>(a: &[T], window_width: usize) -> Vec<&T>
48where
49    T: Ord,
50{
51    sliding_window(a, window_width, |last, new| last <= new)
52}
53
54fn sliding_window<T, F>(a: &[T], window_width: usize, pop_back_cond: F) -> Vec<&T>
55where
56    T: Ord,
57    F: Fn(&T, &T) -> bool, // (last, new)
58{
59    assert!(0 < window_width && window_width <= a.len());
60    let mut result = Vec::new();
61    let mut positions: VecDeque<usize> = VecDeque::new();
62    for (i, v) in a.iter().enumerate() {
63        while let Some(last) = positions.back().copied() {
64            if pop_back_cond(&a[last], v) {
65                positions.pop_back();
66            } else {
67                break;
68            }
69        }
70        positions.push_back(i);
71        if i >= window_width - 1 {
72            let p = positions.front().copied().unwrap();
73            result.push(&a[p]);
74            if p == i - (window_width - 1) {
75                positions.pop_front();
76            }
77        }
78    }
79    result
80}
81
82#[cfg(test)]
83mod tests {
84    use crate::{sliding_window_maximum, sliding_window_minimum};
85
86    #[test]
87    fn test_min() {
88        let a = vec![2, 2, 3, 6, 0, 6, 7, 9, 7, 7, 4, 9];
89        assert_eq!(
90            sliding_window_minimum(&a, 4),
91            vec![
92                &2, // 2 2 3 6
93                &0, //   2 3 6 0
94                &0, //     3 6 0 6
95                &0, //       6 0 6 7
96                &0, //         0 6 7 9
97                &6, //           6 7 9 7
98                &7, //             7 9 7 7
99                &4, //               9 7 7 4
100                &4, //                 7 7 4 9
101            ]
102        );
103
104        assert_eq!(sliding_window_minimum(&a, 1), a.iter().collect::<Vec<_>>());
105
106        assert_eq!(
107            sliding_window_minimum(&a, a.len()),
108            vec![a.iter().min().unwrap()],
109        );
110    }
111
112    #[test]
113    fn test_max() {
114        let a = vec![2, 2, 3, 6, 0, 6, 7, 9, 7, 7, 4, 9];
115        assert_eq!(
116            sliding_window_maximum(&a, 4),
117            vec![
118                &6, // 2 2 3 6
119                &6, //   2 3 6 0
120                &6, //     3 6 0 6
121                &7, //       6 0 6 7
122                &9, //         0 6 7 9
123                &9, //           6 7 9 7
124                &9, //             7 9 7 7
125                &9, //               9 7 7 4
126                &9, //                 7 7 4 9
127            ]
128        );
129
130        assert_eq!(sliding_window_maximum(&a, 1), a.iter().collect::<Vec<_>>());
131
132        assert_eq!(
133            sliding_window_maximum(&a, a.len()),
134            vec![a.iter().max().unwrap()],
135        );
136    }
137
138    #[test]
139    #[should_panic]
140    fn test_empty_0() {
141        assert!(sliding_window_minimum::<u32>(&[], 0).is_empty());
142    }
143
144    #[test]
145    #[should_panic]
146    fn test_empty_1() {
147        assert!(sliding_window_minimum::<u32>(&[], 1).is_empty());
148    }
149}
sliding_window/lib.rs

sliding_window/
lib.rs
