cp_library_rs/algebraic_structure/
actedmonoid_with_size.rs

1//! 長さを保持した作用付きモノイド
2
3use std::ops::{Add, Mul};
4
5use num::{Bounded, FromPrimitive, Zero};
6
7use crate::algebraic_structure::{
8    actedmonoid::{
9        examples::{AddMin, AddSum, UpdateMax, UpdateMin, UpdateMinMax, UpdateSum},
10        ActedMonoid,
11    },
12    monoid::Monoid,
13    to_acted::ToActed,
14};
15
16/// 長さを保持した作用付きモノイド
17pub trait ActedMonoidWithSize: ActedMonoid {
18    /// 区間長 `size` の「単位区間」を表す集約値を返す
19    ///
20    /// 例：`Val = (sum, size)` のとき，`e_with_size(size) = (0, size)` のようなもの
21    #[inline]
22    fn e_with_size(_size: usize) -> Self::Val {
23        Self::e()
24    }
25}
26
27// ========== 区間加算，区間更新 + 区間和系の作用付きモノイドに実装 ==========
28impl<T> ActedMonoidWithSize for AddSum<T>
29where
30    T: Zero + Clone + Add<Output = T> + Mul<Output = T> + FromPrimitive + PartialEq,
31{
32    fn e_with_size(size: usize) -> Self::Val {
33        (T::zero(), size)
34    }
35}
36
37impl<T> ActedMonoidWithSize for UpdateSum<T>
38where
39    T: Zero + Clone + Add<Output = T> + Mul<Output = T> + FromPrimitive + PartialEq,
40{
41    fn e_with_size(size: usize) -> Self::Val {
42        (T::zero(), size)
43    }
44}
45
46// ========== その他の作用付きモノイドに実装 ==========
47impl<M> ActedMonoidWithSize for ToActed<M>
48where
49    M: Monoid,
50    M::Val: PartialEq,
51{
52}
53impl<T: Bounded + Ord + Clone> ActedMonoidWithSize for UpdateMin<T> {}
54impl<T: Bounded + Ord + Clone> ActedMonoidWithSize for UpdateMax<T> {}
55impl<T: Bounded + Ord + Clone> ActedMonoidWithSize for UpdateMinMax<T> {}
56impl<T> ActedMonoidWithSize for AddMin<T> where T: Zero + Clone + Add<Output = T> + Ord + Bounded {}
cp_library_rs/algebraic_structure/actedmonoid_with_size.rs

cp_library_rs/algebraic_structure/
actedmonoid_with_size.rs
