dsalgo 0.2.6

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

pub struct Additive;
pub struct Multiplicative;

pub trait Identity<S = Self, T = Additive> {
    fn identity() -> S;
}

pub trait BinaryOperation<S = Self, T = Additive> {
    fn operate(_: &S, _: &S) -> S;
}

pub trait Inverse<S = Self, T = Additive> {
    fn invert(_: &S) -> S;
}

pub trait Idempotent<S = Self, T = Additive> {}

pub trait Commutative<S = Self, T = Additive> {}

pub trait Semigroup<S = Self, T = Additive>: BinaryOperation<S, T> {}
impl<S, T, U: BinaryOperation<S, T>> Semigroup<S, T> for U {}

pub trait Monoid<S = Self, T = Additive>:
    Semigroup<S, T> + Identity<S, T>
{
}
impl<S, T, U: Semigroup<S, T> + Identity<S, T>> Monoid<S, T> for U {}

pub trait Group<S = Self, T = Additive>: Monoid<S, T> + Inverse<S, T> {}
impl<S, T, U: Monoid<S, T> + Inverse<S, T>> Group<S, T> for U {}

pub trait AbelianGroup<S = Self, T = Additive>:
    Group<S, T> + Commutative<S, T>
{
}
impl<S, T, U: Group<S, T> + Commutative<S, T>> AbelianGroup<S, T> for U {}

pub trait Semiring<S = Self, Add = Additive, Mul = Multiplicative>:
    Monoid<S, Add> + Monoid<S, Mul> + Commutative<S, Add>
{
}
impl<S, Add, Mul, U> Semiring<S, Add, Mul> for U where
    U: Monoid<S, Add> + Monoid<S, Mul> + Commutative<S, Add>
{
}

pub trait Ring<S = Self, Add = Additive, Mul = Multiplicative>:
    Semiring<S, Add, Mul> + Inverse<S, Add>
{
}
impl<S, Add, Mul, U> Ring<S, Add, Mul> for U where
    U: Semiring<S, Add, Mul> + Inverse<S, Add>
{
}

pub trait Default<S = Self, T = Additive> {
    fn default() -> S;
}

#[cfg(test)]
mod tests {
    // struct ExampleSemiring<S>(std::marker::PhantomData<S>);
    struct UsizeAddMul;

    impl super::Identity<usize, super::Additive> for UsizeAddMul {
        fn identity() -> usize { 0 }
    }

    impl super::Identity<usize, super::Multiplicative> for UsizeAddMul {
        fn identity() -> usize { 1 }
    }

    impl super::BinaryOperation<usize, super::Additive> for UsizeAddMul {
        fn operate(a: &usize, b: &usize) -> usize { a + b }
    }

    impl super::BinaryOperation<usize, super::Multiplicative> for UsizeAddMul {
        fn operate(a: &usize, b: &usize) -> usize { a * b }
    }

    impl super::Commutative<usize, super::Additive> for UsizeAddMul {}

    fn need_semiring<S, Add, Mul, U>()
    where
        U: super::Semiring<S, Add, Mul>,
        S: std::fmt::Debug + PartialEq,
    {
        let add_e = <U as super::Identity<S, Add>>::identity();
        let value_add =
            <U as super::BinaryOperation<S, Add>>::operate(&add_e, &add_e);
        assert_eq!(value_add, add_e);

        let mul_e = <U as super::Identity<S, Mul>>::identity();
        let value_mul =
            <U as super::BinaryOperation<S, Mul>>::operate(&mul_e, &mul_e);
        assert_eq!(value_mul, mul_e);
        eprintln!("{:?}", value_add);
    }

    #[test]
    fn test() {
        need_semiring::<
            usize,
            super::Additive,
            super::Multiplicative,
            UsizeAddMul,
        >();
    }
}