GlushkovLast.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
 
#include <regexp/unbounded/UnboundedRegExp.h>
 
#include <regexp/unbounded/UnboundedRegExpAlternation.h>
#include <regexp/unbounded/UnboundedRegExpConcatenation.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
#include <regexp/unbounded/UnboundedRegExpEmpty.h>
#include <regexp/unbounded/UnboundedRegExpEpsilon.h>
#include <regexp/unbounded/UnboundedRegExpIteration.h>
#include <regexp/unbounded/UnboundedRegExpSymbol.h>
 
#include <regexp/properties/RegExpEpsilon.h>
 
namespace regexp {
 
class GlushkovLast {
public:
    template < class SymbolType >
    static ext::set < UnboundedRegExpSymbol < SymbolType > > last ( const regexp::UnboundedRegExp < SymbolType > & re );
 
    template < class SymbolType >
    class Unbounded {
    public:
        static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpAlternation < SymbolType > & node );
        static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpConcatenation < SymbolType > & node );
        static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpIteration < SymbolType > & node );
        static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpSymbol < SymbolType > & node );
        static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpEmpty < SymbolType > & node );
        static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpEpsilon < SymbolType > & node );
    };
 
    template < class SymbolType >
    static ext::set < FormalRegExpSymbol < SymbolType > > last ( const regexp::FormalRegExp < SymbolType > & re );
 
    template < class SymbolType >
    class Formal {
    public:
        static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpAlternation < SymbolType > & node );
        static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpConcatenation < SymbolType > & node );
        static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpIteration < SymbolType > & node );
        static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpSymbol < SymbolType > & node );
        static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpEmpty < SymbolType > & node );
        static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpEpsilon < SymbolType > & node );
    };
};
 
template < class SymbolType >
ext::set < UnboundedRegExpSymbol < SymbolType > > GlushkovLast::last ( const regexp::UnboundedRegExp < SymbolType > & re ) {
    return re.getRegExp ( ).getStructure ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovLast::Unbounded < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovLast::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpAlternation < SymbolType > & node ) {
    ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ret;
 
    for ( const UnboundedRegExpElement < SymbolType > & element : node.getElements ( ) ) {
        ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > tmp = element.template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovLast::Unbounded < SymbolType > > ( );
        ret.insert ( tmp.begin ( ), tmp.end ( ) );
    }
 
    return ret;
}
 
template < class SymbolType >
ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovLast::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpConcatenation < SymbolType > & node ) {
    ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ret;
 
    for ( const UnboundedRegExpElement < SymbolType > & element : ext::make_reverse ( node.getElements ( ) ) ) {
        ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > tmp = element.template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovLast::Unbounded < SymbolType > > ( );
        ret.insert ( tmp.begin ( ), tmp.end ( ) );
 
        if ( ! regexp::properties::RegExpEpsilon::languageContainsEpsilon ( element ) )
            break;
    }
 
    return ret;
}
 
template < class SymbolType >
ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovLast::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpIteration < SymbolType > & node ) {
    return node.getElement ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovLast::Unbounded < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovLast::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpSymbol < SymbolType > & node ) {
    return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > { node };
}
 
template < class SymbolType >
ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovLast::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpEpsilon < SymbolType > & /* node */ ) {
    return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovLast::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpEmpty < SymbolType > & /* node */ ) {
    return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < FormalRegExpSymbol < SymbolType > > GlushkovLast::last ( const regexp::FormalRegExp < SymbolType > & re ) {
    return re.getRegExp ( ).getStructure ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovLast::Formal < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovLast::Formal < SymbolType >::visit ( const regexp::FormalRegExpAlternation < SymbolType > & node ) {
    ext::set < regexp::FormalRegExpSymbol < SymbolType > > left = node.getLeftElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovLast::Formal < SymbolType > > ( );
    ext::set < regexp::FormalRegExpSymbol < SymbolType > > right = node.getRightElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovLast::Formal < SymbolType > > ( );
    left.insert ( right.begin ( ), right.end ( ) );
    return left;
}
 
template < class SymbolType >
ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovLast::Formal < SymbolType >::visit ( const regexp::FormalRegExpConcatenation < SymbolType > & node ) {
    ext::set < regexp::FormalRegExpSymbol < SymbolType > > right = node.getRightElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovLast::Formal < SymbolType > > ( );
    if ( ! regexp::properties::RegExpEpsilon::languageContainsEpsilon ( node.getRightElement ( ) ) ) // If regexp of this subtree can match epsilon, then we need to add next subtree
        return right;
    ext::set < regexp::FormalRegExpSymbol < SymbolType > > left = node.getLeftElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovLast::Formal < SymbolType > > ( );
    right.insert ( left.begin ( ), left.end ( ) );
    return right;
}
 
template < class SymbolType >
ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovLast::Formal < SymbolType >::visit ( const regexp::FormalRegExpIteration < SymbolType > & node ) {
    return node.getElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovLast::Formal < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovLast::Formal < SymbolType >::visit ( const regexp::FormalRegExpSymbol < SymbolType > & node ) {
    return ext::set < regexp::FormalRegExpSymbol < SymbolType > > { node };
}
 
template < class SymbolType >
ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovLast::Formal < SymbolType >::visit ( const regexp::FormalRegExpEpsilon < SymbolType > & /* node */ ) {
    return ext::set < regexp::FormalRegExpSymbol < SymbolType > > ( );
}
 
template < class SymbolType >
ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovLast::Formal < SymbolType >::visit ( const regexp::FormalRegExpEmpty < SymbolType > & /* node */ ) {
    return ext::set < regexp::FormalRegExpSymbol < SymbolType > > ( );
}
 
} /* namespace regexp */