RegExpDerivation.h

Go to the documentation of this file.

 
#pragma once
 
#include <regexp/formal/FormalRegExp.h>
#include <regexp/formal/FormalRegExpElement.h>
#include <regexp/unbounded/UnboundedRegExp.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
 
#include <string/LinearString.h>
 
#include <regexp/unbounded/UnboundedRegExpElements.h>
#include <regexp/formal/FormalRegExpElements.h>
 
#include <regexp/properties/RegExpEpsilon.h>
 
namespace regexp {
 
namespace transform {
 
class RegExpDerivation {
public:
    template < class SymbolType >
    static regexp::FormalRegExp < SymbolType > derivation(const regexp::FormalRegExp < SymbolType > & regexp, const string::LinearString < SymbolType > & string);
 
    template < class SymbolType >
    static regexp::UnboundedRegExp < SymbolType > derivation(const regexp::UnboundedRegExp < SymbolType > & regexp, const string::LinearString < SymbolType > & string);
 
    template < class SymbolType >
    static regexp::FormalRegExp < SymbolType > derivation(const regexp::FormalRegExp < SymbolType > & regexp, const SymbolType & symbol);
 
    template < class SymbolType >
    static regexp::UnboundedRegExp < SymbolType > derivation(const regexp::UnboundedRegExp < SymbolType > & regexp, const SymbolType & symbol);
 
private:
    template < class SymbolType >
    class Formal {
    public:
        static std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > visit(const regexp::FormalRegExpAlternation < SymbolType > & alternation, const SymbolType& argument);
        static std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > visit(const regexp::FormalRegExpConcatenation < SymbolType > & concatenation, const SymbolType& argument);
        static std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > visit(const regexp::FormalRegExpIteration < SymbolType > & iteration, const SymbolType& argument);
        static std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > visit(const regexp::FormalRegExpSymbol < SymbolType > & symbol, const SymbolType& argument);
        static std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > visit(const regexp::FormalRegExpEpsilon < SymbolType > & epsilon, const SymbolType& argument);
        static std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > visit(const regexp::FormalRegExpEmpty < SymbolType > & empty, const SymbolType& argument);
    };
 
    template < class SymbolType >
    class Unbounded {
    public:
        static std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > visit(const regexp::UnboundedRegExpAlternation < SymbolType > & alternation, const SymbolType& argument);
        static std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > visit(const regexp::UnboundedRegExpConcatenation < SymbolType > & concatenation, const SymbolType& argument);
        static std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > visit(const regexp::UnboundedRegExpIteration < SymbolType > & iteration, const SymbolType& argument);
        static std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > visit(const regexp::UnboundedRegExpSymbol < SymbolType > & symbol, const SymbolType& argument);
        static std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > visit(const regexp::UnboundedRegExpEpsilon < SymbolType > & epsilon, const SymbolType& argument);
        static std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > visit(const regexp::UnboundedRegExpEmpty < SymbolType > & empty, const SymbolType& argument);
    };
};
 
template < class SymbolType >
regexp::FormalRegExp < SymbolType > RegExpDerivation::derivation(const regexp::FormalRegExp < SymbolType > & regexp, const SymbolType & symbol) {
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > newRegExp = regexp.getRegExp().getStructure().template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType >>(symbol);
 
    return regexp::FormalRegExp < SymbolType > ( regexp::FormalRegExpStructure < SymbolType > ( std::move ( * newRegExp ) ) );
}
 
template < class SymbolType >
regexp::UnboundedRegExp < SymbolType > RegExpDerivation::derivation(const regexp::UnboundedRegExp < SymbolType > & regexp, const SymbolType & symbol) {
    std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > newRegExp = regexp.getRegExp().getStructure().template accept<std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Unbounded < SymbolType > > ( symbol );
 
    return regexp::UnboundedRegExp < SymbolType > ( regexp::UnboundedRegExpStructure < SymbolType > ( std::move ( * newRegExp ) ) );
}
 
template < class SymbolType >
regexp::FormalRegExp < SymbolType > RegExpDerivation::derivation(const regexp::FormalRegExp < SymbolType > & regexp, const string::LinearString < SymbolType >& string) {
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > newRegExp ( regexp.getRegExp().getStructure().clone() );
 
    for(const auto& symbol : string.getContent())
        newRegExp = newRegExp->template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType >>(symbol);
 
    return regexp::FormalRegExp < SymbolType > ( regexp::FormalRegExpStructure < SymbolType > ( std::move ( * newRegExp ) ) );
}
 
template < class SymbolType >
regexp::UnboundedRegExp < SymbolType > RegExpDerivation::derivation(const regexp::UnboundedRegExp < SymbolType > & regexp, const string::LinearString < SymbolType >& string) {
    std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > newRegExp ( regexp.getRegExp().getStructure().clone() );
 
    for(const auto& symbol : string.getContent())
        newRegExp = newRegExp->template accept<std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Unbounded < SymbolType > > ( symbol );
 
    return regexp::UnboundedRegExp < SymbolType > ( regexp::UnboundedRegExpStructure < SymbolType > ( std::move ( * newRegExp ) ) );
}
 
// ----------------------------------------------------------------------------
 
template < class SymbolType >
std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > RegExpDerivation::Formal < SymbolType >::visit(const regexp::FormalRegExpAlternation < SymbolType > & alternation, const SymbolType& argument) {
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > leftDerivative = alternation.getLeftElement().template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType >>(argument);
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > rightDerivative = alternation.getRightElement().template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType >>(argument);
 
    return std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpAlternation < SymbolType > ( std::move ( * leftDerivative ), std::move ( * rightDerivative ) ) );
}
 
template < class SymbolType >
std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > RegExpDerivation::Formal < SymbolType >::visit(const regexp::FormalRegExpConcatenation < SymbolType > & concatenation, const SymbolType& argument) {
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > leftDerivative = concatenation.getLeftElement().template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType >>(argument);
 
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > res ( new regexp::FormalRegExpConcatenation < SymbolType > ( std::move ( * leftDerivative ), ext::move_copy ( concatenation.getRightElement ( ) ) ) );
 
    if(regexp::properties::RegExpEpsilon::languageContainsEpsilon(concatenation.getLeftElement())) {
        std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > rightDerivative = concatenation.getRightElement().template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType >>(argument);
 
        res = std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpAlternation < SymbolType > ( std::move ( * res ), std::move( * rightDerivative ) ) );
    }
 
    return res;
}
 
template < class SymbolType >
std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > RegExpDerivation::Formal < SymbolType >::visit(const regexp::FormalRegExpIteration < SymbolType > & iteration, const SymbolType& argument) {
    std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > elementDerivative = iteration.getElement().template accept<std::unique_ptr < regexp::FormalRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Formal < SymbolType > > ( argument );
    return std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpConcatenation < SymbolType > ( * elementDerivative, iteration ) );
}
 
template < class SymbolType >
std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > RegExpDerivation::Formal < SymbolType >::visit(const regexp::FormalRegExpSymbol < SymbolType > & symbol, const SymbolType& argument) {
    if(argument == symbol.getSymbol())
        return std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpEpsilon < SymbolType > () );
    else
        return std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpEmpty < SymbolType > () );
}
 
template < class SymbolType >
std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > RegExpDerivation::Formal < SymbolType >::visit(const regexp::FormalRegExpEpsilon < SymbolType > &, const SymbolType&) {
    return std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpEmpty < SymbolType > () );
}
 
template < class SymbolType >
std::unique_ptr < regexp::FormalRegExpElement < SymbolType > > RegExpDerivation::Formal < SymbolType >::visit(const regexp::FormalRegExpEmpty < SymbolType > &, const SymbolType&) {
    return std::unique_ptr < FormalRegExpElement < SymbolType > > ( new regexp::FormalRegExpEmpty < SymbolType > () );
}
 
// ----------------------------------------------------------------------------
 
template < class SymbolType >
std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > RegExpDerivation::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpAlternation < SymbolType > & alternation, const SymbolType& argument) {
    std::unique_ptr < regexp::UnboundedRegExpAlternation < SymbolType > > ret ( new regexp::UnboundedRegExpAlternation < SymbolType > () );
 
    for(const UnboundedRegExpElement < SymbolType > & child : alternation.getElements())
        ret->appendElement( * ( child.template accept<std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Unbounded < SymbolType > > ( argument ) ) );
 
    return std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( ret ) );
}
 
template < class SymbolType >
std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > RegExpDerivation::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpConcatenation < SymbolType > & concatenation, const SymbolType& argument) {
    std::unique_ptr < regexp::UnboundedRegExpAlternation < SymbolType > > ret ( new regexp::UnboundedRegExpAlternation < SymbolType > () );
 
    for(auto child = concatenation.getElements().begin(); child != concatenation.getElements().end(); ++ child) {
        regexp::UnboundedRegExpConcatenation < SymbolType > concat;
        concat.appendElement( * ( child->template accept<std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Unbounded < SymbolType > > ( argument ) ) );
 
        auto succeedingElement = child;
        while ( ++ succeedingElement != concatenation.getElements().end())
            concat.appendElement ( * succeedingElement );
 
        ret->appendElement ( std::move ( concat ) );
 
        if( ! regexp::properties::RegExpEpsilon::languageContainsEpsilon ( * child ) )
            break;
    }
 
    return std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( ret ) );
}
 
template < class SymbolType >
std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > RegExpDerivation::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpIteration < SymbolType > & iteration, const SymbolType& argument) {
    std::unique_ptr < UnboundedRegExpConcatenation < SymbolType > > con ( new regexp::UnboundedRegExpConcatenation < SymbolType > ( ) );
    con->appendElement ( * ( iteration.getElement().template accept<std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > >, regexp::transform::RegExpDerivation::Unbounded < SymbolType > > ( argument ) ) );
    con->appendElement ( iteration );
    return std::unique_ptr < UnboundedRegExpElement < SymbolType > > ( std::move ( con ) );
}
 
template < class SymbolType >
std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > RegExpDerivation::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpSymbol < SymbolType > & symbol, const SymbolType& argument) {
    if(argument == symbol.getSymbol())
        return std::unique_ptr < UnboundedRegExpElement < SymbolType > > ( new regexp::UnboundedRegExpEpsilon < SymbolType > () );
    else
        return std::unique_ptr < UnboundedRegExpElement < SymbolType > > ( new regexp::UnboundedRegExpEmpty < SymbolType > () );
}
 
template < class SymbolType >
std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > RegExpDerivation::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpEpsilon < SymbolType > &, const SymbolType&) {
    return std::unique_ptr < UnboundedRegExpElement < SymbolType > > ( new regexp::UnboundedRegExpEmpty < SymbolType > () );
}
 
template < class SymbolType >
std::unique_ptr < regexp::UnboundedRegExpElement < SymbolType > > RegExpDerivation::Unbounded < SymbolType >::visit(const regexp::UnboundedRegExpEmpty < SymbolType > &, const SymbolType&) {
    return std::unique_ptr < UnboundedRegExpElement < SymbolType > > ( new regexp::UnboundedRegExpEmpty < SymbolType > () );
}
 
} /* namespace transform */
 
} /* namespace regexp */