Trait contest_algorithms::arq_tree::ArqSpec

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

Associated Types

type F

Type of data representing an endomorphism.

type M

Type of monoid elements.

Loading content...

Required methods

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

For eager updates, compose() ho be unimplemented!(). For lazy updates: Require for all f,g,a: apply(compose(f, g), a) = apply(f, apply(g, a))

fn apply(f: &Self::F, a: &Self::M) -> Self::M

For eager updates, apply() can assume to act on a leaf. For lazy updates: Require for all f,a,b: apply(f, op(a, b)) = op(apply(f, a), apply(f, b))

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

Require for all a,b,c: op(a, op(b, c)) = op(op(a, b), c)

fn identity() -> Self::M

Require for all a: op(a, identity()) = op(identity(), a) = a

Loading content...

Implementors

impl ArqSpec for AssignMin

type F = i64

type M = i64

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

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

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

fn identity() -> Self::M

impl ArqSpec for AssignSum

type F = i64

type M = (i64, i64)

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

fn apply(f: &Self::F, (_, s): &Self::M) -> Self::M

fn op((a, s): &Self::M, (b, t): &Self::M) -> Self::M

fn identity() -> Self::M

impl ArqSpec for SupplyDemand

type F = (i64, i64)

type M = (i64, i64, i64)

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

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

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

fn identity() -> Self::M

Loading content...