Trait FoldBisectRev 

pub trait FoldBisectRev: Fold<Range<usize>> {
    // Required method
    fn fold_bisect_rev<F>(
        &self,
        r: usize,
        pred: F,
    ) -> (usize, <Self::Output as Magma>::Set)
       where F: Fn(&<Self::Output as Magma>::Set) -> bool;
}

右端を固定したときの境界を求める。

Required Methods

fn fold_bisect_rev<F>( &self, r: usize, pred: F, ) -> (usize, <Self::Output as Magma>::Set)

where F: Fn(&<Self::Output as Magma>::Set) -> bool,

添字 r と述語 pred を引数に取り、次の条件を満たす l を返す。

• pred(&self.fold(l..r))
• l == 0 || !pred(&self.fold(l - 1..r))

Requirements

対象のモノイドの単位元を e とするとき、pred(e) が成り立つ。

Examples

use nekolib::ds::VecSegtree;
use nekolib::traits::{Fold, FoldBisectRev};
use nekolib::utils::OpAdd;

let vs: VecSegtree<OpAdd<i32>> = vec![2, 4, 1, 3, 5].into();

assert_eq!(vs.fold(..), 15);
assert_eq!(vs.fold_bisect_rev(5, |&x| x <= 0), (5_usize, 0));
assert_eq!(vs.fold_bisect_rev(5, |&x| x < 15), (1_usize, 13));
assert_eq!(vs.fold_bisect_rev(5, |&x| x <= 15), (0_usize, 15));

let r = 5;
let pred = |&x: &i32| x <= 12;
let (l, x) = vs.fold_bisect_rev(r, pred);
assert_eq!(vs.fold(l..r), x);
assert!(pred(&x));
assert!(l == 0 || !pred(&vs.fold(l - 1..r)));

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<A> FoldBisectRev for VecActSegtree<A>

where A: MonoidAction, <A::Operator as Magma>::Set: Clone, <A::Operand as Magma>::Set: Clone,

impl<M> FoldBisectRev for VecSegtree<M>

where M: Monoid, M::Set: Clone,