haar_lib/algebra/semiring/
min_add.rs

1//! MinとAddの半環
2pub use crate::algebra::semiring::*;
3use std::marker::PhantomData;
4
5/// MinとAddの半環
6#[derive(Clone, Copy, Default, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
7pub struct MinAdd<T>(PhantomData<T>);
8impl<T> MinAdd<T> {
9    /// [`MinAdd`]を返す。
10    pub fn new() -> Self {
11        Self(PhantomData)
12    }
13}
14
15macro_rules! impl_semiring {
16    ($($t:ty),*) => {
17        $(impl Semiring for MinAdd<$t> {
18            type Element = Option<$t>;
19            fn zero(&self) -> Self::Element {
20                None // inf
21            }
22            fn one(&self) -> Self::Element {
23                Some(0)
24            }
25            fn add(&self, a: Self::Element, b: Self::Element) -> Self::Element {
26                match (a, b) {
27                    (Some(a), Some(b)) => Some(a.min(b)),
28                    (None, b) => b,
29                    (a, None) => a
30                }
31            }
32            fn mul(&self, a: Self::Element, b: Self::Element) -> Self::Element {
33                a.zip(b).map(|(a, b)| a + b)
34            }
35            fn times(&self, a: Self::Element, n: u64) -> Self::Element {
36                if n == 0 { None } else { a }
37            }
38        })*
39    };
40}
41
42impl_semiring!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);
haar_lib/algebra/semiring/min_add.rs

haar_lib/algebra/semiring/
min_add.rs
