1#![allow(clippy::manual_clamp)]
2
3use super::{magma::*, operations::*};
4use crate::num::{Bounded, One, Zero};
5
6#[codesnip::entry("MonoidAction", include("algebra"))]
7pub trait MonoidAction {
8 type Key;
9 type Agg: Clone;
10 type Act: Clone;
11 type AggMonoid: Monoid<T = Self::Agg>;
12 type ActMonoid: Monoid<T = Self::Act>;
13 fn single_agg(key: &Self::Key) -> Self::Agg;
14 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key;
15 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>;
16 fn toggle(_x: &mut Self::Agg) {}
17
18 #[inline]
19 fn agg_unit() -> Self::Agg {
20 <Self::AggMonoid as Unital>::unit()
21 }
22 #[inline]
23 fn act_unit() -> Self::Act {
24 <Self::ActMonoid as Unital>::unit()
25 }
26 #[inline]
27 fn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg {
28 <Self::AggMonoid as Magma>::operate(x, y)
29 }
30 #[inline]
31 fn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act {
32 <Self::ActMonoid as Magma>::operate(x, y)
33 }
34 #[inline]
35 fn agg_operate_assign(x: &mut Self::Agg, y: &Self::Agg) {
36 *x = <Self::AggMonoid as Magma>::operate(x, y);
37 }
38 #[inline]
39 fn act_operate_assign(x: &mut Self::Act, y: &Self::Act) {
40 *x = <Self::ActMonoid as Magma>::operate(x, y);
41 }
42}
43
44#[codesnip::entry("monoid_action_impls")]
45pub use self::monoid_action_impls::*;
46
47#[codesnip::entry(
48 "monoid_action_impls",
49 include(
50 "MonoidAction",
51 "AdditiveOperation",
52 "TupleOperation",
53 "LastOperation",
54 "LinearOperation",
55 "MaxOperation",
56 "MinOperation",
57 "bounded",
58 "zero_one"
59 )
60)]
61mod monoid_action_impls {
62 use super::*;
63 use std::{
64 cmp::Ordering,
65 marker::PhantomData,
66 ops::{Add, Mul, Sub},
67 };
68 pub struct EmptyLazy<M> {
69 _marker: PhantomData<fn() -> M>,
70 }
71 impl<M> MonoidAction for EmptyLazy<M>
72 where
73 M: Monoid,
74 {
75 type Key = M::T;
76 type Agg = M::T;
77 type Act = ();
78 type AggMonoid = M;
79 type ActMonoid = ();
80 fn single_agg(key: &Self::Key) -> Self::Agg {
81 key.clone()
82 }
83 fn act_key(x: &Self::Key, _a: &Self::Act) -> Self::Key {
84 x.clone()
85 }
86 fn act_agg(x: &Self::Agg, _a: &Self::Act) -> Option<Self::Agg> {
87 Some(x.clone())
88 }
89 }
90 pub struct EmptyAction<T> {
91 _marker: PhantomData<fn() -> T>,
92 }
93 impl<T> MonoidAction for EmptyAction<T>
94 where
95 T: Clone,
96 {
97 type Key = T;
98 type Agg = ();
99 type Act = ();
100 type AggMonoid = ();
101 type ActMonoid = ();
102 fn single_agg(_key: &Self::Key) -> Self::Agg {}
103 fn act_key(x: &Self::Key, _a: &Self::Act) -> Self::Key {
104 x.clone()
105 }
106 fn act_agg(_x: &Self::Agg, _a: &Self::Act) -> Option<Self::Agg> {
107 Some(())
108 }
109 }
110 pub struct FlattenAction<M> {
111 _marker: PhantomData<fn() -> M>,
112 }
113 impl<M> MonoidAction for FlattenAction<M>
114 where
115 M: Monoid,
116 {
117 type Key = M::T;
118 type Agg = M::T;
119 type Act = M::T;
120 type AggMonoid = M;
121 type ActMonoid = M;
122 fn single_agg(key: &Self::Key) -> Self::Agg {
123 key.clone()
124 }
125 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
126 M::operate(x, a)
127 }
128 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
129 Some(M::operate(x, a))
130 }
131 }
132
133 pub struct RangeSumRangeAdd<T> {
134 _marker: PhantomData<fn() -> T>,
135 }
136 impl<T> MonoidAction for RangeSumRangeAdd<T>
137 where
138 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
139 {
140 type Key = T;
141 type Agg = (T, T);
142 type Act = T;
143 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
144 type ActMonoid = AdditiveOperation<T>;
145 fn single_agg(key: &Self::Key) -> Self::Agg {
146 (*key, T::one())
147 }
148 fn act_key(&x: &Self::Key, &a: &Self::Act) -> Self::Key {
149 if <Self::ActMonoid as Unital>::is_unit(&a) {
150 x
151 } else {
152 x + a
153 }
154 }
155 fn act_agg(&(x, y): &Self::Agg, &a: &Self::Act) -> Option<Self::Agg> {
156 Some(if <Self::ActMonoid as Unital>::is_unit(&a) {
157 (x, y)
158 } else {
159 (x + a * y, y)
160 })
161 }
162 }
163
164 pub struct RangeSumRangeLinear<T> {
165 _marker: PhantomData<fn() -> T>,
166 }
167 impl<T> MonoidAction for RangeSumRangeLinear<T>
168 where
169 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
170 {
171 type Key = T;
172 type Agg = (T, T);
173 type Act = (T, T);
174 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
175 type ActMonoid = LinearOperation<T>;
176 fn single_agg(key: &Self::Key) -> Self::Agg {
177 (*key, T::one())
178 }
179 fn act_key(&x: &Self::Key, &(a, b): &Self::Act) -> Self::Key {
180 if <Self::ActMonoid as Unital>::is_unit(&(a, b)) {
181 x
182 } else {
183 a * x + b
184 }
185 }
186 fn act_agg(&(x, y): &Self::Agg, &(a, b): &Self::Act) -> Option<Self::Agg> {
187 Some(if <Self::ActMonoid as Unital>::is_unit(&(a, b)) {
188 (x, y)
189 } else {
190 (a * x + b * y, y)
191 })
192 }
193 }
194
195 pub struct RangeSumRangeUpdate<T> {
196 _marker: PhantomData<fn() -> T>,
197 }
198 impl<T> MonoidAction for RangeSumRangeUpdate<T>
199 where
200 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
201 {
202 type Key = T;
203 type Agg = (T, T);
204 type Act = Option<T>;
205 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
206 type ActMonoid = LastOperation<T>;
207 fn single_agg(key: &Self::Key) -> Self::Agg {
208 (*key, T::one())
209 }
210 fn act_key(&x: &Self::Key, &a: &Self::Act) -> Self::Key {
211 a.unwrap_or(x)
212 }
213 fn act_agg(&(x, y): &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
214 Some((a.map(|a| a * y).unwrap_or(x), y))
215 }
216 }
217
218 pub struct RangeMaxRangeUpdate<T> {
219 _marker: PhantomData<fn() -> T>,
220 }
221 impl<T> MonoidAction for RangeMaxRangeUpdate<T>
222 where
223 T: Clone + PartialEq + Ord + Bounded,
224 {
225 type Key = T;
226 type Agg = T;
227 type Act = Option<T>;
228 type AggMonoid = MaxOperation<T>;
229 type ActMonoid = LastOperation<T>;
230 fn single_agg(key: &Self::Key) -> Self::Agg {
231 key.clone()
232 }
233 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
234 a.as_ref().unwrap_or(x).clone()
235 }
236 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
237 Some(a.as_ref().unwrap_or(x).clone())
238 }
239 }
240
241 pub struct RangeMinRangeUpdate<T> {
242 _marker: PhantomData<fn() -> T>,
243 }
244 impl<T> MonoidAction for RangeMinRangeUpdate<T>
245 where
246 T: Clone + PartialEq + Ord + Bounded,
247 {
248 type Key = T;
249 type Agg = T;
250 type Act = Option<T>;
251 type AggMonoid = MinOperation<T>;
252 type ActMonoid = LastOperation<T>;
253 fn single_agg(key: &Self::Key) -> Self::Agg {
254 key.clone()
255 }
256 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
257 a.as_ref().unwrap_or(x).clone()
258 }
259 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
260 Some(a.as_ref().unwrap_or(x).clone())
261 }
262 }
263
264 pub struct RangeMaxRangeAdd<T> {
265 _marker: PhantomData<fn() -> T>,
266 }
267 impl<T> MonoidAction for RangeMaxRangeAdd<T>
268 where
269 T: Clone + Ord + Bounded + Zero + Add<Output = T>,
270 {
271 type Key = T;
272 type Agg = T;
273 type Act = T;
274 type AggMonoid = MaxOperation<T>;
275 type ActMonoid = AdditiveOperation<T>;
276 fn single_agg(key: &Self::Key) -> Self::Agg {
277 key.clone()
278 }
279 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
280 if <Self::ActMonoid as Unital>::is_unit(a) {
281 x.clone()
282 } else {
283 x.clone() + a.clone()
284 }
285 }
286 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
287 Some(if <Self::ActMonoid as Unital>::is_unit(a) {
288 x.clone()
289 } else {
290 x.clone() + a.clone()
291 })
292 }
293 }
294
295 pub struct RangeMinRangeAdd<T> {
296 _marker: PhantomData<fn() -> T>,
297 }
298 impl<T> MonoidAction for RangeMinRangeAdd<T>
299 where
300 T: Clone + Ord + Bounded + Zero + Add<Output = T>,
301 {
302 type Key = T;
303 type Agg = T;
304 type Act = T;
305 type AggMonoid = MinOperation<T>;
306 type ActMonoid = AdditiveOperation<T>;
307 fn single_agg(key: &Self::Key) -> Self::Agg {
308 key.clone()
309 }
310 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
311 if <Self::ActMonoid as Unital>::is_unit(a) {
312 x.clone()
313 } else {
314 x.clone() + a.clone()
315 }
316 }
317 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
318 Some(if <Self::ActMonoid as Unital>::is_unit(a) {
319 x.clone()
320 } else {
321 x.clone() + a.clone()
322 })
323 }
324 }
325
326 #[derive(Debug, Clone, PartialEq, Eq)]
327 pub struct RangeChminChmaxAdd<T> {
328 lb: T,
329 ub: T,
330 bias: T,
331 }
332 impl<T> RangeChminChmaxAdd<T>
333 where
334 T: Zero + Bounded,
335 {
336 pub fn chmin(x: T) -> Self {
337 Self {
338 lb: T::minimum(),
339 ub: x,
340 bias: T::zero(),
341 }
342 }
343 pub fn chmax(x: T) -> Self {
344 Self {
345 lb: x,
346 ub: T::maximum(),
347 bias: T::zero(),
348 }
349 }
350 pub fn add(x: T) -> Self {
351 Self {
352 lb: T::minimum(),
353 ub: T::maximum(),
354 bias: x,
355 }
356 }
357 }
358 impl<T> Magma for RangeChminChmaxAdd<T>
359 where
360 T: Copy
361 + Zero
362 + One
363 + Ord
364 + Bounded
365 + Add<Output = T>
366 + Sub<Output = T>
367 + Mul<Output = T>
368 + PartialEq,
369 {
370 type T = Self;
371 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
372 Self {
373 lb: (x.lb + x.bias).min(y.ub).max(y.lb) - x.bias,
374 ub: (x.ub + x.bias).max(y.lb).min(y.ub) - x.bias,
375 bias: x.bias + y.bias,
376 }
377 }
378 }
379 impl<T> Associative for RangeChminChmaxAdd<T> where
380 T: Copy
381 + Zero
382 + One
383 + Ord
384 + Bounded
385 + Add<Output = T>
386 + Sub<Output = T>
387 + Mul<Output = T>
388 + PartialEq
389 {
390 }
391 impl<T> Unital for RangeChminChmaxAdd<T>
392 where
393 T: Copy
394 + Zero
395 + One
396 + Ord
397 + Bounded
398 + Add<Output = T>
399 + Sub<Output = T>
400 + Mul<Output = T>
401 + PartialEq,
402 {
403 fn unit() -> Self::T {
404 Self {
405 lb: T::minimum(),
406 ub: T::maximum(),
407 bias: T::zero(),
408 }
409 }
410 }
411
412 #[derive(Debug, Clone, PartialEq, Eq)]
413 pub struct RangeSumRangeChminChmaxAdd<T> {
414 min: T,
415 max: T,
416 min2: T,
417 max2: T,
418 pub sum: T,
419 size: T,
420 n_min: T,
421 n_max: T,
422 }
423
424 impl<T> RangeSumRangeChminChmaxAdd<T>
425 where
426 T: Copy
427 + Zero
428 + One
429 + Ord
430 + Bounded
431 + Add<Output = T>
432 + Sub<Output = T>
433 + Mul<Output = T>
434 + PartialEq,
435 {
436 pub fn single(key: T, size: T) -> Self {
437 Self {
438 min: key,
439 max: key,
440 min2: T::maximum(),
441 max2: T::minimum(),
442 sum: key * size,
443 size,
444 n_min: size,
445 n_max: size,
446 }
447 }
448 }
449 impl<T> Magma for RangeSumRangeChminChmaxAdd<T>
450 where
451 T: Copy
452 + Zero
453 + One
454 + Ord
455 + Bounded
456 + Add<Output = T>
457 + Sub<Output = T>
458 + Mul<Output = T>
459 + PartialEq,
460 {
461 type T = Self;
462 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
463 Self {
464 min: x.min.min(y.min),
465 max: x.max.max(y.max),
466 min2: if x.min == y.min {
467 x.min2.min(y.min2)
468 } else if x.min2 <= y.min {
469 x.min2
470 } else if y.min2 <= x.min {
471 y.min2
472 } else {
473 x.min.max(y.min)
474 },
475 max2: if x.max == y.max {
476 x.max2.max(y.max2)
477 } else if x.max2 >= y.max {
478 x.max2
479 } else if y.max2 >= x.max {
480 y.max2
481 } else {
482 x.max.min(y.max)
483 },
484 sum: x.sum + y.sum,
485 size: x.size + y.size,
486 n_min: match x.min.cmp(&y.min) {
487 Ordering::Less => x.n_min,
488 Ordering::Equal => x.n_min + y.n_min,
489 Ordering::Greater => y.n_min,
490 },
491 n_max: match x.max.cmp(&y.max) {
492 Ordering::Less => y.n_max,
493 Ordering::Equal => x.n_max + y.n_max,
494 Ordering::Greater => x.n_max,
495 },
496 }
497 }
498 }
499 impl<T> Associative for RangeSumRangeChminChmaxAdd<T> where
500 T: Copy
501 + Zero
502 + One
503 + Ord
504 + Bounded
505 + Add<Output = T>
506 + Sub<Output = T>
507 + Mul<Output = T>
508 + PartialEq
509 {
510 }
511 impl<T> Unital for RangeSumRangeChminChmaxAdd<T>
512 where
513 T: Copy
514 + Zero
515 + One
516 + Ord
517 + Bounded
518 + Add<Output = T>
519 + Sub<Output = T>
520 + Mul<Output = T>
521 + PartialEq,
522 {
523 fn unit() -> Self::T {
524 Self {
525 min: T::maximum(),
526 max: T::minimum(),
527 min2: T::maximum(),
528 max2: T::minimum(),
529 sum: T::zero(),
530 size: T::zero(),
531 n_min: T::zero(),
532 n_max: T::zero(),
533 }
534 }
535 }
536
537 impl<T> MonoidAction for RangeSumRangeChminChmaxAdd<T>
538 where
539 T: Copy
540 + Zero
541 + One
542 + Ord
543 + Bounded
544 + Add<Output = T>
545 + Sub<Output = T>
546 + Mul<Output = T>
547 + PartialEq,
548 {
549 type Key = T;
550 type Agg = Self;
551 type Act = RangeChminChmaxAdd<T>;
552 type AggMonoid = Self;
553 type ActMonoid = RangeChminChmaxAdd<T>;
554 fn single_agg(&key: &Self::Key) -> Self::Agg {
555 Self::single(key, T::one())
556 }
557 fn act_key(&x: &Self::Key, a: &Self::Act) -> Self::Key {
558 if <Self::ActMonoid as Unital>::is_unit(a) {
559 x
560 } else {
561 x.max(a.lb).min(a.ub) + a.bias
562 }
563 }
564 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
565 Some(if <Self::ActMonoid as Unital>::is_unit(a) {
566 x.clone()
567 } else if x.size.is_zero() {
568 Self::unit()
569 } else if x.min == x.max || a.lb == a.ub || a.lb >= x.max || a.ub <= x.min {
570 Self::single(x.min.max(a.lb).min(a.ub) + a.bias, x.size)
571 } else if x.min2 == x.max {
572 let mut x = x.clone();
573 let min = x.min.max(a.lb) + a.bias;
574 let max = x.max.min(a.ub) + a.bias;
575 x.min = min;
576 x.max2 = min;
577 x.max = max;
578 x.min2 = max;
579 x.sum = min * x.n_min + max * x.n_max;
580 x
581 } else if a.lb < x.min2 && x.max2 < a.ub {
582 let mut x = x.clone();
583 let min = x.min.max(a.lb);
584 let max = x.max.min(a.ub);
585 x.sum = x.sum + (min - x.min) * x.n_min + (max - x.max) * x.n_max + a.bias * x.size;
586 x.min = min + a.bias;
587 x.max = max + a.bias;
588 x.min2 = x.min2 + a.bias;
589 x.max2 = x.max2 + a.bias;
590 x
591 } else {
592 return None;
593 })
594 }
595 }
596}