RegularEquationSolver.h

Go to the documentation of this file.

 
#pragma once
 
#include <queue>
 
#include <ext/algorithm>
 
#include <alib/map>
#include <alib/deque>
 
#include <exception/CommonException.h>
 
#include <regexp/unbounded/UnboundedRegExp.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
#include <regexp/unbounded/UnboundedRegExpElements.h>
 
namespace equations {
 
template < class TerminalSymbolType, class VariableSymbolType >
class RegularEquationSolver {
public:
    virtual ~RegularEquationSolver ( ) noexcept = default;
 
    void addVariableSymbol ( const VariableSymbolType & symbol );
 
    void removeVariableSymbol ( const VariableSymbolType & symbol );
 
    void setVariableSymbols ( const ext::set < VariableSymbolType > & newSymbols );
 
    void addEquation ( const VariableSymbolType & from, const VariableSymbolType & to, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq );
 
    void addEquation ( const VariableSymbolType & from, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq );
 
    regexp::UnboundedRegExp < TerminalSymbolType > solve ( const VariableSymbolType & solveFor );
 
protected:
    virtual regexp::UnboundedRegExp < TerminalSymbolType > eliminate ( ) = 0;
 
    void sortSymbolsByDepth ( const VariableSymbolType & solveFor );
 
    ext::deque < VariableSymbolType > nonterminalSymbolsByDepth;
 
    ext::map < std::pair < VariableSymbolType, VariableSymbolType >, regexp::UnboundedRegExpAlternation < TerminalSymbolType > > equationTransition;
 
    ext::map < VariableSymbolType, regexp::UnboundedRegExpAlternation < TerminalSymbolType > > equationFinal;
 
    ext::set < VariableSymbolType > nonterminalSymbols;
};
 
template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::setVariableSymbols ( const ext::set < VariableSymbolType > & newSymbols ) {
    ext::set < VariableSymbolType > removed;
    ext::set < VariableSymbolType > added;
 
    std::set_difference ( nonterminalSymbols.begin ( ), nonterminalSymbols.end ( ), newSymbols.begin ( ), newSymbols.end ( ), std::inserter ( removed, removed.end ( ) ) );
    std::set_difference ( newSymbols.begin ( ), newSymbols.end ( ), nonterminalSymbols.begin ( ), nonterminalSymbols.end ( ), std::inserter ( added, added.end ( ) ) );
 
    for ( const VariableSymbolType & symbol : removed ) {
        removeVariableSymbol ( symbol );
    }
 
    for ( const VariableSymbolType & symbol : added ) {
        addVariableSymbol ( symbol );
    }
}
 
template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::removeVariableSymbol ( const VariableSymbolType & symbol ) {
    for ( const auto & kv : equationTransition ) {
        const VariableSymbolType & from = kv.first.first;
        const VariableSymbolType & to = kv.first.second;
        const regexp::UnboundedRegExpAlternation < TerminalSymbolType > & alt = kv.second;
 
        if ( ( from == symbol || to == symbol ) && !alt.getElements ( ).empty ( ) ) {
            throw exception::CommonException ( "Symbol '" + ext::to_string ( symbol ) + "' is in use." );
        }
    }
 
    for ( const auto & kv : equationFinal ) {
        const VariableSymbolType & from = kv.first;
        const regexp::UnboundedRegExpAlternation < TerminalSymbolType > & alt = kv.second;
 
        if ( from == symbol && !alt.getElements ( ).empty ( ) ) {
            throw exception::CommonException ( "Symbol '" + ext::to_string ( from ) + "' is in use." );
        }
    }
 
 
    nonterminalSymbols.erase ( nonterminalSymbols.find ( symbol ) );
    equationFinal.erase ( equationFinal.find ( symbol ) );
 
    for ( const VariableSymbolType & variable : nonterminalSymbols ) {
        equationTransition.erase ( equationTransition.find ( std::make_pair ( variable, symbol ) ) );
        equationTransition.erase ( equationTransition.find ( std::make_pair ( symbol, variable ) ) );
    }
 
    equationTransition.erase ( equationTransition.find ( std::make_pair ( symbol, symbol ) ) );
}
 
template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::addVariableSymbol ( const VariableSymbolType & symbol ) {
    for ( const VariableSymbolType & variable : nonterminalSymbols) {
        equationTransition.insert ( std::make_pair ( std::make_pair ( symbol, variable ), regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
        equationTransition.insert ( std::make_pair ( std::make_pair ( variable, symbol ), regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
    }
 
    equationTransition.insert ( std::make_pair ( std::make_pair ( symbol, symbol ), regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
 
    nonterminalSymbols.insert ( symbol );
    equationFinal.insert ( std::make_pair ( symbol, regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
}
 
template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::addEquation ( const VariableSymbolType & from, const VariableSymbolType & to, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq ) {
    if ( nonterminalSymbols.count ( from ) == 0 ) {
        throw exception::CommonException ( "Symbol from ('" + ext::to_string ( from ) + "') is not in equation system." );
    }
 
    if ( nonterminalSymbols.count ( to ) == 0 ) {
        throw exception::CommonException ( "Symbol to ('" + ext::to_string ( to ) + "') is not in equation system." );
    }
 
    equationTransition.find ( std::make_pair ( from, to ) )->second.appendElement ( eq );
}
 
template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::addEquation ( const VariableSymbolType & from, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq ) {
    if ( nonterminalSymbols.count ( from ) == 0 ) {
        throw exception::CommonException ( "Symbol from ('" + ext::to_string ( from ) + "') is not in equation system." );
    }
 
    equationFinal.find ( from )->second.appendElement ( eq );
}
 
template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::sortSymbolsByDepth ( const VariableSymbolType & solveFor ) {
    ext::set < VariableSymbolType > visited;
    std::queue < VariableSymbolType > queue;
 
    visited.insert ( solveFor );
    queue.push ( solveFor );
 
    while ( ! queue.empty ( ) ) {
        VariableSymbolType variable = std::move ( queue.front ( ) );
        queue.pop ( );
 
        nonterminalSymbolsByDepth.push_back ( variable );
 
        for ( const auto & kv : equationTransition )
            // find all transitions from current symbol that are non-empty, enqueue transition'variable target symbol
            if ( kv.first.first == variable && !kv.second.getElements ( ).empty ( ) && visited.insert ( kv.first.second ).second )
                queue.push ( kv.first.second );
    }
}
 
template < class TerminalSymbolType, class VariableSymbolType >
regexp::UnboundedRegExp < TerminalSymbolType > RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::solve ( const VariableSymbolType & solveFor ) {
    if ( nonterminalSymbols.count ( solveFor ) == 0 ) {
        throw exception::CommonException ( "Symbol solveFor ('" + ext::to_string ( solveFor ) + "') is not in equation system." );
    }
 
    /*
     * Firstly, organize states by depth so we can output better looking
     * expressions. We need to solve equation system for automaton's initial state,
     * so lets start with the deepest ones and walk towards the initial one.
     */
    sortSymbolsByDepth ( solveFor );
    return eliminate ( );
}
 
} /* namespace equations */