pub trait Transducer {
type Input;
type Output;
type State;
Show 15 methods
// Required methods
fn start(&self) -> Self::State;
fn relation(
&self,
state: &Self::State,
input: &Self::Input,
) -> Option<(Self::State, Self::Output)>;
fn accept(&self, state: &Self::State) -> bool;
// Provided methods
fn stepout(&mut self) { ... }
fn dp<M>(self, init: M::T) -> InitTransducerDp<M, Self>
where Self: Sized,
M: Monoid { ... }
fn intersection<U>(self, other: U) -> IntersectionTransducer<(Self, U)>
where Self: Sized,
U: Transducer<Input = Self::Input> { ... }
fn product<U>(self, other: U) -> ProductTransducer<(Self, U)>
where Self: Sized,
U: Transducer { ... }
fn chain<U>(self, other: U) -> ChainTransducer<(Self, U)>
where Self: Sized,
U: Transducer<Input = Self::Output> { ... }
fn with_input(
self,
) -> IntersectionTransducer<(Self, IdentityTransducer<Self::Input>)>
where Self: Sized { ... }
fn map<U, F>(self, f: F) -> MapTransducer<Self, U, F>
where Self: Sized,
F: Fn(&Self::Output) -> U { ... }
fn try_map<U, F>(self, f: F) -> TryMapTransducer<Self, U, F>
where Self: Sized,
F: Fn(&Self::Output) -> Option<U> { ... }
fn retain<F>(self, pred: F) -> RetainTransducer<Self, F>
where Self: Sized,
F: Fn(&Self::Output) -> bool { ... }
fn with_fold<A, F>(self, init: A, f: F) -> FoldTransducer<Self, A, F>
where Self: Sized,
A: Clone,
F: Fn(&A, &Self::Output) -> A { ... }
fn with_try_fold<A, F>(self, init: A, f: F) -> TryFoldTransducer<Self, A, F>
where Self: Sized,
A: Clone,
F: Fn(&A, &Self::Output) -> Option<A> { ... }
fn accepting<F>(self, pred: F) -> AcceptTransducer<Self, F>
where Self: Sized,
F: Fn(&Self::State) -> bool { ... }
}Required Associated Types§
Required Methods§
fn start(&self) -> Self::State
fn relation( &self, state: &Self::State, input: &Self::Input, ) -> Option<(Self::State, Self::Output)>
fn accept(&self, state: &Self::State) -> bool
Provided Methods§
Sourcefn stepout(&mut self)
fn stepout(&mut self)
Examples found in repository?
crates/competitive/src/data_structure/transducer.rs (line 228)
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 }fn dp<M>(self, init: M::T) -> InitTransducerDp<M, Self>
fn intersection<U>(self, other: U) -> IntersectionTransducer<(Self, U)>
fn product<U>(self, other: U) -> ProductTransducer<(Self, U)>where
Self: Sized,
U: Transducer,
fn chain<U>(self, other: U) -> ChainTransducer<(Self, U)>
fn with_input(
self,
) -> IntersectionTransducer<(Self, IdentityTransducer<Self::Input>)>where
Self: Sized,
fn map<U, F>(self, f: F) -> MapTransducer<Self, U, F>
fn try_map<U, F>(self, f: F) -> TryMapTransducer<Self, U, F>
fn retain<F>(self, pred: F) -> RetainTransducer<Self, F>
fn with_fold<A, F>(self, init: A, f: F) -> FoldTransducer<Self, A, F>
fn with_try_fold<A, F>(self, init: A, f: F) -> TryFoldTransducer<Self, A, F>
fn accepting<F>(self, pred: F) -> AcceptTransducer<Self, F>
Dyn Compatibility§
This trait is dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".