Trait contest_algorithms::range_query::specs::ArqSpec

pub trait ArqSpec {
    type S: Clone;
    type F: Clone;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn identity() -> Self::S;
    fn compose(f: &Self::F, g: &Self::F) -> Self::F;
    fn apply(f: &Self::F, a: &Self::S, size: i64) -> Self::S;
}

Associated Types

type S: Clone

Type of underlying array elements.

type F: Clone

Type of data representing an endomorphism.

Loading content...

Required methods

fn op(a: &Self::S, b: &Self::S) -> Self::S

Must satisfy the Associative Law: For all a,b,c, op(a, op(b, c)) = op(op(a, b), c)

fn identity() -> Self::S

Must satisfy the Identity Law: For all a, op(a, identity()) = op(identity(), a) = a

fn compose(f: &Self::F, g: &Self::F) -> Self::F

Must satisfy the Composition Law: For all f,g,a, apply(compose(f, g), a) = apply(f, apply(g, a))

fn apply(f: &Self::F, a: &Self::S, size: i64) -> Self::S

Must satisfy the Distributive Law: For all f,a,b, apply(f, op(a, b), s+t) = op(apply(f, a, s), apply(f, b, t)) The size parameter makes this law easier to satisfy in certain cases.

Loading content...

Implementors

impl ArqSpec for AssignMin

type S = i64

type F = i64

fn op(a: &Self::S, b: &Self::S) -> Self::S

fn identity() -> Self::S

fn compose(f: &Self::F, _: &Self::F) -> Self::F

fn apply(f: &Self::F, _: &Self::S, _: i64) -> Self::S

impl ArqSpec for AssignSum

type S = i64

type F = i64

fn op(a: &Self::S, b: &Self::S) -> Self::S

fn identity() -> Self::S

fn compose(f: &Self::F, _: &Self::F) -> Self::F

fn apply(f: &Self::F, _: &Self::S, size: i64) -> Self::S

impl ArqSpec for SupplyDemand

type S = (i64, i64, i64)

type F = (i64, i64)

fn op((p1, o1, s1): &Self::S, (p2, o2, s2): &Self::S) -> Self::S

fn identity() -> Self::S

fn compose(_: &Self::F, _: &Self::F) -> Self::F

fn apply((p_add, o_add): &Self::F, (p, o, _): &Self::S, s: i64) -> Self::S

Loading content...