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 207)
190 pub fn step<S, I, B>(&mut self, mut sigma: S)
191 where
192 S: FnMut() -> I,
193 I: IntoIterator<Item = B>,
194 B: Borrow<T::Input>,
195 {
196 for (state, value) in self.dp.drain() {
197 for input in sigma() {
198 if let Some((nstate, _)) = self.fst.relation(&state, input.borrow()) {
199 self.ndp
200 .entry(nstate)
201 .and_modify(|acc| M::operate_assign(acc, &value))
202 .or_insert_with(|| value.clone());
203 }
204 }
205 }
206 swap(&mut self.dp, &mut self.ndp);
207 self.fst.stepout();
208 }
209 pub fn step_effect<S, I, B, F>(&mut self, mut sigma: S, mut effect: F)
210 where
211 S: FnMut() -> I,
212 I: IntoIterator<Item = B>,
213 B: Borrow<T::Input>,
214 F: FnMut(&M::T, &T::Output) -> M::T,
215 {
216 for (state, value) in self.dp.drain() {
217 for input in sigma() {
218 if let Some((nstate, output)) = self.fst.relation(&state, input.borrow()) {
219 let nvalue = effect(&value, &output);
220 self.ndp
221 .entry(nstate)
222 .and_modify(|acc| M::operate_assign(acc, &nvalue))
223 .or_insert(nvalue);
224 }
225 }
226 }
227 swap(&mut self.dp, &mut self.ndp);
228 self.fst.stepout();
229 }