cp_library_rs/algebraic_structure/
affine1d.rs

1//! 1次元Affine変換
2
3use std::{
4    fmt::Debug,
5    ops::{Add, Mul},
6};
7
8use crate::{algebraic_structure::monoid::Monoid, linear_algrebra::matrix_exp::Matrix};
9
10use num_traits::{One, Zero};
11
12/// 1次元のAffine変換を表す型
13pub type Affine<T> = (T, T);
14
15/// Affine変換の実装
16pub trait AffineTransform<T> {
17    /// 単位元を返す
18    fn id_() -> Self;
19    /// affine変換をマージする
20    /// - `f.compose(g)` = $`f \circ g`$ = $`f(g(x))`$
21    fn compose(&self, rhs: &Self) -> Self;
22    /// スカラ値xに対し，affine変換を適用する
23    fn apply(&self, x: T) -> T;
24    /// affine変換を累乗する
25    fn pow(&self, p: usize) -> Self;
26}
27
28impl<T> AffineTransform<T> for Affine<T>
29where
30    T: Add<Output = T> + Mul<Output = T> + Zero + One + Copy + PartialEq,
31{
32    fn id_() -> Self {
33        (T::one(), T::zero())
34    }
35    fn compose(&self, rhs: &Self) -> Self {
36        let &(a1, b1) = rhs;
37        let &(a2, b2) = self;
38        //   a2 * (a1 * x + b1) + b2
39        // = (a2 * a1) * x + (a2 * b1 + b2)
40        (a2 * a1, a2 * b1 + b2)
41    }
42    fn apply(&self, x: T) -> T {
43        let &(a, b) = self;
44        a * x + b
45    }
46    fn pow(&self, mut p: usize) -> Self {
47        // 繰り返し2乗法
48        let &(a, b) = self;
49        let mut tmp = Matrix([[a, b], [T::zero(), T::one()]]);
50        let mut res = Matrix::id();
51        while p > 0 {
52            if p & 1 == 1 {
53                res = tmp.dot(&res);
54            }
55            tmp = tmp.dot(&tmp);
56            p >>= 1;
57        }
58        (res.0[0][0], res.0[0][1])
59    }
60}
61
62// モノイドの実装
63impl<T> Monoid for Affine<T>
64where
65    T: Clone + Debug,
66    Affine<T>: AffineTransform<T>,
67{
68    type Val = Affine<T>;
69    fn e() -> Self::Val {
70        AffineTransform::id_()
71    }
72    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
73        right.compose(left)
74    }
75}
cp_library_rs/algebraic_structure/affine1d.rs

cp_library_rs/algebraic_structure/
affine1d.rs
