NFTA.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/TA/NFTA.h>
#include <core/stringApi.hpp>
 
#include <automaton/AutomatonFromStringLexer.h>
 
#include <automaton/string/common/AutomatonFromStringParserCommon.h>
#include <automaton/string/common/AutomatonToStringComposerCommon.h>
 
namespace core {
 
template<class SymbolType, class StateType >
struct stringApi < automaton::NFTA < SymbolType, StateType > > {
    static automaton::NFTA < SymbolType, StateType > parse ( ext::istream & input );
    static bool first ( ext::istream & input );
    static void compose ( ext::ostream & output, const automaton::NFTA < SymbolType, StateType > & automaton );
private:
    static void parseTransition(ext::istream& input, ext::set<StateType>& states, const ext::vector < common::ranked_symbol < SymbolType > >& symbols, ext::set<StateType>& finalStates, ext::set<ext::tuple<ext::vector<StateType>, common::ranked_symbol < SymbolType >, StateType>>& transitionFunction);
    static void composeTransitionsToState(ext::ostream& output, const automaton::NFTA < SymbolType, StateType > & automaton, const StateType & to);
};
 
template<class SymbolType, class StateType >
automaton::NFTA < SymbolType, StateType > stringApi < automaton::NFTA < SymbolType, StateType > >::parse ( ext::istream & input ) {
    automaton::AutomatonFromStringLexer::Token token = automaton::AutomatonFromStringLexer::next(input);
 
    while(token.type == automaton::AutomatonFromStringLexer::TokenType::NEW_LINE) {
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    if(token.type != automaton::AutomatonFromStringLexer::TokenType::NFTA)
        throw exception::CommonException("Unrecognised NFTA token.");
 
    ext::vector < common::ranked_symbol < SymbolType > > symbols;
 
    token = automaton::AutomatonFromStringLexer::next(input);
    while(token.type != automaton::AutomatonFromStringLexer::TokenType::NEW_LINE) {
        automaton::AutomatonFromStringLexer::putback(input, token);
 
        SymbolType symbol = core::stringApi < SymbolType >::parse ( input );
 
        token = automaton::AutomatonFromStringLexer::next ( input );
        if ( token.type != automaton::AutomatonFromStringLexer::TokenType::RANK )
            throw exception::CommonException ( "Missing rank" );
 
        unsigned rank = ext::from_string < unsigned > ( token.value );
 
        symbols.push_back ( common::ranked_symbol < SymbolType > ( std::move ( symbol ), rank ) );
 
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    ext::set<StateType> finalStates;
    ext::set<StateType> states;
    ext::set<ext::tuple<ext::vector < StateType >, common::ranked_symbol < SymbolType >, StateType > > transitionFunction; // from state, on symbol, to state
 
    while(token.type == automaton::AutomatonFromStringLexer::TokenType::NEW_LINE) {
        token = automaton::AutomatonFromStringLexer::next(input);
        if(token.type == automaton::AutomatonFromStringLexer::TokenType::TEOF)
            break;
        else if (token.type == automaton::AutomatonFromStringLexer::TokenType::NEW_LINE)
            continue;
        else
            automaton::AutomatonFromStringLexer::putback(input, token);
 
        parseTransition(input, states, symbols, finalStates, transitionFunction);
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    if(token.type != automaton::AutomatonFromStringLexer::TokenType::TEOF)
        throw exception::CommonException("Extra data after the automaton.");
 
    automaton::NFTA < > res { };
 
    res.setInputAlphabet ( ext::set < common::ranked_symbol < SymbolType > > ( symbols.begin ( ), symbols.end ( ) ) );
    res.setStates(states);
    res.setFinalStates(finalStates);
 
    for ( const ext::tuple < ext::vector < StateType >, common::ranked_symbol < SymbolType >, StateType > & transition : transitionFunction )
        res.addTransition(std::get<1>(transition), std::get<0>(transition), std::get<2>(transition));
 
    return res;
}
 
template<class SymbolType, class StateType >
void stringApi < automaton::NFTA < SymbolType, StateType > >::parseTransition(ext::istream& input, ext::set<StateType>& states, const ext::vector < common::ranked_symbol < SymbolType > > & symbols, ext::set<StateType>& finalStates, ext::set<ext::tuple<ext::vector<StateType>, common::ranked_symbol < SymbolType >, StateType>>& transitionFunction) {
    automaton::AutomatonFromStringLexer::Token token = automaton::AutomatonFromStringLexer::next(input);
    typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator iter = symbols.begin();
 
    ext::set<ext::tuple<ext::vector<StateType>, common::ranked_symbol < SymbolType >>> innerTransitionFunction;
 
    while ( iter != symbols.end ( ) ) {
        if(token.type != automaton::AutomatonFromStringLexer::TokenType::NONE) {
            automaton::AutomatonFromStringLexer::putback(input, token);
            do {
                ext::vector < StateType > from = automaton::AutomatonFromStringParserCommon::parseList < StateType > ( input );
                for ( const StateType & state : from ) {
                    states.insert ( state );
                }
                innerTransitionFunction.insert(ext::make_tuple(std::move ( from ), *iter));
 
                token = automaton::AutomatonFromStringLexer::next(input);
            } while ( token.type == automaton::AutomatonFromStringLexer::TokenType::COMMA );
        } else {
            token = automaton::AutomatonFromStringLexer::next(input);
        }
 
        ++iter;
    }
    automaton::AutomatonFromStringLexer::putback(input, token);
 
    StateType to = core::stringApi<StateType>::parse(input);
    states.insert ( to );
 
    bool initial = false;
    bool final = false;
 
    automaton::AutomatonFromStringParserCommon::initialFinalState(input, final, initial);
    if ( initial )
        throw exception::CommonException ( "NFTA automata do not have initial states." );
    if ( final )
        finalStates.insert ( to );
 
    token = automaton::AutomatonFromStringLexer::next(input);
    if ( token.type != automaton::AutomatonFromStringLexer::TokenType::NEW_LINE && token.type != automaton::AutomatonFromStringLexer::TokenType::TEOF )
        throw exception::CommonException("Invalid line format");
 
    automaton::AutomatonFromStringLexer::putback(input, token);
 
    for ( ext::tuple < ext::vector < StateType >, common::ranked_symbol < SymbolType > > && innerTransition : ext::make_mover ( innerTransitionFunction ) ) {
        transitionFunction.insert ( ext::make_tuple ( std::move ( std::get < 0 > ( innerTransition ) ), std::move ( std::get < 1 > ( innerTransition ) ), to ) );
    }
}
 
template<class SymbolType, class StateType >
bool stringApi < automaton::NFTA < SymbolType, StateType > >::first ( ext::istream & input ) {
    return automaton::AutomatonFromStringLexer::peek ( input ).type == automaton::AutomatonFromStringLexer::TokenType::NFTA;
}
 
template<class SymbolType, class StateType >
void stringApi < automaton::NFTA < SymbolType, StateType > >::compose ( ext::ostream & output, const automaton::NFTA < SymbolType, StateType > & automaton ) {
    output << "NFTA";
    for(const auto& symbol : automaton.getInputAlphabet()) {
        output << " ";
        core::stringApi < SymbolType >::compose(output, symbol.getSymbol ( ) );
        output << " " << ext::to_string ( symbol.getRank ( ) );
    }
 
    output << std::endl;
 
    for(const auto& state : automaton.getStates()) {
        composeTransitionsToState(output, automaton, state);
 
        output << ' ';
        core::stringApi<StateType>::compose(output, state);
 
        if(automaton.getFinalStates().find(state) != automaton.getFinalStates().end())
            output << " >";
 
        output << std::endl;
    }
}
 
template < class SymbolType, class StateType >
void stringApi < automaton::NFTA < SymbolType, StateType > >::composeTransitionsToState(ext::ostream& output, const automaton::NFTA < SymbolType, StateType > & automaton, const StateType & to) {
    ext::multimap < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < StateType > >, StateType > symbolTransitionsToState = automaton.getTransitionsToState(to);
    auto toStateTransitionsIter = symbolTransitionsToState.begin ( );
 
    for(const common::ranked_symbol < SymbolType > & inputSymbol : automaton.getInputAlphabet()) {
        output << ' ';
        bool first = true;
        if ( toStateTransitionsIter == symbolTransitionsToState.end ( ) || toStateTransitionsIter->first.first != inputSymbol ) {
            output << '-';
        } else while ( toStateTransitionsIter != symbolTransitionsToState.end ( ) && toStateTransitionsIter->first.first == inputSymbol ) {
            if ( ! first )
                output << ", ";
 
            first = false;
 
            automaton::AutomatonToStringComposerCommon::composeList ( output, toStateTransitionsIter->first.second );
            ++ toStateTransitionsIter;
        }
    }
}
 
} /* namespace core */