trait FsmState {
    fn step(&self, c: char) -> Box<FsmState>;

    fn is_terminal(&self) -> bool {
        false
    }

    fn is_error(&self) -> bool {
        false
    }

    fn is_valid_end(&self) -> bool {
        self.is_terminal() && !self.is_error()
    }

    fn upcast(&self) -> Box<FsmState>;
}


#[derive(Clone)]
struct A {}
trait AEgress : FsmState { }
impl AEgress for A {}
impl AEgress for B {}
impl AEgress for Error {}

#[derive(Clone)]
struct B {}
trait BEgress : FsmState {}
impl BEgress for B {}
impl BEgress for C {}
impl BEgress for Error {}


#[derive(Clone)]
struct C {}
trait CEgress : FsmState {}
impl CEgress for Error {}


#[derive(Clone)]
struct Error {}
trait ErrorEgress : FsmState {}
impl ErrorEgress for Error {}


impl FsmState for A {
    fn step(&self, c: char) -> Box<FsmState> {
        fn doit(c: char) -> Box<AEgress> {
            match c {
                'a' => Box::new(A {}),
                'b' => Box::new(B {}),
                _ => Box::new(Error {}),
            }
        }

        doit(c).upcast()
    }

    fn upcast(&self) -> Box<FsmState> {
        Box::new(self.clone())
    }
}

impl FsmState for B {
    fn step(&self, c: char) -> Box<FsmState> {
        fn doit(c: char) -> Box<BEgress> {
            match c {
                'b' => Box::new(B {}),
                'c' => Box::new(C {}),
                _ => Box::new(Error {}),
            }
        }

        doit(c).upcast()
    }

    fn upcast(&self) -> Box<FsmState> {
        Box::new(self.clone())
    }
}

impl FsmState for C {
    fn step(&self, c: char) -> Box<FsmState> {
        fn doit(_c: char) -> Box<CEgress> {
            Box::new(Error {})
        }

        doit(c).upcast()
    }

    fn is_terminal(&self) -> bool {
        true
    }

    fn upcast(&self) -> Box<FsmState> {
        Box::new(self.clone())
    }
}

impl FsmState for Error {
    fn step(&self, c: char) -> Box<FsmState> {
        fn doit(_c: char) -> Box<CEgress> {
            Box::new(Error {})
        }

        doit(c).upcast()
    }

    fn is_error(&self) -> bool {
        true
    }

    fn upcast(&self) -> Box<FsmState> {
        Box::new(self.clone())
    }
}


fn accept(s: &str) -> bool {
    let start : Box<FsmState> = Box::new(A {});
    s.chars()
        .fold(start, |st, c| st.step(c))
        .is_valid_end()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_abc() {
        assert!(accept("abc"));
        assert!(accept("aaaabc"));
        assert!(accept("abbbbbc"));
        assert!(accept("aaaaabbbbbc"));
    }
}