nekolib/algo/
window_bisect.rs

1//! 尺取り法。
2
3use super::super::traits::elastic_slice;
4
5use elastic_slice::{ElasticSlice, ExpandBack, ShrinkFront, SliceHash};
6
7/// 尺取り法で、各始端に対して境界を探す。
8///
9/// スライスと述語を引数に取り、スライスの各始端 $l$ に対して $r\_l$ を求める。
10/// $r\_l$ は、以下の両方を満たす $r < n$ が存在すればその $r$、存在しなければ $n$ である。
11/// $$ P(h([l, r))) \\text{ and } \\lnot P(h([l, r+1))). $$
12///
13/// ここで、$P$ は `pred`、$h([l, r))$ は `slice.start() == l`, `slice.end() == r`
14/// における `slice.hash(())` によって計算される。
15///
16/// # Requirements
17/// 各始端 $l$ に対して、$\\lnot P(h([l, m\_l)))$ なる $m\_l$
18/// が存在するとき、次の二つが成り立つ。
19/// - ${}^\\forall i\\in [l, m\_l)$ について $P(h([l, i)))$
20/// - ${}^\\forall i\\in (m\_l, n)$ について $\\lnot P(h([l, i)))$
21///
22/// また、空区間に対しては $P$ は真を返す必要がある[^1]。
23///
24/// [^1]: そうでないと、返り値が定義しにくいためである。
25/// $l-1$ や $-1$ が返り値として挙げられるが、後者では
26/// `1_usize.wrapping_neg()` を使う必要がある上、大小関係がややこしくなり厄介。
27///
28/// # Complexity
29/// `expand_back` および `shrink_front` の呼び出しを高々 $n$ 回、
30/// `pred` の呼び出しを高々 $2n$ 回行う。
31///
32/// # Suggestions
33/// [Examples] を見ての通り、構造体の宣言が大袈裟に感じられる。
34/// 一方で、クロージャを渡すような設計でも綺麗にはならないと思われる。
35///
36/// 構造体を作るのが冗長に感じる程度の場合には、
37/// これを使わずにインラインで書いてしまう方が楽そうに見えてしまう。
38///
39/// [Examples]: #examples
40///
41/// # Examples
42/// ```
43/// use nekolib::traits::{ElasticSlice, ExpandBack, ShrinkFront, SliceHash};
44/// use nekolib::algo::window_bisect;
45///
46/// struct RangeSum {
47///     buf: Vec<i32>,
48///     start: usize,
49///     end: usize,
50///     sum: i32,
51/// }
52///
53/// impl From<Vec<i32>> for RangeSum {
54///     fn from(buf: Vec<i32>) -> Self {
55///         Self { buf, start: 0, end: 0, sum: 0 }
56///     }
57/// }
58///
59/// impl ElasticSlice for RangeSum {
60///     fn reset(&mut self) {
61///         self.start = 0;
62///         self.end = 0;
63///         self.sum = 0;
64///     }
65///     fn full_len(&self) -> usize { self.buf.len() }
66///     fn start(&self) -> usize { self.start }
67///     fn end(&self) -> usize { self.end }
68/// }
69///
70/// impl SliceHash for RangeSum {
71///     type Salt = ();
72///     type Hashed = i32;
73///     fn hash(&self, _: ()) -> i32 { self.sum }
74/// }
75///
76/// impl ExpandBack for RangeSum {
77///     fn expand_back(&mut self) {
78///         self.sum += self.buf[self.end];
79///         self.end += 1;
80///     }
81/// }
82///
83/// impl ShrinkFront for RangeSum {
84///     fn shrink_front(&mut self) {
85///         self.sum -= self.buf[self.start];
86///         self.start += 1;
87///     }
88/// }
89///
90/// let rs: RangeSum = vec![1, 4, 1, 4, 2, 1, 3, 5, 6].into();
91/// assert_eq!(
92///     window_bisect(rs, |x| x <= 5),
93///     vec![2, 3, 4, 4, 6, 7, 7, 8, 8]
94/// );
95///
96/// let rs: RangeSum = vec![6, 2, 5, 2, 3, 2, 1, 1, 1].into();
97/// assert_eq!(
98///     window_bisect(rs, |x| x <= 4),
99///     vec![0, 2, 2, 4, 5, 8, 9, 9, 9]
100/// );
101/// ```
102pub fn window_bisect<S, P>(mut slice: S, pred: P) -> Vec<usize>
103where
104    S: ElasticSlice + ExpandBack + ShrinkFront + SliceHash<Salt = ()>,
105    S::Hashed: Clone,
106    P: Fn(S::Hashed) -> bool,
107{
108    slice.reset();
109    let n = slice.full_len();
110    let mut res = vec![n; n];
111    for l in 0..n {
112        loop {
113            let o = slice.hash(());
114            if !pred(o) {
115                res[l] = slice.end() - 1;
116                break;
117            }
118            if slice.end() == n {
119                return res;
120            }
121            slice.expand_back();
122        }
123        slice.shrink_front();
124    }
125    res
126}
nekolib/algo/window_bisect.rs

nekolib/algo/
window_bisect.rs
