Function nekolib::algo::window_bisect::window_bisect

pub fn window_bisect<S, P>(slice: S, pred: P) -> Vec<usize>where
    S: ElasticSlice + ExpandBack + ShrinkFront + SliceHash<Salt = ()>,
    S::Hashed: Clone,
    P: Fn(S::Hashed) -> bool,

尺取り法で、各始端に対して境界を探す。

スライスと述語を引数に取り、スライスの各始端 $l$ に対して $r_l$ を求める。 $r_l$ は、以下の両方を満たす $r < n$ が存在すればその $r$、存在しなければ $n$ である。 $$P(h([l, r))) \text{ and } \lnot P(h([l, r+1))).$$

ここで、$P$ は pred、$h([l, r))$ は slice.start() == l, slice.end() == r における slice.hash(()) によって計算される。

Requirements

各始端 $l$ に対して、$\lnot P(h([l, m_l)))$ なる $m_l$ が存在するとき、次の二つが成り立つ。

• ${}^\forall i\in [l, m_l)$ について $P(h([l, i)))$
• ${}^\forall i\in (m_l, n)$ について $\lnot P(h([l, i)))$

また、空区間に対しては $P$ は真を返す必要がある¹。

Complexity

expand_back および shrink_front の呼び出しを高々 $n$ 回、 pred の呼び出しを高々 $2n$ 回行う。

Suggestions

Examples を見ての通り、構造体の宣言が大袈裟に感じられる。 一方で、クロージャを渡すような設計でも綺麗にはならないと思われる。

構造体を作るのが冗長に感じる程度の場合には、 これを使わずにインラインで書いてしまう方が楽そうに見えてしまう。

Examples

use nekolib::traits::{ElasticSlice, ExpandBack, ShrinkFront, SliceHash};
use nekolib::algo::window_bisect;

struct RangeSum {
    buf: Vec<i32>,
    start: usize,
    end: usize,
    sum: i32,
}

impl From<Vec<i32>> for RangeSum {
    fn from(buf: Vec<i32>) -> Self {
        Self { buf, start: 0, end: 0, sum: 0 }
    }
}

impl ElasticSlice for RangeSum {
    fn reset(&mut self) {
        self.start = 0;
        self.end = 0;
        self.sum = 0;
    }
    fn full_len(&self) -> usize { self.buf.len() }
    fn start(&self) -> usize { self.start }
    fn end(&self) -> usize { self.end }
}

impl SliceHash for RangeSum {
    type Salt = ();
    type Hashed = i32;
    fn hash(&self, _: ()) -> i32 { self.sum }
}

impl ExpandBack for RangeSum {
    fn expand_back(&mut self) {
        self.sum += self.buf[self.end];
        self.end += 1;
    }
}

impl ShrinkFront for RangeSum {
    fn shrink_front(&mut self) {
        self.sum -= self.buf[self.start];
        self.start += 1;
    }
}

let rs: RangeSum = vec![1, 4, 1, 4, 2, 1, 3, 5, 6].into();
assert_eq!(
    window_bisect(rs, |x| x <= 5),
    vec![2, 3, 4, 4, 6, 7, 7, 8, 8]
);

let rs: RangeSum = vec![6, 2, 5, 2, 3, 2, 1, 1, 1].into();
assert_eq!(
    window_bisect(rs, |x| x <= 4),
    vec![0, 2, 2, 4, 5, 8, 9, 9, 9]
);

---

1. そうでないと、返り値が定義しにくいためである。 $l-1$ や $-1$ が返り値として挙げられるが、後者では 1_usize.wrapping_neg() を使う必要がある上、大小関係がややこしくなり厄介。 ↩