1 extern crate alga;
2 #[macro_use]
3 extern crate alga_derive;
4 #[macro_use]
5 extern crate approx;
6 extern crate quickcheck;
7
8 use std::fmt::{Display, Error, Formatter};
9
10 use alga::general::wrapper::Wrapper as W;
11 use alga::general::*;
12
13 use approx::{AbsDiffEq, RelativeEq, UlpsEq};
14
15 use quickcheck::{Arbitrary, Gen};
16
17 #[derive(Alga, PartialEq, Clone, Debug)]
18 #[alga_traits(GroupAbelian(Additive), Where = "Scalar: AbstractField")]
19 #[alga_quickcheck(check(Rational))]
20 struct Vec2<Scalar> {
21 x: Scalar,
22 y: Scalar,
23 }
24
25 impl<Scalar: AbstractField + Arbitrary> Arbitrary for Vec2<Scalar> {
arbitrary<G: Gen>(g: &mut G) -> Self26 fn arbitrary<G: Gen>(g: &mut G) -> Self {
27 Vec2::new(Scalar::arbitrary(g), Scalar::arbitrary(g))
28 }
29
shrink(&self) -> Box<dyn Iterator<Item = Self>>30 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
31 Box::new(
32 self.x
33 .shrink()
34 .zip(self.y.shrink())
35 .map(|(x, y)| Vec2::new(x, y)),
36 )
37 }
38 }
39
40 impl<Scalar: AbstractField> Vec2<Scalar> {
new(x: Scalar, y: Scalar) -> Vec2<Scalar>41 fn new(x: Scalar, y: Scalar) -> Vec2<Scalar> {
42 Vec2 { x: x, y: y }
43 }
44 }
45
46 impl<Scalar: AbstractField + Display> Display for Vec2<Scalar> {
fmt(&self, fmt: &mut Formatter) -> Result<(), Error>47 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
48 fmt.write_fmt(format_args!("({}, {})", self.x, self.y))
49 }
50 }
51
52 impl<Scalar: AbstractField + AbsDiffEq> AbsDiffEq for Vec2<Scalar>
53 where
54 Scalar::Epsilon: Clone,
55 {
56 type Epsilon = Scalar::Epsilon;
57
default_epsilon() -> Self::Epsilon58 fn default_epsilon() -> Self::Epsilon {
59 Scalar::default_epsilon()
60 }
61
abs_diff_eq(&self, other: &Self, epsilon: Self::Epsilon) -> bool62 fn abs_diff_eq(&self, other: &Self, epsilon: Self::Epsilon) -> bool {
63 self.x.abs_diff_eq(&other.x, epsilon.clone()) && self.y.abs_diff_eq(&other.y, epsilon)
64 }
65 }
66
67 impl<Scalar: AbstractField + RelativeEq> RelativeEq for Vec2<Scalar>
68 where
69 Scalar::Epsilon: Clone,
70 {
default_max_relative() -> Self::Epsilon71 fn default_max_relative() -> Self::Epsilon {
72 Scalar::default_max_relative()
73 }
74
relative_eq( &self, other: &Self, epsilon: Self::Epsilon, max_relative: Self::Epsilon, ) -> bool75 fn relative_eq(
76 &self,
77 other: &Self,
78 epsilon: Self::Epsilon,
79 max_relative: Self::Epsilon,
80 ) -> bool {
81 self.x
82 .relative_eq(&other.x, epsilon.clone(), max_relative.clone())
83 && self.y.relative_eq(&other.y, epsilon, max_relative)
84 }
85 }
86
87 impl<Scalar: AbstractField + UlpsEq> UlpsEq for Vec2<Scalar>
88 where
89 Scalar::Epsilon: Clone,
90 {
default_max_ulps() -> u3291 fn default_max_ulps() -> u32 {
92 Scalar::default_max_ulps()
93 }
94
ulps_eq(&self, other: &Self, epsilon: Self::Epsilon, max_ulps: u32) -> bool95 fn ulps_eq(&self, other: &Self, epsilon: Self::Epsilon, max_ulps: u32) -> bool {
96 self.x.ulps_eq(&other.x, epsilon.clone(), max_ulps)
97 && self.y.ulps_eq(&other.y, epsilon, max_ulps)
98 }
99 }
100
101 impl<Scalar: AbstractField> AbstractMagma<Additive> for Vec2<Scalar> {
operate(&self, lhs: &Self) -> Self102 fn operate(&self, lhs: &Self) -> Self {
103 Vec2::new(self.x.op(Additive, &lhs.x), self.y.op(Additive, &lhs.y))
104 }
105 }
106
107 impl<Scalar: AbstractField> TwoSidedInverse<Additive> for Vec2<Scalar> {
two_sided_inverse(&self) -> Self108 fn two_sided_inverse(&self) -> Self {
109 Vec2::new(
110 TwoSidedInverse::<Additive>::two_sided_inverse(&self.x),
111 TwoSidedInverse::<Additive>::two_sided_inverse(&self.y),
112 )
113 }
114 }
115
116 impl<Scalar: AbstractField> Identity<Additive> for Vec2<Scalar> {
identity() -> Self117 fn identity() -> Self {
118 Vec2 {
119 x: Identity::<Additive>::identity(),
120 y: Identity::<Additive>::identity(),
121 }
122 }
123 }
124
125 impl<Scalar: AbstractField> AbstractModule for Vec2<Scalar> {
126 type AbstractRing = Scalar;
multiply_by(&self, r: Self::AbstractRing) -> Self127 fn multiply_by(&self, r: Self::AbstractRing) -> Self {
128 self.op(Multiplicative, &Vec2::new(r.clone(), r))
129 }
130 }
131
132 impl<Scalar: AbstractField> AbstractMagma<Multiplicative> for Vec2<Scalar> {
operate(&self, lhs: &Self) -> Self133 fn operate(&self, lhs: &Self) -> Self {
134 Vec2::new(
135 self.x.op(Multiplicative, &lhs.x),
136 self.y.op(Multiplicative, &lhs.y),
137 )
138 }
139 }
140
141 impl<Scalar: AbstractField> Identity<Multiplicative> for Vec2<Scalar> {
identity() -> Self142 fn identity() -> Self {
143 Vec2 {
144 x: Identity::<Multiplicative>::identity(),
145 y: Identity::<Multiplicative>::identity(),
146 }
147 }
148 }
149
gcd<T: AbstractRingCommutative + PartialOrd>(a: T, b: T) -> T150 fn gcd<T: AbstractRingCommutative + PartialOrd>(a: T, b: T) -> T {
151 let (mut a, mut b) = (W::<_, _, Multiplicative>::new(a), W::new(b));
152 let zero = W::new(Identity::<Additive>::identity());
153 if a < zero {
154 a = -a;
155 }
156 if b < zero {
157 b = -b;
158 }
159 if a == zero {
160 if b == zero {
161 return zero.val;
162 }
163 return b.val;
164 }
165 if b == zero {
166 return a.val;
167 }
168 while a != b {
169 if a > b {
170 a = a - b.clone();
171 } else {
172 b = b - a.clone();
173 }
174 }
175 a.val
176 }
177
178 #[test]
gcd_works()179 fn gcd_works() {
180 assert_eq!(2, gcd(8, 6));
181 assert_eq!(2, gcd(6, 8));
182 assert_eq!(3, gcd(15, 6));
183 assert_eq!(3, gcd(6, 15));
184 assert_eq!(1, gcd(17, 12345));
185 assert_eq!(1, gcd(42312, 17));
186 assert_eq!(5, gcd(15, -35));
187 assert_eq!(5, gcd(-15, 35));
188 assert_eq!(5, gcd(-15, -35));
189 }
190
191 #[derive(Alga, Clone, Debug)]
192 #[alga_traits(Field(Additive, Multiplicative))]
193 #[alga_quickcheck]
194 struct Rational {
195 a: i64,
196 b: i64,
197 }
198
199 impl Arbitrary for Rational {
arbitrary<G: Gen>(g: &mut G) -> Self200 fn arbitrary<G: Gen>(g: &mut G) -> Self {
201 let mut div = 0;
202 while div == 0 {
203 div = i64::arbitrary(g);
204 }
205 Rational::new(i64::arbitrary(g), div)
206 }
207
shrink(&self) -> Box<dyn Iterator<Item = Self>>208 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
209 RationalShrinker::new(self.clone())
210 }
211 }
212
213 struct RationalShrinker {
214 x: Rational,
215 i: Rational,
216 }
217
218 impl RationalShrinker {
new(x: Rational) -> Box<dyn Iterator<Item = Rational>>219 pub fn new(x: Rational) -> Box<dyn Iterator<Item = Rational>> {
220 if x.a == 0 {
221 quickcheck::empty_shrinker()
222 } else {
223 let shrinker = RationalShrinker {
224 x: x.clone(),
225 i: Rational::new(x.a, x.b * 2),
226 };
227 let items = vec![Rational::new(0, 1)];
228 Box::new(items.into_iter().chain(shrinker))
229 }
230 }
231 }
232
233 impl Iterator for RationalShrinker {
234 type Item = Rational;
next(&mut self) -> Option<Self::Item>235 fn next(&mut self) -> Option<Self::Item> {
236 let next = Rational::new(
237 (self.x.a * self.i.b) - (self.i.a * self.x.b),
238 self.x.b * self.i.b,
239 );
240 if next.a * self.x.b < self.x.a * next.b {
241 let result = Some(next);
242 self.i = Rational::new(self.i.a, self.i.b * 2);
243 result
244 } else {
245 None
246 }
247 }
248 }
249
250 impl Rational {
new(mut a: i64, mut b: i64) -> Self251 fn new(mut a: i64, mut b: i64) -> Self {
252 assert!(b != 0);
253 if b < 0 {
254 b = -b;
255 a = -a;
256 }
257 if a == 0 {
258 Rational::whole(0)
259 } else {
260 let gcd = gcd(a, b);
261 Rational {
262 a: a / gcd,
263 b: b / gcd,
264 }
265 }
266 }
267
whole(n: i64) -> Self268 fn whole(n: i64) -> Self {
269 Rational { a: n, b: 1 }
270 }
271 }
272
273 impl Display for Rational {
fmt(&self, fmt: &mut Formatter) -> Result<(), Error>274 fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
275 if self.b == 1 {
276 fmt.write_fmt(format_args!("{}", self.a))
277 } else {
278 fmt.write_fmt(format_args!("{}⁄{}", self.a, self.b))
279 }
280 }
281 }
282
283 impl PartialEq for Rational {
eq(&self, lhs: &Self) -> bool284 fn eq(&self, lhs: &Self) -> bool {
285 self.a * lhs.b == lhs.a * self.b
286 }
287 }
288
289 impl AbsDiffEq for Rational {
290 type Epsilon = f64;
291
default_epsilon() -> Self::Epsilon292 fn default_epsilon() -> Self::Epsilon {
293 ::std::f64::EPSILON
294 }
295
abs_diff_eq(&self, other: &Self, epsilon: f64) -> bool296 fn abs_diff_eq(&self, other: &Self, epsilon: f64) -> bool {
297 let us = self.a as f64 / self.b as f64;
298 let them = other.a as f64 / other.b as f64;
299 us.abs_diff_eq(&them, epsilon)
300 }
301 }
302
303 impl RelativeEq for Rational {
default_max_relative() -> Self::Epsilon304 fn default_max_relative() -> Self::Epsilon {
305 ::std::f64::EPSILON
306 }
307
relative_eq( &self, other: &Self, epsilon: Self::Epsilon, max_relative: Self::Epsilon, ) -> bool308 fn relative_eq(
309 &self,
310 other: &Self,
311 epsilon: Self::Epsilon,
312 max_relative: Self::Epsilon,
313 ) -> bool {
314 let us = self.a as f64 / self.b as f64;
315 let them = other.a as f64 / other.b as f64;
316 us.relative_eq(&them, epsilon, max_relative)
317 }
318 }
319
320 impl UlpsEq for Rational {
default_max_ulps() -> u32321 fn default_max_ulps() -> u32 {
322 4
323 }
324
ulps_eq(&self, other: &Self, epsilon: Self::Epsilon, max_ulps: u32) -> bool325 fn ulps_eq(&self, other: &Self, epsilon: Self::Epsilon, max_ulps: u32) -> bool {
326 let us = self.a as f64 / self.b as f64;
327 let them = other.a as f64 / other.b as f64;
328 us.ulps_eq(&them, epsilon, max_ulps)
329 }
330 }
331
332 impl AbstractMagma<Additive> for Rational {
operate(&self, lhs: &Self) -> Self333 fn operate(&self, lhs: &Self) -> Self {
334 let a = self.a * lhs.b + lhs.a * self.b;
335 let b = self.b * lhs.b;
336 let gcd = gcd(a, b);
337 Rational::new(a / gcd, b / gcd)
338 }
339 }
340
341 impl TwoSidedInverse<Additive> for Rational {
two_sided_inverse(&self) -> Self342 fn two_sided_inverse(&self) -> Self {
343 Rational::new(-self.a, self.b)
344 }
345 }
346
347 impl Identity<Additive> for Rational {
identity() -> Self348 fn identity() -> Self {
349 Rational::whole(0)
350 }
351 }
352
353 impl AbstractMagma<Multiplicative> for Rational {
operate(&self, lhs: &Self) -> Self354 fn operate(&self, lhs: &Self) -> Self {
355 let a = self.a * lhs.a;
356 let b = self.b * lhs.b;
357 let gcd = gcd(a, b);
358 Rational::new(a / gcd, b / gcd)
359 }
360 }
361
362 impl TwoSidedInverse<Multiplicative> for Rational {
two_sided_inverse(&self) -> Self363 fn two_sided_inverse(&self) -> Self {
364 if self.a == 0 {
365 self.clone()
366 } else {
367 Rational::new(self.b, self.a)
368 }
369 }
370 }
371
372 impl Identity<Multiplicative> for Rational {
identity() -> Self373 fn identity() -> Self {
374 Rational::whole(1)
375 }
376 }
377
main()378 fn main() {
379 let vec = || {
380 W::<_, Additive, Multiplicative>::new(Vec2::new(Rational::new(1, 2), Rational::whole(3)))
381 };
382 let vec2 = || W::new(Vec2::new(Rational::whole(5), Rational::new(11, 7)));
383 let vec3 = || W::new(Vec2::new(Rational::new(7, 11), Rational::whole(17)));
384
385 let vec4 = (vec() * vec2()) + (vec() * vec3());
386 let vec5 = vec() * (vec2() + vec3());
387 if relative_eq!(vec4, vec5) {
388 println!("{} == {}", vec4, vec5);
389 } else {
390 println!("{} != {}", vec4, vec5);
391 }
392 }
393