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>;
18
19pub trait Transducer {
20    type Input;
21    type Output;
22    type State;
23    fn start(&self) -> Self::State;
24    fn relation(
25        &self,
26        state: &Self::State,
27        input: &Self::Input,
28    ) -> Option<(Self::State, Self::Output)>;
29    fn accept(&self, state: &Self::State) -> bool;
30    fn stepout(&mut self) {}
31    fn dp<M>(self, init: M::T) -> InitTransducerDp<M, Self>
32    where
33        Self: Sized,
34        M: Monoid,
35    {
36        InitTransducerDp::new(self, init)
37    }
38
39    fn intersection<U>(self, other: U) -> IntersectionTransducer<(Self, U)>
40    where
41        Self: Sized,
42        U: Transducer<Input = Self::Input>,
43    {
44        IntersectionTransducer((self, other))
45    }
46    fn product<U>(self, other: U) -> ProductTransducer<(Self, U)>
47    where
48        Self: Sized,
49        U: Transducer,
50    {
51        ProductTransducer((self, other))
52    }
53    fn chain<U>(self, other: U) -> ChainTransducer<(Self, U)>
54    where
55        Self: Sized,
56        U: Transducer<Input = Self::Output>,
57    {
58        ChainTransducer((self, other))
59    }
60    fn with_input(self) -> IntersectionTransducer<(Self, IdentityTransducer<Self::Input>)>
61    where
62        Self: Sized,
63    {
64        IntersectionTransducer((self, IdentityTransducer::new()))
65    }
66    fn map<U, F>(self, f: F) -> MapTransducer<Self, U, F>
67    where
68        Self: Sized,
69        F: Fn(&Self::Output) -> U,
70    {
71        MapTransducer::new(self, f)
72    }
73    fn try_map<U, F>(self, f: F) -> TryMapTransducer<Self, U, F>
74    where
75        Self: Sized,
76        F: Fn(&Self::Output) -> Option<U>,
77    {
78        TryMapTransducer::new(self, f)
79    }
80    fn retain<F>(self, pred: F) -> RetainTransducer<Self, F>
81    where
82        Self: Sized,
83        F: Fn(&Self::Output) -> bool,
84    {
85        RetainTransducer::new(self, pred)
86    }
87    fn with_fold<A, F>(self, init: A, f: F) -> FoldTransducer<Self, A, F>
88    where
89        Self: Sized,
90        A: Clone,
91        F: Fn(&A, &Self::Output) -> A,
92    {
93        FoldTransducer::new(self, init, f)
94    }
95    fn with_try_fold<A, F>(self, init: A, f: F) -> TryFoldTransducer<Self, A, F>
96    where
97        Self: Sized,
98        A: Clone,
99        F: Fn(&A, &Self::Output) -> Option<A>,
100    {
101        TryFoldTransducer::new(self, init, f)
102    }
103    fn accepting<F>(self, pred: F) -> AcceptTransducer<Self, F>
104    where
105        Self: Sized,
106        F: Fn(&Self::State) -> bool,
107    {
108        AcceptTransducer::new(self, pred)
109    }
110}
111
112#[derive(Debug, Clone)]
113pub struct InitTransducerDp<M, A>
114where
115    M: Monoid,
116    A: Transducer,
117{
118    fst: A,
119    init: M::T,
120}
121
122impl<M, A> InitTransducerDp<M, A>
123where
124    M: Monoid,
125    A: Transducer,
126{
127    pub fn new(fst: A, init: M::T) -> Self {
128        Self { fst, init }
129    }
130    pub fn with_factory<F>(self, factory: F) -> Transducerdp<M, A, F::Container>
131    where
132        F: ContainerFactory<Container: Container<Key = A::State, Value = M::T>>,
133    {
134        Transducerdp::new(self.fst, self.init, factory)
135    }
136    pub fn with_hashmap(self) -> Transducerdp<M, A, HashMap<A::State, M::T>>
137    where
138        A: Transducer<State: Eq + Hash>,
139    {
140        self.with_factory(HashMapFactory::default())
141    }
142    pub fn with_vecmap<F>(
143        self,
144        key_to_index: F,
145    ) -> Transducerdp<M, A, VecMap<false, A::State, M::T, F>>
146    where
147        F: Fn(&A::State) -> usize + Clone,
148    {
149        self.with_factory(VecMapFactory::new(key_to_index))
150    }
151    pub fn with_fixed_vecmap<F>(
152        self,
153        key_to_index: F,
154        len: usize,
155    ) -> Transducerdp<M, A, VecMap<true, A::State, M::T, F>>
156    where
157        F: Fn(&A::State) -> usize + Clone,
158    {
159        self.with_factory(FixedVecMapFactory::new(key_to_index, len))
160    }
161}
162
163#[derive(Clone)]
164pub struct Transducerdp<M, T, C>
165where
166    M: Monoid,
167    T: Transducer,
168    C: Container<Key = T::State, Value = M::T>,
169{
170    fst: T,
171    pub dp: C,
172    ndp: C,
173    _marker: PhantomData<fn() -> M>,
174}
175
176impl<M, T, C> Debug for Transducerdp<M, T, C>
177where
178    M: Monoid<T: Debug>,
179    T: Transducer<State: Debug> + Debug,
180    C: Container<Key = T::State, Value = M::T> + Debug,
181{
182    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
183        f.debug_struct("Transducerdp")
184            .field("fst", &self.fst)
185            .field("dp", &self.dp)
186            .field("ndp", &self.ndp)
187            .finish()
188    }
189}
190
191impl<M, T, C> Transducerdp<M, T, C>
192where
193    M: Monoid,
194    T: Transducer,
195    C: Container<Key = T::State, Value = M::T>,
196{
197    pub fn new<F>(fst: T, init: M::T, factory: F) -> Self
198    where
199        F: ContainerFactory<Container = C>,
200    {
201        let mut dp = factory.create_container();
202        let ndp = factory.create_container();
203        dp.insert(fst.start(), init);
204        Self {
205            fst,
206            dp,
207            ndp,
208            _marker: PhantomData,
209        }
210    }
211    pub fn step<S, I, B>(&mut self, mut sigma: S)
212    where
213        S: FnMut() -> I,
214        I: IntoIterator<Item = B>,
215        B: Borrow<T::Input>,
216    {
217        for (state, value) in self.dp.drain() {
218            for input in sigma() {
219                if let Some((nstate, _)) = self.fst.relation(&state, input.borrow()) {
220                    self.ndp
221                        .entry(nstate)
222                        .and_modify(|acc| M::operate_assign(acc, &value))
223                        .or_insert_with(|| value.clone());
224                }
225            }
226        }
227        swap(&mut self.dp, &mut self.ndp);
228        self.fst.stepout();
229    }
230    pub fn step_effect<S, I, B, F>(&mut self, mut sigma: S, mut effect: F)
231    where
232        S: FnMut() -> I,
233        I: IntoIterator<Item = B>,
234        B: Borrow<T::Input>,
235        F: FnMut(&M::T, &T::Output) -> M::T,
236    {
237        for (state, value) in self.dp.drain() {
238            for input in sigma() {
239                if let Some((nstate, output)) = self.fst.relation(&state, input.borrow()) {
240                    let nvalue = effect(&value, &output);
241                    self.ndp
242                        .entry(nstate)
243                        .and_modify(|acc| M::operate_assign(acc, &nvalue))
244                        .or_insert(nvalue);
245                }
246            }
247        }
248        swap(&mut self.dp, &mut self.ndp);
249        self.fst.stepout();
250    }
251    pub fn fold_accept(&self) -> M::T {
252        let mut acc = M::unit();
253        for (state, value) in self.dp.iter() {
254            if self.fst.accept(state) {
255                M::operate_assign(&mut acc, value);
256            }
257        }
258        acc
259    }
260    pub fn map_fold_accept<U, F, D>(&self, mut f: F, mut map: D) -> D
261    where
262        F: FnMut(&T::State) -> U,
263        D: Container<Key = U, Value = M::T>,
264    {
265        for (state, value) in self.dp.iter() {
266            if self.fst.accept(state) {
267                map.entry(f(state))
268                    .and_modify(|acc| M::operate_assign(acc, value))
269                    .or_insert_with(|| value.clone());
270            }
271        }
272        map
273    }
274    pub fn run<S, I, B>(&mut self, mut sigma: S, len: usize) -> M::T
275    where
276        S: FnMut() -> I,
277        I: IntoIterator<Item = B>,
278        B: Borrow<T::Input>,
279    {
280        for _ in 0..len {
281            self.step(&mut sigma);
282        }
283        self.fold_accept()
284    }
285    pub fn run_effect<S, I, B, F>(&mut self, mut sigma: S, len: usize, mut effect: F) -> M::T
286    where
287        S: FnMut() -> I,
288        I: IntoIterator<Item = B>,
289        B: Borrow<T::Input>,
290        F: FnMut(&M::T, &T::Output) -> M::T,
291    {
292        for _ in 0..len {
293            self.step_effect(&mut sigma, &mut effect);
294        }
295        self.fold_accept()
296    }
297}
298
299#[derive(Debug, Clone)]
300pub struct IntersectionTransducer<Tuple>(pub Tuple);
301
302macro_rules! impl_intersection_transducer {
303    (@impl $($T:ident)*, $($a:ident)*, $($b:ident)*) => {
304        impl<A, $($T),*> Transducer for IntersectionTransducer<($($T,)*)>
305        where
306            $($T: Transducer<Input = A>,)*
307        {
308            type Input = A;
309            type Output = ($($T::Output,)*);
310            type State = ($($T::State,)*);
311            fn start(&self) -> Self::State {
312                let Self(($($a,)*)) = self;
313                ($($a.start(),)*)
314            }
315            fn relation(&self, state: &Self::State, input: &Self::Input) -> Option<(Self::State, Self::Output)> {
316                let Self(($($a,)*)) = self;
317                let ($($b,)*) = state;
318                match ($($a.relation($b, input),)*) {
319                    ($(Some(($a, $b)),)*) => Some((($($a,)*), ($($b,)*))),
320                    _ => None,
321                }
322            }
323            fn accept(&self, state: &Self::State) -> bool {
324                let Self(($($a,)*)) = self;
325                let ($($b,)*) = state;
326                $($a.accept($b))&&*
327            }
328            fn stepout(&mut self) {
329                let Self(($($a,)*)) = self;
330                $($a.stepout();)*
331            }
332        }
333    };
334    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $TT:ident $aa:ident $bb:ident) => {
335        impl_intersection_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb);
336    };
337    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $TT:ident $aa:ident $bb:ident $($tt:tt)*) => {
338        impl_intersection_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb);
339        impl_intersection_transducer!(@inc $($T)* $TT, $($a)* $aa, $($b)* $bb, $($tt)*);
340    };
341    ($($tt:tt)*) => {
342        impl_intersection_transducer!(@inc , , , $($tt)*);
343    };
344}
345impl_intersection_transducer!(
346    T0 a0 b0
347    T1 a1 b1
348    T2 a2 b2
349    T3 a3 b3
350    T4 a4 b4
351    T5 a5 b5
352    T6 a6 b6
353    T7 a7 b7
354    T8 a8 b8
355    T9 a9 b9
356);
357
358#[derive(Debug, Clone)]
359pub struct ProductTransducer<Tuple>(pub Tuple);
360
361macro_rules! impl_product_transducer {
362    (@impl $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*) => {
363        impl<$($T),*> Transducer for ProductTransducer<($($T,)*)>
364        where
365            $($T: Transducer,)*
366        {
367            type Input = ($($T::Input,)*);
368            type Output = ($($T::Output,)*);
369            type State = ($($T::State,)*);
370            fn start(&self) -> Self::State {
371                let Self(($($a,)*)) = self;
372                ($($a.start(),)*)
373            }
374            fn relation(&self, state: &Self::State, ($($c,)*): &Self::Input) -> Option<(Self::State, Self::Output)> {
375                let Self(($($a,)*)) = self;
376                let ($($b,)*) = state;
377                match ($($a.relation($b, $c),)*) {
378                    ($(Some(($a, $b)),)*) => Some((($($a,)*), ($($b,)*))),
379                    _ => None,
380                }
381            }
382            fn accept(&self, state: &Self::State) -> bool {
383                let Self(($($a,)*)) = self;
384                let ($($b,)*) = state;
385                $($a.accept($b))&&*
386            }
387            fn stepout(&mut self) {
388                let Self(($($a,)*)) = self;
389                $($a.stepout();)*
390            }
391        }
392    };
393    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident) => {
394        impl_product_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
395    };
396    (@inc $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident $($tt:tt)*) => {
397        impl_product_transducer!(@impl $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
398        impl_product_transducer!(@inc $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc, $($tt)*);
399    };
400    ($($tt:tt)*) => {
401        impl_product_transducer!(@inc , , , , $($tt)*);
402    };
403}
404impl_product_transducer!(
405    T0 a0 b0 c0
406    T1 a1 b1 c1
407    T2 a2 b2 c2
408    T3 a3 b3 c3
409    T4 a4 b4 c4
410    T5 a5 b5 c5
411    T6 a6 b6 c6
412    T7 a7 b7 c7
413    T8 a8 b8 c8
414    T9 a9 b9 c9
415);
416
417#[derive(Debug, Clone)]
418pub struct ChainTransducer<Tuple>(pub Tuple);
419
420macro_rules! impl_chain_transducer {
421    (@impl $T_head:ident, $($T_tail:ident)*, $($T_init:ident)*, $T_last:ident, $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*) => {
422        impl<$($T),*> Transducer for ChainTransducer<($($T,)*)>
423        where
424            $T_head: Transducer,
425            $($T_tail: Transducer<Input = $T_init::Output>,)*
426        {
427            type Input = $T_head::Input;
428            type Output = $T_last::Output;
429            type State = ($($T::State,)*);
430            fn start(&self) -> Self::State {
431                let Self(($($a,)*)) = self;
432                ($($a.start(),)*)
433            }
434            fn relation(&self, state: &Self::State, input: &Self::Input) -> Option<(Self::State, Self::Output)> {
435                let Self(($($a,)*)) = self;
436                let ($($b,)*) = state;
437                $(let ($c, input) = $a.relation($b, &input)?;)*
438                Some((($($c,)*), input))
439            }
440            fn accept(&self, state: &Self::State) -> bool {
441                let Self(($($a,)*)) = self;
442                let ($($b,)*) = state;
443                $($a.accept($b))&&*
444            }
445            fn stepout(&mut self) {
446                let Self(($($a,)*)) = self;
447                $($a.stepout();)*
448            }
449        }
450    };
451    (@inc $T0:ident $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident) => {
452        impl_chain_transducer!(@impl $T0, $($T)* $TT, $T0 $($T)*, $TT, $T0 $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
453    };
454    (@inc , $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident $($tt:tt)*) => {
455        impl_chain_transducer!(@impl $TT, , , $TT,  $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
456        impl_chain_transducer!(@inc $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc, $($tt)*);
457    };
458    (@inc $T0:ident $($T:ident)*, $($a:ident)*, $($b:ident)*, $($c:ident)*, $TT:ident $aa:ident $bb:ident $cc:ident $($tt:tt)*) => {
459        impl_chain_transducer!(@impl $T0, $($T)* $TT, $T0 $($T)*, $TT, $T0 $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc);
460        impl_chain_transducer!(@inc $T0 $($T)* $TT, $($a)* $aa, $($b)* $bb, $($c)* $cc, $($tt)*);
461    };
462    ($($tt:tt)*) => {
463        impl_chain_transducer!(@inc , , , , $($tt)*);
464    };
465}
466impl_chain_transducer!(
467    T0 a0 b0 c0
468    T1 a1 b1 c1
469    T2 a2 b2 c2
470    T3 a3 b3 c3
471    T4 a4 b4 c4
472    T5 a5 b5 c5
473    T6 a6 b6 c6
474    T7 a7 b7 c7
475    T8 a8 b8 c8
476    T9 a9 b9 c9
477);
478
479#[derive(Debug, Clone)]
480pub struct FunctionalTransducer<I, O, S, F, G, H>
481where
482    F: Fn() -> S,
483    G: Fn(&S, &I) -> Option<(S, O)>,
484    H: Fn(&S) -> bool,
485{
486    fn_start: F,
487    fn_relation: G,
488    fn_accept: H,
489    _marker: Marker<(I, O, S)>,
490}
491impl<I, O, S, F, G, H> FunctionalTransducer<I, O, S, F, G, H>
492where
493    F: Fn() -> S,
494    G: Fn(&S, &I) -> Option<(S, O)>,
495    H: Fn(&S) -> bool,
496{
497    pub fn new(fn_start: F, fn_relation: G, fn_accept: H) -> Self {
498        Self {
499            fn_start,
500            fn_relation,
501            fn_accept,
502            _marker: PhantomData,
503        }
504    }
505}
506impl<I, O, S, F, G, H> Transducer for FunctionalTransducer<I, O, S, F, G, H>
507where
508    F: Fn() -> S,
509    G: Fn(&S, &I) -> Option<(S, O)>,
510    H: Fn(&S) -> bool,
511{
512    type Input = I;
513    type Output = O;
514    type State = S;
515    fn start(&self) -> Self::State {
516        (self.fn_start)()
517    }
518    fn relation(
519        &self,
520        state: &Self::State,
521        input: &Self::Input,
522    ) -> Option<(Self::State, Self::Output)> {
523        (self.fn_relation)(state, input)
524    }
525    fn accept(&self, state: &Self::State) -> bool {
526        (self.fn_accept)(state)
527    }
528}
529
530#[derive(Debug, Clone)]
531pub struct MapTransducer<T, U, F> {
532    inner: T,
533    f: F,
534    _marker: Marker<U>,
535}
536impl<T, U, F> MapTransducer<T, U, F> {
537    pub fn new(inner: T, f: F) -> Self {
538        Self {
539            inner,
540            f,
541            _marker: PhantomData,
542        }
543    }
544}
545impl<T, U, F> Transducer for MapTransducer<T, U, F>
546where
547    T: Transducer,
548    F: Fn(&T::Output) -> U,
549{
550    type Input = T::Input;
551    type Output = U;
552    type State = T::State;
553    fn start(&self) -> Self::State {
554        self.inner.start()
555    }
556    fn relation(
557        &self,
558        state: &Self::State,
559        input: &Self::Input,
560    ) -> Option<(Self::State, Self::Output)> {
561        let (next_state, output) = self.inner.relation(state, input)?;
562        Some((next_state, (self.f)(&output)))
563    }
564    fn accept(&self, state: &Self::State) -> bool {
565        self.inner.accept(state)
566    }
567    fn stepout(&mut self) {
568        self.inner.stepout();
569    }
570}
571
572#[derive(Debug, Clone)]
573pub struct TryMapTransducer<T, U, F> {
574    inner: T,
575    f: F,
576    _marker: Marker<U>,
577}
578impl<T, U, F> TryMapTransducer<T, U, F> {
579    pub fn new(inner: T, f: F) -> Self {
580        Self {
581            inner,
582            f,
583            _marker: PhantomData,
584        }
585    }
586}
587impl<T, U, F> Transducer for TryMapTransducer<T, U, F>
588where
589    T: Transducer,
590    F: Fn(&T::Output) -> Option<U>,
591{
592    type Input = T::Input;
593    type Output = U;
594    type State = T::State;
595    fn start(&self) -> Self::State {
596        self.inner.start()
597    }
598    fn relation(
599        &self,
600        state: &Self::State,
601        input: &Self::Input,
602    ) -> Option<(Self::State, Self::Output)> {
603        let (next_state, output) = self.inner.relation(state, input)?;
604        (self.f)(&output).map(|output| (next_state, output))
605    }
606    fn accept(&self, state: &Self::State) -> bool {
607        self.inner.accept(state)
608    }
609    fn stepout(&mut self) {
610        self.inner.stepout();
611    }
612}
613
614#[derive(Debug, Clone)]
615pub struct RetainTransducer<T, F> {
616    inner: T,
617    pred: F,
618}
619impl<T, F> RetainTransducer<T, F> {
620    pub fn new(inner: T, pred: F) -> Self {
621        Self { inner, pred }
622    }
623}
624impl<T, F> Transducer for RetainTransducer<T, F>
625where
626    T: Transducer,
627    F: Fn(&T::Output) -> bool,
628{
629    type Input = T::Input;
630    type Output = T::Output;
631    type State = T::State;
632    fn start(&self) -> Self::State {
633        self.inner.start()
634    }
635    fn relation(
636        &self,
637        state: &Self::State,
638        input: &Self::Input,
639    ) -> Option<(Self::State, Self::Output)> {
640        let (next_state, output) = self.inner.relation(state, input)?;
641        (self.pred)(&output).then_some((next_state, output))
642    }
643    fn accept(&self, state: &Self::State) -> bool {
644        self.inner.accept(state)
645    }
646    fn stepout(&mut self) {
647        self.inner.stepout();
648    }
649}
650
651#[derive(Debug, Clone)]
652pub struct FoldTransducer<T, A, F> {
653    inner: T,
654    init: A,
655    f: F,
656}
657impl<T, A, F> FoldTransducer<T, A, F> {
658    pub fn new(inner: T, init: A, f: F) -> Self {
659        Self { inner, init, f }
660    }
661}
662impl<T, A, F> Transducer for FoldTransducer<T, A, F>
663where
664    T: Transducer,
665    A: Clone,
666    F: Fn(&A, &T::Output) -> A,
667{
668    type Input = T::Input;
669    type Output = T::Output;
670    type State = (T::State, A);
671    fn start(&self) -> Self::State {
672        (self.inner.start(), self.init.clone())
673    }
674    fn relation(
675        &self,
676        (state, acc): &Self::State,
677        input: &Self::Input,
678    ) -> Option<(Self::State, Self::Output)> {
679        let (next_state, output) = self.inner.relation(state, input)?;
680        let next_acc = (self.f)(acc, &output);
681        Some(((next_state, next_acc), output))
682    }
683    fn accept(&self, (state, _): &Self::State) -> bool {
684        self.inner.accept(state)
685    }
686    fn stepout(&mut self) {
687        self.inner.stepout();
688    }
689}
690
691#[derive(Debug, Clone)]
692pub struct TryFoldTransducer<T, A, F> {
693    inner: T,
694    init: A,
695    f: F,
696}
697impl<T, A, F> TryFoldTransducer<T, A, F> {
698    pub fn new(inner: T, init: A, f: F) -> Self {
699        Self { inner, init, f }
700    }
701}
702impl<T, A, F> Transducer for TryFoldTransducer<T, A, F>
703where
704    T: Transducer,
705    A: Clone,
706    F: Fn(&A, &T::Output) -> Option<A>,
707{
708    type Input = T::Input;
709    type Output = T::Output;
710    type State = (T::State, A);
711    fn start(&self) -> Self::State {
712        (self.inner.start(), self.init.clone())
713    }
714    fn relation(
715        &self,
716        (state, acc): &Self::State,
717        input: &Self::Input,
718    ) -> Option<(Self::State, Self::Output)> {
719        let (next_state, output) = self.inner.relation(state, input)?;
720        let next_acc = (self.f)(acc, &output)?;
721        Some(((next_state, next_acc), output))
722    }
723    fn accept(&self, (state, _): &Self::State) -> bool {
724        self.inner.accept(state)
725    }
726    fn stepout(&mut self) {
727        self.inner.stepout();
728    }
729}
730
731#[derive(Debug, Clone)]
732pub struct AcceptTransducer<T, F> {
733    inner: T,
734    pred: F,
735}
736impl<T, F> AcceptTransducer<T, F> {
737    pub fn new(inner: T, pred: F) -> Self {
738        Self { inner, pred }
739    }
740}
741impl<T, F> Transducer for AcceptTransducer<T, F>
742where
743    T: Transducer,
744    F: Fn(&T::State) -> bool,
745{
746    type Input = T::Input;
747    type Output = T::Output;
748    type State = T::State;
749    fn start(&self) -> Self::State {
750        self.inner.start()
751    }
752    fn relation(
753        &self,
754        state: &Self::State,
755        input: &Self::Input,
756    ) -> Option<(Self::State, Self::Output)> {
757        self.inner.relation(state, input)
758    }
759    fn accept(&self, state: &Self::State) -> bool {
760        self.inner.accept(state) && (self.pred)(state)
761    }
762    fn stepout(&mut self) {
763        self.inner.stepout();
764    }
765}
766
767#[derive(Debug, Clone)]
768pub struct EqualTransducer<T>(PhantomData<fn() -> T>);
769impl<T> EqualTransducer<T> {
770    pub fn new() -> Self {
771        Default::default()
772    }
773}
774impl<T> Default for EqualTransducer<T> {
775    fn default() -> Self {
776        Self(PhantomData)
777    }
778}
779impl<T> Transducer for EqualTransducer<T>
780where
781    T: PartialEq,
782{
783    type Input = (T, T);
784    type Output = ();
785    type State = ();
786    fn start(&self) -> Self::State {}
787    fn relation(
788        &self,
789        _state: &Self::State,
790        input: &Self::Input,
791    ) -> Option<(Self::State, Self::Output)> {
792        (input.0 == input.1).then_some(((), ()))
793    }
794    fn accept(&self, _state: &Self::State) -> bool {
795        true
796    }
797}
798
799#[derive(Debug, Clone)]
800/// DFA to accept Less/Greater than (or equal to) in lexicographical order
801pub struct LexicographicalTransducer<T> {
802    ordering: Ordering,
803    equal: bool,
804    _marker: PhantomData<fn() -> T>,
805}
806impl<T> LexicographicalTransducer<T> {
807    pub fn less_than() -> Self {
808        Self {
809            ordering: Ordering::Less,
810            equal: false,
811            _marker: PhantomData,
812        }
813    }
814    pub fn less_than_or_equal() -> Self {
815        Self {
816            ordering: Ordering::Less,
817            equal: true,
818            _marker: PhantomData,
819        }
820    }
821    pub fn greater_than() -> Self {
822        Self {
823            ordering: Ordering::Greater,
824            equal: false,
825            _marker: PhantomData,
826        }
827    }
828    pub fn greater_than_or_equal() -> Self {
829        Self {
830            ordering: Ordering::Greater,
831            equal: true,
832            _marker: PhantomData,
833        }
834    }
835}
836impl<T> Transducer for LexicographicalTransducer<T>
837where
838    T: Ord,
839{
840    type Input = (T, T);
841    type Output = ();
842    /// is equal
843    type State = bool;
844    fn start(&self) -> Self::State {
845        true
846    }
847    fn relation(
848        &self,
849        state: &Self::State,
850        input: &Self::Input,
851    ) -> Option<(Self::State, Self::Output)> {
852        match (state, input.1.cmp(&input.0)) {
853            (true, Ordering::Equal) => Some((true, ())),
854            (true, ord) if ord == self.ordering => None,
855            _ => Some((false, ())),
856        }
857    }
858    fn accept(&self, state: &Self::State) -> bool {
859        self.equal || !state
860    }
861}
862
863#[derive(Debug, Clone)]
864/// DFA to accept Less/Greater than (or equal to) in reversed lexicographical order
865pub struct RevLexicographicalTransducer<T> {
866    ordering: Ordering,
867    equal: bool,
868    _marker: PhantomData<fn() -> T>,
869}
870impl<T> RevLexicographicalTransducer<T> {
871    pub fn less_than() -> Self {
872        Self {
873            ordering: Ordering::Less,
874            equal: false,
875            _marker: PhantomData,
876        }
877    }
878    pub fn less_than_or_equal() -> Self {
879        Self {
880            ordering: Ordering::Less,
881            equal: true,
882            _marker: PhantomData,
883        }
884    }
885    pub fn greater_than() -> Self {
886        Self {
887            ordering: Ordering::Greater,
888            equal: false,
889            _marker: PhantomData,
890        }
891    }
892    pub fn greater_than_or_equal() -> Self {
893        Self {
894            ordering: Ordering::Greater,
895            equal: true,
896            _marker: PhantomData,
897        }
898    }
899}
900impl<T> Transducer for RevLexicographicalTransducer<T>
901where
902    T: Ord,
903{
904    type Input = (T, T);
905    type Output = ();
906    /// accept
907    type State = bool;
908    fn start(&self) -> Self::State {
909        self.equal
910    }
911    fn relation(
912        &self,
913        state: &Self::State,
914        input: &Self::Input,
915    ) -> Option<(Self::State, Self::Output)> {
916        Some((
917            match input.0.cmp(&input.1) {
918                Ordering::Equal => *state,
919                ord => ord == self.ordering,
920            },
921            (),
922        ))
923    }
924    fn accept(&self, state: &Self::State) -> bool {
925        *state
926    }
927}
928
929#[derive(Debug, Clone)]
930pub struct SequenceTransducer<'a, T, A> {
931    sequence: &'a [T],
932    _marker: PhantomData<fn() -> A>,
933}
934impl<'a, T, A> SequenceTransducer<'a, T, A> {
935    pub fn new(sequence: &'a [T]) -> Self {
936        Self {
937            sequence,
938            _marker: PhantomData,
939        }
940    }
941}
942impl<T, A> Transducer for SequenceTransducer<'_, T, A>
943where
944    T: Clone,
945{
946    type Input = A;
947    type Output = T;
948    type State = ();
949    fn start(&self) -> Self::State {}
950    fn relation(
951        &self,
952        _state: &Self::State,
953        _input: &Self::Input,
954    ) -> Option<(Self::State, Self::Output)> {
955        self.sequence.first().map(|c| ((), c.clone()))
956    }
957    fn accept(&self, _state: &Self::State) -> bool {
958        true
959    }
960    fn stepout(&mut self) {
961        if !self.sequence.is_empty() {
962            self.sequence = &self.sequence[1..];
963        }
964    }
965}
966
967#[derive(Debug, Clone)]
968pub struct RevSequenceTransducer<'a, T, A> {
969    sequence: &'a [T],
970    _marker: PhantomData<fn() -> A>,
971}
972impl<'a, T, A> RevSequenceTransducer<'a, T, A> {
973    pub fn new(sequence: &'a [T]) -> Self {
974        Self {
975            sequence,
976            _marker: PhantomData,
977        }
978    }
979}
980impl<T, A> Transducer for RevSequenceTransducer<'_, T, A>
981where
982    T: Clone,
983{
984    type Input = A;
985    type Output = T;
986    type State = ();
987    fn start(&self) -> Self::State {}
988    fn relation(
989        &self,
990        _state: &Self::State,
991        _input: &Self::Input,
992    ) -> Option<(Self::State, Self::Output)> {
993        self.sequence.last().map(|c| ((), c.clone()))
994    }
995    fn accept(&self, _state: &Self::State) -> bool {
996        true
997    }
998    fn stepout(&mut self) {
999        if !self.sequence.is_empty() {
1000            self.sequence = &self.sequence[..self.sequence.len() - 1];
1001        }
1002    }
1003}
1004
1005pub struct IteratorTransducer<I, A>
1006where
1007    I: Iterator,
1008{
1009    iter: RefCell<Peekable<I>>,
1010    _marker: PhantomData<fn() -> A>,
1011}
1012impl<I, A> Clone for IteratorTransducer<I, A>
1013where
1014    I: Iterator<Item: Clone> + Clone,
1015{
1016    fn clone(&self) -> Self {
1017        Self {
1018            iter: self.iter.clone(),
1019            _marker: self._marker,
1020        }
1021    }
1022}
1023impl<I, A> Debug for IteratorTransducer<I, A>
1024where
1025    I: Iterator<Item: Debug> + Debug,
1026{
1027    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
1028        f.debug_struct("IteratorTransducer")
1029            .field("iter", &self.iter)
1030            .field("_marker", &self._marker)
1031            .finish()
1032    }
1033}
1034impl<I, A> IteratorTransducer<I, A>
1035where
1036    I: Iterator,
1037{
1038    pub fn new(iter: I) -> Self {
1039        Self::new_peekable(iter.peekable())
1040    }
1041    pub fn new_peekable(iter: Peekable<I>) -> Self {
1042        Self {
1043            iter: RefCell::new(iter),
1044            _marker: PhantomData,
1045        }
1046    }
1047}
1048impl<I, A> Transducer for IteratorTransducer<I, A>
1049where
1050    I: Iterator<Item: Clone>,
1051{
1052    type Input = A;
1053    type Output = I::Item;
1054    type State = ();
1055    fn start(&self) -> Self::State {}
1056    fn relation(
1057        &self,
1058        _state: &Self::State,
1059        _input: &Self::Input,
1060    ) -> Option<(Self::State, Self::Output)> {
1061        self.iter.borrow_mut().peek().cloned().map(|c| ((), c))
1062    }
1063    fn accept(&self, _state: &Self::State) -> bool {
1064        true
1065    }
1066    fn stepout(&mut self) {
1067        self.iter.borrow_mut().next();
1068    }
1069}
1070
1071#[derive(Debug, Clone)]
1072pub struct MonoidalTransducer<M>(PhantomData<fn() -> M>)
1073where
1074    M: Monoid;
1075impl<M> MonoidalTransducer<M>
1076where
1077    M: Monoid,
1078{
1079    pub fn new() -> Self {
1080        Default::default()
1081    }
1082}
1083impl<M> Default for MonoidalTransducer<M>
1084where
1085    M: Monoid,
1086{
1087    fn default() -> Self {
1088        Self(PhantomData)
1089    }
1090}
1091impl<M> Transducer for MonoidalTransducer<M>
1092where
1093    M: Monoid,
1094{
1095    type Input = M::T;
1096    type Output = ();
1097    type State = M::T;
1098    fn start(&self) -> Self::State {
1099        M::unit()
1100    }
1101    fn relation(
1102        &self,
1103        state: &Self::State,
1104        input: &Self::Input,
1105    ) -> Option<(Self::State, Self::Output)> {
1106        Some((M::operate(state, input), ()))
1107    }
1108    fn accept(&self, _state: &Self::State) -> bool {
1109        true
1110    }
1111}
1112
1113#[derive(Debug, Clone)]
1114pub struct IdentityTransducer<I>(PhantomData<fn() -> I>);
1115impl<I> IdentityTransducer<I> {
1116    pub fn new() -> Self {
1117        Default::default()
1118    }
1119}
1120impl<I> Default for IdentityTransducer<I> {
1121    fn default() -> Self {
1122        Self(PhantomData)
1123    }
1124}
1125impl<I> Transducer for IdentityTransducer<I>
1126where
1127    I: Clone,
1128{
1129    type Input = I;
1130    type Output = I;
1131    type State = ();
1132    fn start(&self) -> Self::State {}
1133    fn relation(
1134        &self,
1135        _state: &Self::State,
1136        input: &Self::Input,
1137    ) -> Option<(Self::State, Self::Output)> {
1138        Some(((), input.clone()))
1139    }
1140    fn accept(&self, _state: &Self::State) -> bool {
1141        true
1142    }
1143}
1144
1145#[derive(Debug, Clone)]
1146pub struct AlwaysAcceptingTransducer<A>(PhantomData<fn() -> A>);
1147impl<A> AlwaysAcceptingTransducer<A> {
1148    pub fn new() -> Self {
1149        Default::default()
1150    }
1151}
1152impl<A> Default for AlwaysAcceptingTransducer<A> {
1153    fn default() -> Self {
1154        Self(PhantomData)
1155    }
1156}
1157impl<A> Transducer for AlwaysAcceptingTransducer<A> {
1158    type Input = A;
1159    type Output = ();
1160    type State = ();
1161    fn start(&self) -> Self::State {}
1162    fn relation(
1163        &self,
1164        _state: &Self::State,
1165        _input: &Self::Input,
1166    ) -> Option<(Self::State, Self::Output)> {
1167        Some(((), ()))
1168    }
1169    fn accept(&self, _state: &Self::State) -> bool {
1170        true
1171    }
1172}
1173
1174/// build transducer
1175///
1176/// - `transducer!(A)`
1177/// - `<= seq`, `seq >=`: [`LexicographicalTransducer::less_than_or_equal()`](LexicographicalTransducer::less_than_or_equal) with [`SequenceTransducer`](SequenceTransducer)
1178/// - `>= seq`, `seq <=`: [`LexicographicalTransducer::greater_than_or_equal()`](LexicographicalTransducer::greater_than_or_equal) with [`SequenceTransducer`](SequenceTransducer)
1179/// - `< seq`, `seq >`: [`LexicographicalTransducer::less_than()`](LexicographicalTransducer::less_than) with [`SequenceTransducer`](SequenceTransducer)
1180/// - `> seq`, `seq <`: [`LexicographicalTransducer::greater_than()`](LexicographicalTransducer::greater_than) with [`SequenceTransducer`](SequenceTransducer)
1181/// - `!<= seq`, `seq !>=`: [`RevLexicographicalTransducer::less_than_or_equal()`](RevLexicographicalTransducer::less_than_or_equal) with [`SequenceTransducer`](SequenceTransducer)
1182/// - `!>= seq`, `seq !<=`: [`RevLexicographicalTransducer::greater_than_or_equal()`](RevLexicographicalTransducer::greater_than_or_equal) with [`SequenceTransducer`](SequenceTransducer)
1183/// - `!< seq`, `seq !>`: [`RevLexicographicalTransducer::less_than()`](RevLexicographicalTransducer::less_than) with [`SequenceTransducer`](SequenceTransducer)
1184/// - `!> seq`, `seq !<`: [`RevLexicographicalTransducer::greater_than()`](RevLexicographicalTransducer::greater_than) with [`SequenceTransducer`](SequenceTransducer)
1185/// - `<=`: [`LexicographicalTransducer::less_than_or_equal()`](LexicographicalTransducer::less_than_or_equal)
1186/// - `>=`: [`LexicographicalTransducer::greater_than_or_equal()`](LexicographicalTransducer::greater_than_or_equal)
1187/// - `<`: [`LexicographicalTransducer::less_than()`](LexicographicalTransducer::less_than)
1188/// - `>`: [`LexicographicalTransducer::greater_than()`](LexicographicalTransducer::greater_than)
1189/// - `!<=`: [`RevLexicographicalTransducer::less_than_or_equal()`](RevLexicographicalTransducer::less_than_or_equal)
1190/// - `!>=`: [`RevLexicographicalTransducer::greater_than_or_equal()`](RevLexicographicalTransducer::greater_than_or_equal)
1191/// - `!<`: [`RevLexicographicalTransducer::less_than()`](RevLexicographicalTransducer::less_than)
1192/// - `!>`: [`RevLexicographicalTransducer::greater_than()`](RevLexicographicalTransducer::greater_than)
1193/// - `=> f g h`: [`FunctionalTransducer::new(f, g, h)`](FunctionalTransducer)
1194/// - `@id`: [`IdentityTransducer::new()`](IdentityTransducer)
1195/// - `@it e`: [`IteratorTransducer::new(e)`](IteratorTransducer)
1196/// - `@map f`: `@id |>` [`map(f)`](Transducer::map)
1197/// - `@try_map f`: `@id |>` [`try_map(f)`](Transducer::try_map)
1198/// - `@seq e`: [`SequenceTransducer::new(e)`](SequenceTransducer)
1199/// - `@rseq e`: [`RevSequenceTransducer::new(e)`](RevSequenceTransducer)
1200/// - `@`: [`AlwaysAcceptingTransducer::new()`](AlwaysAcceptingTransducer)
1201/// - `A |> method(args...)`: [`Transducer`](Transducer)`::method(A, args...)`
1202/// - `A |> map(f)`: [`Transducer::map(A, f)`](Transducer::map)
1203/// - `A |> try_map(f)`: [`Transducer::try_map(A, f)`](Transducer::try_map)
1204/// - `A |> retain(f)`: [`Transducer::retain(A, f)`](Transducer::retain)
1205/// - `A |> with_fold(init, f)`: [`Transducer::with_fold(A, init, f)`](Transducer::with_fold)
1206/// - `A |> with_try_fold(init, f)`: [`Transducer::with_try_fold(A, init, f)`](Transducer::with_try_fold)
1207/// - `A |> accepting(f)`: [`Transducer::accepting(A, f)`](Transducer::accepting)
1208/// - `A . B`: [`ChainTransducer((A, B))`](ChainTransducer)
1209/// - `A * B`: [`ProductTransducer((A, B))`](ProductTransducer)
1210/// - `A & B`: [`IntersectionTransducer((A, B))`](IntersectionTransducer)
1211#[macro_export]
1212macro_rules! transducer {
1213    (@check $e:expr)                                         => {{ #[inline(always)] fn check_transucer<T>(fst: T) -> T where T: Transducer { fst } check_transucer($e) }};
1214    (@inner ($($t:tt)*))                                     => { $crate::transducer!(@inner $($t)*) };
1215    (@inner => $f:expr, $g:expr, $h:expr $(,)?)              => { $crate::transducer!(@check FunctionalTransducer::new($f, $g, $h)) };
1216    (@inner = $e:expr)                                       => { $crate::transducer!(((@id & (@seq &$e)) . =)) };
1217    (@inner <= $e:expr)                                      => { $crate::transducer!(((@id & (@seq &$e)) . <=)) };
1218    (@inner >= $e:expr)                                      => { $crate::transducer!(((@id & (@seq &$e)) . >=)) };
1219    (@inner < $e:expr)                                       => { $crate::transducer!(((@id & (@seq &$e)) . <)) };
1220    (@inner > $e:expr)                                       => { $crate::transducer!(((@id & (@seq &$e)) . >)) };
1221    (@inner !<= $e:expr)                                     => { $crate::transducer!(((@id & (@rseq &$e)) . !<=)) };
1222    (@inner !>= $e:expr)                                     => { $crate::transducer!(((@id & (@rseq &$e)) . !>=)) };
1223    (@inner !< $e:expr)                                      => { $crate::transducer!(((@id & (@rseq &$e)) . !<)) };
1224    (@inner !> $e:expr)                                      => { $crate::transducer!(((@id & (@rseq &$e)) . !>)) };
1225    (@inner $e:ident =)                                      => { $crate::transducer!((((@seq &$e) & @id) . =)) };
1226    (@inner $e:ident <=)                                     => { $crate::transducer!((((@seq &$e) & @id) . <=)) };
1227    (@inner $e:ident >=)                                     => { $crate::transducer!((((@seq &$e) & @id) . >=)) };
1228    (@inner $e:ident <)                                      => { $crate::transducer!((((@seq &$e) & @id) . <)) };
1229    (@inner $e:ident >)                                      => { $crate::transducer!((((@seq &$e) & @id) . >)) };
1230    (@inner $e:ident !<=)                                    => { $crate::transducer!((((@rseq &$e) & @id) . !<=)) };
1231    (@inner $e:ident !>=)                                    => { $crate::transducer!((((@rseq &$e) & @id) . !>=)) };
1232    (@inner $e:ident !<)                                     => { $crate::transducer!((((@rseq &$e) & @id) . !<)) };
1233    (@inner $e:ident !>)                                     => { $crate::transducer!((((@rseq &$e) & @id) . !>)) };
1234    (@inner =)                                               => { $crate::transducer!(@check EqualTransducer::new()) };
1235    (@inner <=)                                              => { $crate::transducer!(@check LexicographicalTransducer::less_than_or_equal()) };
1236    (@inner >=)                                              => { $crate::transducer!(@check LexicographicalTransducer::greater_than_or_equal()) };
1237    (@inner <)                                               => { $crate::transducer!(@check LexicographicalTransducer::less_than()) };
1238    (@inner >)                                               => { $crate::transducer!(@check LexicographicalTransducer::greater_than()) };
1239    (@inner !<=)                                             => { $crate::transducer!(@check RevLexicographicalTransducer::less_than_or_equal()) };
1240    (@inner !>=)                                             => { $crate::transducer!(@check RevLexicographicalTransducer::greater_than_or_equal()) };
1241    (@inner !<)                                              => { $crate::transducer!(@check RevLexicographicalTransducer::less_than()) };
1242    (@inner !>)                                              => { $crate::transducer!(@check RevLexicographicalTransducer::greater_than()) };
1243    (@inner @id)                                             => { $crate::transducer!(@check IdentityTransducer::new()) };
1244    (@inner @it $e:expr)                                     => { $crate::transducer!(@check IteratorTransducer::new($e)) };
1245    (@inner @map $f:expr)                                    => { $crate::transducer!(@check Transducer::map(IdentityTransducer::new(), $f)) };
1246    (@inner @try_map $f:expr)                                => { $crate::transducer!(@check Transducer::try_map(IdentityTransducer::new(), $f)) };
1247    (@inner @seq $e:expr)                                    => { $crate::transducer!(@check SequenceTransducer::new($e)) };
1248    (@inner @rseq $e:expr)                                   => { $crate::transducer!(@check RevSequenceTransducer::new($e)) };
1249    (@inner @<$t:ty>)                                        => { $crate::transducer!(@check AlwaysAcceptingTransducer::<$t>::new()) };
1250    (@inner @)                                               => { $crate::transducer!(@check AlwaysAcceptingTransducer::new()) };
1251    (@inner $($t:tt)*)                                       => { $crate::transducer!(@inter [] [] $($t)*) };
1252    (@inter [$([$($a:tt)*])*])                               => { $crate::transducer!(@check IntersectionTransducer(($($crate::transducer!(@inner $($a)*),)*))) };
1253    (@inter [] [$($b:tt)*])                                  => { $crate::transducer!(@prod [] [] $($b)*) };
1254    (@inter [$($a:tt)*] [$($b:tt)*])                         => { $crate::transducer!(@inter [$($a)* [$($b)*]]) };
1255    (@inter [$($a:tt)*] [$($b:tt)*] & $($t:tt)*)             => { $crate::transducer!(@inter [$($a)* [$($b)*]] [] $($t)*) };
1256    (@inter [$($a:tt)*] [$($b:tt)*] $op:tt $($t:tt)*)        => { $crate::transducer!(@inter [$($a)*] [$($b)* $op] $($t)*) };
1257    (@prod [$([$($a:tt)*])*])                                => { $crate::transducer!(@check ProductTransducer(($($crate::transducer!(@inner $($a)*),)*))) };
1258    (@prod [] [$($b:tt)*])                                   => { $crate::transducer!(@chain [] [] $($b)*) };
1259    (@prod [$($a:tt)*] [$($b:tt)*])                          => { $crate::transducer!(@prod [$($a)* [$($b)*]]) };
1260    (@prod [$($a:tt)*] [$($b:tt)*] * $($t:tt)*)              => { $crate::transducer!(@prod [$($a)* [$($b)*]] [] $($t)*) };
1261    (@prod [$($a:tt)*] [$($b:tt)*] $op:tt $($t:tt)*)         => { $crate::transducer!(@prod [$($a)*] [$($b)* $op] $($t)*) };
1262    (@chain [$([$($a:tt)*])*])                               => { $crate::transducer!(@check ChainTransducer(($($crate::transducer!(@wrap [] $($a)*),)*))) };
1263    (@chain [] [$($b:tt)*])                                  => { $crate::transducer!(@wrap [] $($b)*) };
1264    (@chain [$($a:tt)*] [$($b:tt)*])                         => { $crate::transducer!(@chain [$($a)* [$($b)*]]) };
1265    (@chain [$($a:tt)*] [$($b:tt)*] . $($t:tt)*)             => { $crate::transducer!(@chain [$($a)* [$($b)*]] [] $($t)*) };
1266    (@chain [$($a:tt)*] [$($b:tt)*] $op:tt $($t:tt)*)        => { $crate::transducer!(@chain [$($a)*] [$($b)* $op] $($t)*) };
1267    (@wrap [$($b:tt)*])                                      => { $crate::transducer!(@inner $($b)*) };
1268    (@wrap [$($b:tt)*] |> $($t:tt)*)                         => { $crate::transducer!(@wrap_apply [$crate::transducer!(@inner $($b)*)] $($t)*) };
1269    (@wrap [$($b:tt)*] $op:tt $($t:tt)*)                     => { $crate::transducer!(@wrap [$($b)* $op] $($t)*) };
1270    (@wrapped [$e:expr])                                     => { $crate::transducer!(@check $e) };
1271    (@wrapped [$e:expr] |> $($t:tt)*)                        => { $crate::transducer!(@wrap_apply [$e] $($t)*) };
1272    (@wrap_apply [$e:expr] $method:ident($($args:expr),* $(,)?) $($t:tt)*) => { $crate::transducer!(@wrapped [Transducer::$method($e $(, $args)*)] $($t)*) };
1273    (@id $($t:tt)*)                                          => { $crate::transducer!(@inner @id $($t)*) };
1274    (@it $($t:tt)*)                                          => { $crate::transducer!(@inner @it $($t)*) };
1275    (@map $($t:tt)*)                                         => { $crate::transducer!(@inner @map $($t)*) };
1276    (@try_map $($t:tt)*)                                     => { $crate::transducer!(@inner @try_map $($t)*) };
1277    (@seq $($t:tt)*)                                         => { $crate::transducer!(@inner @seq $($t)*) };
1278    (@rseq $($t:tt)*)                                        => { $crate::transducer!(@inner @rseq $($t)*) };
1279    (@$tag:ident $($t:tt)*)                                  => { ::std::compile_error!(::std::stringify!($tag, $($t)*)) };
1280    ($($t:tt)*)                                              => {{ $crate::transducer!(@inner $($t)*) }};
1281}
1282
1283#[cfg(test)]
1284mod tests {
1285    use super::*;
1286    use crate::{
1287        algebra::AdditiveOperation,
1288        tools::{
1289            NotEmptySegment, ToDigitSequence, Xorshift,
1290            testutil::{exhaustive_sequences, sample_usize, structured_sequences},
1291        },
1292    };
1293    use std::{collections::HashMap, iter::repeat_n};
1294
1295    #[test]
1296    fn test_equal_transducer() {
1297        type A = AdditiveOperation<usize>;
1298        const Q: usize = 100;
1299        let mut rng = Xorshift::default();
1300        for ((l, r), radix) in rng
1301            .random_iter((NotEmptySegment(10usize.pow(9)), 2..=10))
1302            .take(Q)
1303        {
1304            let rr = r.to_digit_sequence_radix(radix);
1305            let ll = l.to_digit_sequence_radix_len(radix, rr.len());
1306            let n = r - l;
1307            assert_eq!(
1308                n,
1309                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & =)
1310                    .dp::<A>(1)
1311                    .with_hashmap()
1312                    .run(
1313                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1314                        ll.len()
1315                    )
1316            );
1317        }
1318    }
1319
1320    #[test]
1321    fn test_lexicographical_transducer() {
1322        type A = AdditiveOperation<usize>;
1323        const Q: usize = 100;
1324        let mut rng = Xorshift::default();
1325        for ((l, r), radix) in rng
1326            .random_iter((NotEmptySegment(10usize.pow(9)), 2..=10))
1327            .take(Q)
1328        {
1329            let rr = r.to_digit_sequence_radix(radix);
1330            let ll = l.to_digit_sequence_radix_len(radix, rr.len());
1331            let n = r - l;
1332            assert_eq!(
1333                n * (n + 1) / 2,
1334                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & <=)
1335                    .dp::<A>(1)
1336                    .with_hashmap()
1337                    .run(
1338                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1339                        ll.len()
1340                    )
1341            );
1342            assert_eq!(
1343                n * (n + 1) / 2,
1344                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & >=)
1345                    .dp::<A>(1)
1346                    .with_hashmap()
1347                    .run(
1348                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1349                        ll.len()
1350                    )
1351            );
1352            assert_eq!(
1353                n * (n - 1) / 2,
1354                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & <)
1355                    .dp::<A>(1)
1356                    .with_hashmap()
1357                    .run(
1358                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1359                        ll.len()
1360                    )
1361            );
1362            assert_eq!(
1363                n * (n - 1) / 2,
1364                transducer!((((ll <=) & (< rr)) * ((ll <=) & (< rr))) & >)
1365                    .dp::<A>(1)
1366                    .with_hashmap()
1367                    .run(
1368                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1369                        ll.len()
1370                    )
1371            );
1372        }
1373    }
1374
1375    #[test]
1376    fn test_revlexicographical_transducer() {
1377        type A = AdditiveOperation<usize>;
1378        const Q: usize = 100;
1379        let mut rng = Xorshift::default();
1380        for ((l, r), radix) in rng
1381            .random_iter((NotEmptySegment(10usize.pow(9)), 2..=10))
1382            .take(Q)
1383        {
1384            let rr = r.to_digit_sequence_radix(radix);
1385            let ll = l.to_digit_sequence_radix_len(radix, rr.len());
1386            let n = r - l;
1387            assert_eq!(
1388                n * (n + 1) / 2,
1389                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !<=)
1390                    .dp::<A>(1)
1391                    .with_hashmap()
1392                    .run(
1393                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1394                        ll.len()
1395                    )
1396            );
1397            assert_eq!(
1398                n * (n + 1) / 2,
1399                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !>=)
1400                    .dp::<A>(1)
1401                    .with_hashmap()
1402                    .run(
1403                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1404                        ll.len()
1405                    )
1406            );
1407            assert_eq!(
1408                n * (n - 1) / 2,
1409                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !<)
1410                    .dp::<A>(1)
1411                    .with_hashmap()
1412                    .run(
1413                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1414                        ll.len()
1415                    )
1416            );
1417            assert_eq!(
1418                n * (n - 1) / 2,
1419                transducer!((((ll !<=) & (!< rr)) * ((ll !<=) & (!< rr))) & !>)
1420                    .dp::<A>(1)
1421                    .with_hashmap()
1422                    .run(
1423                        || (0..radix * radix).map(|x| (x / radix, x % radix)),
1424                        ll.len()
1425                    )
1426            );
1427        }
1428    }
1429
1430    #[test]
1431    fn test_lexicographical_sequence() {
1432        type A = AdditiveOperation<usize>;
1433        const Q: usize = 100;
1434        let mut rng = Xorshift::default();
1435        for (n, r) in rng.random_iter((0..10usize.pow(18), 2..=10)).take(Q) {
1436            let nd = n.to_digit_sequence_radix(r);
1437            assert_eq!(
1438                n + 1,
1439                transducer!(<= nd)
1440                    .dp::<A>(1)
1441                    .with_hashmap()
1442                    .run(|| 0..r, nd.len())
1443            );
1444            assert_eq!(
1445                n,
1446                transducer!(< nd)
1447                    .dp::<A>(1)
1448                    .with_hashmap()
1449                    .run(|| 0..r, nd.len())
1450            );
1451            assert_eq!(
1452                r.pow(nd.len() as _) - n,
1453                transducer!(>= nd)
1454                    .dp::<A>(1)
1455                    .with_hashmap()
1456                    .run(|| 0..r, nd.len())
1457            );
1458            assert_eq!(
1459                r.pow(nd.len() as _) - n - 1,
1460                transducer!(> nd)
1461                    .dp::<A>(1)
1462                    .with_hashmap()
1463                    .run(|| 0..r, nd.len())
1464            );
1465        }
1466    }
1467
1468    #[test]
1469    fn test_revlexicographical_sequence() {
1470        type A = AdditiveOperation<usize>;
1471        const Q: usize = 100;
1472        let mut rng = Xorshift::default();
1473        for (n, r) in rng.random_iter((0..10usize.pow(18), 2..=10)).take(Q) {
1474            let nd = n.to_digit_sequence_radix(r);
1475            assert_eq!(
1476                n + 1,
1477                transducer!(!<= nd)
1478                    .dp::<A>(1)
1479                    .with_hashmap()
1480                    .run(|| 0..r, nd.len())
1481            );
1482            assert_eq!(
1483                n,
1484                transducer!(!< nd)
1485                    .dp::<A>(1)
1486                    .with_hashmap()
1487                    .run(|| 0..r, nd.len())
1488            );
1489            assert_eq!(
1490                r.pow(nd.len() as _) - n,
1491                transducer!(!>= nd)
1492                    .dp::<A>(1)
1493                    .with_hashmap()
1494                    .run(|| 0..r, nd.len())
1495            );
1496            assert_eq!(
1497                r.pow(nd.len() as _) - n - 1,
1498                transducer!(!> nd)
1499                    .dp::<A>(1)
1500                    .with_hashmap()
1501                    .run(|| 0..r, nd.len())
1502            );
1503        }
1504    }
1505
1506    #[test]
1507    fn test_prim() {
1508        type A = AdditiveOperation<usize>;
1509        const Q: usize = 100;
1510        let mut rng = Xorshift::default();
1511        for (n, r, c) in rng
1512            .random_iter((0..10usize.pow(18), 2..=10, 2..200))
1513            .take(Q)
1514        {
1515            let nd = n.to_digit_sequence_radix(r);
1516            let fst = transducer!((< nd) & (=> || 0usize, |s, a| Some(((s * r + a) % c, ())), |s| *s == 0));
1517            assert_eq!(
1518                n.div_ceil(c),
1519                fst.clone().dp::<A>(1).with_hashmap().run(|| 0..r, nd.len())
1520            );
1521
1522            assert_eq!(
1523                n.div_ceil(c),
1524                fst.dp::<A>(1)
1525                    .with_vecmap(|&((_, s0), s1): &((((), ()), bool), usize)| s1 * 2 + s0 as usize)
1526                    .run(|| 0..r, nd.len())
1527            );
1528        }
1529    }
1530
1531    #[test]
1532    fn test_add_lte() {
1533        type A = AdditiveOperation<usize>;
1534        const Q: usize = 100;
1535        let mut rng = Xorshift::default();
1536        // (x, y) where x + a <= y, l <= x, y <= r
1537        for ((l, r), a) in rng
1538            .random_iter((NotEmptySegment(100usize), 0usize..100))
1539            .take(Q)
1540        {
1541            let ll = l.to_digit_sequence_radix_len(2, 20);
1542            let rr = r.to_digit_sequence_radix_len(2, 20);
1543            let aa = a.to_digit_sequence_radix_len(2, 20);
1544
1545            let fst = transducer!(
1546                ((ll !<=) * (!<= rr)) & (
1547                    (
1548                        (
1549                            ((@rseq &aa) & (@id))
1550                            |> map(|&(a, (x, _y))| x + a)
1551                            . (=> || 0usize, |s, i| Some(((s + i) / 2, (s + i) % 2)), |s| *s == 0)
1552                        ) & (@id |> map(|&(_x, y)| y))
1553                    ) . (!<=)
1554                )
1555            );
1556
1557            let result = fst
1558                .dp::<A>(1)
1559                .with_hashmap()
1560                .run(|| (0usize..4).map(|bit| (bit & 1, (bit >> 1) & 1)), 20);
1561            let expected: usize = (l..=r)
1562                .map(|x| (l..=r).filter(|&y| x + a <= y).count())
1563                .sum();
1564            assert_eq!(expected, result);
1565        }
1566    }
1567
1568    fn trace<T>(
1569        fst: &mut T,
1570        inputs: impl IntoIterator<Item = T::Input>,
1571    ) -> Vec<(T::State, T::Output)>
1572    where
1573        T: Transducer<State: Clone>,
1574    {
1575        let mut state = fst.start();
1576        let mut results = vec![];
1577        for input in inputs {
1578            if let Some((next_state, output)) = fst.relation(&state, &input) {
1579                results.push((next_state.clone(), output));
1580                state = next_state;
1581                fst.stepout();
1582            } else {
1583                break;
1584            }
1585        }
1586        results
1587    }
1588
1589    fn sum_transducer(
1590        initial: usize,
1591    ) -> impl Transducer<Input = usize, State = usize, Output = usize> + Clone {
1592        transducer!(=> move || initial,
1593            |state: &usize, input: &usize| Some((state + input, state + input)),
1594            |_: &usize| true)
1595    }
1596
1597    fn transducer_inputs() -> Vec<Vec<usize>> {
1598        let mut rng = Xorshift::default();
1599        let lengths = sample_usize(&mut rng, 32, 0..=128, 100);
1600        exhaustive_sequences(0..3, 0..=7)
1601            .chain(
1602                structured_sequences(&mut rng, 0..3, lengths)
1603                    .map(|values| values.into_iter().map(|i| [0, 1, 10][i]).collect()),
1604            )
1605            .collect()
1606    }
1607
1608    #[test]
1609    fn test_transducer_with_input() {
1610        let mut rng = Xorshift::default();
1611        for inputs in transducer_inputs() {
1612            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1613                let sums: Vec<_> = inputs
1614                    .iter()
1615                    .scan(initial, |sum, x| {
1616                        *sum += x;
1617                        Some(*sum)
1618                    })
1619                    .collect();
1620                let base = sum_transducer(initial);
1621                let mut with_input = base.clone().with_input();
1622                assert_eq!(with_input.start(), (initial, ()));
1623                assert_eq!(
1624                    trace(&mut with_input, inputs.iter().copied()),
1625                    sums.iter()
1626                        .zip(&inputs)
1627                        .map(|(&s, &x)| ((s, ()), (s, x)))
1628                        .collect::<Vec<_>>()
1629                );
1630            }
1631        }
1632    }
1633
1634    #[test]
1635    fn test_transducer_intersection() {
1636        let mut rng = Xorshift::default();
1637        for inputs in transducer_inputs() {
1638            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1639                let sums: Vec<_> = inputs
1640                    .iter()
1641                    .scan(initial, |sum, x| {
1642                        *sum += x;
1643                        Some(*sum)
1644                    })
1645                    .collect();
1646                let base = sum_transducer(initial);
1647                let mut intersection = base.clone().intersection(IdentityTransducer::new());
1648                assert_eq!(intersection.start(), (initial, ()));
1649                assert_eq!(
1650                    trace(&mut intersection, inputs.iter().copied()),
1651                    sums.iter()
1652                        .zip(&inputs)
1653                        .map(|(&s, &x)| ((s, ()), (s, x)))
1654                        .collect::<Vec<_>>()
1655                );
1656            }
1657        }
1658    }
1659
1660    #[test]
1661    fn test_transducer_product() {
1662        let mut rng = Xorshift::default();
1663        for inputs in transducer_inputs() {
1664            let n = inputs.len();
1665            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1666                let sums: Vec<_> = inputs
1667                    .iter()
1668                    .scan(initial, |sum, x| {
1669                        *sum += x;
1670                        Some(*sum)
1671                    })
1672                    .collect();
1673                let base = sum_transducer(initial);
1674                let other: Vec<usize> = rng.random_iter(0..=10).take(n).collect();
1675                let mut product = base.clone().product(AlwaysAcceptingTransducer::new());
1676                assert_eq!(product.start(), (initial, ()));
1677                assert_eq!(
1678                    trace(&mut product, inputs.iter().copied().zip(other)),
1679                    sums.iter().map(|&s| ((s, ()), (s, ()))).collect::<Vec<_>>()
1680                );
1681            }
1682        }
1683    }
1684
1685    #[test]
1686    fn test_transducer_chain() {
1687        let mut rng = Xorshift::default();
1688        for inputs in transducer_inputs() {
1689            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1690                let sums: Vec<_> = inputs
1691                    .iter()
1692                    .scan(initial, |sum, x| {
1693                        *sum += x;
1694                        Some(*sum)
1695                    })
1696                    .collect();
1697                let base = sum_transducer(initial);
1698                for factor in (0..=2).chain([rng.random(0..=1024)]) {
1699                    let mut chain = base.clone().chain(IdentityTransducer::new());
1700                    assert_eq!(
1701                        trace(&mut chain, inputs.iter().copied()),
1702                        sums.iter().map(|&s| ((s, ()), s)).collect::<Vec<_>>()
1703                    );
1704                    let mut chain = base.clone().chain(transducer!(@map |x: &usize| x * factor));
1705                    assert_eq!(
1706                        trace(&mut chain, inputs.iter().copied()),
1707                        sums.iter()
1708                            .map(|&s| ((s, ()), s * factor))
1709                            .collect::<Vec<_>>()
1710                    );
1711                }
1712            }
1713        }
1714    }
1715
1716    #[test]
1717    fn test_transducer_map() {
1718        let mut rng = Xorshift::default();
1719        for inputs in transducer_inputs() {
1720            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1721                let sums: Vec<_> = inputs
1722                    .iter()
1723                    .scan(initial, |sum, x| {
1724                        *sum += x;
1725                        Some(*sum)
1726                    })
1727                    .collect();
1728                for factor in (0..=2).chain([rng.random(0..=1024)]) {
1729                    let mut mapped = transducer!((=> || initial,
1730                |state: &usize, input: &usize| Some((state + input, state + input)),
1731                |_: &usize| true) |> map(|x: &usize| x * factor));
1732                    assert_eq!(mapped.start(), initial);
1733                    assert_eq!(
1734                        trace(&mut mapped, inputs.iter().copied()),
1735                        sums.iter().map(|&s| (s, s * factor)).collect::<Vec<_>>()
1736                    );
1737                }
1738            }
1739        }
1740    }
1741
1742    #[test]
1743    fn test_transducer_try_map() {
1744        let mut rng = Xorshift::default();
1745        for inputs in transducer_inputs() {
1746            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1747                let sums: Vec<_> = inputs
1748                    .iter()
1749                    .scan(initial, |sum, x| {
1750                        *sum += x;
1751                        Some(*sum)
1752                    })
1753                    .collect();
1754                let base = sum_transducer(initial);
1755                for factor in (0..=2).chain([rng.random(0..=1024)]) {
1756                    let mut limits: Vec<_> = [initial]
1757                        .into_iter()
1758                        .chain(sums.iter().copied())
1759                        .flat_map(|s| [s.saturating_sub(1), s, s + 1])
1760                        .collect();
1761                    limits.sort_unstable();
1762                    limits.dedup();
1763                    for limit in limits {
1764                        let mut filtered = base
1765                            .clone()
1766                            .try_map(|x: &usize| (*x <= limit).then_some(x * factor));
1767                        assert_eq!(
1768                            trace(&mut filtered, inputs.iter().copied()),
1769                            sums.iter()
1770                                .take_while(|&&s| s <= limit)
1771                                .map(|&s| (s, s * factor))
1772                                .collect::<Vec<_>>()
1773                        );
1774                    }
1775                }
1776            }
1777        }
1778    }
1779
1780    #[test]
1781    fn test_transducer_retain() {
1782        let mut rng = Xorshift::default();
1783        for inputs in transducer_inputs() {
1784            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1785                let sums: Vec<_> = inputs
1786                    .iter()
1787                    .scan(initial, |sum, x| {
1788                        *sum += x;
1789                        Some(*sum)
1790                    })
1791                    .collect();
1792                let base = sum_transducer(initial);
1793                let mut limits: Vec<_> = [initial]
1794                    .into_iter()
1795                    .chain(sums.iter().copied())
1796                    .flat_map(|s| [s.saturating_sub(1), s, s + 1])
1797                    .collect();
1798                limits.sort_unstable();
1799                limits.dedup();
1800                for limit in limits {
1801                    let mut retained = base.clone().retain(|x: &usize| *x <= limit);
1802                    assert_eq!(
1803                        trace(&mut retained, inputs.iter().copied()),
1804                        sums.iter()
1805                            .take_while(|&&s| s <= limit)
1806                            .map(|&s| (s, s))
1807                            .collect::<Vec<_>>()
1808                    );
1809                }
1810            }
1811        }
1812    }
1813
1814    #[test]
1815    fn test_transducer_try_map_input() {
1816        let mut rng = Xorshift::default();
1817        for inputs in transducer_inputs() {
1818            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1819                for factor in (0..=2).chain([rng.random(0..=1024)]) {
1820                    let mut limits: Vec<_> = [initial]
1821                        .into_iter()
1822                        .chain(inputs.iter().copied())
1823                        .flat_map(|s| [s.saturating_sub(1), s, s + 1])
1824                        .collect();
1825                    limits.sort_unstable();
1826                    limits.dedup();
1827                    for limit in limits {
1828                        let mut mapped =
1829                            transducer!(@try_map |x: &usize| (*x <= limit).then_some(x * factor));
1830                        assert_eq!(mapped.start(), ());
1831                        assert_eq!(
1832                            trace(&mut mapped, inputs.iter().copied()),
1833                            inputs
1834                                .iter()
1835                                .take_while(|&&x| x <= limit)
1836                                .map(|&x| ((), x * factor))
1837                                .collect::<Vec<_>>()
1838                        );
1839                    }
1840                }
1841            }
1842        }
1843    }
1844
1845    #[test]
1846    fn test_transducer_with_fold() {
1847        let mut rng = Xorshift::default();
1848        for inputs in transducer_inputs() {
1849            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1850                let sums: Vec<_> = inputs
1851                    .iter()
1852                    .scan(initial, |sum, x| {
1853                        *sum += x;
1854                        Some(*sum)
1855                    })
1856                    .collect();
1857                let mut folded =
1858                    transducer!(@id |> with_fold(initial, |acc: &usize, x: &usize| acc + x));
1859                assert_eq!(folded.start(), ((), initial));
1860                assert_eq!(
1861                    trace(&mut folded, inputs.iter().copied()),
1862                    sums.iter()
1863                        .zip(&inputs)
1864                        .map(|(&s, &x)| (((), s), x))
1865                        .collect::<Vec<_>>()
1866                );
1867            }
1868        }
1869    }
1870
1871    #[test]
1872    fn test_transducer_with_try_fold() {
1873        let mut rng = Xorshift::default();
1874        for inputs in transducer_inputs() {
1875            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1876                let sums: Vec<_> = inputs
1877                    .iter()
1878                    .scan(initial, |sum, x| {
1879                        *sum += x;
1880                        Some(*sum)
1881                    })
1882                    .collect();
1883                let mut limits: Vec<_> = [initial]
1884                    .into_iter()
1885                    .chain(sums.iter().copied())
1886                    .flat_map(|s| [s.saturating_sub(1), s, s + 1])
1887                    .collect();
1888                limits.sort_unstable();
1889                limits.dedup();
1890                for limit in limits {
1891                    let mut folded = transducer!(@id |> with_try_fold(initial, |acc: &usize, x: &usize| (acc + x <= limit).then_some(acc + x)));
1892                    assert_eq!(folded.start(), ((), initial));
1893                    assert_eq!(
1894                        trace(&mut folded, inputs.iter().copied()),
1895                        sums.iter()
1896                            .zip(&inputs)
1897                            .take_while(|&(&s, _)| s <= limit)
1898                            .map(|(&s, &x)| (((), s), x))
1899                            .collect::<Vec<_>>()
1900                    );
1901                }
1902            }
1903        }
1904    }
1905
1906    #[test]
1907    fn test_transducer_accepting() {
1908        let mut rng = Xorshift::default();
1909        for inputs in transducer_inputs() {
1910            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1911                let sums: Vec<_> = inputs
1912                    .iter()
1913                    .scan(initial, |sum, x| {
1914                        *sum += x;
1915                        Some(*sum)
1916                    })
1917                    .collect();
1918                let base = sum_transducer(initial);
1919                let mut limits: Vec<_> = [initial]
1920                    .into_iter()
1921                    .chain(sums.iter().copied())
1922                    .flat_map(|s| [s.saturating_sub(1), s, s + 1])
1923                    .collect();
1924                limits.sort_unstable();
1925                limits.dedup();
1926                for limit in limits {
1927                    let accepting = base.clone().accepting(|state: &usize| *state >= limit);
1928                    let mut state = accepting.start();
1929                    assert_eq!(accepting.accept(&state), initial >= limit);
1930                    for (&x, &sum) in inputs.iter().zip(&sums) {
1931                        let (next, output) = accepting.relation(&state, &x).unwrap();
1932                        assert_eq!((next, output), (sum, sum));
1933                        assert_eq!(accepting.accept(&next), sum >= limit);
1934                        state = next;
1935                    }
1936                }
1937            }
1938        }
1939    }
1940
1941    #[test]
1942    fn test_transducer_composition_rejection() {
1943        for outputs in exhaustive_sequences([None, Some(0usize), Some(1)], 2..=2) {
1944            for accepting in exhaustive_sequences([false, true], 2..=2) {
1945                let left = transducer!(=> || (),
1946                    |_: &(), _: &usize| outputs[0].map(|x| ((), x)),
1947                    |_: &()| accepting[0]);
1948                let right = transducer!(=> || (),
1949                    |_: &(), _: &usize| outputs[1].map(|x| ((), x)),
1950                    |_: &()| accepting[1]);
1951                let intersection = left.clone().intersection(right.clone());
1952                let product = left.clone().product(right.clone());
1953                let chain = left.chain(right);
1954                assert_eq!(
1955                    intersection.accept(&intersection.start()),
1956                    accepting[0] && accepting[1]
1957                );
1958                assert_eq!(
1959                    product.accept(&product.start()),
1960                    accepting[0] && accepting[1]
1961                );
1962                assert_eq!(chain.accept(&chain.start()), accepting[0] && accepting[1]);
1963                for input in 0..=2 {
1964                    let paired = outputs[0].zip(outputs[1]).map(|output| (((), ()), output));
1965                    assert_eq!(intersection.relation(&((), ()), &input), paired);
1966                    assert_eq!(product.relation(&((), ()), &(input, input)), paired);
1967                    assert_eq!(
1968                        chain.relation(&((), ()), &input),
1969                        outputs[0].and(outputs[1]).map(|x| (((), ()), x))
1970                    );
1971                }
1972            }
1973        }
1974    }
1975
1976    #[test]
1977    fn test_transducer_iterator() {
1978        for inputs in transducer_inputs() {
1979            let n = inputs.len();
1980            let mut iter = IteratorTransducer::<_, ()>::new(inputs.iter().copied());
1981            assert_eq!(
1982                trace(&mut iter, repeat_n((), n + 1)),
1983                inputs.iter().map(|&x| ((), x)).collect::<Vec<_>>()
1984            );
1985            assert!(trace(&mut iter, [()]).is_empty());
1986        }
1987    }
1988
1989    #[test]
1990    fn test_transducer_monoidal() {
1991        let mut rng = Xorshift::default();
1992        for inputs in transducer_inputs() {
1993            for initial in (0..=2).chain([rng.random(0..=1024)]) {
1994                let sums: Vec<_> = inputs
1995                    .iter()
1996                    .scan(initial, |sum, x| {
1997                        *sum += x;
1998                        Some(*sum)
1999                    })
2000                    .collect();
2001                let mut monoidal = MonoidalTransducer::<AdditiveOperation<usize>>::new();
2002                assert_eq!(
2003                    trace(&mut monoidal, inputs.iter().copied()),
2004                    sums.iter().map(|&s| (s - initial, ())).collect::<Vec<_>>()
2005                );
2006                assert!(monoidal.accept(&0));
2007                for &sum in &sums {
2008                    assert!(monoidal.accept(&sum));
2009                }
2010            }
2011        }
2012    }
2013
2014    #[test]
2015    fn test_transducer_always_accepting() {
2016        for inputs in transducer_inputs() {
2017            let n = inputs.len();
2018            let mut always = transducer!(@<usize>);
2019            assert_eq!(
2020                trace(&mut always, inputs.iter().copied()),
2021                vec![((), ()); n]
2022            );
2023            let mut always = transducer!(@);
2024            assert_eq!(trace(&mut always, inputs), vec![((), ()); n]);
2025        }
2026    }
2027
2028    #[test]
2029    fn test_transducer_map_fold_accept() {
2030        type M = AdditiveOperation<usize>;
2031        let mut rng = Xorshift::default();
2032        let mut cases: Vec<_> = exhaustive_sequences(0..3, 0..=4).collect();
2033        for _ in 0..1000 {
2034            let width = rng.random(0..=4);
2035            cases.push(rng.random_iter(0..=10).take(width).collect());
2036        }
2037        for inputs in cases {
2038            for n in 0..=6 {
2039                for divisor in 1..=10 {
2040                    let mut dp = transducer!(=> || 0usize,
2041                |state: &usize, input: &usize| Some((state + input, state + input)),
2042                |_: &usize| true)
2043                    .with_input()
2044                    .dp::<M>(1)
2045                    .with_hashmap();
2046                    let mut expected = vec![0usize];
2047                    for _ in 0..n {
2048                        dp.step(|| inputs.iter().copied());
2049                        expected = expected
2050                            .iter()
2051                            .flat_map(|&s| inputs.iter().map(move |&x| s + x))
2052                            .collect();
2053                    }
2054                    let mut histogram = HashMap::new();
2055                    for sum in expected {
2056                        *histogram.entry(sum % divisor).or_insert(0) += 1;
2057                    }
2058                    assert_eq!(
2059                        dp.map_fold_accept(|&(state, _)| state % divisor, HashMap::new()),
2060                        histogram
2061                    );
2062                }
2063            }
2064        }
2065    }
2066
2067    #[test]
2068    fn test_transducer_step_and_run_effect() {
2069        type M = AdditiveOperation<usize>;
2070        let mut rng = Xorshift::default();
2071        let mut cases: Vec<_> = exhaustive_sequences(0..3, 0..=4).collect();
2072        for _ in 0..1000 {
2073            let width = rng.random(0..=4);
2074            cases.push(rng.random_iter(0..=10).take(width).collect());
2075        }
2076        for inputs in cases {
2077            for n in 0..=6 {
2078                let width = inputs.len();
2079                let initial = rng.random(0..=10);
2080                let base = transducer!(=> || 0usize,
2081                |_: &usize, input: &usize| Some((0usize, *input)),
2082                |_: &usize| true);
2083                let mut dp = base.clone().dp::<M>(initial).with_hashmap();
2084                let mut expected = initial;
2085                for _ in 0..n {
2086                    dp.step_effect(|| inputs.iter().copied(), |value, output| value + output);
2087                    expected = width * expected + inputs.iter().sum::<usize>();
2088                    assert_eq!(dp.fold_accept(), expected);
2089                }
2090                let total = base
2091                    .dp::<M>(initial)
2092                    .with_fixed_vecmap(|state: &usize| *state, 1)
2093                    .run_effect(|| inputs.iter().copied(), n, |value, output| value + output);
2094                assert_eq!(total, expected);
2095            }
2096        }
2097    }
2098}
competitive/data_structure/transducer.rs

competitive/data_structure/
transducer.rs
