competitive/data_structure/
transducer.rs

1use super::{
2    Container, ContainerEntry, ContainerFactory, FixedVecMapFactory, HashMapFactory, Monoid,
3    VecMap, VecMapFactory,
4};
5use std::{
6    borrow::Borrow,
7    cell::RefCell,
8    cmp::Ordering,
9    collections::HashMap,
10    fmt::{self, Debug, Formatter},
11    hash::Hash,
12    iter::Peekable,
13    marker::PhantomData,
14    mem::swap,
15};
16
17type Marker<T> = PhantomData<fn() -> T>;
18type ChainMapTrasducer<S, T, U, F> = ChainTransducer<(S, MapTransducer<T, U, F>)>;
19type ChainFilterMapTrasducer<S, T, U, F> = ChainTransducer<(S, FilterMapTransducer<T, U, F>)>;
20
21pub trait Transducer {
22    type Input;
23    type Output;
24    type State;
25    fn start(&self) -> Self::State;
26    fn relation(
27        &self,
28        state: &Self::State,
29        input: &Self::Input,
30    ) -> Option<(Self::State, Self::Output)>;
31    fn accept(&self, state: &Self::State) -> bool;
32    fn stepout(&mut self) {}
33    fn dp<M>(self, init: M::T) -> InitTransducerDp<M, Self>
34    where
35        Self: Sized,
36        M: Monoid,
37    {
38        InitTransducerDp::new(self, init)
39    }
40
41    fn intersection<U>(self, other: U) -> IntersectionTransducer<(Self, U)>
42    where
43        Self: Sized,
44        U: Transducer<Input = Self::Input>,
45    {
46        IntersectionTransducer((self, other))
47    }
48    fn product<U>(self, other: U) -> ProductTransducer<(Self, U)>
49    where
50        Self: Sized,
51        U: Transducer,
52    {
53        ProductTransducer((self, other))
54    }
55    fn chain<U>(self, other: U) -> ChainTransducer<(Self, U)>
56    where
57        Self: Sized,
58        U: Transducer<Input = Self::Output>,
59    {
60        ChainTransducer((self, other))
61    }
62    fn with_input(self) -> IntersectionTransducer<(Self, IdentityTransducer<Self::Input>)>
63    where
64        Self: Sized,
65    {
66        IntersectionTransducer((self, IdentityTransducer::new()))
67    }
68    fn map<U, F>(self, f: F) -> ChainMapTrasducer<Self, Self::Output, U, F>
69    where
70        Self: Sized,
71        F: Fn(&Self::Output) -> U,
72    {
73        ChainTransducer((self, MapTransducer::new(f)))
74    }
75    fn filter_map<U, F>(self, f: F) -> ChainFilterMapTrasducer<Self, Self::Output, U, F>
76    where
77        Self: Sized,
78        F: Fn(&Self::Output) -> Option<U>,
79    {
80        ChainTransducer((self, FilterMapTransducer::new(f)))
81    }
82}
83
84#[derive(Debug, Clone)]
85pub struct InitTransducerDp<M, A>
86where
87    M: Monoid,
88    A: Transducer,
89{
90    fst: A,
91    init: M::T,
92}
93
94impl<M, A> InitTransducerDp<M, A>
95where
96    M: Monoid,
97    A: Transducer,
98{
99    pub fn new(fst: A, init: M::T) -> Self {
100        Self { fst, init }
101    }
102    pub fn with_factory<F>(self, factory: F) -> Transducerdp<M, A, F::Container>
103    where
104        F: ContainerFactory,
105        F::Container: Container<Key = A::State, Value = M::T>,
106    {
107        Transducerdp::new(self.fst, self.init, factory)
108    }
109    pub fn with_hashmap(self) -> Transducerdp<M, A, HashMap<A::State, M::T>>
110    where
111        A::State: Eq + Hash,
112    {
113        Transducerdp::new(self.fst, self.init, HashMapFactory::default())
114    }
115    pub fn with_vecmap<F>(
116        self,
117        key_to_index: F,
118    ) -> Transducerdp<M, A, VecMap<false, A::State, M::T, F>>
119    where
120        F: Fn(&A::State) -> usize + Clone,
121    {
122        Transducerdp::new(self.fst, self.init, VecMapFactory::new(key_to_index))
123    }
124    pub fn with_fixed_vecmap<F>(
125        self,
126        key_to_index: F,
127        len: usize,
128    ) -> Transducerdp<M, A, VecMap<true, A::State, M::T, F>>
129    where
130        F: Fn(&A::State) -> usize + Clone,
131    {
132        Transducerdp::new(
133            self.fst,
134            self.init,
135            FixedVecMapFactory::new(key_to_index, len),
136        )
137    }
138}
139
140#[derive(Clone)]
141pub struct Transducerdp<M, T, C>
142where
143    M: Monoid,
144    T: Transducer,
145    C: Container<Key = T::State, Value = M::T>,
146{
147    fst: T,
148    pub dp: C,
149    ndp: C,
150    _marker: PhantomData<fn() -> M>,
151}
152
153impl<M, T, C> Debug for Transducerdp<M, T, C>
154where
155    M: Monoid,
156    T: Transducer + Debug,
157    T::State: Debug,
158    M::T: Debug,
159    C: Container<Key = T::State, Value = M::T> + Debug,
160{
161    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
162        f.debug_struct("Transducerdp")
163            .field("fst", &self.fst)
164            .field("dp", &self.dp)
165            .field("ndp", &self.ndp)
166            .finish()
167    }
168}
169
170impl<M, T, C> Transducerdp<M, T, C>
171where
172    M: Monoid,
173    T: Transducer,
174    C: Container<Key = T::State, Value = M::T>,
175{
176    pub fn new<F>(fst: T, init: M::T, factory: F) -> Self
177    where
178        F: ContainerFactory<Container = C>,
179    {
180        let mut dp = factory.create_container();
181        let ndp = factory.create_container();
182        dp.insert(fst.start(), init);
183        Self {
184            fst,
185            dp,
186            ndp,
187            _marker: PhantomData,
188        }
189    }
190    pub fn step<S, I, B>(&mut self, mut sigma: S)
191    where
192        S: FnMut() -> I,
193        I: IntoIterator<Item = B>,
194        B: Borrow<T::Input>,
195    {
196        for (state, value) in self.dp.drain() {
197            for input in sigma() {
198                if let Some((nstate, _)) = self.fst.relation(&state, input.borrow()) {
199                    self.ndp
200                        .entry(nstate)
201                        .and_modify(|acc| M::operate_assign(acc, &value))
202                        .or_insert_with(|| value.clone());
203                }
204            }
205        }
206        swap(&mut self.dp, &mut self.ndp);
207        self.fst.stepout();
208    }
209    pub fn step_effect<S, I, B, F>(&mut self, mut sigma: S, mut effect: F)
210    where
211        S: FnMut() -> I,
212        I: IntoIterator<Item = B>,
213        B: Borrow<T::Input>,
214        F: FnMut(&M::T, &T::Output) -> M::T,
215    {
216        for (state, value) in self.dp.drain() {
217            for input in sigma() {
218                if let Some((nstate, output)) = self.fst.relation(&state, input.borrow()) {
219                    let nvalue = effect(&value, &output);
220                    self.ndp
221                        .entry(nstate)
222                        .and_modify(|acc| M::operate_assign(acc, &nvalue))
223                        .or_insert(nvalue);
224                }
225            }
226        }
227        swap(&mut self.dp, &mut self.ndp);
228        self.fst.stepout();
229    }
230    pub fn fold_accept(&self) -> M::T {
231        let mut acc = M::unit();
232        for (state, value) in self.dp.iter() {
233            if self.fst.accept(state) {
234                M::operate_assign(&mut acc, value);
235            }
236        }
237        acc
238    }
239    pub fn map_fold_accept<U, F, D>(&self, mut f: F, mut map: D) -> D
240    where
241        F: FnMut(&T::State) -> U,
242        D: Container<Key = U, Value = M::T>,
243    {
244        for (state, value) in self.dp.iter() {
245            if self.fst.accept(state) {
246                map.entry(f(state))
247                    .and_modify(|acc| M::operate_assign(acc, value))
248                    .or_insert_with(|| value.clone());
249            }
250        }
251        map
252    }
253    pub fn run<S, I, B>(&mut self, mut sigma: S, len: usize) -> M::T
254    where
255        S: FnMut() -> I,
256        I: IntoIterator<Item = B>,
257        B: Borrow<T::Input>,
258    {
259        for _ in 0..len {
260            self.step(&mut sigma);
261        }
262        self.fold_accept()
263    }
264    pub fn run_effect<S, I, B, F>(&mut self, mut sigma: S, len: usize, mut effect: F) -> M::T
265    where
266        S: FnMut() -> I,
267        I: IntoIterator<Item = B>,
268        B: Borrow<T::Input>,
269        F: FnMut(&M::T, &T::Output) -> M::T,
270    {
271        for _ in 0..len {
272            self.step_effect(&mut sigma, &mut effect);
273        }
274        self.fold_accept()
275    }
276}
277
278#[derive(Debug, Clone)]
279pub struct IntersectionTransducer<Tuple>(pub Tuple);
280
281macro_rules! impl_intersection_transducer {
282    (@impl $($T:ident)*, $($a:ident)*, $($b:ident)*) => {
283        impl<A, $($T),*> Transducer for IntersectionTransducer<($($T,)*)>
284        where
285            $($T: Transducer<Input = A>,)*
286        {
287            type Input = A;
288            type Output = ($($T::Output,)*);
289            type State = ($($T::State,)*);
290            fn start(&self) -> Self::State {
291                let Self(($($a,)*)) = self;
292                ($($a.start(),)*)
293            }
294            fn relation(&self, state: &Self::State, input: &Self::Input) -> Option<(Self::State, Self::Output)> {
295                let Self(($($a,)*)) = self;
296                let ($($b,)*) = state;
297                match ($($a.relation($b, input),)*) {
298                    ($(Some(($a, $b)),)*) => Some((($($a,)*), ($($b,)*))),
299                    _ => None,
300                }
301            }
302            fn accept(&self, state: &Self::State) -> bool {
303                let Self(($($a,)*)) = self;
304                let ($($b,)*) = state;
305                $($a.accept($b))&&*
306            }
307            fn stepout(&mut self) {
308                let Self(($($a,)*)) = self;
309                $($a.stepout();)*
310            }
311        }
312    };
313    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $TT:ident $aa:ident $bb:ident) => {
314        impl_intersection_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb);
315    };
316    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $TT:ident $aa:ident $bb:ident $($tt:tt)*) => {
317        impl_intersection_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb);
318        impl_intersection_transducer!(@inc $($T)* $TT, $($a)* $aa, $($b)* $bb, $($tt)*);
319    };
320    ($($tt:tt)*) => {
321        impl_intersection_transducer!(@inc , , , $($tt)*);
322    };
323}
324impl_intersection_transducer!(
325    T0 a0 b0
326    T1 a1 b1
327    T2 a2 b2
328    T3 a3 b3
329    T4 a4 b4
330    T5 a5 b5
331    T6 a6 b6
332    T7 a7 b7
333    T8 a8 b8
334    T9 a9 b9
335);
336
337#[derive(Debug, Clone)]
338pub struct ProductTransducer<Tuple>(pub Tuple);
339
340macro_rules! impl_product_transducer {
341    (@impl $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*) => {
342        impl<$($T),*> Transducer for ProductTransducer<($($T,)*)>
343        where
344            $($T: Transducer,)*
345        {
346            type Input = ($($T::Input,)*);
347            type Output = ($($T::Output,)*);
348            type State = ($($T::State,)*);
349            fn start(&self) -> Self::State {
350                let Self(($($a,)*)) = self;
351                ($($a.start(),)*)
352            }
353            fn relation(&self, state: &Self::State, ($($c,)*): &Self::Input) -> Option<(Self::State, Self::Output)> {
354                let Self(($($a,)*)) = self;
355                let ($($b,)*) = state;
356                match ($($a.relation($b, $c),)*) {
357                    ($(Some(($a, $b)),)*) => Some((($($a,)*), ($($b,)*))),
358                    _ => None,
359                }
360            }
361            fn accept(&self, state: &Self::State) -> bool {
362                let Self(($($a,)*)) = self;
363                let ($($b,)*) = state;
364                $($a.accept($b))&&*
365            }
366            fn stepout(&mut self) {
367                let Self(($($a,)*)) = self;
368                $($a.stepout();)*
369            }
370        }
371    };
372    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident) => {
373        impl_product_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
374    };
375    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident $($tt:tt)*) => {
376        impl_product_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
377        impl_product_transducer!(@inc $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc, $($tt)*);
378    };
379    ($($tt:tt)*) => {
380        impl_product_transducer!(@inc , , , , $($tt)*);
381    };
382}
383impl_product_transducer!(
384    T0 a0 b0 c0
385    T1 a1 b1 c1
386    T2 a2 b2 c2
387    T3 a3 b3 c3
388    T4 a4 b4 c4
389    T5 a5 b5 c5
390    T6 a6 b6 c6
391    T7 a7 b7 c7
392    T8 a8 b8 c8
393    T9 a9 b9 c9
394);
395
396#[derive(Debug, Clone)]
397pub struct ChainTransducer<Tuple>(pub Tuple);
398
399macro_rules! impl_chain_transducer {
400    (@impl $T_head:ident, $($T_tail:ident)*, $($T_init:ident)*, $T_last:ident, $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*) => {
401        impl<$($T),*> Transducer for ChainTransducer<($($T,)*)>
402        where
403            $T_head: Transducer,
404            $($T_tail: Transducer<Input = $T_init::Output>,)*
405        {
406            type Input = $T_head::Input;
407            type Output = $T_last::Output;
408            type State = ($($T::State,)*);
409            fn start(&self) -> Self::State {
410                let Self(($($a,)*)) = self;
411                ($($a.start(),)*)
412            }
413            fn relation(&self, state: &Self::State, input: &Self::Input) -> Option<(Self::State, Self::Output)> {
414                let Self(($($a,)*)) = self;
415                let ($($b,)*) = state;
416                $(let ($c, input) = $a.relation($b, &input)?;)*
417                Some((($($c,)*), input))
418            }
419            fn accept(&self, state: &Self::State) -> bool {
420                let Self(($($a,)*)) = self;
421                let ($($b,)*) = state;
422                $($a.accept($b))&&*
423            }
424            fn stepout(&mut self) {
425                let Self(($($a,)*)) = self;
426                $($a.stepout();)*
427            }
428        }
429    };
430    (@inc $T0:ident $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident) => {
431        impl_chain_transducer!(@impl $T0, $($T)* $TT, $T0 $($T)*, $TT, $T0 $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
432    };
433    (@inc , $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident $($tt:tt)*) => {
434        impl_chain_transducer!(@impl $TT, , , $TT,  $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
435        impl_chain_transducer!(@inc $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc, $($tt)*);
436    };
437    (@inc $T0:ident $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident $($tt:tt)*) => {
438        impl_chain_transducer!(@impl $T0, $($T)* $TT, $T0 $($T)*, $TT, $T0 $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
439        impl_chain_transducer!(@inc $T0 $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc, $($tt)*);
440    };
441    ($($tt:tt)*) => {
442        impl_chain_transducer!(@inc , , , , $($tt)*);
443    };
444}
445impl_chain_transducer!(
446    T0 a0 b0 c0
447    T1 a1 b1 c1
448    T2 a2 b2 c2
449    T3 a3 b3 c3
450    T4 a4 b4 c4
451    T5 a5 b5 c5
452    T6 a6 b6 c6
453    T7 a7 b7 c7
454    T8 a8 b8 c8
455    T9 a9 b9 c9
456);
457
458#[derive(Debug, Clone)]
459pub struct FunctionalTransducer<I, O, S, F, G, H>
460where
461    F: Fn() -> S,
462    G: Fn(&S, &I) -> Option<(S, O)>,
463    H: Fn(&S) -> bool,
464{
465    fn_start: F,
466    fn_relation: G,
467    fn_accept: H,
468    _marker: Marker<(I, O, S)>,
469}
470impl<I, O, S, F, G, H> FunctionalTransducer<I, O, S, F, G, H>
471where
472    F: Fn() -> S,
473    G: Fn(&S, &I) -> Option<(S, O)>,
474    H: Fn(&S) -> bool,
475{
476    pub fn new(fn_start: F, fn_relation: G, fn_accept: H) -> Self {
477        Self {
478            fn_start,
479            fn_relation,
480            fn_accept,
481            _marker: PhantomData,
482        }
483    }
484}
485impl<I, O, S, F, G, H> Transducer for FunctionalTransducer<I, O, S, F, G, H>
486where
487    F: Fn() -> S,
488    G: Fn(&S, &I) -> Option<(S, O)>,
489    H: Fn(&S) -> bool,
490{
491    type Input = I;
492    type Output = O;
493    type State = S;
494    fn start(&self) -> Self::State {
495        (self.fn_start)()
496    }
497    fn relation(
498        &self,
499        state: &Self::State,
500        input: &Self::Input,
501    ) -> Option<(Self::State, Self::Output)> {
502        (self.fn_relation)(state, input)
503    }
504    fn accept(&self, state: &Self::State) -> bool {
505        (self.fn_accept)(state)
506    }
507}
508
509#[derive(Debug, Clone)]
510pub struct MapTransducer<T, U, F>
511where
512    F: Fn(&T) -> U,
513{
514    f: F,
515    _marker: PhantomData<fn() -> (T, U)>,
516}
517impl<T, U, F> MapTransducer<T, U, F>
518where
519    F: Fn(&T) -> U,
520{
521    pub fn new(f: F) -> Self {
522        Self {
523            f,
524            _marker: PhantomData,
525        }
526    }
527}
528impl<T, U, F> Transducer for MapTransducer<T, U, F>
529where
530    F: Fn(&T) -> U,
531{
532    type Input = T;
533    type Output = U;
534    type State = ();
535    fn start(&self) -> Self::State {}
536    fn relation(
537        &self,
538        _state: &Self::State,
539        input: &Self::Input,
540    ) -> Option<(Self::State, Self::Output)> {
541        Some(((), (self.f)(input)))
542    }
543    fn accept(&self, _state: &Self::State) -> bool {
544        true
545    }
546}
547
548#[derive(Debug, Clone)]
549pub struct FilterMapTransducer<T, U, F>
550where
551    F: Fn(&T) -> Option<U>,
552{
553    f: F,
554    _marker: PhantomData<fn() -> (T, U)>,
555}
556impl<T, U, F> FilterMapTransducer<T, U, F>
557where
558    F: Fn(&T) -> Option<U>,
559{
560    pub fn new(f: F) -> Self {
561        Self {
562            f,
563            _marker: PhantomData,
564        }
565    }
566}
567impl<T, U, F> Transducer for FilterMapTransducer<T, U, F>
568where
569    F: Fn(&T) -> Option<U>,
570{
571    type Input = T;
572    type Output = U;
573    type State = ();
574    fn start(&self) -> Self::State {}
575    fn relation(
576        &self,
577        _state: &Self::State,
578        input: &Self::Input,
579    ) -> Option<(Self::State, Self::Output)> {
580        (self.f)(input).map(|output| ((), output))
581    }
582    fn accept(&self, _state: &Self::State) -> bool {
583        true
584    }
585}
586
587#[derive(Debug, Clone)]
588pub struct EqualTransducer<T>(PhantomData<fn() -> T>);
589impl<T> EqualTransducer<T> {
590    pub fn new() -> Self {
591        Default::default()
592    }
593}
594impl<T> Default for EqualTransducer<T> {
595    fn default() -> Self {
596        Self(PhantomData)
597    }
598}
599impl<T> Transducer for EqualTransducer<T>
600where
601    T: PartialEq,
602{
603    type Input = (T, T);
604    type Output = ();
605    type State = ();
606    fn start(&self) -> Self::State {}
607    fn relation(
608        &self,
609        _state: &Self::State,
610        input: &Self::Input,
611    ) -> Option<(Self::State, Self::Output)> {
612        (input.0 == input.1).then_some(((), ()))
613    }
614    fn accept(&self, _state: &Self::State) -> bool {
615        true
616    }
617}
618
619#[derive(Debug, Clone)]
620/// DFA to accept Less/Greater than (or equal to) in lexicographical order
621pub struct LexicographicalTransducer<T> {
622    ordering: Ordering,
623    equal: bool,
624    _marker: PhantomData<fn() -> T>,
625}
626impl<T> LexicographicalTransducer<T> {
627    pub fn less_than() -> Self {
628        Self {
629            ordering: Ordering::Less,
630            equal: false,
631            _marker: PhantomData,
632        }
633    }
634    pub fn less_than_or_equal() -> Self {
635        Self {
636            ordering: Ordering::Less,
637            equal: true,
638            _marker: PhantomData,
639        }
640    }
641    pub fn greater_than() -> Self {
642        Self {
643            ordering: Ordering::Greater,
644            equal: false,
645            _marker: PhantomData,
646        }
647    }
648    pub fn greater_than_or_equal() -> Self {
649        Self {
650            ordering: Ordering::Greater,
651            equal: true,
652            _marker: PhantomData,
653        }
654    }
655}
656impl<T> Transducer for LexicographicalTransducer<T>
657where
658    T: Ord,
659{
660    type Input = (T, T);
661    type Output = ();
662    /// is equal
663    type State = bool;
664    fn start(&self) -> Self::State {
665        true
666    }
667    fn relation(
668        &self,
669        state: &Self::State,
670        input: &Self::Input,
671    ) -> Option<(Self::State, Self::Output)> {
672        match (state, input.1.cmp(&input.0)) {
673            (true, Ordering::Equal) => Some((true, ())),
674            (true, ord) if ord == self.ordering => None,
675            _ => Some((false, ())),
676        }
677    }
678    fn accept(&self, state: &Self::State) -> bool {
679        self.equal || !state
680    }
681}
682
683#[derive(Debug, Clone)]
684/// DFA to accept Less/Greater than (or equal to) in reversed lexicographical order
685pub struct RevLexicographicalTransducer<T> {
686    ordering: Ordering,
687    equal: bool,
688    _marker: PhantomData<fn() -> T>,
689}
690impl<T> RevLexicographicalTransducer<T> {
691    pub fn less_than() -> Self {
692        Self {
693            ordering: Ordering::Less,
694            equal: false,
695            _marker: PhantomData,
696        }
697    }
698    pub fn less_than_or_equal() -> Self {
699        Self {
700            ordering: Ordering::Less,
701            equal: true,
702            _marker: PhantomData,
703        }
704    }
705    pub fn greater_than() -> Self {
706        Self {
707            ordering: Ordering::Greater,
708            equal: false,
709            _marker: PhantomData,
710        }
711    }
712    pub fn greater_than_or_equal() -> Self {
713        Self {
714            ordering: Ordering::Greater,
715            equal: true,
716            _marker: PhantomData,
717        }
718    }
719}
720impl<T> Transducer for RevLexicographicalTransducer<T>
721where
722    T: Ord,
723{
724    type Input = (T, T);
725    type Output = ();
726    /// accept
727    type State = bool;
728    fn start(&self) -> Self::State {
729        self.equal
730    }
731    fn relation(
732        &self,
733        state: &Self::State,
734        input: &Self::Input,
735    ) -> Option<(Self::State, Self::Output)> {
736        Some((
737            match input.0.cmp(&input.1) {
738                Ordering::Equal => *state,
739                ord => ord == self.ordering,
740            },
741            (),
742        ))
743    }
744    fn accept(&self, state: &Self::State) -> bool {
745        *state
746    }
747}
748
749#[derive(Debug, Clone)]
750pub struct SequenceTransducer<'a, T, A> {
751    sequence: &'a [T],
752    _marker: PhantomData<fn() -> A>,
753}
754impl<'a, T, A> SequenceTransducer<'a, T, A> {
755    pub fn new(sequence: &'a [T]) -> Self {
756        Self {
757            sequence,
758            _marker: PhantomData,
759        }
760    }
761}
762impl<T, A> Transducer for SequenceTransducer<'_, T, A>
763where
764    T: Clone,
765{
766    type Input = A;
767    type Output = T;
768    type State = ();
769    fn start(&self) -> Self::State {}
770    fn relation(
771        &self,
772        _state: &Self::State,
773        _input: &Self::Input,
774    ) -> Option<(Self::State, Self::Output)> {
775        self.sequence.first().map(|c| ((), c.clone()))
776    }
777    fn accept(&self, _state: &Self::State) -> bool {
778        true
779    }
780    fn stepout(&mut self) {
781        if !self.sequence.is_empty() {
782            self.sequence = &self.sequence[1..];
783        }
784    }
785}
786
787#[derive(Debug, Clone)]
788pub struct RevSequenceTransducer<'a, T, A> {
789    sequence: &'a [T],
790    _marker: PhantomData<fn() -> A>,
791}
792impl<'a, T, A> RevSequenceTransducer<'a, T, A> {
793    pub fn new(sequence: &'a [T]) -> Self {
794        Self {
795            sequence,
796            _marker: PhantomData,
797        }
798    }
799}
800impl<T, A> Transducer for RevSequenceTransducer<'_, T, A>
801where
802    T: Clone,
803{
804    type Input = A;
805    type Output = T;
806    type State = ();
807    fn start(&self) -> Self::State {}
808    fn relation(
809        &self,
810        _state: &Self::State,
811        _input: &Self::Input,
812    ) -> Option<(Self::State, Self::Output)> {
813        self.sequence.last().map(|c| ((), c.clone()))
814    }
815    fn accept(&self, _state: &Self::State) -> bool {
816        true
817    }
818    fn stepout(&mut self) {
819        if !self.sequence.is_empty() {
820            self.sequence = &self.sequence[..self.sequence.len() - 1];
821        }
822    }
823}
824
825pub struct IteratorTransducer<I, A>
826where
827    I: Iterator,
828{
829    iter: RefCell<Peekable<I>>,
830    _marker: PhantomData<fn() -> A>,
831}
832impl<I, A> Clone for IteratorTransducer<I, A>
833where
834    I: Iterator + Clone,
835    I::Item: Clone,
836{
837    fn clone(&self) -> Self {
838        Self {
839            iter: self.iter.clone(),
840            _marker: self._marker,
841        }
842    }
843}
844impl<I, A> Debug for IteratorTransducer<I, A>
845where
846    I: Iterator + Debug,
847    I::Item: Debug,
848{
849    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
850        f.debug_struct("IteratorTransducer")
851            .field("iter", &self.iter)
852            .field("_marker", &self._marker)
853            .finish()
854    }
855}
856impl<I, A> IteratorTransducer<I, A>
857where
858    I: Iterator,
859{
860    pub fn new(iter: I) -> Self {
861        Self::new_peekable(iter.peekable())
862    }
863    pub fn new_peekable(iter: Peekable<I>) -> Self {
864        Self {
865            iter: RefCell::new(iter),
866            _marker: PhantomData,
867        }
868    }
869}
870impl<I, A> Transducer for IteratorTransducer<I, A>
871where
872    I: Iterator,
873    I::Item: Clone,
874{
875    type Input = A;
876    type Output = I::Item;
877    type State = ();
878    fn start(&self) -> Self::State {}
879    fn relation(
880        &self,
881        _state: &Self::State,
882        _input: &Self::Input,
883    ) -> Option<(Self::State, Self::Output)> {
884        self.iter.borrow_mut().peek().cloned().map(|c| ((), c))
885    }
886    fn accept(&self, _state: &Self::State) -> bool {
887        true
888    }
889    fn stepout(&mut self) {
890        self.iter.borrow_mut().next();
891    }
892}
893
894#[derive(Debug, Clone)]
895pub struct MonoidalTransducer<M>(PhantomData<fn() -> M>)
896where
897    M: Monoid;
898impl<M> MonoidalTransducer<M>
899where
900    M: Monoid,
901{
902    pub fn new() -> Self {
903        Default::default()
904    }
905}
906impl<M> Default for MonoidalTransducer<M>
907where
908    M: Monoid,
909{
910    fn default() -> Self {
911        Self(PhantomData)
912    }
913}
914impl<M> Transducer for MonoidalTransducer<M>
915where
916    M: Monoid,
917{
918    type Input = M::T;
919    type Output = ();
920    type State = M::T;
921    fn start(&self) -> Self::State {
922        M::unit()
923    }
924    fn relation(
925        &self,
926        state: &Self::State,
927        input: &Self::Input,
928    ) -> Option<(Self::State, Self::Output)> {
929        Some((M::operate(state, input), ()))
930    }
931    fn accept(&self, _state: &Self::State) -> bool {
932        true
933    }
934}
935
936#[derive(Debug, Clone)]
937pub struct IdentityTransducer<I>(PhantomData<fn() -> I>);
938impl<I> IdentityTransducer<I> {
939    pub fn new() -> Self {
940        Default::default()
941    }
942}
943impl<I> Default for IdentityTransducer<I> {
944    fn default() -> Self {
945        Self(PhantomData)
946    }
947}
948impl<I> Transducer for IdentityTransducer<I>
949where
950    I: Clone,
951{
952    type Input = I;
953    type Output = I;
954    type State = ();
955    fn start(&self) -> Self::State {}
956    fn relation(
957        &self,
958        _state: &Self::State,
959        input: &Self::Input,
960    ) -> Option<(Self::State, Self::Output)> {
961        Some(((), input.clone()))
962    }
963    fn accept(&self, _state: &Self::State) -> bool {
964        true
965    }
966}
967
968#[derive(Debug, Clone)]
969pub struct AlwaysAcceptingTransducer<A>(PhantomData<fn() -> A>);
970impl<A> AlwaysAcceptingTransducer<A> {
971    pub fn new() -> Self {
972        Default::default()
973    }
974}
975impl<A> Default for AlwaysAcceptingTransducer<A> {
976    fn default() -> Self {
977        Self(PhantomData)
978    }
979}
980impl<A> Transducer for AlwaysAcceptingTransducer<A> {
981    type Input = A;
982    type Output = ();
983    type State = ();
984    fn start(&self) -> Self::State {}
985    fn relation(
986        &self,
987        _state: &Self::State,
988        _input: &Self::Input,
989    ) -> Option<(Self::State, Self::Output)> {
990        Some(((), ()))
991    }
992    fn accept(&self, _state: &Self::State) -> bool {
993        true
994    }
995}
996
997/// build transducer
998///
999/// - `transducer!(A)`
1000/// - `<= seq`, `seq >=`: [`LexicographicalTransducer::less_than_or_equal()`](`LexicographicalTransducer::less_than_or_equal`) with [`SequenceTransducer`](`SequenceTransducer`)
1001/// - `>= seq`, `seq <=`: [`LexicographicalTransducer::greater_than_or_equal()`](`LexicographicalTransducer::greater_than_or_equal`) with [`SequenceTransducer`](`SequenceTransducer`)
1002/// - `< seq`, `seq >`: [`LexicographicalTransducer::less_than()`](`LexicographicalTransducer::less_than`) with [`SequenceTransducer`](`SequenceTransducer`)
1003/// - `> seq`, `seq <`: [`LexicographicalTransducer::greater_than()`](`LexicographicalTransducer::greater_than`) with [`SequenceTransducer`](`SequenceTransducer`)
1004/// - `!<= seq`, `seq !>=`: [`RevLexicographicalTransducer::less_than_or_equal()`](`RevLexicographicalTransducer::less_than_or_equal`) with [`SequenceTransducer`](`SequenceTransducer`)
1005/// - `!>= seq`, `seq !<=`: [`RevLexicographicalTransducer::greater_than_or_equal()`](`RevLexicographicalTransducer::greater_than_or_equal`) with [`SequenceTransducer`](`SequenceTransducer`)
1006/// - `!< seq`, `seq !>`: [`RevLexicographicalTransducer::less_than()`](`RevLexicographicalTransducer::less_than`) with [`SequenceTransducer`](`SequenceTransducer`)
1007/// - `!> seq`, `seq !<`: [`RevLexicographicalTransducer::greater_than()`](`RevLexicographicalTransducer::greater_than`) with [`SequenceTransducer`](`SequenceTransducer`)
1008/// - `<=`: [`LexicographicalTransducer::less_than_or_equal()`](`LexicographicalTransducer::less_than_or_equal`)
1009/// - `>=`: [`LexicographicalTransducer::greater_than_or_equal()`](`LexicographicalTransducer::greater_than_or_equal`)
1010/// - `<`: [`LexicographicalTransducer::less_than()`](`LexicographicalTransducer::less_than`)
1011/// - `>`: [`LexicographicalTransducer::greater_than()`](`LexicographicalTransducer::greater_than`)
1012/// - `!<=`: [`RevLexicographicalTransducer::less_than_or_equal()`](`RevLexicographicalTransducer::less_than_or_equal`)
1013/// - `!>=`: [`RevLexicographicalTransducer::greater_than_or_equal()`](`RevLexicographicalTransducer::greater_than_or_equal`)
1014/// - `!<`: [`RevLexicographicalTransducer::less_than()`](`RevLexicographicalTransducer::less_than`)
1015/// - `!>`: [`RevLexicographicalTransducer::greater_than()`](`RevLexicographicalTransducer::greater_than`)
1016/// - `=> f g h`: [`FunctionalTransducer::new(f, g, h)`](`FunctionalTransducer`)
1017/// - `@id`: [`IdentityTransducer::new()`](`IdentityTransducer`)
1018/// - `@it e`: [`IteratorTransducer::new(e)`](`IteratorTransducer`)
1019/// - `@map f`: [`MapTransducer::new(f)`](`MapTransducer`)
1020/// - `@fmap f`: [`FilterMapTransducer::new(f)`](`FilterMapTransducer`)
1021/// - `@seq e`: [`SequenceTransducer::new(e)`](`SequenceTransducer`)
1022/// - `@rseq e`: [`RevSequenceTransducer::new(e)`](`RevSequenceTransducer`)
1023/// - `@`: [`AlwaysAcceptingTransducer::new()`](`AlwaysAcceptingTransducer`)
1024/// - `A . B`: [`ChainTransducer((A, B))`](`ChainTransducer`)
1025/// - `A * B`: [`ProductTransducer((A, B))`](`ProductTransducer`)
1026/// - `A & B`: [`IntersectionTransducer((A, B))`](`IntersectionTransducer`)
1027#[macro_export]
1028macro_rules! transducer {
1029    (@check $e:expr)                                         => {{ #[inline(always)] fn check_transucer<T>(fst: T) -> T where T: Transducer { fst } check_transucer($e) }};
1030    (@inner ($($t:tt)*))                                     => { $crate::transducer!(@inner $($t)*) };
1031    (@inner => $f:expr, $g:expr, $h:expr $(,)?)              => { $crate::transducer!(@check FunctionalTransducer::new($f, $g, $h)) };
1032    (@inner = $e:expr)                                       => { $crate::transducer!(((@id & (@seq &$e)) . =)) };
1033    (@inner <= $e:expr)                                      => { $crate::transducer!(((@id & (@seq &$e)) . <=)) };
1034    (@inner >= $e:expr)                                      => { $crate::transducer!(((@id & (@seq &$e)) . >=)) };
1035    (@inner < $e:expr)                                       => { $crate::transducer!(((@id & (@seq &$e)) . <)) };
1036    (@inner > $e:expr)                                       => { $crate::transducer!(((@id & (@seq &$e)) . >)) };
1037    (@inner !<= $e:expr)                                     => { $crate::transducer!(((@id & (@rseq &$e)) . !<=)) };
1038    (@inner !>= $e:expr)                                     => { $crate::transducer!(((@id & (@rseq &$e)) . !>=)) };
1039    (@inner !< $e:expr)                                      => { $crate::transducer!(((@id & (@rseq &$e)) . !<)) };
1040    (@inner !> $e:expr)                                      => { $crate::transducer!(((@id & (@rseq &$e)) . !>)) };
1041    (@inner $e:ident =)                                      => { $crate::transducer!((((@seq &$e) & @id) . =)) };
1042    (@inner $e:ident <=)                                     => { $crate::transducer!((((@seq &$e) & @id) . <=)) };
1043    (@inner $e:ident >=)                                     => { $crate::transducer!((((@seq &$e) & @id) . >=)) };
1044    (@inner $e:ident <)                                      => { $crate::transducer!((((@seq &$e) & @id) . <)) };
1045    (@inner $e:ident >)                                      => { $crate::transducer!((((@seq &$e) & @id) . >)) };
1046    (@inner $e:ident !<=)                                    => { $crate::transducer!((((@rseq &$e) & @id) . !<=)) };
1047    (@inner $e:ident !>=)                                    => { $crate::transducer!((((@rseq &$e) & @id) . !>=)) };
1048    (@inner $e:ident !<)                                     => { $crate::transducer!((((@rseq &$e) & @id) . !<)) };
1049    (@inner $e:ident !>)                                     => { $crate::transducer!((((@rseq &$e) & @id) . !>)) };
1050    (@inner =)                                               => { $crate::transducer!(@check EqualTransducer::new()) };
1051    (@inner <=)                                              => { $crate::transducer!(@check LexicographicalTransducer::less_than_or_equal()) };
1052    (@inner >=)                                              => { $crate::transducer!(@check LexicographicalTransducer::greater_than_or_equal()) };
1053    (@inner <)                                               => { $crate::transducer!(@check LexicographicalTransducer::less_than()) };
1054    (@inner >)                                               => { $crate::transducer!(@check LexicographicalTransducer::greater_than()) };
1055    (@inner !<=)                                             => { $crate::transducer!(@check RevLexicographicalTransducer::less_than_or_equal()) };
1056    (@inner !>=)                                             => { $crate::transducer!(@check RevLexicographicalTransducer::greater_than_or_equal()) };
1057    (@inner !<)                                              => { $crate::transducer!(@check RevLexicographicalTransducer::less_than()) };
1058    (@inner !>)                                              => { $crate::transducer!(@check RevLexicographicalTransducer::greater_than()) };
1059    (@inner @id)                                             => { $crate::transducer!(@check IdentityTransducer::new()) };
1060    (@inner @it $e:expr)                                     => { $crate::transducer!(@check IteratorTransducer::new($e)) };
1061    (@inner @map $f:expr)                                    => { $crate::transducer!(@check MapTransducer::new($f)) };
1062    (@inner @fmap $f:expr)                                   => { $crate::transducer!(@check FilterMapTransducer::new($f)) };
1063    (@inner @seq $e:expr)                                    => { $crate::transducer!(@check SequenceTransducer::new($e)) };
1064    (@inner @rseq $e:expr)                                   => { $crate::transducer!(@check RevSequenceTransducer::new($e)) };
1065    (@inner @<$t:ty>)                                        => { $crate::transducer!(@check AlwaysAcceptingTransducer::<$t>::new()) };
1066    (@inner @)                                               => { $crate::transducer!(@check AlwaysAcceptingTransducer::new()) };
1067    (@inner $($t:tt)*)                                       => { $crate::transducer!(@inter [] [] $($t)*) };
1068    (@inter [$([$($a:tt)*])*])                               => { $crate::transducer!(@check IntersectionTransducer(($($crate::transducer!(@inner $($a)*),)*))) };
1069    (@inter [] [$($b:tt)*])                                  => { $crate::transducer!(@prod [] [] $($b)*) };
1070    (@inter [$($a:tt)*] [$($b:tt)*])                         => { $crate::transducer!(@inter [$($a)* [$($b)*]]) };
1071    (@inter [$($a:tt)*] [$($b:tt)*] & $($t:tt)*)             => { $crate::transducer!(@inter [$($a)* [$($b)*]] [] $($t)*) };
1072    (@inter [$($a:tt)*] [$($b:tt)*] $op:tt $($t:tt)*)        => { $crate::transducer!(@inter [$($a)*] [$($b)* $op] $($t)*) };
1073    (@prod [$([$($a:tt)*])*])                                => { $crate::transducer!(@check ProductTransducer(($($crate::transducer!(@inner $($a)*),)*))) };
1074    (@prod [] [$($b:tt)*])                                   => { $crate::transducer!(@chain [] [] $($b)*) };
1075    (@prod [$($a:tt)*] [$($b:tt)*])                          => { $crate::transducer!(@prod [$($a)* [$($b)*]]) };
1076    (@prod [$($a:tt)*] [$($b:tt)*] * $($t:tt)*)              => { $crate::transducer!(@prod [$($a)* [$($b)*]] [] $($t)*) };
1077    (@prod [$($a:tt)*] [$($b:tt)*] $op:tt $($t:tt)*)         => { $crate::transducer!(@prod [$($a)*] [$($b)* $op] $($t)*) };
1078    (@chain [$([$($a:tt)*])*])                               => { $crate::transducer!(@check ChainTransducer(($($crate::transducer!(@inner $($a)*),)*))) };
1079    (@chain [] [$($b:tt)*])                                  => { $crate::transducer!(@check $($b)*) };
1080    (@chain [$($a:tt)*] [$($b:tt)*])                         => { $crate::transducer!(@chain [$($a)* [$($b)*]]) };
1081    (@chain [$($a:tt)*] [$($b:tt)*] . $($t:tt)*)             => { $crate::transducer!(@chain [$($a)* [$($b)*]] [] $($t)*) };
1082    (@chain [$($a:tt)*] [$($b:tt)*] $op:tt $($t:tt)*)        => { $crate::transducer!(@chain [$($a)*] [$($b)* $op] $($t)*) };
1083    (@id $($t:tt)*)                                          => { $crate::transducer!(@inner @id $($t)*) };
1084    (@it $($t:tt)*)                                          => { $crate::transducer!(@inner @it $($t)*) };
1085    (@map $($t:tt)*)                                         => { $crate::transducer!(@inner @map $($t)*) };
1086    (@fmap $($t:tt)*)                                        => { $crate::transducer!(@inner @fmap $($t)*) };
1087    (@seq $($t:tt)*)                                         => { $crate::transducer!(@inner @seq $($t)*) };
1088    (@rseq $($t:tt)*)                                        => { $crate::transducer!(@inner @rseq $($t)*) };
1089    (@$tag:ident $($t:tt)*)                                  => { ::std::compile_error!(::std::stringify!($tag, $($t)*)) };
1090    ($($t:tt)*)                                              => {{ $crate::transducer!(@inner $($t)*) }};
1091}
1092
1093#[cfg(test)]
1094mod tests {
1095    use super::*;
1096    use crate::{
1097        algebra::AdditiveOperation,
1098        tools::{NotEmptySegment, ToDigitSequence, Xorshift},
1099        transducer,
1100    };
1101
1102    #[test]
1103    fn test_equal_transducer() {
1104        type A = AdditiveOperation<usize>;
1105        const Q: usize = 100;
1106        let mut rng = Xorshift::default();
1107        for ((l, r), radix) in rng
1108            .random_iter((NotEmptySegment(10usize.pow(9)), 2..=10))
1109            .take(Q)
1110        {
1111            let rr = r.to_digit_sequence_radix(radix);
1112            let ll = l.to_digit_sequence_radix_len(radix, rr.len());
1113            let n = r - l;
1114            assert_eq!(
1115                n,
1116                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & =)
1117                    .dp::<A>(1)
1118                    .with_hashmap()
1119                    .run(
1120                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1121                        ll.len()
1122                    )
1123            );
1124        }
1125    }
1126
1127    #[test]
1128    fn test_lexicographical_transducer() {
1129        type A = AdditiveOperation<usize>;
1130        const Q: usize = 100;
1131        let mut rng = Xorshift::default();
1132        for ((l, r), radix) in rng
1133            .random_iter((NotEmptySegment(10usize.pow(9)), 2..=10))
1134            .take(Q)
1135        {
1136            let rr = r.to_digit_sequence_radix(radix);
1137            let ll = l.to_digit_sequence_radix_len(radix, rr.len());
1138            let n = r - l;
1139            assert_eq!(
1140                n * (n + 1) / 2,
1141                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & <=)
1142                    .dp::<A>(1)
1143                    .with_hashmap()
1144                    .run(
1145                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1146                        ll.len()
1147                    )
1148            );
1149            assert_eq!(
1150                n * (n + 1) / 2,
1151                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & >=)
1152                    .dp::<A>(1)
1153                    .with_hashmap()
1154                    .run(
1155                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1156                        ll.len()
1157                    )
1158            );
1159            assert_eq!(
1160                n * (n - 1) / 2,
1161                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & <)
1162                    .dp::<A>(1)
1163                    .with_hashmap()
1164                    .run(
1165                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1166                        ll.len()
1167                    )
1168            );
1169            assert_eq!(
1170                n * (n - 1) / 2,
1171                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & >)
1172                    .dp::<A>(1)
1173                    .with_hashmap()
1174                    .run(
1175                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1176                        ll.len()
1177                    )
1178            );
1179        }
1180    }
1181
1182    #[test]
1183    fn test_revlexicographical_transducer() {
1184        type A = AdditiveOperation<usize>;
1185        const Q: usize = 100;
1186        let mut rng = Xorshift::default();
1187        for ((l, r), radix) in rng
1188            .random_iter((NotEmptySegment(10usize.pow(9)), 2..=10))
1189            .take(Q)
1190        {
1191            let rr = r.to_digit_sequence_radix(radix);
1192            let ll = l.to_digit_sequence_radix_len(radix, rr.len());
1193            let n = r - l;
1194            assert_eq!(
1195                n * (n + 1) / 2,
1196                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !<=)
1197                    .dp::<A>(1)
1198                    .with_hashmap()
1199                    .run(
1200                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1201                        ll.len()
1202                    )
1203            );
1204            assert_eq!(
1205                n * (n + 1) / 2,
1206                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !>=)
1207                    .dp::<A>(1)
1208                    .with_hashmap()
1209                    .run(
1210                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1211                        ll.len()
1212                    )
1213            );
1214            assert_eq!(
1215                n * (n - 1) / 2,
1216                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !<)
1217                    .dp::<A>(1)
1218                    .with_hashmap()
1219                    .run(
1220                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1221                        ll.len()
1222                    )
1223            );
1224            assert_eq!(
1225                n * (n - 1) / 2,
1226                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !>)
1227                    .dp::<A>(1)
1228                    .with_hashmap()
1229                    .run(
1230                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1231                        ll.len()
1232                    )
1233            );
1234        }
1235    }
1236
1237    #[test]
1238    fn test_lexicographical_sequence() {
1239        type A = AdditiveOperation<usize>;
1240        const Q: usize = 100;
1241        let mut rng = Xorshift::default();
1242        for (n, r) in rng.random_iter((0..10usize.pow(18), 2..=10)).take(Q) {
1243            let nd = n.to_digit_sequence_radix(r);
1244            assert_eq!(
1245                n + 1,
1246                transducer!(<= nd)
1247                    .dp::<A>(1)
1248                    .with_hashmap()
1249                    .run(|| 0..r, nd.len())
1250            );
1251            assert_eq!(
1252                n,
1253                transducer!(< nd)
1254                    .dp::<A>(1)
1255                    .with_hashmap()
1256                    .run(|| 0..r, nd.len())
1257            );
1258            assert_eq!(
1259                r.pow(nd.len() as _) - n,
1260                transducer!(>= nd)
1261                    .dp::<A>(1)
1262                    .with_hashmap()
1263                    .run(|| 0..r, nd.len())
1264            );
1265            assert_eq!(
1266                r.pow(nd.len() as _) - n - 1,
1267                transducer!(> nd)
1268                    .dp::<A>(1)
1269                    .with_hashmap()
1270                    .run(|| 0..r, nd.len())
1271            );
1272        }
1273    }
1274
1275    #[test]
1276    fn test_revlexicographical_sequence() {
1277        type A = AdditiveOperation<usize>;
1278        const Q: usize = 100;
1279        let mut rng = Xorshift::default();
1280        for (n, r) in rng.random_iter((0..10usize.pow(18), 2..=10)).take(Q) {
1281            let nd = n.to_digit_sequence_radix(r);
1282            assert_eq!(
1283                n + 1,
1284                transducer!(!<= nd)
1285                    .dp::<A>(1)
1286                    .with_hashmap()
1287                    .run(|| 0..r, nd.len())
1288            );
1289            assert_eq!(
1290                n,
1291                transducer!(!< nd)
1292                    .dp::<A>(1)
1293                    .with_hashmap()
1294                    .run(|| 0..r, nd.len())
1295            );
1296            assert_eq!(
1297                r.pow(nd.len() as _) - n,
1298                transducer!(!>= nd)
1299                    .dp::<A>(1)
1300                    .with_hashmap()
1301                    .run(|| 0..r, nd.len())
1302            );
1303            assert_eq!(
1304                r.pow(nd.len() as _) - n - 1,
1305                transducer!(!> nd)
1306                    .dp::<A>(1)
1307                    .with_hashmap()
1308                    .run(|| 0..r, nd.len())
1309            );
1310        }
1311    }
1312
1313    #[test]
1314    fn test_prim() {
1315        type A = AdditiveOperation<usize>;
1316        const Q: usize = 100;
1317        let mut rng = Xorshift::default();
1318        for (n, r, c) in rng
1319            .random_iter((0..10usize.pow(18), 2..=10, 2..200))
1320            .take(Q)
1321        {
1322            let nd = n.to_digit_sequence_radix(r);
1323            let fst = transducer!((< nd) & (=> || 0usize, |s, a| Some(((s * r + a) % c, ())), |s| *s == 0));
1324            assert_eq!(
1325                n.div_ceil(c),
1326                fst.clone().dp::<A>(1).with_hashmap().run(|| 0..r, nd.len())
1327            );
1328
1329            assert_eq!(
1330                n.div_ceil(c),
1331                fst.dp::<A>(1)
1332                    .with_vecmap(|&((_, s0), s1): &((((), ()), bool), usize)| s1 * 2 + s0 as usize)
1333                    .run(|| 0..r, nd.len())
1334            );
1335        }
1336    }
1337
1338    #[test]
1339    fn test_add_lte() {
1340        type A = AdditiveOperation<usize>;
1341        const Q: usize = 100;
1342        let mut rng = Xorshift::default();
1343        // (x, y) where x + a <= y, l <= x, y <= r
1344        for ((l, r), a) in rng
1345            .random_iter((NotEmptySegment(100usize), 0usize..100))
1346            .take(Q)
1347        {
1348            let ll = l.to_digit_sequence_radix_len(2, 20);
1349            let rr = r.to_digit_sequence_radix_len(2, 20);
1350            let aa = a.to_digit_sequence_radix_len(2, 20);
1351
1352            let fst = transducer!(
1353                ((ll !<=) * (!<= rr)) & (
1354                    (
1355                        (
1356                            ((@rseq &aa) & (@id))
1357                            . (@map |&(a, (x, _y))| x + a)
1358                            . (=> || 0usize, |s, i| Some(((s + i) / 2, (s + i) % 2)), |s| *s == 0)
1359                        ) & (@map |&(_x, y)| y)
1360                    ) . (!<=)
1361                )
1362            );
1363
1364            let result = fst
1365                .dp::<A>(1)
1366                .with_hashmap()
1367                .run(|| (0usize..4).map(|bit| (bit & 1, (bit >> 1) & 1)), 20);
1368            let expected: usize = (l..=r)
1369                .map(|x| (l..=r).filter(|&y| x + a <= y).count())
1370                .sum();
1371            assert_eq!(expected, result);
1372        }
1373    }
1374}
competitive/data_structure/transducer.rs

competitive/data_structure/
transducer.rs
