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

competitive/data_structure/
transducer.rs
