pub trait Transducer {
type Input;
type Output;
type State;
// 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,
) -> ChainTransducer<(Self, MapTransducer<Self::Output, U, F>)>
where Self: Sized,
F: Fn(&Self::Output) -> U { ... }
fn filter_map<U, F>(
self,
f: F,
) -> ChainTransducer<(Self, FilterMapTransducer<Self::Output, U, F>)>
where Self: Sized,
F: Fn(&Self::Output) -> Option<U> { ... }
}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 200)
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 }