haar_lib/algebra/
dihedral.rs

1//! 二面体群 $D_n$
2//!
3//! # Problems
4//! - <https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0390>
5
6pub use crate::algebra::traits::*;
7
8/// 二面体群$D_n$の元
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum DihedralValue {
11    /// 回転
12    R(usize),
13    /// 鏡映
14    S(usize),
15}
16
17use DihedralValue::{R, S};
18
19/// 二面体群$D_n$
20#[derive(Clone, Copy, Debug)]
21pub struct Dihedral {
22    n: usize,
23    value: DihedralValue,
24}
25
26impl PartialEq for Dihedral {
27    fn eq(&self, other: &Self) -> bool {
28        match (self, other) {
29            (Self { n: 0, value: R(0) }, Self { value: R(0), .. }) => true,
30            (Self { value: R(0), .. }, Self { n: 0, value: R(0) }) => true,
31            _ => self.n == other.n && self.value == other.value,
32        }
33    }
34}
35
36impl Dihedral {
37    fn _op(a: Self, b: Self) -> Self {
38        match (a.n, b.n) {
39            (0, _) => return b,
40            (_, 0) => return a,
41            _ => {}
42        }
43
44        let n = a.n;
45        assert_eq!(b.n, a.n);
46
47        let value = match (a.value, b.value) {
48            (R(x), R(y)) => R((x + y) % n),
49            (R(x), S(y)) => S((n + y - x) % n),
50            (S(x), R(y)) => S((x + y) % n),
51            (S(x), S(y)) => R((n + y - x) % n),
52        };
53
54        Self { n, value }
55    }
56
57    /// $D_n$の回転を表す元$R_i$を返す。
58    pub fn r(i: usize, n: usize) -> Self {
59        assert!(n > 0);
60        assert!(i < n);
61        Self { n, value: R(i) }
62    }
63
64    /// $D_n$の鏡映を表す元$S_i$を返す。
65    pub fn s(i: usize, n: usize) -> Self {
66        assert!(n > 0);
67        assert!(i < n);
68        Self { n, value: S(i) }
69    }
70}
71
72impl Set for Dihedral {}
73
74impl BinaryOp for Dihedral {
75    fn op(self, b: Self) -> Self {
76        Dihedral::_op(self, b)
77    }
78}
79
80impl Identity for Dihedral {
81    fn id() -> Self {
82        Self { n: 0, value: R(0) }
83    }
84}
85
86impl Inverse for Dihedral {
87    fn inv(self) -> Self {
88        let Self { n, value } = self;
89        let value = if n != 0 {
90            match value {
91                R(x) => R(if x == 0 { 0 } else { n - x }),
92                S(_) => value,
93            }
94        } else {
95            value
96        };
97        Self { n, value }
98    }
99}
100
101impl Associative for Dihedral {}
haar_lib/algebra/dihedral.rs

haar_lib/algebra/
dihedral.rs
