cp_library_rs/algebraic_structure/
semilattice.rs

1//! 半束
2
3use std::ops::Rem;
4
5use crate::algebraic_structure::operation::{Max, Min, GCD};
6
7use num_traits::{Bounded, Zero};
8
9/// 半束
10///
11/// - 単位元をもち，可環かつ冪等な2項演算
12pub trait Semilattice {
13    /// 元の型
14    type Val: Clone;
15    /// 単位元
16    fn id() -> Self::Val;
17    /// 可換かつ冪等な二項演算
18    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val;
19}
20
21// ========== 実装 ==========
22impl<T: Ord + Bounded + Clone> Semilattice for Min<T> {
23    type Val = T;
24    fn id() -> Self::Val {
25        T::max_value()
26    }
27    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
28        x.min(y).clone()
29    }
30}
31
32impl<T: Ord + Bounded + Clone> Semilattice for Max<T> {
33    type Val = T;
34    fn id() -> Self::Val {
35        T::max_value()
36    }
37    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
38        x.max(y).clone()
39    }
40}
41
42impl<T: Zero + Rem<T>> Semilattice for GCD<T> {
43    type Val = usize;
44    fn id() -> Self::Val {
45        0
46    }
47    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
48        GCD::gcd(x, y)
49    }
50}

cp_library_rs/algebraic_structure/semilattice.rs

cp_library_rs/algebraic_structure/
semilattice.rs