// codesnip-guard: transducer
#[cfg_attr(any(),rustfmt::skip)]pub use self::transducer::*;#[cfg_attr(any(),rustfmt::skip)]mod transducer{use super::{AdditiveOperation,Container,ContainerEntry,Monoid,One,Zero};use std::{borrow::Borrow,cell::RefCell,cmp::Ordering,collections::HashMap,fmt::{self,Debug,Formatter},hash::{Hash,RandomState},iter::Peekable,marker::PhantomData,mem::swap,ops::Add};type Marker<T>=PhantomData<fn()->T>;pub trait Transducer{type Input;type Output;type State;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;#[doc=" Advances after processing the current layer."]fn stepout(&mut self){}fn dp<M>(self,init:M::T)->TransducerDp<M,Self,HashMap<Self::State,M::T>>where Self:Sized,Self::State:Eq+Hash,M:Monoid{let hash_builder=RandomState::new();self.dp_with(init,| |HashMap::with_hasher(hash_builder.clone()))}fn dp_with<M,C>(self,init:M::T,create:impl FnMut()->C)->TransducerDp<M,Self,C>where Self:Sized,M:Monoid,C:Container<Key=Self::State,Value=M::T>{TransducerDp::new(self,init,create)}fn counting<V>(self)->TransducerDp<AdditiveOperation<V>,Self,HashMap<Self::State,V>>where Self:Sized,Self::State:Eq+Hash,V:Clone+Zero+One+Add<Output=V>{self.dp(V::one())}fn counting_with<V,C>(self,create:impl FnMut()->C)->TransducerDp<AdditiveOperation<V>,Self,C>where Self:Sized,V:Clone+Zero+One+Add<Output=V>,C:Container<Key=Self::State,Value=V>{self.dp_with(V::one(),create)}fn intersection<U>(self,other:U)->IntersectionTransducer<(Self,U)>where Self:Sized,U:Transducer<Input=Self::Input>{IntersectionTransducer((self,other))}fn product<U>(self,other:U)->ProductTransducer<(Self,U)>where Self:Sized,U:Transducer{ProductTransducer((self,other))}fn chain<U>(self,other:U)->ChainTransducer<(Self,U)>where Self:Sized,U:Transducer<Input=Self::Output>{ChainTransducer((self,other))}#[doc=" Appends a cloned input to each output as `(output, input)`, preserving the state."]fn with_input(self)->WithInputTransducer<Self>where Self:Sized{WithInputTransducer::new(self)}fn map<U,F>(self,f:F)->MapTransducer<Self,U,F>where Self:Sized,F:Fn(Self::Output)->U{MapTransducer::new(self,f)}fn try_map<U,F>(self,f:F)->TryMapTransducer<Self,U,F>where Self:Sized,F:Fn(Self::Output)->Option<U>{TryMapTransducer::new(self,f)}#[doc=" Converts each input without adding a state component."]fn map_input<I,F>(self,f:F)->MapInputTransducer<Self,I,F>where Self:Sized,F:Fn(&I)->Self::Input{MapInputTransducer::new(self,f)}fn retain<F>(self,pred:F)->RetainTransducer<Self,F>where Self:Sized,F:Fn(&Self::Output)->bool{RetainTransducer::new(self,pred)}fn with_fold<A,F>(self,init:A,f:F)->FoldTransducer<Self,A,F>where Self:Sized,F:Fn(&A,&Self::Output)->A{FoldTransducer::new(self,init,f)}fn with_try_fold<A,F>(self,init:A,f:F)->TryFoldTransducer<Self,A,F>where Self:Sized,F:Fn(&A,&Self::Output)->Option<A>{TryFoldTransducer::new(self,init,f)}fn accepting<F>(self,pred:F)->AcceptTransducer<Self,F>where Self:Sized,F:Fn(&Self::State)->bool{AcceptTransducer::new(self,pred)}}#[doc=" `start`, `relation` and `accept` are independent of the layer and call count."]pub trait StationaryTransducer:Transducer{}impl<T>StationaryTransducer for&T where T:StationaryTransducer+?Sized{}impl<T>Transducer for&T where T:StationaryTransducer+?Sized{type Input=T::Input;type Output=T::Output;type State=T::State;fn start(&self)->Self::State{T::start(self)}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{T::relation(self,state,input)}fn accept(&self,state:&Self::State)->bool{T::accept(self,state)}}#[doc=" Aggregation follows the container's iteration order."]pub struct TransducerDp<M,T,C>{fst:T,pub dp:C,ndp:C,_marker:PhantomData<fn()->M>}impl<M,T,C>Clone for TransducerDp<M,T,C>where T:Clone,C:Clone{fn clone(&self)->Self{Self{fst:self.fst.clone(),dp:self.dp.clone(),ndp:self.ndp.clone(),_marker:PhantomData}}}impl<M,T,C>Debug for TransducerDp<M,T,C>where T:Debug,C:Debug{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("TransducerDp").field("fst",&self.fst).field("dp",&self.dp).field("ndp",&self.ndp).finish()}}impl<M,T,C>TransducerDp<M,T,C>where M:Monoid,T:Transducer,C:Container<Key=T::State,Value=M::T>{#[doc=" Calls `create` twice; each call must return an independent empty container."]#[inline]pub fn new(fst:T,init:M::T,mut create:impl FnMut()->C)->Self{let mut dp=create();let ndp=create();dp.insert(fst.start(),init);Self{fst,dp,ndp,_marker:PhantomData}}#[doc=" Calls `sigma` once per reachable state to enumerate its candidate inputs."]pub fn step<S,I,B>(&mut self,mut sigma:S)where S:FnMut(&T::State)->I,I:IntoIterator<Item=B>,B:Borrow<T::Input>{self.dp.drain().for_each(|(state,value)|{for input in sigma(&state){if let Some((nstate,_))=self.fst.relation(&state,input.borrow()){self.ndp.entry(nstate).and_modify(|acc|M::operate_assign(acc,&value)).or_insert_with(| |value.clone());}}});swap(&mut self.dp,&mut self.ndp);self.fst.stepout();}#[doc=" `effect(value, output)` must preserve `M::operate` for each output."]pub fn step_effect<S,I,B,F>(&mut self,mut sigma:S,mut effect:F)where S:FnMut(&T::State)->I,I:IntoIterator<Item=B>,B:Borrow<T::Input>,F:FnMut(&M::T,T::Output)->M::T{self.dp.drain().for_each(|(state,value)|{for input in sigma(&state){if let Some((nstate,output))=self.fst.relation(&state,input.borrow()){let nvalue=effect(&value,output);self.ndp.entry(nstate).and_modify(|acc|M::operate_assign(acc,&nvalue)).or_insert(nvalue);}}});swap(&mut self.dp,&mut self.ndp);self.fst.stepout();}pub fn fold_accept(&self)->M::T{let mut acc=M::unit();for(_,value)in self.iter_accept(){M::operate_assign(&mut acc,value);}acc}pub fn iter_accept(&self)->impl Iterator<Item=(&T::State,&M::T)>{self.dp.iter().filter(|(state,_)|self.fst.accept(state))}pub fn map_fold_accept<U,F,D>(&self,mut f:F,mut map:D)->D where F:FnMut(&T::State)->U,D:Container<Key=U,Value=M::T>{for(state,value)in self.iter_accept(){map.entry(f(state)).and_modify(|acc|M::operate_assign(acc,value)).or_insert_with(| |value.clone());}map}#[doc=" Advances `len` further layers and aggregates the accepting states."]#[inline]pub fn run<S,I,B>(&mut self,len:usize,mut sigma:S)->M::T where S:FnMut(&T::State)->I,I:IntoIterator<Item=B>,B:Borrow<T::Input>{for _ in 0..len{self.step(&mut sigma);}self.fold_accept()}pub fn run_effect<S,I,B,F>(&mut self,len:usize,mut sigma:S,mut effect:F)->M::T where S:FnMut(&T::State)->I,I:IntoIterator<Item=B>,B:Borrow<T::Input>,F:FnMut(&M::T,T::Output)->M::T{for _ in 0..len{self.step_effect(&mut sigma,&mut effect);}self.fold_accept()}}#[doc=" Runs each component from left to right, stopping at the first rejected transition."]#[derive(Debug,Clone)]pub struct IntersectionTransducer<Tuple>(pub Tuple);macro_rules!impl_intersection_transducer{(@impl$($T:ident)*,$($a:ident)*,$($b:ident)*)=>{impl<A,$($T),*>StationaryTransducer for IntersectionTransducer<($($T,)*)>where$($T:StationaryTransducer<Input=A>,)*{}impl<A,$($T),*>Transducer for IntersectionTransducer<($($T,)*)>where$($T:Transducer<Input=A>,)*{type Input=A;type Output=($($T::Output,)*);type State=($($T::State,)*);fn start(&self)->Self::State{let Self(($($a,)*))=self;($($a.start(),)*)}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let Self(($($a,)*))=self;let($($b,)*)=state;$(let($a,$b)=$a.relation($b,input)?;)*Some((($($a,)*),($($b,)*)))}fn accept(&self,state:&Self::State)->bool{let Self(($($a,)*))=self;let($($b,)*)=state;$($a.accept($b))&&*}fn stepout(&mut self){let Self(($($a,)*))=self;$($a.stepout();)*}}};(@inc$($T:ident)*,$($a:ident)*,$($b:ident)*,$TT:ident$aa:ident$bb:ident)=>{impl_intersection_transducer!(@impl$($T)*$TT,$($a)*$aa,$($b)*$bb);};(@inc$($T:ident)*,$($a:ident)*,$($b:ident)*,$TT:ident$aa:ident$bb:ident$($tt:tt)*)=>{impl_intersection_transducer!(@impl$($T)*$TT,$($a)*$aa,$($b)*$bb);impl_intersection_transducer!(@inc$($T)*$TT,$($a)*$aa,$($b)*$bb,$($tt)*);};($($tt:tt)*)=>{impl_intersection_transducer!(@inc,,,$($tt)*);};}impl_intersection_transducer!(T0 a0 b0 T1 a1 b1 T2 a2 b2 T3 a3 b3 T4 a4 b4 T5 a5 b5 T6 a6 b6 T7 a7 b7 T8 a8 b8 T9 a9 b9);#[derive(Debug,Clone)]pub struct ProductTransducer<Tuple>(pub Tuple);macro_rules!impl_product_transducer{(@impl$($T:ident)*,$($a:ident)*,$($b:ident)*,$($c:ident)*)=>{impl<$($T),*>StationaryTransducer for ProductTransducer<($($T,)*)>where$($T:StationaryTransducer,)*{}impl<$($T),*>Transducer for ProductTransducer<($($T,)*)>where$($T:Transducer,)*{type Input=($($T::Input,)*);type Output=($($T::Output,)*);type State=($($T::State,)*);fn start(&self)->Self::State{let Self(($($a,)*))=self;($($a.start(),)*)}fn relation(&self,state:&Self::State,($($c,)*):&Self::Input)->Option<(Self::State,Self::Output)>{let Self(($($a,)*))=self;let($($b,)*)=state;$(let($a,$b)=$a.relation($b,$c)?;)*Some((($($a,)*),($($b,)*)))}fn accept(&self,state:&Self::State)->bool{let Self(($($a,)*))=self;let($($b,)*)=state;$($a.accept($b))&&*}fn stepout(&mut self){let Self(($($a,)*))=self;$($a.stepout();)*}}};(@inc$($T:ident)*,$($a:ident)*,$($b:ident)*,$($c:ident)*,$TT:ident$aa:ident$bb:ident$cc:ident)=>{impl_product_transducer!(@impl$($T)*$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc);};(@inc$($T:ident)*,$($a:ident)*,$($b:ident)*,$($c:ident)*,$TT:ident$aa:ident$bb:ident$cc:ident$($tt:tt)*)=>{impl_product_transducer!(@impl$($T)*$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc);impl_product_transducer!(@inc$($T)*$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc,$($tt)*);};($($tt:tt)*)=>{impl_product_transducer!(@inc,,,,$($tt)*);};}impl_product_transducer!(T0 a0 b0 c0 T1 a1 b1 c1 T2 a2 b2 c2 T3 a3 b3 c3 T4 a4 b4 c4 T5 a5 b5 c5 T6 a6 b6 c6 T7 a7 b7 c7 T8 a8 b8 c8 T9 a9 b9 c9);#[derive(Debug,Clone)]pub struct ChainTransducer<Tuple>(pub Tuple);macro_rules!impl_chain_transducer{(@impl$T_head:ident,$($T_tail:ident)*,$($T_init:ident)*,$T_last:ident,$($T:ident)*,$($a:ident)*,$($b:ident)*,$($c:ident)*)=>{impl<$($T),*>StationaryTransducer for ChainTransducer<($($T,)*)>where$T_head:StationaryTransducer,$($T_tail:StationaryTransducer<Input=$T_init::Output>,)*{}impl<$($T),*>Transducer for ChainTransducer<($($T,)*)>where$T_head:Transducer,$($T_tail:Transducer<Input=$T_init::Output>,)*{type Input=$T_head::Input;type Output=$T_last::Output;type State=($($T::State,)*);fn start(&self)->Self::State{let Self(($($a,)*))=self;($($a.start(),)*)}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let Self(($($a,)*))=self;let($($b,)*)=state;$(let($c,input)=$a.relation($b,&input)?;)*Some((($($c,)*),input))}fn accept(&self,state:&Self::State)->bool{let Self(($($a,)*))=self;let($($b,)*)=state;$($a.accept($b))&&*}fn stepout(&mut self){let Self(($($a,)*))=self;$($a.stepout();)*}}};(@inc$T0:ident$($T:ident)*,$($a:ident)*,$($b:ident)*,$($c:ident)*,$TT:ident$aa:ident$bb:ident$cc:ident)=>{impl_chain_transducer!(@impl$T0,$($T)*$TT,$T0$($T)*,$TT,$T0$($T)*$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc);};(@inc,$($a:ident)*,$($b:ident)*,$($c:ident)*,$TT:ident$aa:ident$bb:ident$cc:ident$($tt:tt)*)=>{impl_chain_transducer!(@impl$TT,,,$TT,$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc);impl_chain_transducer!(@inc$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc,$($tt)*);};(@inc$T0:ident$($T:ident)*,$($a:ident)*,$($b:ident)*,$($c:ident)*,$TT:ident$aa:ident$bb:ident$cc:ident$($tt:tt)*)=>{impl_chain_transducer!(@impl$T0,$($T)*$TT,$T0$($T)*,$TT,$T0$($T)*$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc);impl_chain_transducer!(@inc$T0$($T)*$TT,$($a)*$aa,$($b)*$bb,$($c)*$cc,$($tt)*);};($($tt:tt)*)=>{impl_chain_transducer!(@inc,,,,$($tt)*);};}impl_chain_transducer!(T0 a0 b0 c0 T1 a1 b1 c1 T2 a2 b2 c2 T3 a3 b3 c3 T4 a4 b4 c4 T5 a5 b5 c5 T6 a6 b6 c6 T7 a7 b7 c7 T8 a8 b8 c8 T9 a9 b9 c9);#[derive(Debug)]pub struct FunctionalTransducer<I,O,S,F,G,H>{fn_start:F,fn_relation:G,fn_accept:H,_marker:Marker<(I,O,S)>}impl<I,O,S,F,G,H>Clone for FunctionalTransducer<I,O,S,F,G,H>where F:Clone,G:Clone,H:Clone{fn clone(&self)->Self{Self{fn_start:self.fn_start.clone(),fn_relation:self.fn_relation.clone(),fn_accept:self.fn_accept.clone(),_marker:PhantomData}}}impl<I,O,S,F,G,H>FunctionalTransducer<I,O,S,F,G,H>where F:Fn()->S,G:Fn(&S,&I)->Option<(S,O)>,H:Fn(&S)->bool{pub fn new(fn_start:F,fn_relation:G,fn_accept:H)->Self{Self{fn_start,fn_relation,fn_accept,_marker:PhantomData}}}impl<I,O,S,F,G,H>StationaryTransducer for FunctionalTransducer<I,O,S,F,G,H>where F:Fn()->S,G:Fn(&S,&I)->Option<(S,O)>,H:Fn(&S)->bool{}impl<I,O,S,F,G,H>Transducer for FunctionalTransducer<I,O,S,F,G,H>where F:Fn()->S,G:Fn(&S,&I)->Option<(S,O)>,H:Fn(&S)->bool{type Input=I;type Output=O;type State=S;fn start(&self)->Self::State{(self.fn_start)()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{(self.fn_relation)(state,input)}fn accept(&self,state:&Self::State)->bool{(self.fn_accept)(state)}}#[derive(Debug)]pub struct MapTransducer<T,U,F>{inner:T,f:F,_marker:Marker<U>}impl<T,U,F>Clone for MapTransducer<T,U,F>where T:Clone,F:Clone{fn clone(&self)->Self{Self{inner:self.inner.clone(),f:self.f.clone(),_marker:PhantomData}}}impl<T,U,F>MapTransducer<T,U,F>{pub fn new(inner:T,f:F)->Self where T:Transducer,F:Fn(T::Output)->U{Self{inner,f,_marker:PhantomData}}}impl<T,U,F>StationaryTransducer for MapTransducer<T,U,F>where T:StationaryTransducer,F:Fn(T::Output)->U{}impl<T,U,F>Transducer for MapTransducer<T,U,F>where T:Transducer,F:Fn(T::Output)->U{type Input=T::Input;type Output=U;type State=T::State;fn start(&self)->Self::State{self.inner.start()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let(next_state,output)=self.inner.relation(state,input)?;Some((next_state,(self.f)(output)))}fn accept(&self,state:&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug)]pub struct TryMapTransducer<T,U,F>{inner:T,f:F,_marker:Marker<U>}impl<T,U,F>Clone for TryMapTransducer<T,U,F>where T:Clone,F:Clone{fn clone(&self)->Self{Self{inner:self.inner.clone(),f:self.f.clone(),_marker:PhantomData}}}impl<T,U,F>TryMapTransducer<T,U,F>{pub fn new(inner:T,f:F)->Self where T:Transducer,F:Fn(T::Output)->Option<U>{Self{inner,f,_marker:PhantomData}}}impl<T,U,F>StationaryTransducer for TryMapTransducer<T,U,F>where T:StationaryTransducer,F:Fn(T::Output)->Option<U>{}impl<T,U,F>Transducer for TryMapTransducer<T,U,F>where T:Transducer,F:Fn(T::Output)->Option<U>{type Input=T::Input;type Output=U;type State=T::State;fn start(&self)->Self::State{self.inner.start()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let(next_state,output)=self.inner.relation(state,input)?;(self.f)(output).map(|output|(next_state,output))}fn accept(&self,state:&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug,Clone)]pub struct WithInputTransducer<T>{inner:T}impl<T>WithInputTransducer<T>{pub fn new(inner:T)->Self{Self{inner}}}impl<T>StationaryTransducer for WithInputTransducer<T>where T:StationaryTransducer,T::Input:Clone{}impl<T>Transducer for WithInputTransducer<T>where T:Transducer,T::Input:Clone{type Input=T::Input;type Output=(T::Output,T::Input);type State=T::State;fn start(&self)->Self::State{self.inner.start()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let(next_state,output)=self.inner.relation(state,input)?;Some((next_state,(output,input.clone())))}fn accept(&self,state:&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug)]pub struct MapInputTransducer<T,I,F>{inner:T,f:F,_marker:Marker<I>}impl<T,I,F>Clone for MapInputTransducer<T,I,F>where T:Clone,F:Clone{fn clone(&self)->Self{Self{inner:self.inner.clone(),f:self.f.clone(),_marker:PhantomData}}}impl<T,I,F>MapInputTransducer<T,I,F>{pub fn new(inner:T,f:F)->Self where T:Transducer,F:Fn(&I)->T::Input{Self{inner,f,_marker:PhantomData}}}impl<T,I,F>StationaryTransducer for MapInputTransducer<T,I,F>where T:StationaryTransducer,F:Fn(&I)->T::Input{}impl<T,I,F>Transducer for MapInputTransducer<T,I,F>where T:Transducer,F:Fn(&I)->T::Input{type Input=I;type Output=T::Output;type State=T::State;fn start(&self)->Self::State{self.inner.start()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{self.inner.relation(state,&(self.f)(input))}fn accept(&self,state:&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug,Clone)]pub struct RetainTransducer<T,F>{inner:T,pred:F}impl<T,F>RetainTransducer<T,F>{pub fn new(inner:T,pred:F)->Self where T:Transducer,F:Fn(&T::Output)->bool{Self{inner,pred}}}impl<T,F>StationaryTransducer for RetainTransducer<T,F>where T:StationaryTransducer,F:Fn(&T::Output)->bool{}impl<T,F>Transducer for RetainTransducer<T,F>where T:Transducer,F:Fn(&T::Output)->bool{type Input=T::Input;type Output=T::Output;type State=T::State;fn start(&self)->Self::State{self.inner.start()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let(next_state,output)=self.inner.relation(state,input)?;(self.pred)(&output).then_some((next_state,output))}fn accept(&self,state:&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug,Clone)]pub struct FoldTransducer<T,A,F>{inner:T,init:A,f:F}impl<T,A,F>FoldTransducer<T,A,F>{pub fn new(inner:T,init:A,f:F)->Self where T:Transducer,F:Fn(&A,&T::Output)->A{Self{inner,init,f}}}impl<T,A,F>StationaryTransducer for FoldTransducer<T,A,F>where T:StationaryTransducer,A:Clone,F:Fn(&A,&T::Output)->A{}impl<T,A,F>Transducer for FoldTransducer<T,A,F>where T:Transducer,A:Clone,F:Fn(&A,&T::Output)->A{type Input=T::Input;type Output=T::Output;type State=(T::State,A);fn start(&self)->Self::State{(self.inner.start(),self.init.clone())}fn relation(&self,(state,acc):&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let(next_state,output)=self.inner.relation(state,input)?;let next_acc=(self.f)(acc,&output);Some(((next_state,next_acc),output))}fn accept(&self,(state,_):&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug,Clone)]pub struct TryFoldTransducer<T,A,F>{inner:T,init:A,f:F}impl<T,A,F>TryFoldTransducer<T,A,F>{pub fn new(inner:T,init:A,f:F)->Self where T:Transducer,F:Fn(&A,&T::Output)->Option<A>{Self{inner,init,f}}}impl<T,A,F>StationaryTransducer for TryFoldTransducer<T,A,F>where T:StationaryTransducer,A:Clone,F:Fn(&A,&T::Output)->Option<A>{}impl<T,A,F>Transducer for TryFoldTransducer<T,A,F>where T:Transducer,A:Clone,F:Fn(&A,&T::Output)->Option<A>{type Input=T::Input;type Output=T::Output;type State=(T::State,A);fn start(&self)->Self::State{(self.inner.start(),self.init.clone())}fn relation(&self,(state,acc):&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{let(next_state,output)=self.inner.relation(state,input)?;let next_acc=(self.f)(acc,&output)?;Some(((next_state,next_acc),output))}fn accept(&self,(state,_):&Self::State)->bool{self.inner.accept(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug,Clone)]pub struct AcceptTransducer<T,F>{inner:T,pred:F}impl<T,F>AcceptTransducer<T,F>{pub fn new(inner:T,pred:F)->Self where T:Transducer,F:Fn(&T::State)->bool{Self{inner,pred}}}impl<T,F>StationaryTransducer for AcceptTransducer<T,F>where T:StationaryTransducer,F:Fn(&T::State)->bool{}impl<T,F>Transducer for AcceptTransducer<T,F>where T:Transducer,F:Fn(&T::State)->bool{type Input=T::Input;type Output=T::Output;type State=T::State;fn start(&self)->Self::State{self.inner.start()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{self.inner.relation(state,input)}fn accept(&self,state:&Self::State)->bool{self.inner.accept(state)&&(self.pred)(state)}fn stepout(&mut self){self.inner.stepout();}}#[derive(Debug)]pub struct EqualTransducer<T>(PhantomData<fn()->T>);impl<T>Clone for EqualTransducer<T>{fn clone(&self)->Self{Self(PhantomData)}}impl<T>EqualTransducer<T>{pub fn new()->Self{Default::default()}}impl<T>Default for EqualTransducer<T>{fn default()->Self{Self(PhantomData)}}impl<T>StationaryTransducer for EqualTransducer<T>where T:PartialEq{}impl<T>Transducer for EqualTransducer<T>where T:PartialEq{type Input=(T,T);type Output=();type State=();fn start(&self)->Self::State{}fn relation(&self,_state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{(input.0==input.1).then_some(((),()))}fn accept(&self,_state:&Self::State)->bool{true}}#[derive(Debug)]#[doc=" DFA to accept Less/Greater than (or equal to) in lexicographical order"]pub struct LexicographicalTransducer<T>{ordering:Ordering,equal:bool,_marker:PhantomData<fn()->T>}impl<T>Clone for LexicographicalTransducer<T>{fn clone(&self)->Self{Self{ordering:self.ordering,equal:self.equal,_marker:PhantomData}}}impl<T>LexicographicalTransducer<T>{pub fn less_than()->Self{Self{ordering:Ordering::Less,equal:false,_marker:PhantomData}}pub fn less_than_or_equal()->Self{Self{ordering:Ordering::Less,equal:true,_marker:PhantomData}}pub fn greater_than()->Self{Self{ordering:Ordering::Greater,equal:false,_marker:PhantomData}}pub fn greater_than_or_equal()->Self{Self{ordering:Ordering::Greater,equal:true,_marker:PhantomData}}}impl<T>StationaryTransducer for LexicographicalTransducer<T>where T:Ord{}impl<T>Transducer for LexicographicalTransducer<T>where T:Ord{type Input=(T,T);type Output=();#[doc=" is equal"]type State=bool;fn start(&self)->Self::State{true}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{if!state{return Some((false,()));}match input.0 .cmp(&input.1){Ordering::Equal=>Some((true,())),ord if ord==self.ordering=>Some((false,())),_=>None,}}fn accept(&self,state:&Self::State)->bool{self.equal||!state}}#[derive(Debug)]#[doc=" DFA to accept Less/Greater than (or equal to) in reversed lexicographical order"]pub struct RevLexicographicalTransducer<T>{ordering:Ordering,equal:bool,_marker:PhantomData<fn()->T>}impl<T>Clone for RevLexicographicalTransducer<T>{fn clone(&self)->Self{Self{ordering:self.ordering,equal:self.equal,_marker:PhantomData}}}impl<T>RevLexicographicalTransducer<T>{pub fn less_than()->Self{Self{ordering:Ordering::Less,equal:false,_marker:PhantomData}}pub fn less_than_or_equal()->Self{Self{ordering:Ordering::Less,equal:true,_marker:PhantomData}}pub fn greater_than()->Self{Self{ordering:Ordering::Greater,equal:false,_marker:PhantomData}}pub fn greater_than_or_equal()->Self{Self{ordering:Ordering::Greater,equal:true,_marker:PhantomData}}}impl<T>StationaryTransducer for RevLexicographicalTransducer<T>where T:Ord{}impl<T>Transducer for RevLexicographicalTransducer<T>where T:Ord{type Input=(T,T);type Output=();#[doc=" accept"]type State=bool;fn start(&self)->Self::State{self.equal}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{Some((match input.0 .cmp(&input.1){Ordering::Equal=>*state,ord=>ord==self.ordering,},()))}fn accept(&self,state:&Self::State)->bool{*state}}#[derive(Debug)]pub struct SequenceTransducer<'a,T,A>{sequence:&'a[T],_marker:PhantomData<fn()->A>}impl<'a,T,A>Clone for SequenceTransducer<'a,T,A>{fn clone(&self)->Self{Self{sequence:self.sequence,_marker:PhantomData}}}impl<'a,T,A>SequenceTransducer<'a,T,A>{pub fn new(sequence:&'a[T])->Self{Self{sequence,_marker:PhantomData}}}impl<T,A>Transducer for SequenceTransducer<'_,T,A>where T:Clone{type Input=A;type Output=T;type State=();fn start(&self)->Self::State{}fn relation(&self,_state:&Self::State,_input:&Self::Input)->Option<(Self::State,Self::Output)>{self.sequence.first().map(|c|((),c.clone()))}fn accept(&self,_state:&Self::State)->bool{true}fn stepout(&mut self){if!self.sequence.is_empty(){self.sequence=&self.sequence[1..];}}}#[derive(Debug)]pub struct RevSequenceTransducer<'a,T,A>{sequence:&'a[T],_marker:PhantomData<fn()->A>}impl<'a,T,A>Clone for RevSequenceTransducer<'a,T,A>{fn clone(&self)->Self{Self{sequence:self.sequence,_marker:PhantomData}}}impl<'a,T,A>RevSequenceTransducer<'a,T,A>{pub fn new(sequence:&'a[T])->Self{Self{sequence,_marker:PhantomData}}}impl<T,A>Transducer for RevSequenceTransducer<'_,T,A>where T:Clone{type Input=A;type Output=T;type State=();fn start(&self)->Self::State{}fn relation(&self,_state:&Self::State,_input:&Self::Input)->Option<(Self::State,Self::Output)>{self.sequence.last().map(|c|((),c.clone()))}fn accept(&self,_state:&Self::State)->bool{true}fn stepout(&mut self){if!self.sequence.is_empty(){self.sequence=&self.sequence[..self.sequence.len()-1];}}}pub struct IteratorTransducer<I,A>where I:Iterator{iter:RefCell<Peekable<I>>,_marker:PhantomData<fn()->A>}impl<I,A>Clone for IteratorTransducer<I,A>where I:Iterator<Item:Clone>+Clone{fn clone(&self)->Self{Self{iter:self.iter.clone(),_marker:self._marker}}}impl<I,A>Debug for IteratorTransducer<I,A>where I:Iterator<Item:Debug>+Debug{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("IteratorTransducer").field("iter",&self.iter).field("_marker",&self._marker).finish()}}impl<I,A>IteratorTransducer<I,A>where I:Iterator{pub fn new(iter:I)->Self{Self::new_peekable(iter.peekable())}pub fn new_peekable(iter:Peekable<I>)->Self{Self{iter:RefCell::new(iter),_marker:PhantomData}}}impl<I,A>Transducer for IteratorTransducer<I,A>where I:Iterator<Item:Clone>{type Input=A;type Output=I::Item;type State=();fn start(&self)->Self::State{}fn relation(&self,_state:&Self::State,_input:&Self::Input)->Option<(Self::State,Self::Output)>{self.iter.borrow_mut().peek().cloned().map(|c|((),c))}fn accept(&self,_state:&Self::State)->bool{true}fn stepout(&mut self){self.iter.borrow_mut().next();}}#[derive(Debug)]pub struct MonoidalTransducer<M>(PhantomData<fn()->M>);impl<M>Clone for MonoidalTransducer<M>{fn clone(&self)->Self{Self(PhantomData)}}impl<M>MonoidalTransducer<M>{pub fn new()->Self{Default::default()}}impl<M>Default for MonoidalTransducer<M>{fn default()->Self{Self(PhantomData)}}impl<M>StationaryTransducer for MonoidalTransducer<M>where M:Monoid{}impl<M>Transducer for MonoidalTransducer<M>where M:Monoid{type Input=M::T;type Output=();type State=M::T;fn start(&self)->Self::State{M::unit()}fn relation(&self,state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{Some((M::operate(state,input),()))}fn accept(&self,_state:&Self::State)->bool{true}}#[derive(Debug)]pub struct IdentityTransducer<I>(PhantomData<fn()->I>);impl<I>Clone for IdentityTransducer<I>{fn clone(&self)->Self{Self(PhantomData)}}impl<I>IdentityTransducer<I>{pub fn new()->Self{Default::default()}}impl<I>Default for IdentityTransducer<I>{fn default()->Self{Self(PhantomData)}}impl<I>StationaryTransducer for IdentityTransducer<I>where I:Clone{}impl<I>Transducer for IdentityTransducer<I>where I:Clone{type Input=I;type Output=I;type State=();fn start(&self)->Self::State{}fn relation(&self,_state:&Self::State,input:&Self::Input)->Option<(Self::State,Self::Output)>{Some(((),input.clone()))}fn accept(&self,_state:&Self::State)->bool{true}}#[derive(Debug)]pub struct AlwaysAcceptingTransducer<A>(PhantomData<fn()->A>);impl<A>Clone for AlwaysAcceptingTransducer<A>{fn clone(&self)->Self{Self(PhantomData)}}impl<A>AlwaysAcceptingTransducer<A>{pub fn new()->Self{Default::default()}}impl<A>Default for AlwaysAcceptingTransducer<A>{fn default()->Self{Self(PhantomData)}}impl<A>StationaryTransducer for AlwaysAcceptingTransducer<A>{}impl<A>Transducer for AlwaysAcceptingTransducer<A>{type Input=A;type Output=();type State=();fn start(&self)->Self::State{}fn relation(&self,_state:&Self::State,_input:&Self::Input)->Option<(Self::State,Self::Output)>{Some(((),()))}fn accept(&self,_state:&Self::State)->bool{true}}#[doc=" build transducer"]#[doc=""]#[doc=" - `transducer!(A)`"]#[doc=" - `<= seq`, `seq >=`: [`LexicographicalTransducer::less_than_or_equal()`](LexicographicalTransducer::less_than_or_equal) with [`SequenceTransducer`]"]#[doc=" - `>= seq`, `seq <=`: [`LexicographicalTransducer::greater_than_or_equal()`](LexicographicalTransducer::greater_than_or_equal) with [`SequenceTransducer`]"]#[doc=" - `< seq`, `seq >`: [`LexicographicalTransducer::less_than()`](LexicographicalTransducer::less_than) with [`SequenceTransducer`]"]#[doc=" - `> seq`, `seq <`: [`LexicographicalTransducer::greater_than()`](LexicographicalTransducer::greater_than) with [`SequenceTransducer`]"]#[doc=" - `!<= seq`, `seq !>=`: [`RevLexicographicalTransducer::less_than_or_equal()`](RevLexicographicalTransducer::less_than_or_equal) with [`RevSequenceTransducer`]"]#[doc=" - `!>= seq`, `seq !<=`: [`RevLexicographicalTransducer::greater_than_or_equal()`](RevLexicographicalTransducer::greater_than_or_equal) with [`RevSequenceTransducer`]"]#[doc=" - `!< seq`, `seq !>`: [`RevLexicographicalTransducer::less_than()`](RevLexicographicalTransducer::less_than) with [`RevSequenceTransducer`]"]#[doc=" - `!> seq`, `seq !<`: [`RevLexicographicalTransducer::greater_than()`](RevLexicographicalTransducer::greater_than) with [`RevSequenceTransducer`]"]#[doc=" - `<=`: [`LexicographicalTransducer::less_than_or_equal()`](LexicographicalTransducer::less_than_or_equal)"]#[doc=" - `>=`: [`LexicographicalTransducer::greater_than_or_equal()`](LexicographicalTransducer::greater_than_or_equal)"]#[doc=" - `<`: [`LexicographicalTransducer::less_than()`](LexicographicalTransducer::less_than)"]#[doc=" - `>`: [`LexicographicalTransducer::greater_than()`](LexicographicalTransducer::greater_than)"]#[doc=" - `!<=`: [`RevLexicographicalTransducer::less_than_or_equal()`](RevLexicographicalTransducer::less_than_or_equal)"]#[doc=" - `!>=`: [`RevLexicographicalTransducer::greater_than_or_equal()`](RevLexicographicalTransducer::greater_than_or_equal)"]#[doc=" - `!<`: [`RevLexicographicalTransducer::less_than()`](RevLexicographicalTransducer::less_than)"]#[doc=" - `!>`: [`RevLexicographicalTransducer::greater_than()`](RevLexicographicalTransducer::greater_than)"]#[doc=" - `=> f g h`: [`FunctionalTransducer::new(f, g, h)`](FunctionalTransducer)"]#[doc=" - `@id`: [`IdentityTransducer::new()`](IdentityTransducer)"]#[doc=" - `@it e`: [`IteratorTransducer::new(e)`](IteratorTransducer)"]#[doc=" - `@map f`: `@id |>` [`map(f)`](Transducer::map)"]#[doc=" - `@try_map f`: `@id |>` [`try_map(f)`](Transducer::try_map)"]#[doc=" - `@seq e`: [`SequenceTransducer::new(e)`](SequenceTransducer)"]#[doc=" - `@rseq e`: [`RevSequenceTransducer::new(e)`](RevSequenceTransducer)"]#[doc=" - `@`: [`AlwaysAcceptingTransducer::new()`](AlwaysAcceptingTransducer)"]#[doc=" - `A |> method(args...)`: [`Transducer`]`::method(A, args...)`"]#[doc=" - `A |> map(f)`: [`Transducer::map(A, f)`](Transducer::map)"]#[doc=" - `A |> try_map(f)`: [`Transducer::try_map(A, f)`](Transducer::try_map)"]#[doc=" - `A |> retain(f)`: [`Transducer::retain(A, f)`](Transducer::retain)"]#[doc=" - `A |> with_fold(init, f)`: [`Transducer::with_fold(A, init, f)`](Transducer::with_fold)"]#[doc=" - `A |> with_try_fold(init, f)`: [`Transducer::with_try_fold(A, init, f)`](Transducer::with_try_fold)"]#[doc=" - `A |> accepting(f)`: [`Transducer::accepting(A, f)`](Transducer::accepting)"]#[doc=" - `A . B`: [`ChainTransducer((A, B))`](ChainTransducer)"]#[doc=" - `A * B`: [`ProductTransducer((A, B))`](ProductTransducer)"]#[doc=" - `A & B`: [`IntersectionTransducer((A, B))`](IntersectionTransducer)"]#[doc=" - Use a block for Rust expressions containing DSL operators: `{ machine.clone() }`."]#[macro_export]macro_rules!transducer{(@check$e:expr)=>{{#[inline(always)]fn check_transucer<T>(fst:T)->T where T:Transducer{fst}check_transucer($e)}};(@inner($($t:tt)*))=>{$crate::transducer!(@inner$($t)*)};(@inner=>$f:expr,$g:expr,$h:expr$(,)?)=>{$crate::transducer!(@check FunctionalTransducer::new($f,$g,$h))};(@inner=$e:expr)=>{$crate::transducer!(((@id&(@seq&$e)). =))};(@inner<=$e:expr)=>{$crate::transducer!(((@id&(@seq&$e)).<=))};(@inner>=$e:expr)=>{$crate::transducer!(((@id&(@seq&$e)).>=))};(@inner<$e:expr)=>{$crate::transducer!(((@id&(@seq&$e)).<))};(@inner>$e:expr)=>{$crate::transducer!(((@id&(@seq&$e)).>))};(@inner!<=$e:expr)=>{$crate::transducer!(((@id&(@rseq&$e)).!<=))};(@inner!>=$e:expr)=>{$crate::transducer!(((@id&(@rseq&$e)).!>=))};(@inner!<$e:expr)=>{$crate::transducer!(((@id&(@rseq&$e)).!<))};(@inner!>$e:expr)=>{$crate::transducer!(((@id&(@rseq&$e)).!>))};(@inner$e:ident=)=>{$crate::transducer!(@inner=$e)};(@inner$e:ident<=)=>{$crate::transducer!(@inner>=$e)};(@inner$e:ident>=)=>{$crate::transducer!(@inner<=$e)};(@inner$e:ident<)=>{$crate::transducer!(@inner>$e)};(@inner$e:ident>)=>{$crate::transducer!(@inner<$e)};(@inner$e:ident!<=)=>{$crate::transducer!(@inner!>=$e)};(@inner$e:ident!>=)=>{$crate::transducer!(@inner!<=$e)};(@inner$e:ident!<)=>{$crate::transducer!(@inner!>$e)};(@inner$e:ident!>)=>{$crate::transducer!(@inner!<$e)};(@inner=)=>{$crate::transducer!(@check EqualTransducer::new())};(@inner<=)=>{$crate::transducer!(@check LexicographicalTransducer::less_than_or_equal())};(@inner>=)=>{$crate::transducer!(@check LexicographicalTransducer::greater_than_or_equal())};(@inner<)=>{$crate::transducer!(@check LexicographicalTransducer::less_than())};(@inner>)=>{$crate::transducer!(@check LexicographicalTransducer::greater_than())};(@inner!<=)=>{$crate::transducer!(@check RevLexicographicalTransducer::less_than_or_equal())};(@inner!>=)=>{$crate::transducer!(@check RevLexicographicalTransducer::greater_than_or_equal())};(@inner!<)=>{$crate::transducer!(@check RevLexicographicalTransducer::less_than())};(@inner!>)=>{$crate::transducer!(@check RevLexicographicalTransducer::greater_than())};(@inner@id)=>{$crate::transducer!(@check IdentityTransducer::new())};(@inner@it$e:expr)=>{$crate::transducer!(@check IteratorTransducer::new($e))};(@inner@map$f:expr)=>{$crate::transducer!(@check Transducer::map(IdentityTransducer::new(),$f))};(@inner@try_map$f:expr)=>{$crate::transducer!(@check Transducer::try_map(IdentityTransducer::new(),$f))};(@inner@seq$e:expr)=>{$crate::transducer!(@check SequenceTransducer::new($e))};(@inner@rseq$e:expr)=>{$crate::transducer!(@check RevSequenceTransducer::new($e))};(@inner@<$t:ty>)=>{$crate::transducer!(@check AlwaysAcceptingTransducer::<$t>::new())};(@inner@)=>{$crate::transducer!(@check AlwaysAcceptingTransducer::new())};(@inner$e:ident)=>{$crate::transducer!(@check$e)};(@inner$e:block)=>{$crate::transducer!(@check$e)};(@inner$($t:tt)*)=>{$crate::transducer!(@inter[][]$($t)*)};(@inter[$([$($a:tt)*])*])=>{$crate::transducer!(@check IntersectionTransducer(($($crate::transducer!(@inner$($a)*),)*)))};(@inter[][$($b:tt)*])=>{$crate::transducer!(@prod[][]$($b)*)};(@inter[$($a:tt)*][$($b:tt)*])=>{$crate::transducer!(@inter[$($a)*[$($b)*]])};(@inter[$($a:tt)*][$($b:tt)*]&$($t:tt)*)=>{$crate::transducer!(@inter[$($a)*[$($b)*]][]$($t)*)};(@inter[$($a:tt)*][$($b:tt)*]$op:tt$($t:tt)*)=>{$crate::transducer!(@inter[$($a)*][$($b)*$op]$($t)*)};(@prod[$([$($a:tt)*])*])=>{$crate::transducer!(@check ProductTransducer(($($crate::transducer!(@inner$($a)*),)*)))};(@prod[][$($b:tt)*])=>{$crate::transducer!(@chain[][]$($b)*)};(@prod[$($a:tt)*][$($b:tt)*])=>{$crate::transducer!(@prod[$($a)*[$($b)*]])};(@prod[$($a:tt)*][$($b:tt)*]*$($t:tt)*)=>{$crate::transducer!(@prod[$($a)*[$($b)*]][]$($t)*)};(@prod[$($a:tt)*][$($b:tt)*]$op:tt$($t:tt)*)=>{$crate::transducer!(@prod[$($a)*][$($b)*$op]$($t)*)};(@chain[$([$($a:tt)*])*])=>{$crate::transducer!(@check ChainTransducer(($($crate::transducer!(@wrap[]$($a)*),)*)))};(@chain[][$($b:tt)*])=>{$crate::transducer!(@wrap[]$($b)*)};(@chain[$($a:tt)*][$($b:tt)*])=>{$crate::transducer!(@chain[$($a)*[$($b)*]])};(@chain[$($a:tt)*][$($b:tt)*].$($t:tt)*)=>{$crate::transducer!(@chain[$($a)*[$($b)*]][]$($t)*)};(@chain[$($a:tt)*][$($b:tt)*]$op:tt$($t:tt)*)=>{$crate::transducer!(@chain[$($a)*][$($b)*$op]$($t)*)};(@wrap[$($b:tt)*])=>{$crate::transducer!(@inner$($b)*)};(@wrap[$($b:tt)*]|>$($t:tt)*)=>{$crate::transducer!(@wrap_apply[$crate::transducer!(@inner$($b)*)]$($t)*)};(@wrap[$($b:tt)*]$op:tt$($t:tt)*)=>{$crate::transducer!(@wrap[$($b)*$op]$($t)*)};(@wrapped[$e:expr])=>{$crate::transducer!(@check$e)};(@wrapped[$e:expr]|>$($t:tt)*)=>{$crate::transducer!(@wrap_apply[$e]$($t)*)};(@wrap_apply[$e:expr]$method:ident($($args:expr),*$(,)?)$($t:tt)*)=>{$crate::transducer!(@wrapped[Transducer::$method($e$(,$args)*)]$($t)*)};(@id$($t:tt)*)=>{$crate::transducer!(@inner@id$($t)*)};(@it$($t:tt)*)=>{$crate::transducer!(@inner@it$($t)*)};(@map$($t:tt)*)=>{$crate::transducer!(@inner@map$($t)*)};(@try_map$($t:tt)*)=>{$crate::transducer!(@inner@try_map$($t)*)};(@seq$($t:tt)*)=>{$crate::transducer!(@inner@seq$($t)*)};(@rseq$($t:tt)*)=>{$crate::transducer!(@inner@rseq$($t)*)};(@$tag:ident$($t:tt)*)=>{::std::compile_error!(::std::stringify!($tag,$($t)*))};($($t:tt)*)=>{{$crate::transducer!(@inner$($t)*)}};}}
// codesnip-guard: AdditiveOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::additive_operation_impl::AdditiveOperation;#[cfg_attr(any(),rustfmt::skip)]mod additive_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Add,Neg,Sub}};#[doc=" $+$"]pub struct AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()+y.clone()}}impl<T>Unital for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{#[inline]fn unit()->Self::T{Zero::zero()}}impl<T>Associative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Commutative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Invertible for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>+Sub<Output=T>+Neg<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{-x.clone()}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()-y.clone()}}}
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}
// codesnip-guard: container
#[cfg_attr(any(),rustfmt::skip)]pub use self::container::{Container,ContainerEntry};#[cfg_attr(any(),rustfmt::skip)]mod container{use std::{cmp::Ord,collections::{BTreeMap,HashMap,btree_map,hash_map},hash::{BuildHasher,Hash},iter::FusedIterator};pub trait Container{type Key;type Value;type Entry<'a>:ContainerEntry<'a,Key=Self::Key,Value=Self::Value>where Self:'a,Self::Key:'a,Self::Value:'a;type Iter<'a>:Iterator<Item=(&'a Self::Key,&'a Self::Value)>where Self:'a,Self::Key:'a,Self::Value:'a;type Drain<'a>:Iterator<Item=(Self::Key,Self::Value)>where Self:'a,Self::Key:'a,Self::Value:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>;fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>;fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>;fn remove(&mut self,key:&Self::Key)->Option<Self::Value>;fn entry(&mut self,key:Self::Key)->Self::Entry<'_>;fn iter(&self)->Self::Iter<'_>;fn drain(&mut self)->Self::Drain<'_>;}pub trait ContainerEntry<'a>{type Key:'a;type Value:'a;fn or_default(self)->&'a mut Self::Value where Self::Value:Default;fn or_insert(self,default:Self::Value)->&'a mut Self::Value;fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value;fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value;fn key(&self)->&Self::Key;fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value);}#[derive(Debug)]pub struct BTreeMapDrain<'a,K,V>{inner:&'a mut BTreeMap<K,V>}impl<K,V>Container for BTreeMap<K,V>where K:Ord{type Key=K;type Value=V;type Entry<'a>=btree_map::Entry<'a,K,V>where K:'a,V:'a;type Iter<'a>=btree_map::Iter<'a,K,V>where K:'a,V:'a;type Drain<'a>=BTreeMapDrain<'a,K,V>where K:'a,V:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>{self.get(key)}fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>{self.get_mut(key)}fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>{self.insert(key,value)}fn remove(&mut self,key:&Self::Key)->Option<Self::Value>{self.remove(key)}fn entry(&mut self,key:Self::Key)->Self::Entry<'_>{self.entry(key)}fn iter(&self)->Self::Iter<'_>{self.iter()}fn drain(&mut self)->Self::Drain<'_>{BTreeMapDrain{inner:self}}}impl<K,V>Iterator for BTreeMapDrain<'_,K,V>where K:Ord{type Item=(K,V);fn next(&mut self)->Option<Self::Item>{self.inner.pop_first()}}impl<K,V>DoubleEndedIterator for BTreeMapDrain<'_,K,V>where K:Ord{fn next_back(&mut self)->Option<Self::Item>{self.inner.pop_last()}}impl<K,V>ExactSizeIterator for BTreeMapDrain<'_,K,V>where K:Ord{fn len(&self)->usize{self.inner.len()}}impl<K,V>FusedIterator for BTreeMapDrain<'_,K,V>where K:Ord{}impl<'a,K,V>ContainerEntry<'a>for btree_map::Entry<'a,K,V>where K:'a+Ord,V:'a{type Key=K;type Value=V;fn or_default(self)->&'a mut Self::Value where Self::Value:Default{self.or_default()}fn or_insert(self,default:Self::Value)->&'a mut Self::Value{self.or_insert(default)}fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value{self.or_insert_with(default)}fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value{self.or_insert_with_key(default)}fn key(&self)->&Self::Key{self.key()}fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value){self.and_modify(f)}}impl<K,V,S>Container for HashMap<K,V,S>where K:Eq+Hash,S:BuildHasher{type Key=K;type Value=V;type Entry<'a>=hash_map::Entry<'a,K,V>where S:'a,K:'a,V:'a;type Iter<'a>=hash_map::Iter<'a,K,V>where S:'a,K:'a,V:'a;type Drain<'a>=hash_map::Drain<'a,K,V>where S:'a,K:'a,V:'a;fn get(&self,key:&Self::Key)->Option<&Self::Value>{self.get(key)}fn get_mut(&mut self,key:&Self::Key)->Option<&mut Self::Value>{self.get_mut(key)}fn insert(&mut self,key:Self::Key,value:Self::Value)->Option<Self::Value>{self.insert(key,value)}fn remove(&mut self,key:&Self::Key)->Option<Self::Value>{self.remove(key)}fn entry(&mut self,key:Self::Key)->Self::Entry<'_>{self.entry(key)}fn iter(&self)->Self::Iter<'_>{self.iter()}fn drain(&mut self)->Self::Drain<'_>{self.drain()}}impl<'a,K,V>ContainerEntry<'a>for hash_map::Entry<'a,K,V>where K:'a+Eq+Hash,V:'a{type Key=K;type Value=V;fn or_default(self)->&'a mut Self::Value where Self::Value:Default{self.or_default()}fn or_insert(self,default:Self::Value)->&'a mut Self::Value{self.or_insert(default)}fn or_insert_with<F>(self,default:F)->&'a mut Self::Value where F:FnOnce()->Self::Value{self.or_insert_with(default)}fn or_insert_with_key<F>(self,default:F)->&'a mut Self::Value where F:FnOnce(&Self::Key)->Self::Value{self.or_insert_with_key(default)}fn key(&self)->&Self::Key{self.key()}fn and_modify<F>(self,f:F)->Self where F:FnOnce(&mut Self::Value){self.and_modify(f)}}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}