1use super::{Bounded, One, Zero, magma::*};
4
5#[codesnip::entry("MaxOperation")]
6pub use self::max_operation_impl::MaxOperation;
7#[codesnip::entry("MaxOperation", include("algebra", "bounded"))]
8mod max_operation_impl {
9 use super::*;
10 use std::marker::PhantomData;
11 pub struct MaxOperation<T>
13 where
14 T: Clone + Ord + Bounded,
15 {
16 _marker: PhantomData<fn() -> T>,
17 }
18 impl<T> Magma for MaxOperation<T>
19 where
20 T: Clone + Ord + Bounded,
21 {
22 type T = T;
23 #[inline]
24 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
25 x.max(y).clone()
26 }
27 }
28 impl<T> Unital for MaxOperation<T>
29 where
30 T: Clone + Ord + Bounded,
31 {
32 #[inline]
33 fn unit() -> Self::T {
34 <T as Bounded>::minimum()
35 }
36 }
37 impl<T> Associative for MaxOperation<T> where T: Clone + Ord + Bounded {}
38 impl<T> Commutative for MaxOperation<T> where T: Clone + Ord + Bounded {}
39 impl<T> Idempotent for MaxOperation<T> where T: Clone + Ord + Bounded {}
40
41 #[cfg(test)]
42 mod tests {
43 use super::*;
44
45 #[test]
46 fn test_max_operation() {
47 type M = MaxOperation<i32>;
48 assert_eq!(M::operate(&1, &2), 2);
49 assert_eq!(M::operate(&2, &1), 2);
50 assert_eq!(M::operate(&2, &2), 2);
51 for a in -10..=10 {
52 assert!(M::check_unital(&a));
53 assert!(M::check_idempotent(&a));
54 for b in -10..=10 {
55 assert!(M::check_commutative(&a, &b));
56 for c in -10..=10 {
57 assert!(M::check_associative(&a, &b, &c));
58 }
59 }
60 }
61 }
62 }
63}
64
65#[codesnip::entry("MinOperation")]
66pub use self::min_operation_impl::MinOperation;
67#[codesnip::entry("MinOperation", include("algebra", "bounded"))]
68mod min_operation_impl {
69 use super::*;
70 use std::marker::PhantomData;
71 pub struct MinOperation<T>
73 where
74 T: Clone + Ord + Bounded,
75 {
76 _marker: PhantomData<fn() -> T>,
77 }
78 impl<T> Magma for MinOperation<T>
79 where
80 T: Clone + Ord + Bounded,
81 {
82 type T = T;
83 #[inline]
84 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
85 x.min(y).clone()
86 }
87 }
88 impl<T> Unital for MinOperation<T>
89 where
90 T: Clone + Ord + Bounded,
91 {
92 #[inline]
93 fn unit() -> Self::T {
94 <T as Bounded>::maximum()
95 }
96 }
97 impl<T> Associative for MinOperation<T> where T: Clone + Ord + Bounded {}
98 impl<T> Commutative for MinOperation<T> where T: Clone + Ord + Bounded {}
99 impl<T> Idempotent for MinOperation<T> where T: Clone + Ord + Bounded {}
100
101 #[cfg(test)]
102 mod tests {
103 use super::*;
104
105 #[test]
106 fn test_min_operation() {
107 type M = MinOperation<i32>;
108 assert_eq!(M::operate(&1, &2), 1);
109 assert_eq!(M::operate(&2, &1), 1);
110 assert_eq!(M::operate(&2, &2), 2);
111 for a in -10..=10 {
112 assert!(M::check_unital(&a));
113 assert!(M::check_idempotent(&a));
114 for b in -10..=10 {
115 assert!(M::check_commutative(&a, &b));
116 for c in -10..=10 {
117 assert!(M::check_associative(&a, &b, &c));
118 }
119 }
120 }
121 }
122 }
123}
124
125#[codesnip::entry("FirstOperation")]
126pub use self::first_operation_impl::FirstOperation;
127#[codesnip::entry("FirstOperation", include("algebra"))]
128mod first_operation_impl {
129 use super::*;
130 use std::marker::PhantomData;
131 pub struct FirstOperation<T>
133 where
134 T: Clone,
135 {
136 _marker: PhantomData<fn() -> T>,
137 }
138 impl<T> Magma for FirstOperation<T>
139 where
140 T: Clone,
141 {
142 type T = Option<T>;
143 #[inline]
144 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
145 x.as_ref().or(y.as_ref()).cloned()
146 }
147 }
148 impl<T> Unital for FirstOperation<T>
149 where
150 T: Clone,
151 {
152 #[inline]
153 fn unit() -> Self::T {
154 None
155 }
156 }
157 impl<T> Associative for FirstOperation<T> where T: Clone {}
158 impl<T> Idempotent for FirstOperation<T> where T: Clone {}
159
160 #[cfg(test)]
161 mod tests {
162 use super::*;
163
164 #[test]
165 fn test_first_operation() {
166 type M = FirstOperation<i32>;
167 assert_eq!(M::operate(&Some(1), &Some(2)), Some(1));
168 assert_eq!(M::operate(&Some(2), &Some(1)), Some(2));
169 assert_eq!(M::operate(&Some(1), &None), Some(1));
170 assert_eq!(M::operate(&None, &Some(1)), Some(1));
171 assert_eq!(M::operate(&None, &None), None);
172 let iter = [Some(1), Some(2), Some(3), None];
173 for a in iter {
174 assert!(M::check_unital(&a));
175 assert!(M::check_idempotent(&a));
176 for b in iter {
177 for c in iter {
178 assert!(M::check_associative(&a, &b, &c));
179 }
180 }
181 }
182 }
183 }
184}
185
186#[codesnip::entry("LastOperation")]
187pub use self::last_operation_impl::LastOperation;
188#[codesnip::entry("LastOperation", include("algebra"))]
189mod last_operation_impl {
190 use super::*;
191 use std::marker::PhantomData;
192 pub struct LastOperation<T>
194 where
195 T: Clone,
196 {
197 _marker: PhantomData<fn() -> T>,
198 }
199 impl<T> Magma for LastOperation<T>
200 where
201 T: Clone,
202 {
203 type T = Option<T>;
204 #[inline]
205 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
206 y.as_ref().or(x.as_ref()).cloned()
207 }
208 }
209 impl<T> Unital for LastOperation<T>
210 where
211 T: Clone,
212 {
213 #[inline]
214 fn unit() -> Self::T {
215 None
216 }
217 }
218 impl<T> Associative for LastOperation<T> where T: Clone {}
219 impl<T> Idempotent for LastOperation<T> where T: Clone {}
220
221 #[cfg(test)]
222 mod tests {
223 use super::*;
224
225 #[test]
226 fn test_last_operation() {
227 type M = LastOperation<i32>;
228 assert_eq!(M::operate(&Some(1), &Some(2)), Some(2));
229 assert_eq!(M::operate(&Some(2), &Some(1)), Some(1));
230 assert_eq!(M::operate(&Some(1), &None), Some(1));
231 assert_eq!(M::operate(&None, &Some(1)), Some(1));
232 assert_eq!(M::operate(&None, &None), None);
233 let iter = [Some(1), Some(2), Some(3), None];
234 for a in iter {
235 assert!(M::check_unital(&a));
236 assert!(M::check_idempotent(&a));
237 for b in iter {
238 for c in iter {
239 assert!(M::check_associative(&a, &b, &c));
240 }
241 }
242 }
243 }
244 }
245}
246
247#[codesnip::entry("AdditiveOperation")]
248pub use self::additive_operation_impl::AdditiveOperation;
249#[codesnip::entry("AdditiveOperation", include("algebra", "zero_one"))]
250mod additive_operation_impl {
251 use super::*;
252 use std::{
253 marker::PhantomData,
254 ops::{Add, Neg, Sub},
255 };
256 pub struct AdditiveOperation<T>
258 where
259 T: Clone + Zero + Add<Output = T>,
260 {
261 _marker: PhantomData<fn() -> T>,
262 }
263 impl<T> Magma for AdditiveOperation<T>
264 where
265 T: Clone + Zero + Add<Output = T>,
266 {
267 type T = T;
268 #[inline]
269 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
270 x.clone() + y.clone()
271 }
272 }
273 impl<T> Unital for AdditiveOperation<T>
274 where
275 T: Clone + Zero + Add<Output = T>,
276 {
277 #[inline]
278 fn unit() -> Self::T {
279 Zero::zero()
280 }
281 }
282 impl<T> Associative for AdditiveOperation<T> where T: Clone + Zero + Add<Output = T> {}
283 impl<T> Commutative for AdditiveOperation<T> where T: Clone + Zero + Add<Output = T> {}
284 impl<T> Invertible for AdditiveOperation<T>
285 where
286 T: Clone + Zero + Add<Output = T> + Sub<Output = T> + Neg<Output = T>,
287 {
288 #[inline]
289 fn inverse(x: &Self::T) -> Self::T {
290 -x.clone()
291 }
292 #[inline]
293 fn rinv_operate(x: &Self::T, y: &Self::T) -> Self::T {
294 x.clone() - y.clone()
295 }
296 }
297
298 #[cfg(test)]
299 mod tests {
300 use super::*;
301
302 #[test]
303 fn test_additive_operation() {
304 type M = AdditiveOperation<i32>;
305 assert_eq!(M::operate(&1, &2), 3);
306 assert_eq!(M::operate(&2, &1), 3);
307 assert_eq!(M::operate(&1, &0), 1);
308 assert_eq!(M::operate(&0, &1), 1);
309 assert_eq!(M::operate(&0, &0), 0);
310 for a in -10..=10 {
311 assert!(M::check_unital(&a));
312 assert!(M::check_invertible(&a));
313 for b in -10..=10 {
314 assert!(M::check_commutative(&a, &b));
315 for c in -10..=10 {
316 assert!(M::check_associative(&a, &b, &c));
317 }
318 }
319 }
320 }
321 }
322}
323
324#[codesnip::entry("MultiplicativeOperation")]
325pub use self::multiplicative_operation_impl::MultiplicativeOperation;
326#[codesnip::entry("MultiplicativeOperation", include("algebra", "zero_one"))]
327mod multiplicative_operation_impl {
328 use super::*;
329 use std::{
330 marker::PhantomData,
331 ops::{Div, Mul},
332 };
333 pub struct MultiplicativeOperation<T>
335 where
336 T: Clone + One + Mul<Output = T>,
337 {
338 _marker: PhantomData<fn() -> T>,
339 }
340 impl<T> Magma for MultiplicativeOperation<T>
341 where
342 T: Clone + One + Mul<Output = T>,
343 {
344 type T = T;
345 #[inline]
346 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
347 x.clone() * y.clone()
348 }
349 }
350 impl<T> Unital for MultiplicativeOperation<T>
351 where
352 T: Clone + One + Mul<Output = T>,
353 {
354 #[inline]
355 fn unit() -> Self::T {
356 One::one()
357 }
358 }
359 impl<T> Associative for MultiplicativeOperation<T> where T: Clone + One + Mul<Output = T> {}
360 impl<T> Commutative for MultiplicativeOperation<T> where T: Clone + One + Mul<Output = T> {}
361 impl<T> Invertible for MultiplicativeOperation<T>
362 where
363 T: Clone + One + Mul<Output = T> + Div<Output = T>,
364 {
365 #[inline]
366 fn inverse(x: &Self::T) -> Self::T {
367 Self::unit().div(x.clone())
368 }
369 #[inline]
370 fn rinv_operate(x: &Self::T, y: &Self::T) -> Self::T {
371 (x.clone()).div(y.clone())
372 }
373 }
374
375 #[cfg(test)]
376 mod tests {
377 use super::*;
378 use crate::num::mint_basic::MInt998244353;
379
380 #[test]
381 fn test_multiplicative_operation() {
382 type MInt = MInt998244353;
383 type M = MultiplicativeOperation<MInt>;
384 assert_eq!(M::operate(&MInt::new(1), &MInt::new(2)), MInt::new(2));
385 assert_eq!(M::operate(&MInt::new(2), &MInt::new(1)), MInt::new(2));
386 assert_eq!(M::operate(&MInt::new(1), &MInt::new(1)), MInt::new(1));
387 assert_eq!(M::operate(&MInt::new(1), &MInt::new(0)), MInt::new(0));
388 assert_eq!(M::operate(&MInt::new(0), &MInt::new(1)), MInt::new(0));
389 assert_eq!(M::operate(&MInt::new(0), &MInt::new(0)), MInt::new(0));
390 let iter = (-10..=10).map(MInt::from);
391 for a in iter.clone() {
392 assert!(M::check_unital(&a));
393 if !a.is_zero() {
394 assert!(M::check_invertible(&a));
395 }
396 for b in iter.clone() {
397 assert!(M::check_commutative(&a, &b));
398 for c in iter.clone() {
399 assert!(M::check_associative(&a, &b, &c));
400 }
401 }
402 }
403 }
404 }
405}
406
407#[codesnip::entry("LinearOperation")]
408pub use self::linear_operation_impl::LinearOperation;
409#[codesnip::entry("LinearOperation", include("algebra", "zero_one"))]
410mod linear_operation_impl {
411 use super::*;
412 use std::{
413 marker::PhantomData,
414 ops::{Add, Div, Mul, Neg, Sub},
415 };
416 pub struct LinearOperation<T>
418 where
419 T: Clone + Zero + Add<Output = T> + One + Mul<Output = T>,
420 {
421 _marker: PhantomData<fn() -> T>,
422 }
423 impl<T> LinearOperation<T>
424 where
425 T: Clone + Zero + Add<Output = T> + One + Mul<Output = T>,
426 {
427 pub fn apply(f: &(T, T), x: &T) -> T {
428 f.0.clone() * x.clone() + f.1.clone()
429 }
430 }
431 impl<T> Magma for LinearOperation<T>
432 where
433 T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
434 {
435 type T = (T, T);
436 #[inline]
437 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
438 (
439 y.0.clone() * x.0.clone(),
440 y.0.clone() * x.1.clone() + y.1.clone(),
441 )
442 }
443 }
444 impl<T> Unital for LinearOperation<T>
445 where
446 T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
447 {
448 #[inline]
449 fn unit() -> Self::T {
450 (One::one(), Zero::zero())
451 }
452 }
453 impl<T> Associative for LinearOperation<T> where
454 T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>
455 {
456 }
457 impl<T> Invertible for LinearOperation<T>
458 where
459 T: Clone
460 + Zero
461 + One
462 + Add<Output = T>
463 + Sub<Output = T>
464 + Neg<Output = T>
465 + Mul<Output = T>
466 + Div<Output = T>,
467 {
468 fn inverse(x: &Self::T) -> Self::T {
469 let y = <T as One>::one().div(x.0.clone());
470 (y.clone(), -y.mul(x.1.clone()))
471 }
472 }
473
474 #[cfg(test)]
475 mod tests {
476 use super::*;
477 use crate::num::mint_basic::MInt998244353;
478
479 #[test]
480 fn test_linear_operation() {
481 type MInt = MInt998244353;
482 type M = LinearOperation<MInt>;
483 let iter = (-5..=5).flat_map(|x| (-5..=5).map(move |y| (MInt::from(x), MInt::from(y))));
484 for a in iter.clone() {
485 assert!(M::check_unital(&a));
486 if !a.0.is_zero() {
487 assert!(M::check_invertible(&a));
488 }
489 for b in iter.clone() {
490 for c in iter.clone() {
491 assert!(M::check_associative(&a, &b, &c));
492 }
493 for x in (-5..=5).map(MInt::from) {
494 assert_eq!(
495 M::apply(&M::operate(&a, &b), &x),
496 M::apply(&b, &M::apply(&a, &x))
497 );
498 }
499 }
500 }
501 }
502 }
503}
504
505#[codesnip::entry("BitAndOperation")]
506pub use self::bitand_operation_impl::{BitAndIdentity, BitAndOperation};
507#[codesnip::entry("BitAndOperation", include("algebra"))]
508mod bitand_operation_impl {
509 use super::*;
510 use std::{marker::PhantomData, ops::BitAnd};
511 pub struct BitAndOperation<T>
513 where
514 T: Clone + BitAndIdentity,
515 {
516 _marker: PhantomData<fn() -> T>,
517 }
518 pub trait BitAndIdentity: Sized + BitAnd<Output = Self> {
519 fn all_one() -> Self;
520 }
521 #[macro_export]
522 macro_rules! impl_bitand_identity {
523 ([$($wh:tt)*], $t:ty, $all_one:expr) => {
524 impl<$($wh)*> BitAndIdentity for $t {
525 #[inline]
526 fn all_one() -> Self {
527 $all_one
528 }
529 }
530 };
531 ($t:ty, $all_one:expr) => {
532 impl BitAndIdentity for $t {
533 #[inline]
534 fn all_one() -> Self {
535 $all_one
536 }
537 }
538 };
539 }
540 impl_bitand_identity!(bool, true);
541 impl_bitand_identity!(usize, usize::MAX);
542 impl_bitand_identity!(u8, u8::MAX);
543 impl_bitand_identity!(u16, u16::MAX);
544 impl_bitand_identity!(u32, u32::MAX);
545 impl_bitand_identity!(u64, u64::MAX);
546 impl_bitand_identity!(u128, u128::MAX);
547 impl_bitand_identity!(isize, -1);
548 impl_bitand_identity!(i8, -1);
549 impl_bitand_identity!(i16, -1);
550 impl_bitand_identity!(i32, -1);
551 impl_bitand_identity!(i64, -1);
552 impl_bitand_identity!(i128, -1);
553 impl<T> Magma for BitAndOperation<T>
554 where
555 T: Clone + BitAndIdentity,
556 {
557 type T = T;
558 #[inline]
559 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
560 x.clone() & y.clone()
561 }
562 }
563 impl<T> Unital for BitAndOperation<T>
564 where
565 T: Clone + BitAndIdentity,
566 {
567 #[inline]
568 fn unit() -> Self::T {
569 BitAndIdentity::all_one()
570 }
571 }
572 impl<T> Associative for BitAndOperation<T> where T: Clone + BitAndIdentity {}
573 impl<T> Commutative for BitAndOperation<T> where T: Clone + BitAndIdentity {}
574 impl<T> Idempotent for BitAndOperation<T> where T: Clone + BitAndIdentity {}
575
576 #[cfg(test)]
577 mod tests {
578 use super::*;
579
580 #[test]
581 fn test_bitand_operation() {
582 macro_rules! impl_test_bitand_operation {
583 ($ty:ty, $array:expr) => {{
584 type M = BitAndOperation<$ty>;
585 for a in $array {
586 assert!(M::check_unital(&a));
587 assert!(M::check_idempotent(&a));
588 for b in $array {
589 assert!(M::check_commutative(&a, &b));
590 for c in $array {
591 assert!(M::check_associative(&a, &b, &c));
592 }
593 }
594 }
595 }};
596 }
597 impl_test_bitand_operation!(bool, [true, false]);
598 impl_test_bitand_operation!(usize, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
599 impl_test_bitand_operation!(u8, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
600 impl_test_bitand_operation!(u16, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
601 impl_test_bitand_operation!(u32, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
602 impl_test_bitand_operation!(u64, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
603 impl_test_bitand_operation!(u128, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
604 impl_test_bitand_operation!(isize, [0, 1, 2, 3, 4, 5, -1, -2, isize::MIN, isize::MAX]);
605 impl_test_bitand_operation!(i8, [0, 1, 2, 3, 4, 5, -1, -2, i8::MIN, i8::MAX]);
606 impl_test_bitand_operation!(i16, [0, 1, 2, 3, 4, 5, -1, -2, i16::MIN, i16::MAX]);
607 impl_test_bitand_operation!(i32, [0, 1, 2, 3, 4, 5, -1, -2, i32::MIN, i32::MAX]);
608 impl_test_bitand_operation!(i64, [0, 1, 2, 3, 4, 5, -1, -2, i64::MIN, i64::MAX]);
609 impl_test_bitand_operation!(i128, [0, 1, 2, 3, 4, 5, -1, -2, i128::MIN, i128::MAX]);
610 }
611 }
612}
613
614#[codesnip::entry("BitOrOperation")]
615pub use self::bitor_operation_impl::{BitOrIdentity, BitOrOperation};
616#[codesnip::entry("BitOrOperation", include("algebra"))]
617mod bitor_operation_impl {
618 use super::*;
619 use std::{marker::PhantomData, ops::BitOr};
620 pub struct BitOrOperation<T>
622 where
623 T: Clone + BitOrIdentity,
624 {
625 _marker: PhantomData<fn() -> T>,
626 }
627 pub trait BitOrIdentity: Sized + BitOr<Output = Self> {
628 fn all_zero() -> Self;
629 }
630 #[macro_export]
631 macro_rules! impl_bitor_identity {
632 ([$($wh:tt)*], $t:ty, $all_zero:expr) => {
633 impl<$($wh)*> BitOrIdentity for $t {
634 #[inline]
635 fn all_zero() -> Self {
636 $all_zero
637 }
638 }
639 };
640 ($t:ty, $all_zero:expr) => {
641 impl BitOrIdentity for $t {
642 #[inline]
643 fn all_zero() -> Self {
644 $all_zero
645 }
646 }
647 };
648 }
649 impl_bitor_identity!(bool, false);
650 impl_bitor_identity!(usize, 0);
651 impl_bitor_identity!(u8, 0);
652 impl_bitor_identity!(u16, 0);
653 impl_bitor_identity!(u32, 0);
654 impl_bitor_identity!(u64, 0);
655 impl_bitor_identity!(u128, 0);
656 impl_bitor_identity!(isize, 0);
657 impl_bitor_identity!(i8, 0);
658 impl_bitor_identity!(i16, 0);
659 impl_bitor_identity!(i32, 0);
660 impl_bitor_identity!(i64, 0);
661 impl_bitor_identity!(i128, 0);
662 impl<T> Magma for BitOrOperation<T>
663 where
664 T: Clone + BitOrIdentity,
665 {
666 type T = T;
667 #[inline]
668 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
669 x.clone() | y.clone()
670 }
671 }
672 impl<T> Unital for BitOrOperation<T>
673 where
674 T: Clone + BitOrIdentity,
675 {
676 #[inline]
677 fn unit() -> Self::T {
678 BitOrIdentity::all_zero()
679 }
680 }
681 impl<T> Associative for BitOrOperation<T> where T: Clone + BitOrIdentity {}
682 impl<T> Commutative for BitOrOperation<T> where T: Clone + BitOrIdentity {}
683 impl<T> Idempotent for BitOrOperation<T> where T: Clone + BitOrIdentity {}
684
685 #[cfg(test)]
686 mod tests {
687 use super::*;
688
689 #[test]
690 fn test_bitor_operation() {
691 macro_rules! impl_test_bitor_operation {
692 ($ty:ty, $array:expr) => {{
693 type M = BitOrOperation<$ty>;
694 for a in $array {
695 assert!(M::check_unital(&a));
696 assert!(M::check_idempotent(&a));
697 for b in $array {
698 assert!(M::check_commutative(&a, &b));
699 for c in $array {
700 assert!(M::check_associative(&a, &b, &c));
701 }
702 }
703 }
704 }};
705 }
706 impl_test_bitor_operation!(bool, [true, false]);
707 impl_test_bitor_operation!(usize, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
708 impl_test_bitor_operation!(u8, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
709 impl_test_bitor_operation!(u16, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
710 impl_test_bitor_operation!(u32, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
711 impl_test_bitor_operation!(u64, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
712 impl_test_bitor_operation!(u128, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
713 impl_test_bitor_operation!(isize, [0, 1, 2, 3, 4, 5, -1, -2, isize::MIN, isize::MAX]);
714 impl_test_bitor_operation!(i8, [0, 1, 2, 3, 4, 5, -1, -2, i8::MIN, i8::MAX]);
715 impl_test_bitor_operation!(i16, [0, 1, 2, 3, 4, 5, -1, -2, i16::MIN, i16::MAX]);
716 impl_test_bitor_operation!(i32, [0, 1, 2, 3, 4, 5, -1, -2, i32::MIN, i32::MAX]);
717 impl_test_bitor_operation!(i64, [0, 1, 2, 3, 4, 5, -1, -2, i64::MIN, i64::MAX]);
718 impl_test_bitor_operation!(i128, [0, 1, 2, 3, 4, 5, -1, -2, i128::MIN, i128::MAX]);
719 }
720 }
721}
722
723#[codesnip::entry("BitXorOperation")]
724pub use self::bitxor_operation_impl::{BitXorIdentity, BitXorOperation};
725#[codesnip::entry("BitXorOperation", include("algebra"))]
726mod bitxor_operation_impl {
727 use super::*;
728 use std::{marker::PhantomData, ops::BitXor};
729 pub struct BitXorOperation<T>
731 where
732 T: Clone + BitXorIdentity,
733 {
734 _marker: PhantomData<fn() -> T>,
735 }
736 pub trait BitXorIdentity: Sized + BitXor<Output = Self> {
737 fn xor_zero() -> Self;
738 }
739 #[macro_export]
740 macro_rules! impl_bitxor_identity {
741 ([$($wh:tt)*], $t:ty, $xor_zero:expr) => {
742 impl<$($wh)*> BitXorIdentity for $t {
743 #[inline]
744 fn xor_zero() -> Self { $xor_zero }
745 }
746 };
747 ($t:ty, $xor_zero:expr) =>{
748 impl BitXorIdentity for $t {
749 #[inline]
750 fn xor_zero() -> Self { $xor_zero }
751 }
752 };
753 }
754 impl_bitxor_identity!(bool, false);
755 impl_bitxor_identity!(usize, 0);
756 impl_bitxor_identity!(u8, 0);
757 impl_bitxor_identity!(u16, 0);
758 impl_bitxor_identity!(u32, 0);
759 impl_bitxor_identity!(u64, 0);
760 impl_bitxor_identity!(u128, 0);
761 impl_bitxor_identity!(isize, 0);
762 impl_bitxor_identity!(i8, 0);
763 impl_bitxor_identity!(i16, 0);
764 impl_bitxor_identity!(i32, 0);
765 impl_bitxor_identity!(i64, 0);
766 impl_bitxor_identity!(i128, 0);
767 impl<T> Magma for BitXorOperation<T>
768 where
769 T: Clone + BitXorIdentity,
770 {
771 type T = T;
772 #[inline]
773 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
774 x.clone() ^ y.clone()
775 }
776 }
777 impl<T> Unital for BitXorOperation<T>
778 where
779 T: Clone + BitXorIdentity,
780 {
781 #[inline]
782 fn unit() -> Self::T {
783 BitXorIdentity::xor_zero()
784 }
785 }
786 impl<T> Associative for BitXorOperation<T> where T: Clone + BitXorIdentity {}
787 impl<T> Commutative for BitXorOperation<T> where T: Clone + BitXorIdentity {}
788 impl<T> Invertible for BitXorOperation<T>
789 where
790 T: Clone + BitXorIdentity,
791 {
792 fn inverse(x: &Self::T) -> Self::T {
793 x.clone()
794 }
795 }
796
797 #[cfg(test)]
798 mod tests {
799 use super::*;
800
801 #[test]
802 fn test_bitxor_operation() {
803 macro_rules! impl_test_bitxor_operation {
804 ($ty:ty, $array:expr) => {{
805 type M = BitXorOperation<$ty>;
806 for a in $array {
807 assert!(M::check_unital(&a));
808 assert!(M::check_invertible(&a));
809 for b in $array {
810 assert!(M::check_commutative(&a, &b));
811 for c in $array {
812 assert!(M::check_associative(&a, &b, &c));
813 }
814 }
815 }
816 }};
817 }
818 impl_test_bitxor_operation!(bool, [true, false]);
819 impl_test_bitxor_operation!(usize, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
820 impl_test_bitxor_operation!(u8, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
821 impl_test_bitxor_operation!(u16, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
822 impl_test_bitxor_operation!(u32, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
823 impl_test_bitxor_operation!(u64, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
824 impl_test_bitxor_operation!(u128, [0, 1, 2, 3, 4, 5, !0 - 1, !0]);
825 impl_test_bitxor_operation!(isize, [0, 1, 2, 3, 4, 5, -1, -2, isize::MIN, isize::MAX]);
826 impl_test_bitxor_operation!(i8, [0, 1, 2, 3, 4, 5, -1, -2, i8::MIN, i8::MAX]);
827 impl_test_bitxor_operation!(i16, [0, 1, 2, 3, 4, 5, -1, -2, i16::MIN, i16::MAX]);
828 impl_test_bitxor_operation!(i32, [0, 1, 2, 3, 4, 5, -1, -2, i32::MIN, i32::MAX]);
829 impl_test_bitxor_operation!(i64, [0, 1, 2, 3, 4, 5, -1, -2, i64::MIN, i64::MAX]);
830 impl_test_bitxor_operation!(i128, [0, 1, 2, 3, 4, 5, -1, -2, i128::MIN, i128::MAX]);
831 }
832 }
833}
834
835#[codesnip::entry("LogicalLinearOperation")]
836pub use self::logical_linear_operation_impl::LogicalLinearOperation;
837#[codesnip::entry(
838 "LogicalLinearOperation",
839 include("algebra", "BitXorOperation", "BitAndOperation")
840)]
841mod logical_linear_operation_impl {
842 use super::*;
843 use std::{
844 marker::PhantomData,
845 ops::{BitAnd, BitXor},
846 };
847 pub struct LogicalLinearOperation<T>
849 where
850 T: Clone + BitXorIdentity + BitAndIdentity + BitXor<Output = T> + BitAnd<Output = T>,
851 {
852 _marker: PhantomData<fn() -> T>,
853 }
854 impl<T> LogicalLinearOperation<T>
855 where
856 T: Clone + BitXorIdentity + BitAndIdentity + BitXor<Output = T> + BitAnd<Output = T>,
857 {
858 pub fn eval((a, b): &<Self as Magma>::T, x: &T) -> T {
859 a.clone() & x.clone() ^ b.clone()
860 }
861 }
862 impl<T> Magma for LogicalLinearOperation<T>
863 where
864 T: Clone + BitXorIdentity + BitAndIdentity + BitXor<Output = T> + BitAnd<Output = T>,
865 {
866 type T = (T, T);
867 #[inline]
868 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
869 (
870 y.0.clone() & x.0.clone(),
871 y.0.clone() & x.1.clone() ^ y.1.clone(),
872 )
873 }
874 }
875 impl<T> Unital for LogicalLinearOperation<T>
876 where
877 T: Clone + BitXorIdentity + BitAndIdentity + BitXor<Output = T> + BitAnd<Output = T>,
878 {
879 #[inline]
880 fn unit() -> Self::T {
881 (BitAndIdentity::all_one(), BitXorIdentity::xor_zero())
882 }
883 }
884 impl<T> Associative for LogicalLinearOperation<T> where
885 T: Clone + BitXorIdentity + BitAndIdentity + BitXor<Output = T> + BitAnd<Output = T>
886 {
887 }
888
889 #[cfg(test)]
890 mod tests {
891 use super::*;
892
893 #[test]
894 fn test_logical_linear_operation() {
895 type M = LogicalLinearOperation<i32>;
896 let iter = (-3..=3).flat_map(|x| (-3..=3).map(move |y| (x, y)));
897 for a in iter.clone() {
898 assert!(M::check_unital(&a));
899 for b in iter.clone() {
900 for c in iter.clone() {
901 assert!(M::check_associative(&a, &b, &c));
902 }
903 for x in -3..=3 {
904 assert_eq!(
905 M::eval(&M::operate(&a, &b), &x),
906 M::eval(&b, &M::eval(&a, &x))
907 );
908 }
909 }
910 }
911 }
912 }
913}
914
915#[codesnip::entry("TupleOperation", include("algebra"))]
916mod tuple_operation_impl {
917 use super::*;
918 macro_rules! impl_tuple_operation {
919 (@impl) => {
920 impl Magma for () {
921 type T = ();
922 fn operate(_x: &Self::T, _y: &Self::T) -> Self::T {}
923 }
924 impl Unital for () {
925 fn unit() -> Self::T {}
926 }
927 impl Associative for () {}
928 impl Commutative for () {}
929 impl Idempotent for () {}
930 impl Invertible for () {
931 fn inverse(_x: &Self::T) -> Self::T {}
932 }
933 };
934 (@impl $($T:ident $i:tt)*) => {
935 impl<$($T: Magma),*> Magma for ($($T,)*) {
936 type T = ($(<$T as Magma>::T,)*);
937 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
938 ($(<$T as Magma>::operate(&x.$i, &y.$i),)*)
939 }
940 }
941 impl<$($T: Unital),*> Unital for ($($T,)*) {
942 fn unit() -> Self::T {
943 ($(<$T as Unital>::unit(),)*)
944 }
945 }
946 impl<$($T: Associative),*> Associative for ($($T,)*) {}
947 impl<$($T: Commutative),*> Commutative for ($($T,)*) {}
948 impl<$($T: Idempotent),*> Idempotent for ($($T,)*) {}
949 impl<$($T: Invertible),*> Invertible for ($($T,)*) {
950 fn inverse(x: &Self::T) -> Self::T {
951 ($(<$T as Invertible>::inverse(&x.$i),)*)
952 }
953 }
954 };
955 (@inner $($T:ident $i:tt)*; $U:ident $j:tt $($t:tt)*) => {
956 impl_tuple_operation!(@impl $($T $i)*);
957 impl_tuple_operation!(@inner $($T $i)* $U $j; $($t)*);
958 };
959 (@inner $($T:ident $i:tt)*;) => {
960 impl_tuple_operation!(@impl $($T $i)*);
961 };
962 ($($t:tt)*) => {
963 impl_tuple_operation!(@inner ; $($t)*);
964 };
965 }
966 impl_tuple_operation!(A 0 B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9);
967
968 #[cfg(test)]
969 mod tests {
970 use super::*;
971 use crate::num::mint_basic::MInt998244353;
972
973 #[test]
974 fn test_tuple_operation() {
975 type MInt = MInt998244353;
976 type M = (AdditiveOperation<MInt>, MultiplicativeOperation<MInt>);
977 let iter = (-5..=5).flat_map(|x| (-5..=5).map(move |y| (MInt::from(x), MInt::from(y))));
978 for a in iter.clone() {
979 assert!(M::check_unital(&a));
980 if !a.1.is_zero() {
981 assert!(M::check_invertible(&a));
982 }
983 for b in iter.clone() {
984 assert!(M::check_commutative(&a, &b));
985 for c in iter.clone() {
986 assert!(M::check_associative(&a, &b, &c));
987 }
988 }
989 }
990 }
991 }
992}
993
994#[codesnip::entry("ArrayOperation")]
995pub use self::array_operation_impl::ArrayOperation;
996#[codesnip::entry("ArrayOperation", include("algebra", "array"))]
997mod array_operation_impl {
998 use super::*;
999 use crate::array;
1000 use std::marker::PhantomData;
1001 pub struct ArrayOperation<M, const N: usize> {
1002 _marker: PhantomData<fn() -> M>,
1003 }
1004 impl<M, const N: usize> Magma for ArrayOperation<M, N>
1005 where
1006 M: Magma,
1007 {
1008 type T = [M::T; N];
1009 #[inline]
1010 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1011 array!(|i| M::operate(&x[i], &y[i]); N)
1012 }
1013 }
1014 impl<M, const N: usize> Unital for ArrayOperation<M, N>
1015 where
1016 M: Unital,
1017 {
1018 #[inline]
1019 fn unit() -> Self::T {
1020 array!(|| M::unit(); N)
1021 }
1022 }
1023 impl<M, const N: usize> Associative for ArrayOperation<M, N> where M: Associative {}
1024 impl<M, const N: usize> Commutative for ArrayOperation<M, N> where M: Commutative {}
1025 impl<M, const N: usize> Idempotent for ArrayOperation<M, N> where M: Idempotent {}
1026 impl<M, const N: usize> Invertible for ArrayOperation<M, N>
1027 where
1028 M: Invertible,
1029 {
1030 #[inline]
1031 fn inverse(x: &Self::T) -> Self::T {
1032 array!(|i| M::inverse(&x[i]); N)
1033 }
1034 }
1035
1036 #[cfg(test)]
1037 mod tests {
1038 use super::*;
1039
1040 #[test]
1041 fn test_array_operation() {
1042 type M = ArrayOperation<AdditiveOperation<i32>, 2>;
1043
1044 let iter = (-5..=5).flat_map(|x| (-5..=5).map(move |y| [x, y]));
1045 for a in iter.clone() {
1046 assert!(M::check_unital(&a));
1047 assert!(M::check_invertible(&a));
1048 for b in iter.clone() {
1049 assert!(M::check_commutative(&a, &b));
1050 for c in iter.clone() {
1051 assert!(M::check_associative(&a, &b, &c));
1052 }
1053 }
1054 }
1055 }
1056 }
1057}
1058
1059#[codesnip::entry("CountingOperation")]
1060pub use self::counting_operation_impl::CountingOperation;
1061#[codesnip::entry("CountingOperation", include("algebra"))]
1062mod counting_operation_impl {
1063 use super::*;
1064 use std::marker::PhantomData;
1065 pub struct CountingOperation<M> {
1066 _marker: PhantomData<fn() -> M>,
1067 }
1068 impl<M> Magma for CountingOperation<M>
1069 where
1070 M: Magma<T: PartialEq> + Idempotent,
1071 {
1072 type T = (M::T, usize);
1073 #[inline]
1074 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1075 let z = M::operate(&x.0, &y.0);
1076 match (z == x.0, z == y.0) {
1077 (true, true) => (z, x.1 + y.1),
1078 (true, false) => (z, x.1),
1079 (false, true) => (z, y.1),
1080 (false, false) => (z, 1),
1081 }
1082 }
1083 }
1084 impl<M> Unital for CountingOperation<M>
1085 where
1086 M: Unital<T: PartialEq> + Idempotent,
1087 {
1088 #[inline]
1089 fn unit() -> Self::T {
1090 (M::unit(), 0)
1091 }
1092 }
1093 impl<M> Associative for CountingOperation<M> where M: Associative<T: PartialEq> + Idempotent {}
1094 impl<M> Commutative for CountingOperation<M> where M: Commutative<T: PartialEq> + Idempotent {}
1095
1096 #[cfg(test)]
1097 mod tests {
1098 use super::*;
1099
1100 #[test]
1101 fn test_counting_operation() {
1102 type M = CountingOperation<MaxOperation<i32>>;
1103 let iter = (-5..=5).flat_map(|x| (1..=5).map(move |y| (x, y)));
1104 for a in iter.clone() {
1105 assert!(M::check_unital(&a));
1106 for b in iter.clone() {
1107 assert!(M::check_commutative(&a, &b));
1108 for c in iter.clone() {
1109 assert!(M::check_associative(&a, &b, &c));
1110 }
1111 }
1112 }
1113 }
1114 }
1115}
1116
1117#[codesnip::entry("ReverseOperation")]
1118pub use self::reverse_operation_impl::ReverseOperation;
1119#[codesnip::entry("ReverseOperation", include("algebra"))]
1120mod reverse_operation_impl {
1121 use super::*;
1122 use std::marker::PhantomData;
1123 pub struct ReverseOperation<M> {
1124 _marker: PhantomData<fn() -> M>,
1125 }
1126 impl<M> Magma for ReverseOperation<M>
1127 where
1128 M: Magma,
1129 {
1130 type T = M::T;
1131 #[inline]
1132 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1133 M::operate(y, x)
1134 }
1135 }
1136 impl<M> Unital for ReverseOperation<M>
1137 where
1138 M: Unital,
1139 {
1140 #[inline]
1141 fn unit() -> Self::T {
1142 M::unit()
1143 }
1144 }
1145 impl<M> Associative for ReverseOperation<M> where M: Associative {}
1146 impl<M> Commutative for ReverseOperation<M> where M: Commutative {}
1147 impl<M> Invertible for ReverseOperation<M>
1148 where
1149 M: Invertible,
1150 {
1151 #[inline]
1152 fn inverse(x: &Self::T) -> Self::T {
1153 M::inverse(x)
1154 }
1155 }
1156 impl<M> Idempotent for ReverseOperation<M> where M: Idempotent {}
1157
1158 #[cfg(test)]
1159 mod tests {
1160 use super::*;
1161 use crate::num::mint_basic::MInt998244353;
1162
1163 #[test]
1164 fn test_reverse_operation() {
1165 type MInt = MInt998244353;
1166 type M = ReverseOperation<LinearOperation<MInt>>;
1167 let iter = (-3..=3).flat_map(|x| (-3..=3).map(move |y| (MInt::from(x), MInt::from(y))));
1168 for a in iter.clone() {
1169 assert!(M::check_unital(&a));
1170 if !a.0.is_zero() {
1171 assert!(M::check_invertible(&a));
1172 }
1173 for b in iter.clone() {
1174 for c in iter.clone() {
1175 assert!(M::check_associative(&a, &b, &c));
1176 }
1177 }
1178 }
1179 }
1180 }
1181}
1182
1183#[codesnip::entry("TopkOperation")]
1184pub use self::topk_operation_impl::TopkOperation;
1185#[codesnip::entry("TopkOperation", include("algebra", "bounded", "array"))]
1186mod topk_operation_impl {
1187 use super::*;
1188 use std::marker::PhantomData;
1189 pub struct TopkOperation<const K: usize, T>
1190 where
1191 T: Clone + Ord + Bounded,
1192 {
1193 _marker: PhantomData<fn() -> T>,
1194 }
1195 impl<const K: usize, T> Magma for TopkOperation<K, T>
1196 where
1197 T: Clone + Ord + Bounded,
1198 {
1199 type T = [T; K];
1200 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1201 let mut i = 0;
1202 let mut j = 0;
1203 crate::array![|| if i == K || j != K && x[i] < y[j] {
1204 let t = &y[j];
1205 j += 1;
1206 t.clone()
1207 } else {
1208 let t = &x[i];
1209 i += 1;
1210 t.clone()
1211 }; K]
1212 }
1213 }
1214 impl<const K: usize, T> Unital for TopkOperation<K, T>
1215 where
1216 T: Clone + Ord + Bounded,
1217 {
1218 fn unit() -> Self::T {
1219 crate::array![|| <T as Bounded>::minimum(); K]
1220 }
1221 }
1222 impl<const K: usize, T> Associative for TopkOperation<K, T> where T: Clone + Ord + Bounded {}
1223 impl<const K: usize, T> Commutative for TopkOperation<K, T> where T: Clone + Ord + Bounded {}
1224
1225 #[cfg(test)]
1226 mod tests {
1227 use super::*;
1228 use crate::{array, tools::Xorshift};
1229
1230 #[test]
1231 fn test_topk_operation() {
1232 type M = TopkOperation<4, i64>;
1233 let mut rng = Xorshift::default();
1234 for _ in 0..100 {
1235 let mut x = [i64::MIN; 4];
1236 for _ in 0..100 {
1237 let mut y = [i64::MIN; 4];
1238 for y in &mut y {
1239 *y = rng.random(0..1000);
1240 }
1241 y.sort_unstable();
1242 y.reverse();
1243 let z = {
1244 let mut x = x.to_vec();
1245 x.extend(&y);
1246 x.sort_unstable();
1247 x.reverse();
1248 x.truncate(4);
1249 x
1250 };
1251 let zz = M::operate(&x, &y);
1252 for (z, zz) in z.iter().zip(&zz) {
1253 assert_eq!(z, zz);
1254 }
1255 x = zz;
1256 }
1257
1258 let mut g = || {
1259 if rng.random(0..3) == 0 {
1260 i64::MIN
1261 } else {
1262 rng.random(0..10)
1263 }
1264 };
1265 let mut a = array![|| g(); 4];
1266 a.sort_unstable();
1267 a.reverse();
1268 assert!(M::check_unital(&a));
1269 let mut b = array![|| g(); 4];
1270 b.sort_unstable();
1271 b.reverse();
1272 assert!(M::check_commutative(&a, &b));
1273 let mut c = array![|| g(); 4];
1274 c.sort_unstable();
1275 c.reverse();
1276 assert!(M::check_associative(&a, &b, &c));
1277 }
1278 }
1279 }
1280}
1281
1282#[codesnip::entry("BottomkOperation")]
1283pub use self::bottomk_operation_impl::BottomkOperation;
1284#[codesnip::entry("BottomkOperation", include("algebra", "bounded", "array"))]
1285mod bottomk_operation_impl {
1286 use super::*;
1287 use std::marker::PhantomData;
1288 pub struct BottomkOperation<const K: usize, T>
1289 where
1290 T: Clone + Ord + Bounded,
1291 {
1292 _marker: PhantomData<fn() -> T>,
1293 }
1294 impl<const K: usize, T> Magma for BottomkOperation<K, T>
1295 where
1296 T: Clone + Ord + Bounded,
1297 {
1298 type T = [T; K];
1299 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1300 let mut i = 0;
1301 let mut j = 0;
1302 crate::array![|| if i == K || j != K && x[i] > y[j] {
1303 let t = &y[j];
1304 j += 1;
1305 t.clone()
1306 } else {
1307 let t = &x[i];
1308 i += 1;
1309 t.clone()
1310 }; K]
1311 }
1312 }
1313 impl<const K: usize, T> Unital for BottomkOperation<K, T>
1314 where
1315 T: Clone + Ord + Bounded,
1316 {
1317 fn unit() -> Self::T {
1318 crate::array![|| <T as Bounded>::maximum(); K]
1319 }
1320 }
1321 impl<const K: usize, T> Associative for BottomkOperation<K, T> where T: Clone + Ord + Bounded {}
1322 impl<const K: usize, T> Commutative for BottomkOperation<K, T> where T: Clone + Ord + Bounded {}
1323
1324 #[cfg(test)]
1325 mod tests {
1326 use super::*;
1327 use crate::{array, tools::Xorshift};
1328
1329 #[test]
1330 fn test_bottomk_operation() {
1331 type M = BottomkOperation<4, i64>;
1332 let mut rng = Xorshift::default();
1333 for _ in 0..100 {
1334 let mut x = [i64::MAX; 4];
1335 for _ in 0..100 {
1336 let mut y = [i64::MAX; 4];
1337 for y in &mut y {
1338 *y = rng.random(0..1000);
1339 }
1340 y.sort_unstable();
1341 let z = {
1342 let mut x = x.to_vec();
1343 x.extend(&y);
1344 x.sort_unstable();
1345 x.truncate(4);
1346 x
1347 };
1348 let zz = M::operate(&x, &y);
1349 for (z, zz) in z.iter().zip(&zz) {
1350 assert_eq!(z, zz);
1351 }
1352 x = zz;
1353 }
1354
1355 let mut g = || {
1356 if rng.random(0..3) == 0 {
1357 i64::MAX
1358 } else {
1359 rng.random(0..10)
1360 }
1361 };
1362 let mut a = array![|| g(); 4];
1363 a.sort_unstable();
1364 assert!(M::check_unital(&a));
1365 let mut b = array![|| g(); 4];
1366 b.sort_unstable();
1367 assert!(M::check_commutative(&a, &b));
1368 let mut c = array![|| g(); 4];
1369 c.sort_unstable();
1370 assert!(M::check_associative(&a, &b, &c));
1371 }
1372 }
1373 }
1374}
1375
1376#[codesnip::entry("PermutationOperation")]
1377pub use self::permutation_operation_impl::PermutationOperation;
1378#[codesnip::entry("PermutationOperation", include("algebra"))]
1379mod permutation_operation_impl {
1380 use super::*;
1381 pub enum PermutationOperation {}
1382 impl Magma for PermutationOperation {
1383 type T = Vec<usize>;
1384 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1385 let n = x.len().max(y.len());
1386 let z: Vec<_> = (0..n)
1387 .map(|i| {
1388 let j = y.get(i).cloned().unwrap_or(i);
1389 x.get(j).cloned().unwrap_or(j)
1390 })
1391 .collect();
1392 z
1393 }
1394 }
1395 impl Associative for PermutationOperation {}
1396 impl Unital for PermutationOperation {
1397 fn unit() -> Self::T {
1398 Vec::new()
1399 }
1400
1401 fn is_unit(x: &Self::T) -> bool
1402 where
1403 Self::T: PartialEq,
1404 {
1405 x.iter().enumerate().all(|(i, &x)| i == x)
1406 }
1407 }
1408 impl Invertible for PermutationOperation {
1409 fn inverse(x: &Self::T) -> Self::T {
1410 let mut y = vec![0; x.len()];
1411 for (i, x) in x.iter().enumerate() {
1412 y[*x] = i;
1413 }
1414 y
1415 }
1416 }
1417
1418 #[cfg(test)]
1419 mod tests {
1420 use super::*;
1421 use crate::tools::Xorshift;
1422
1423 #[test]
1424 fn test_permutation_operation() {
1425 type M = PermutationOperation;
1426 let mut rng = Xorshift::default();
1427 for _ in 0..100 {
1428 let mut a: Vec<usize> = (0..rng.random(0..20)).collect();
1429 let mut b: Vec<usize> = (0..rng.random(0..20)).collect();
1430 let mut c: Vec<usize> = (0..rng.random(0..20)).collect();
1431 rng.shuffle(&mut a);
1432 rng.shuffle(&mut b);
1433 rng.shuffle(&mut c);
1434 assert!(M::check_unital(&a));
1435 assert!(M::check_invertible(&a));
1436 assert!(M::check_associative(&a, &b, &c));
1437 }
1438 }
1439 }
1440}
1441
1442#[codesnip::entry("FindMajorityOperation")]
1443pub use self::find_majority_operation_impl::FindMajorityOperation;
1444#[codesnip::entry("FindMajorityOperation", include("algebra"))]
1445mod find_majority_operation_impl {
1446 use super::*;
1447 use std::{cmp::Ordering, marker::PhantomData};
1448 pub struct FindMajorityOperation<T> {
1456 _marker: PhantomData<fn() -> T>,
1457 }
1458 impl<T> Magma for FindMajorityOperation<T>
1459 where
1460 T: Clone + Eq,
1461 {
1462 type T = (Option<T>, usize);
1463 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1464 if y.0.is_none() {
1465 x.clone()
1466 } else if x.0.is_none() {
1467 y.clone()
1468 } else {
1469 match (x.0.eq(&y.0), x.1.cmp(&y.1)) {
1470 (true, _) => (x.0.clone(), x.1 + y.1),
1471 (_, Ordering::Less) => (y.0.clone(), y.1 - x.1),
1472 (_, Ordering::Equal) => (None, 0),
1473 (_, Ordering::Greater) => (x.0.clone(), x.1 - y.1),
1474 }
1475 }
1476 }
1477 }
1478 impl<T> Unital for FindMajorityOperation<T>
1479 where
1480 T: Clone + Eq,
1481 {
1482 fn unit() -> Self::T {
1483 (None, 0)
1484 }
1485 }
1486 impl<T> Associative for FindMajorityOperation<T> where T: Clone + Eq {}
1487
1488 #[cfg(test)]
1489 mod tests {
1490 use super::*;
1491 use std::{collections::HashMap, iter::once};
1492
1493 #[test]
1494 fn test_find_majority_operation() {
1495 type M = FindMajorityOperation<i32>;
1496 let iter = (-5..=5)
1497 .flat_map(|x| (1..=5).map(move |y| (Some(x), y)))
1498 .chain(once((None, 0)));
1499 for a in iter.clone() {
1500 assert!(M::check_unital(&a));
1501 for b in iter.clone() {
1502 for c in iter.clone() {
1503 let mut count = HashMap::<_, usize>::new();
1506 for (key, cnt) in [a, b, c] {
1507 if let Some(key) = key {
1508 *count.entry(key).or_default() += cnt;
1509 }
1510 }
1511 let max = count.values().max().cloned().unwrap_or_default();
1512 let sum: usize = count.values().sum();
1513 if max * 2 > sum {
1514 assert_eq!(
1515 M::operate(&M::operate(&a, &b), &c).0,
1516 count.into_iter().find(|&(_, v)| v == max).map(|(k, _)| k)
1517 );
1518 }
1519 }
1520 }
1521 }
1522 }
1523 }
1524}
1525
1526pub use self::concatenate_operation::{ConcatenateOperation, SortedConcatenateOperation};
1527mod concatenate_operation {
1528 use super::*;
1529 use std::marker::PhantomData;
1530 pub struct ConcatenateOperation<T> {
1531 _marker: PhantomData<fn() -> T>,
1532 }
1533 impl<T> Magma for ConcatenateOperation<T>
1534 where
1535 T: Clone,
1536 {
1537 type T = Vec<T>;
1538 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1539 x.iter().chain(y.iter()).cloned().collect()
1540 }
1541 }
1542 impl<T> Unital for ConcatenateOperation<T>
1543 where
1544 T: Clone,
1545 {
1546 fn unit() -> Self::T {
1547 Vec::new()
1548 }
1549 }
1550 impl<T> Associative for ConcatenateOperation<T> where T: Clone {}
1551
1552 pub struct SortedConcatenateOperation<T> {
1553 _marker: PhantomData<fn() -> T>,
1554 }
1555 impl<T> Magma for SortedConcatenateOperation<T>
1556 where
1557 T: Clone + Ord,
1558 {
1559 type T = Vec<T>;
1560 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1561 let mut xit = x.iter().cloned().peekable();
1562 let mut yit = y.iter().cloned().peekable();
1563 let mut z = Vec::with_capacity(x.len() + y.len());
1564 loop {
1565 match (xit.peek(), yit.peek()) {
1566 (None, None) => break,
1567 (Some(_), None) => z.push(xit.next().unwrap()),
1568 (Some(x), Some(y)) if x <= y => z.push(xit.next().unwrap()),
1569 _ => z.push(yit.next().unwrap()),
1570 }
1571 }
1572 z
1573 }
1574 }
1575 impl<T> Unital for SortedConcatenateOperation<T>
1576 where
1577 T: Clone + Ord,
1578 {
1579 fn unit() -> Self::T {
1580 Vec::new()
1581 }
1582 }
1583 impl<T> Associative for SortedConcatenateOperation<T> where T: Clone + Ord {}
1584 impl<T> Commutative for SortedConcatenateOperation<T> where T: Clone + Ord {}
1585
1586 #[cfg(test)]
1587 mod tests {
1588 use super::*;
1589 use crate::{rand, tools::Xorshift};
1590
1591 #[test]
1592 fn test_concatenate_operation() {
1593 type M = ConcatenateOperation<i32>;
1594 let mut rng = Xorshift::default();
1595 for _ in 0..100 {
1596 rand!(rng, n: 0..4, a: [0..10; n], m: 0..4, b: [0..10; m], l: 0..4, c: [0..10; l]);
1597 assert!(M::check_unital(&a));
1598 assert!(M::check_associative(&a, &b, &c));
1599
1600 let ab: Vec<_> = a.iter().chain(b.iter()).cloned().collect();
1601 assert_eq!(M::operate(&a, &b), ab);
1602 }
1603 }
1604
1605 #[test]
1606 fn test_sorted_concatenate_operation() {
1607 type M = SortedConcatenateOperation<i32>;
1608 let mut rng = Xorshift::default();
1609 for _ in 0..100 {
1610 rand!(rng, n: 0..4, mut a: [0..10; n], m: 0..4, mut b: [0..10; m], l: 0..4, mut c: [0..10; l]);
1611 a.sort_unstable();
1612 b.sort_unstable();
1613 c.sort_unstable();
1614 assert!(M::check_unital(&a));
1615 assert!(M::check_commutative(&a, &b));
1616 assert!(M::check_associative(&a, &b, &c));
1617
1618 let mut ab: Vec<_> = a.iter().chain(b.iter()).cloned().collect();
1619 ab.sort_unstable();
1620 assert_eq!(M::operate(&a, &b), ab);
1621 }
1622 }
1623 }
1624}
1625
1626#[codesnip::entry("MinimumIntervalMovementOperation")]
1627pub use self::minimum_interval_movement_impl::{
1628 MinimumIntervalMovement, MinimumIntervalMovementOperation,
1629};
1630#[codesnip::entry(
1631 "MinimumIntervalMovementOperation",
1632 include("algebra", "bounded", "zero_one")
1633)]
1634mod minimum_interval_movement_impl {
1635 use super::*;
1636 use std::{
1637 marker::PhantomData,
1638 ops::{Add, Sub},
1639 };
1640
1641 pub struct MinimumIntervalMovementOperation<T> {
1642 _marker: PhantomData<fn() -> T>,
1643 }
1644 #[derive(Debug, Clone)]
1645 pub struct MinimumIntervalMovement<T> {
1646 pos_range: (T, T),
1647 move_range: (T, T),
1648 cost: T,
1649 }
1650 impl<T> MinimumIntervalMovement<T>
1651 where
1652 T: Clone + Zero,
1653 {
1654 pub fn new(l: T, r: T) -> Self {
1655 Self {
1656 pos_range: (l.clone(), r.clone()),
1657 move_range: (l, r),
1658 cost: T::zero(),
1659 }
1660 }
1661 }
1662 impl<T> MinimumIntervalMovement<T>
1663 where
1664 T: Clone + Ord + Zero,
1665 {
1666 pub fn position(&self, x: &T) -> T {
1667 x.clamp(&self.pos_range.0, &self.pos_range.1).clone()
1668 }
1669 }
1670 impl<T> MinimumIntervalMovement<T>
1671 where
1672 T: Clone + Ord + Add<Output = T> + Sub<Output = T> + Zero,
1673 {
1674 pub fn move_cost(&self, x: &T) -> T {
1675 x.max(&self.move_range.0).clone() - x.min(&self.move_range.1).clone()
1676 + self.cost.clone()
1677 }
1678 }
1679 impl<T> Magma for MinimumIntervalMovementOperation<T>
1680 where
1681 T: Clone + Ord + Add<Output = T> + Sub<Output = T> + Zero,
1682 {
1683 type T = MinimumIntervalMovement<T>;
1684 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
1685 let pos_range = (
1686 (&x.pos_range.0)
1687 .clamp(&y.pos_range.0, &y.pos_range.1)
1688 .clone(),
1689 (&x.pos_range.1)
1690 .clamp(&y.pos_range.0, &y.pos_range.1)
1691 .clone(),
1692 );
1693 let move_range = (
1694 (&y.move_range.0)
1695 .clamp(&x.move_range.0, &x.move_range.1)
1696 .clone(),
1697 (&y.move_range.1)
1698 .clamp(&x.move_range.0, &x.move_range.1)
1699 .clone(),
1700 );
1701 let cost = x.cost.clone() + y.move_cost(&x.position(&move_range.0));
1702 MinimumIntervalMovement {
1703 pos_range,
1704 move_range,
1705 cost,
1706 }
1707 }
1708 }
1709 impl<T> Associative for MinimumIntervalMovementOperation<T> where
1710 T: Clone + Ord + Add<Output = T> + Sub<Output = T> + Zero
1711 {
1712 }
1713 impl<T> Unital for MinimumIntervalMovementOperation<T>
1714 where
1715 T: Clone + Ord + Add<Output = T> + Sub<Output = T> + Zero + Bounded,
1716 {
1717 fn unit() -> Self::T {
1718 MinimumIntervalMovement::new(T::minimum(), T::maximum())
1719 }
1720 }
1721
1722 #[cfg(test)]
1723 mod tests {
1724 use super::*;
1725 use crate::{chmin, tools::Xorshift};
1726 use std::collections::HashMap;
1727
1728 #[test]
1729 fn test_minimum_interval_movement_operation() {
1730 type M = MinimumIntervalMovementOperation<i32>;
1731 let mut rng = Xorshift::default();
1732 for _ in 0..100 {
1733 let mut min = M::unit();
1734 let mut cost = HashMap::new();
1735 let s: i32 = rng.random(-100..100);
1736 cost.insert(s, 0i32);
1737 for _ in 0..10 {
1738 let l = rng.random(-100..100);
1739 let r = rng.random(l..=100);
1740 let m = MinimumIntervalMovement::new(l, r);
1741 min = M::operate(&min, &m);
1742 let mut ncost = HashMap::new();
1743 for (x, c) in cost {
1744 for nx in l..=r {
1745 let nc = c + (x - nx).abs();
1746 chmin!(*ncost.entry(nx).or_insert(nc), nc);
1747 }
1748 }
1749 cost = ncost;
1750 let x = min.position(&s);
1751 let c = min.move_cost(&s);
1752 assert_eq!(Some(&c), cost.get(&x));
1753 }
1754 }
1755 }
1756 }
1757}