use std::*;
pub enum RegEx<'a, T, U: Copy = ()> {
Eps,
Atom( Box<'a + Fn( usize, &T ) -> bool> ),
Alt( Box<RegEx<'a, T, U>>, Box<RegEx<'a, T, U>> ),
Seq( Box<RegEx<'a, T, U>>, Box<RegEx<'a, T, U>>, usize ),
Repeat( Box<RegEx<'a, T, U>>, usize ),
Weight( isize ),
Mark( U ),
}
impl<'a, T, U: Copy> ops::Add for Box<RegEx<'a, T, U>> {
type Output = Box<RegEx<'a, T, U>>;
fn add( self, other: Self ) -> Self::Output {
Box::new( RegEx::Alt( self, other ) )
}
}
impl<'a, T, U: Copy> ops::Mul for Box<RegEx<'a, T, U>> {
type Output = Box<RegEx<'a, T, U>>;
fn mul( self, other: Self ) -> Self::Output {
Box::new( RegEx::Seq( self, other, usize::MAX ) )
}
}
pub fn eps<'a, T, U: Copy>() -> Box<RegEx<'a, T, U>> {
Box::new( RegEx::Eps )
}
pub fn atom<'a, T, U: Copy, F: 'a + Fn( usize, &T ) -> bool>( f: F ) -> Box<RegEx<'a, T, U>> {
Box::new( RegEx::Atom( Box::new( f ) ) )
}
pub fn rep<'a, T, U: Copy>( e0: Box<RegEx<'a, T, U>> ) -> Box<RegEx<'a, T, U>> {
Box::new( RegEx::Repeat( e0, usize::MAX ) )
}
pub fn weight<'a, T, U: Copy>( w: isize ) -> Box<RegEx<'a, T, U>> {
Box::new( RegEx::Weight( w ) )
}
pub fn mark<'a, T, U: Copy>( m: U ) -> Box<RegEx<'a, T, U>> {
Box::new( RegEx::Mark( m ) )
}
pub fn opt<'a, T, U: Copy>( e0: Box<RegEx<'a, T, U>> ) -> Box<RegEx<'a, T, U>> {
eps() + e0
}
pub fn any<'a, T, U: Copy>() -> Box<RegEx<'a, T, U>> {
atom( move |_, _| true )
}
pub fn val<'a, T: 'a + PartialEq, U: Copy>( v0: T ) -> Box<RegEx<'a, T, U>> {
atom( move |_, v| *v == v0 )
}
pub struct RegExRoot<'a, T, U: Copy = ()> {
regex: Box<RegEx<'a, T, U>>,
nstate: usize,
}
impl<'a, T, U: Copy> RegExRoot<'a, T, U> {
pub fn new( mut e: Box<RegEx<'a, T, U>> ) -> RegExRoot<'a, T, U> {
let n = Self::renumber( &mut e, 0 );
RegExRoot{
regex: e,
nstate: n,
}
}
fn renumber( e: &mut RegEx<T, U>, i: usize ) -> usize {
match *e {
RegEx::Eps => i,
RegEx::Atom( _ ) => i,
RegEx::Alt( ref mut e0, ref mut e1 ) => {
Self::renumber( e1, Self::renumber( e0, i ) )
}
RegEx::Seq( ref mut e0, ref mut e1, ref mut s ) => {
*s = Self::renumber( e0, i );
Self::renumber( e1, *s + 1 )
}
RegEx::Repeat( ref mut e0, ref mut s ) => {
*s = i;
Self::renumber( e0, i + 1 )
}
RegEx::Weight( _ ) => i,
RegEx::Mark( _ ) => i,
}
}
}
struct Path<T: Copy>( usize, T, Option<rc::Rc<Path<T>>> );
#[derive( Clone )]
struct State<T: Copy>( isize, Option<rc::Rc<Path<T>>> );
#[derive( Clone )]
pub struct Matcher<'a, T: 'a, U: 'a + Copy = ()> {
root: &'a RegExRoot<'a, T, U>,
index: usize,
s0: State<U>,
states: Vec<State<U>>,
s1: State<U>,
}
impl<'a, T, U: Copy> Matcher<'a, T, U> {
pub fn new( root: &'a RegExRoot<'a, T, U> ) -> Matcher<'a, T, U> {
let mut this = Matcher{
root: root,
index: 0,
s0: State( 0, None ),
states: vec![ State( isize::MAX, None ); root.nstate ],
s1: State( isize::MAX, None ),
};
this.s1 = this.propagate( &root.regex, State( 0, None ) );
this
}
pub fn feed( &mut self, v: &T ) {
let s0 = mem::replace( &mut self.s0, State( isize::MAX, None ) );
let s1 = self.shift( &self.root.regex, v, s0 );
self.index += 1;
let s2 = self.propagate( &self.root.regex, State( isize::MAX, None ) );
self.s1 = Self::choice( s1, s2 );
}
pub fn feed_iter<'b, Iter: IntoIterator<Item = &'b T>>( &mut self, iter: Iter ) where 'a: 'b {
for v in iter {
self.feed( v );
}
}
pub fn is_match( &self ) -> bool {
self.s1.0 != isize::MAX
}
pub fn is_alive( &self ) -> bool {
self.s0.0 != isize::MAX ||
self.s1.0 != isize::MAX ||
self.states.iter().any( |s| s.0 != isize::MAX )
}
pub fn path( &self ) -> Vec<(usize, U)> {
let mut result = Vec::new();
let mut it = self.s1.1.clone();
while let Some( e ) = it {
result.push( (e.0, e.1) );
it = e.2.clone();
}
result.reverse();
result
}
fn choice( s0: State<U>, s1: State<U> ) -> State<U> {
if s0.0 < s1.0 { s0 } else { s1 }
}
fn choice_inplace( s0: &mut State<U>, s1: State<U> ) {
if s0.0 > s1.0 {
*s0 = s1;
}
}
fn propagate( &mut self, e: &RegEx<T, U>, s0: State<U> ) -> State<U> {
match *e {
RegEx::Eps => s0,
RegEx::Atom( _ ) => State( isize::MAX, None ),
RegEx::Alt( ref e0, ref e1 ) => {
let s1 = self.propagate( e0, s0.clone() );
let s2 = self.propagate( e1, s0 );
Self::choice( s1, s2 )
}
RegEx::Seq( ref e0, ref e1, s ) => {
let s1 = self.propagate( e0, s0 );
Self::choice_inplace( &mut self.states[s], s1 );
let s2 = self.states[s].clone();
self.propagate( e1, s2 )
}
RegEx::Repeat( ref e0, s ) => {
Self::choice_inplace( &mut self.states[s], s0 );
let s1 = self.states[s].clone();
let s2 = self.propagate( e0, s1 );
Self::choice_inplace( &mut self.states[s], s2 );
self.states[s].clone()
}
RegEx::Weight( w ) => {
let dw = if s0.0 != isize::MAX { w } else { 0 };
State( s0.0 + dw, s0.1 )
}
RegEx::Mark( m ) => {
State( s0.0, Some( rc::Rc::new( Path( self.index, m, s0.1 ) ) ) )
}
}
}
fn shift( &mut self, e: &RegEx<T, U>, v: &T, s0: State<U> ) -> State<U> {
match *e {
RegEx::Eps => State( isize::MAX, None ),
RegEx::Atom( ref f ) => {
if s0.0 != isize::MAX && f( self.index, v ) {
s0
}
else {
State( isize::MAX, None )
}
}
RegEx::Alt( ref e0, ref e1 ) => {
let s1 = self.shift( e0, v, s0.clone() );
let s2 = self.shift( e1, v, s0 );
Self::choice( s1, s2 )
}
RegEx::Seq( ref e0, ref e1, s ) => {
let s1 = self.shift( e0, v, s0 );
let s2 = mem::replace( &mut self.states[s], s1 );
self.shift( e1, v, s2 )
}
RegEx::Repeat( ref e0, s ) => {
let s1 = mem::replace( &mut self.states[s], State( isize::MAX, None ) );
self.states[s] = self.shift( e0, v, s1 );
State( isize::MAX, None )
}
RegEx::Weight( _ ) => State( isize::MAX, None ),
RegEx::Mark( _ ) => State( isize::MAX, None ),
}
}
}