permutation_rs/group/
tree.rs

1//! In order to cut down on exponential growth of words when forming products
2//! we are creating the structure of a calculation. When actual calculations
3//! need to be done, we can use a morphism to determine the result.
4//!
5//! # Examples
6//! Below you find an example of how an `SLP` can be used.
7//!
8//! ```rust
9//! # #[macro_use] extern crate permutation_rs;
10//! # use std::collections::HashMap;
11//! # use permutation_rs::group::{GroupElement, Morphism};
12//! # use permutation_rs::group::tree::SLP;
13//! # use permutation_rs::group::free::Word;
14//! # fn main() {
15//! let left = SLP::Generator(0);
16//! let right = SLP::Generator(1);
17//! let expression = left.times(&right.inverse());
18//!
19//! let morphism = morphism!(
20//!     0, 'a',
21//!     1, 'b');
22//!
23//! let word = expression.transform(&morphism);
24//!
25//! let expected = Word::new(vec![('a', 1), ('b', -1)]);
26//!
27//! assert_eq!(word, expected);
28//! # }
29//! ```
30
31use std::fmt;
32use std::fmt::Display;
33use super::{GroupElement, Morphism};
34use super::free::Word;
35
36/// Single Line Program (SLP) references various elements to form a expression
37/// That can be evaluated to actual group elements.
38#[derive(Debug, PartialEq, Eq, Hash, Clone)]
39pub enum SLP {
40    /// The identity element of a SLP.
41    Identity,
42    /// A generator, indexed by an integer.
43    Generator(u64),
44    /// Product of two SLPs.
45    Product(Box<SLP>, Box<SLP>),
46    /// Inverse of a SLP.
47    Inverse(Box<SLP>),
48}
49
50impl SLP {
51    /// Map the `SLP` in to a `Word` according to the `Morphism`.
52    pub fn transform(&self, morphism: &Morphism<SLP, Word>) -> Word {
53        match *self {
54            SLP::Identity => Word::identity(),
55            ref g @ SLP::Generator(_) => morphism.transform(&g),
56            SLP::Product(ref left, ref right) => (*left).transform(&morphism).times(&(*right).transform(&morphism)),
57            SLP::Inverse(ref g) => (*g).transform(&morphism).inverse(),
58        }
59    }
60}
61
62impl GroupElement for SLP {
63    fn is_identity(&self) -> bool {
64        match *self {
65            SLP::Identity => true,
66            _ => false,
67        }
68    }
69
70    fn times(&self, multiplicant: &SLP) -> SLP {
71        let left: SLP = self.clone();
72        let right: SLP = multiplicant.clone();
73        SLP::Product(Box::new(left), Box::new(right))
74    }
75
76    fn inverse(&self) -> SLP {
77        SLP::Inverse(Box::new(self.clone()))
78    }
79}
80
81impl Display for SLP {
82    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
83        match *self {
84            SLP::Identity => write!(f, "Id"),
85            SLP::Generator(n) => write!(f, "G_{}", n),
86            SLP::Product(ref left, ref right) => write!(f, "({}) * ({})", left, right),
87            SLP::Inverse(ref term) => write!(f, "({})^-1", term),
88        }
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::super::GroupElement;
95    use super::*;
96
97    #[test]
98    fn slp_should_know_when_it_is_the_identity() {
99        let not_identity = SLP::Generator(1);
100
101        assert!(!not_identity.is_identity());
102
103        let identity = SLP::Identity;
104
105        assert!(identity.is_identity());
106    }
107
108    #[test]
109    fn multiplication_should_be_from_left_to_right() {
110        let first = SLP::Generator(1);
111
112        let second = SLP::Generator(2);
113
114        let product = first.times(&second);
115
116        let expected = SLP::Product(Box::new(first), Box::new(second));
117
118        assert_eq!(product, expected);
119    }
120
121    #[test]
122    fn inverse_should_multiply_to_identity() {
123        let first = SLP::Generator(1);
124
125        let inverse = first.inverse();
126
127        let expected = SLP::Inverse(Box::new(first));
128
129        assert_eq!(inverse, expected);
130    }
131
132    #[test]
133    fn should_display_correctly() {
134        let identity = SLP::Identity;
135        let generator = SLP::Generator(1);
136        let product = SLP::Product(
137            Box::new(SLP::Generator(1)),
138            Box::new(SLP::Generator(2)));
139        let inverse = SLP::Inverse(Box::new(SLP::Generator(1)));
140
141
142        assert_eq!("Id", format!("{}", identity));
143        assert_eq!("G_1", format!("{}", generator));
144        assert_eq!("(G_1) * (G_2)", format!("{}", product));
145        assert_eq!("(G_1)^-1", format!("{}",  inverse));
146    }
147}
permutation_rs/group/tree.rs

permutation_rs/group/
tree.rs
