Run.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
#include <ext/iterator>
 
#include <string/LinearString.h>
#include <tree/ranked/RankedTree.h>
#include <tree/ranked/UnorderedRankedTree.h>
 
#include <automaton/FSM/DFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/TA/DFTA.h>
#include <automaton/TA/NFTA.h>
#include <automaton/TA/UnorderedDFTA.h>
#include <automaton/TA/ArcFactoredDeterministicZAutomaton.h>
#include <automaton/PDA/InputDrivenDPDA.h>
#include <automaton/PDA/VisiblyPushdownDPDA.h>
#include <automaton/PDA/RealTimeHeightDeterministicDPDA.h>
#include <automaton/PDA/DPDA.h>
#include <automaton/PDA/NPDA.h>
#include <automaton/PDA/NPDTA.h>
#include <global/GlobalData.h>
 
#include <label/FailStateLabel.h>
 
#include <alib/deque>
 
#include <automaton/properties/EpsilonClosure.h>
 
namespace automaton {
 
namespace run {
 
class Run {
 
    template < class SymbolType >
    struct graphStructuredStack {
        struct Element {
            Element ( std::shared_ptr < Element > parent, SymbolType data ) : m_parent ( std::move ( parent) ), m_data ( std::move ( data ) ) {}
            std::shared_ptr < Element > m_parent;
            SymbolType m_data;
        };
 
        graphStructuredStack ( std::shared_ptr < Element > value ) : m_value ( std::move ( value ) ) { }
 
        std::shared_ptr < Element > m_value;
 
        static std::strong_ordering compareElements ( std::shared_ptr < Element > first, std::shared_ptr < Element > second ) {
            if ( first == nullptr || second == nullptr )
                return first <=> second;
 
            std::strong_ordering res = first->m_data <=> second->m_data;
            if ( res != 0 )
                return res;
 
            return compareElements ( first->m_parent, second->m_parent );
        }
 
        std::strong_ordering operator <=> ( const graphStructuredStack < SymbolType > & other ) const {
            return compareElements ( m_value, other.m_value );
        }
    };
 
    template < class Type >
    static ext::deque < Type > reconstruct ( graphStructuredStack < Type > stack ) {
        std::shared_ptr < typename graphStructuredStack < Type >::Element > stackNode = stack.m_value;
        ext::deque < Type > finalContent;
        while ( stackNode ) {
            finalContent.push_front ( stackNode->m_data );
            stackNode = stackNode->m_parent;
        }
        return finalContent;
    }
 
    template < class SymbolType, class StateType >
    static ext::pair < bool, StateType > calculateState ( const automaton::DFTA < SymbolType, StateType > & automaton, const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::set < unsigned > & occ, unsigned & i );
 
    template < class SymbolType, class StateType >
    static ext::pair < bool, StateType > calculateState ( const automaton::UnorderedDFTA < SymbolType, StateType > & automaton, const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::set < unsigned > & occ, unsigned & i );
 
    template < class SymbolType, class StateType >
    static ext::pair < bool, StateType > calculateState ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const ext::tree < SymbolType > & node, ext::set < unsigned > & occ, unsigned & i );
 
    template < class SymbolType, class StateType >
    static ext::pair < bool, ext::set < StateType > > calculateStates ( const automaton::NFTA < SymbolType, StateType > & automaton, const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::set < unsigned > & occ, unsigned & i );
 
    template < class SymbolType >
    static bool canPop ( const ext::deque < SymbolType > & pushdownStore, const ext::vector < SymbolType > & pop );
 
    template < class Type >
    static bool canPop ( graphStructuredStack < Type > pushdownStore, const ext::vector < Type > & pop );
 
public:
    template < class SymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned > > calculateState ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
 
    template < class SymbolType, class StateType >
    static ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > calculateStates ( const automaton::NFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
 
    template < class SymbolType, class StateType >
    static ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > calculateStates ( const automaton::EpsilonNFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string );
 
    template < class SymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned > > calculateState ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree );
 
    template < class SymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned > > calculateState ( const automaton::UnorderedDFTA < SymbolType, StateType > & automaton, const tree::UnorderedRankedTree < SymbolType > & tree );
 
    template < class SymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned > > calculateState ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree );
 
    template < class SymbolType, class StateType >
    static ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > calculateStates ( const automaton::NFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > calculateState ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > calculateState ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > calculateState ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > calculateState ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
 
    template < class InputSymbolType, class OutputSymbolType, class PushdownStoreSymbolType, class StateType >
    static ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType >, ext::deque < OutputSymbolType > > > calculateStates ( const automaton::NPDTA < InputSymbolType, OutputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > > calculateStates ( const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string );
};
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned > > Run::calculateState ( const automaton::DFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
    unsigned i = 0;
    ext::set < unsigned > occurrences;
    StateType state = automaton.getInitialState ( );
 
    for ( const SymbolType & symbol : string.getContent ( ) ) {
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occurrences.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << state << std::endl;
 
        auto transition = automaton.getTransitions ( ).find ( ext::make_pair ( state, symbol ) );
 
        if ( transition == automaton.getTransitions ( ).end ( ) )
            return ext::make_tuple ( false, state, occurrences );
 
        state = transition->second;
        i++;
    }
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occurrences.insert ( i );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << std::endl;
 
    return ext::make_tuple ( true, state, occurrences );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > Run::calculateStates ( const automaton::NFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
    unsigned i = 0;
    ext::set < unsigned > occurrences;
    ext::set < StateType > states {
        automaton.getInitialState ( )
    };
 
    for ( const StateType & state : states )
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occurrences.insert ( i );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << states << std::endl;
 
    for ( const SymbolType & symbol : string.getContent ( ) ) {
        ext::set < StateType > next;
 
        for ( const StateType & state : states ) {
            auto transitions = automaton.getTransitions ( ).equal_range ( ext::make_pair ( state, symbol ) );
 
            for ( const auto & transition : transitions )
                next.insert ( transition.second );
        }
 
        i++;
        states = next;
 
        for ( const StateType & state : states )
            if ( automaton.getFinalStates ( ).contains ( state ) )
                occurrences.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << states << std::endl;
    }
 
    return ext::make_tuple ( true, states, occurrences );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > Run::calculateStates ( const automaton::EpsilonNFA < SymbolType, StateType > & automaton, const string::LinearString < SymbolType > & string ) {
    unsigned i = 0;
    ext::set < unsigned > occurrences;
    ext::set < StateType > states {
        automaton.getInitialState ( )
    };
 
    for ( const StateType & state : states )
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occurrences.insert ( i );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << states << std::endl;
 
    for ( const SymbolType & symbol : string.getContent ( ) ) {
        ext::set < StateType > next;
 
        for ( const StateType & state : states ) {
            auto transitions = automaton.getTransitions ( ).equal_range ( ext::make_pair ( state, common::symbol_or_epsilon < SymbolType > ( symbol ) ) );
 
            if ( transitions.empty ( ) ) continue;
 
            for ( const auto & transition : transitions )
                next.insert ( transition.second );
        }
 
        ext::set < StateType > epsilonNext;
 
        for ( const StateType & state : next ) {
            const ext::set < StateType > closure = automaton::properties::EpsilonClosure::epsilonClosure ( automaton, state );
            epsilonNext.insert ( closure.begin ( ), closure.end ( ) );
        }
 
        i++;
        states = epsilonNext;
 
        for ( const StateType & state : states )
            if ( automaton.getFinalStates ( ).contains ( state ) )
                occurrences.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << states << std::endl;
    }
 
    return ext::make_tuple ( true, states, occurrences );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::pair < bool, StateType > Run::calculateState ( const automaton::DFTA < SymbolType, StateType > & automaton, const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::set < unsigned > & occ, unsigned & i ) {
    ext::vector < StateType > states;
 
    states.reserve ( node.getData ( ).getRank ( ) );
 
    unsigned tmp = i;
    i++;
 
    bool sign = true;
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) ) {
        ext::pair < bool, StateType > res = calculateState ( automaton, child, occ, i );
 
        if ( ! res.first )
            sign = false;
        else
            states.push_back ( res.second );
    }
 
    if ( ! sign )
        return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
 
    const auto & it = automaton.getTransitions ( ).find ( ext::make_pair ( node.getData ( ), states ) );
 
    if ( it == automaton.getTransitions ( ).end ( ) ) return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
 
    StateType state = it->second;
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( tmp );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << std::endl;
 
    return ext::make_pair ( true, state );
}
 
template < class SymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned > > Run::calculateState ( const automaton::DFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree ) {
    ext::set < unsigned > occ;
    unsigned i = 0;
    ext::pair < bool, StateType > res = calculateState ( automaton, tree.getContent ( ), occ, i );
 
    return ext::make_tuple ( res.first, res.second, occ );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::pair < bool, StateType > Run::calculateState ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const ext::tree < SymbolType > & node, ext::set < unsigned > & occ, unsigned & i ) {
    ext::vector < StateType > childStates;
 
    childStates.reserve ( node.getChildren ( ).size ( ) );
 
    unsigned tmp = i ++;
 
    for ( const ext::tree < SymbolType > & child : node.getChildren ( ) ) {
        ext::pair < bool, StateType > res = calculateState ( automaton, child, occ, i );
 
        if ( ! res.first )
            return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
        else
            childStates.push_back ( res.second );
    }
 
    const auto & it = automaton.getTransitions ( ).find ( node.getData ( ) );
 
    if ( it == automaton.getTransitions ( ).end ( ) )
        return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
 
    StateType state = it->second;
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << childStates;
 
    for ( const StateType & childState : childStates ) {
        const auto & itChildState = automaton.getTransitions ( ).find ( ext::make_pair ( state, childState ) );
 
        if ( itChildState == automaton.getTransitions ( ).end ( ) ) {
            if ( common::GlobalData::verbose )
                common::Streams::log << "->" << label::FailStateLabel::instance < StateType > ( ) << std::endl;
            return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
        }
 
        state = itChildState->second;
 
        if ( common::GlobalData::verbose )
            common::Streams::log << " -> " << state;
    }
 
    if ( common::GlobalData::verbose )
        common::Streams::log << std::endl;
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( tmp );
 
    return ext::make_pair ( true, state );
}
 
template < class SymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned > > Run::calculateState ( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & automaton, const tree::UnrankedTree < SymbolType > & tree ) {
    ext::set < unsigned > occ;
    unsigned i = 0;
    ext::pair < bool, StateType > res = calculateState ( automaton, tree.getContent ( ), occ, i );
 
    return ext::make_tuple ( res.first, res.second, occ );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::pair < bool, StateType > Run::calculateState ( const automaton::UnorderedDFTA < SymbolType, StateType > & automaton, const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::set < unsigned > & occ, unsigned & i ) {
    ext::multiset < StateType > states;
 
    unsigned tmp = i;
    i++;
 
    bool sign = true;
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) ) {
        ext::pair < bool, StateType > res = calculateState ( automaton, child, occ, i );
 
        if ( ! res.first )
            sign = false;
        else
            states.insert ( res.second );
    }
 
    if ( ! sign )
        return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
 
    const auto & it = automaton.getTransitions ( ).find ( ext::make_pair ( node.getData ( ), states ) );
 
    if ( it == automaton.getTransitions ( ).end ( ) ) return ext::make_pair ( false, label::FailStateLabel::instance < StateType > ( ) );
 
    StateType state = it->second;
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( tmp );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << std::endl;
 
    return ext::make_pair ( true, state );
}
 
template < class SymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned > > Run::calculateState ( const automaton::UnorderedDFTA < SymbolType, StateType > & automaton, const tree::UnorderedRankedTree < SymbolType > & tree ) {
    ext::set < unsigned > occ;
    unsigned i = 0;
    ext::pair < bool, StateType > res = calculateState ( automaton, tree.getContent ( ), occ, i );
 
    return ext::make_tuple ( res.first, res.second, occ );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType, class StateType >
ext::pair < bool, ext::set < StateType > > Run::calculateStates ( const automaton::NFTA < SymbolType, StateType > & automaton, const ext::tree < common::ranked_symbol < SymbolType > > & node, ext::set < unsigned > & occ, unsigned & i ) {
    ext::vector < ext::set < StateType > > resStates;
 
    resStates.reserve ( node.getData ( ).getRank ( ) );
 
    unsigned tmp = i;
    i++;
 
    bool sign = true;
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) ) {
        std::pair < bool, ext::set < StateType > > childStates = calculateStates ( automaton, child, occ, i );
 
        if ( childStates.second.empty ( ) )
            sign = false;
 
        resStates.push_back ( childStates.second );
    }
 
    ext::set < StateType > states;
 
    for ( const auto & transition : automaton.getTransitions ( ) ) {
        if ( transition.first.first != node.getData ( ) )
            continue;
 
        unsigned rank = transition.first.first.getRank ( );
        unsigned j;
 
        for ( j = 0; j < rank; j++ )
            if ( ! resStates [ j ].contains ( transition.first.second [ j ] ) )
                break;
 
        if ( j == rank )
            states.insert ( transition.second );
    }
 
    for ( const StateType & state : states )
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occ.insert ( tmp );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << states << std::endl;
 
    return ext::make_pair ( sign, states );
}
 
template < class SymbolType, class StateType >
ext::tuple < bool, ext::set < StateType >, ext::set < unsigned > > Run::calculateStates ( const automaton::NFTA < SymbolType, StateType > & automaton, const tree::RankedTree < SymbolType > & tree ) {
    ext::set < unsigned > occ;
    unsigned i = 0;
    ext::pair < bool, ext::set < StateType > > res = calculateStates ( automaton, tree.getContent ( ), occ, i );
 
    return ext::make_tuple ( res.first, res.second, occ );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class SymbolType >
bool Run::canPop ( const ext::deque < SymbolType > & pushdownStore, const ext::vector < SymbolType > & pop ) {
    unsigned popSize = pop.size ( );
    unsigned pushdownStoreSize = pushdownStore.size ( );
 
    if ( pushdownStoreSize < popSize ) return false;
 
    for ( unsigned i = 0; i < popSize; i++ )
        if ( pop[i] != pushdownStore[pushdownStoreSize - i - 1] )
            return false;
 
    return true;
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > Run::calculateState ( const automaton::InputDrivenDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
    StateType state = automaton.getInitialState ( );
    ext::deque < PushdownStoreSymbolType > pushdownStore {
        automaton.getInitialSymbol ( )
    };
    unsigned i = 0;
    ext::set < unsigned > occ;
 
    for ( const InputSymbolType & symbol : string.getContent ( ) ) {
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occ.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << state << std::endl;
 
        auto transition = automaton.getTransitions ( ).find ( ext::make_pair ( state, symbol ) );
 
        if ( transition == automaton.getTransitions ( ).end ( ) )
            return ext::make_tuple ( false, state, occ, pushdownStore );
 
        const std::pair < ext::vector < PushdownStoreSymbolType >, ext::vector < PushdownStoreSymbolType > > & operation = automaton.getPushdownStoreOperations ( ).find ( symbol )->second;
 
        if ( !canPop ( pushdownStore, operation.first ) )
            return ext::make_tuple ( false, state, occ, pushdownStore );
 
        for ( unsigned j = 0; j < operation.first.size ( ); j++ ) pushdownStore.pop_back ( );
 
        for ( const auto & push : ext::make_reverse ( operation.second ) ) pushdownStore.push_back ( push );
 
        state = transition->second;
        i++;
    }
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( i );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << std::endl;
 
    return ext::make_tuple ( true, state, occ, pushdownStore );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > Run::calculateState ( const automaton::VisiblyPushdownDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
    StateType state = automaton.getInitialState ( );
    ext::deque < PushdownStoreSymbolType > pushdownStore {
        automaton.getBottomOfTheStackSymbol ( )
    };
    unsigned i = 0;
    ext::set < unsigned > occ;
 
    for ( const InputSymbolType & symbol : string.getContent ( ) ) {
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occ.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << state << std::endl;
 
        if ( automaton.getCallInputAlphabet ( ).contains ( symbol ) ) {
            auto transition = automaton.getCallTransitions ( ).find ( ext::make_pair ( state, symbol ) );
 
            if ( transition == automaton.getCallTransitions ( ).end ( ) )
                return ext::make_tuple ( false, state, occ, pushdownStore );
 
            pushdownStore.push_back ( transition->second.second );
            state = transition->second.first;
        } else if ( automaton.getReturnInputAlphabet ( ).contains ( symbol ) ) {
            auto transition = automaton.getReturnTransitions ( ).find ( ext::make_tuple ( state, symbol, pushdownStore.back ( ) ) );
 
            if ( transition == automaton.getReturnTransitions ( ).end ( ) )
                return ext::make_tuple ( false, state, occ, pushdownStore );
 
            if ( pushdownStore.back ( ) != automaton.getBottomOfTheStackSymbol ( ) ) pushdownStore.pop_back ( );
 
            state = transition->second;
        } else if ( automaton.getLocalInputAlphabet ( ).contains ( symbol ) ) {
            auto transition = automaton.getLocalTransitions ( ).find ( ext::make_pair ( state, symbol ) );
 
            if ( transition == automaton.getLocalTransitions ( ).end ( ) )
                return ext::make_tuple ( false, state, occ, pushdownStore );
 
            state = transition->second;
        } else {
            return ext::make_tuple ( false, state, occ, pushdownStore );
        }
 
        i++;
    }
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( i );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << std::endl;
 
    return ext::make_tuple ( true, state, occ, pushdownStore );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > Run::calculateState ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
    StateType state = automaton.getInitialState ( );
    ext::deque < PushdownStoreSymbolType > pushdownStore {
        automaton.getBottomOfTheStackSymbol ( )
    };
    unsigned i = 0;
    ext::set < unsigned > occ;
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( i );
 
    if ( common::GlobalData::verbose )
        common::Streams::log << state << std::endl;
 
    for ( auto symbolIter = string.getContent ( ).begin ( ); symbolIter != string.getContent ( ).end ( ); ) {
 
        bool transitionFound = false;
 
        auto callTransition = automaton.getCallTransitions ( ).find ( std::pair < StateType, common::symbol_or_epsilon < InputSymbolType > > ( state, * symbolIter ) );
 
        if ( callTransition != automaton.getCallTransitions ( ).end ( ) ) {
            symbolIter++;
            i++;
        } else {
            callTransition = automaton.getCallTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
        }
 
        if ( callTransition != automaton.getCallTransitions ( ).end ( ) ) {
            pushdownStore.push_back ( callTransition->second.second );
            state = callTransition->second.first;
            transitionFound = true;
        }
 
        if ( ! transitionFound ) {
            auto returnTransition = automaton.getReturnTransitions ( ).find ( std::tuple < StateType, common::symbol_or_epsilon < InputSymbolType >, PushdownStoreSymbolType > ( state, * symbolIter, pushdownStore.back ( ) ) );
 
            if ( returnTransition != automaton.getReturnTransitions ( ).end ( ) ) {
                symbolIter++;
                i++;
            } else {
                returnTransition = automaton.getReturnTransitions ( ).find ( std::make_tuple ( state, common::symbol_or_epsilon < InputSymbolType > ( ), pushdownStore.back ( ) ) );
            }
 
            if ( returnTransition != automaton.getReturnTransitions ( ).end ( ) ) {
                pushdownStore.pop_back ( );
                state = returnTransition->second;
                transitionFound = true;
            }
        }
 
        if ( ! transitionFound ) {
            auto localTransition = automaton.getLocalTransitions ( ).find ( std::pair < StateType, common::symbol_or_epsilon < InputSymbolType > > ( state, * symbolIter ) );
 
            if ( localTransition != automaton.getLocalTransitions ( ).end ( ) ) {
                symbolIter++;
                i++;
            } else {
                localTransition = automaton.getLocalTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
            }
 
            if ( localTransition != automaton.getLocalTransitions ( ).end ( ) ) {
                state = localTransition->second;
                transitionFound = true;
            }
        }
 
        if ( ! transitionFound )
            return ext::make_tuple ( false, state, occ, pushdownStore );
 
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occ.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << state << std::endl;
    }
 
    while ( true ) {
 
        bool transitionFound = false;
 
        auto callTransition = automaton.getCallTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
 
        if ( callTransition != automaton.getCallTransitions ( ).end ( ) ) {
            pushdownStore.push_back ( callTransition->second.second );
            state = callTransition->second.first;
            transitionFound = true;
        }
 
        if ( ! transitionFound ) {
            auto returnTransition = automaton.getReturnTransitions ( ).find ( std::make_tuple ( state, common::symbol_or_epsilon < InputSymbolType > ( ), pushdownStore.back ( ) ) );
 
            if ( returnTransition != automaton.getReturnTransitions ( ).end ( ) ) {
                pushdownStore.pop_back ( );
                state = returnTransition->second;
                transitionFound = true;
            }
        }
 
        if ( ! transitionFound ) {
            auto localTransition = automaton.getLocalTransitions ( ).find ( std::make_pair ( state, common::symbol_or_epsilon < InputSymbolType > ( ) ) );
 
            if ( localTransition != automaton.getLocalTransitions ( ).end ( ) ) {
                state = localTransition->second;
                transitionFound = true;
            }
        }
 
        if ( ! transitionFound )
            break;
 
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occ.insert ( i );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << state << std::endl;
    }
 
    return ext::make_tuple ( true, state, occ, pushdownStore );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
ext::tuple < bool, StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > Run::calculateState ( const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
    StateType state = automaton.getInitialState ( );
    ext::deque < PushdownStoreSymbolType > pushdownStore {
        automaton.getInitialSymbol ( )
    };
    ext::set < unsigned > occ;
 
    for ( auto symbolIter = string.getContent ( ).begin ( ); symbolIter != string.getContent ( ).end ( ); ) {
 
        if ( automaton.getFinalStates ( ).contains ( state ) )
            occ.insert ( std::distance ( string.getContent ( ).begin ( ), symbolIter ) );
 
        if ( common::GlobalData::verbose ) {
            common::Streams::log << "State : " << state << std::endl;
            common::Streams::log << "PushdownStore : " << pushdownStore << std::endl;
        }
 
        auto transitions = automaton.getTransitionsFromState ( state );
        auto transition  = transitions.begin ( );
 
        for ( ; transition != transitions.end ( ); transition++ ) {
            if ( ( std::get < 1 > ( transition->first ) != * symbolIter ) && !std::get < 1 > ( transition->first ).is_epsilon ( ) ) continue;
 
            if ( canPop ( pushdownStore, std::get < 2 > ( transition->first ) ) ) break;
        }
 
        if ( transition == transitions.end ( ) )
            return ext::make_tuple ( false, state, occ, pushdownStore );
 
        if ( common::GlobalData::verbose )
            common::Streams::log << "Transition: " << transition->first << " to " << transition->second << std::endl;
 
        for ( unsigned j = 0; j < std::get < 2 > ( transition->first ).size ( ); j++ ) pushdownStore.pop_back ( );
 
        for ( const auto & symbol : ext::make_reverse ( transition->second.second ) ) pushdownStore.push_back ( symbol );
 
        state = transition->second.first;
 
        if ( !std::get < 1 > ( transition->first ).is_epsilon ( ) ) {
            symbolIter++;
        }
    }
 
    if ( automaton.getFinalStates ( ).contains ( state ) )
        occ.insert ( string.getContent ( ).size ( ) );
 
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "State: " << state << std::endl;
        common::Streams::log << "PushdownStore: " << pushdownStore << std::endl;
    }
 
    return ext::make_tuple ( true, state, occ, pushdownStore );
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class Type >
bool Run::canPop ( graphStructuredStack < Type > pushdownStore, const ext::vector < Type > & pop ) {
    std::shared_ptr < typename graphStructuredStack < Type >::Element > node = pushdownStore.m_value;
    for ( const Type & symbol : pop ) {
        if ( node == nullptr || node->m_data != symbol )
            return false;
        node = node->m_parent;
    }
 
    return true;
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class InputSymbolType, class OutputSymbolType, class PushdownStoreSymbolType, class StateType >
ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType >, ext::deque < OutputSymbolType > > > Run::calculateStates ( const automaton::NPDTA < InputSymbolType, OutputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
    ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType >, ext::deque < OutputSymbolType > > > res;
 
    ext::deque < ext::tuple < StateType, ext::set < unsigned >, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType >, graphStructuredStack < OutputSymbolType > > > bftQueue;
    graphStructuredStack < PushdownStoreSymbolType > initialStack ( std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( nullptr, automaton.getInitialSymbol ( ) ) );
    graphStructuredStack < OutputSymbolType > initialOutput ( nullptr );
    bftQueue . emplace_back ( automaton . getInitialState (), ext::set < unsigned > {}, string . getContent () . begin (), std::move ( initialStack ), std::move ( initialOutput ) );
 
    ext::set < ext::tuple < StateType, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType > > > bftVisited;
 
    while ( ! bftQueue . empty () ) {
        auto configuration = std::move ( bftQueue . front () );
        bftQueue . pop_front ();
 
        StateType state = std::move ( std::get < 0 > ( configuration ) );
        ext::set < unsigned > occurrences = std::move ( std::get < 1 > ( configuration ) );
        typename ext::vector<InputSymbolType>::const_iterator symbolIter = std::get < 2 > ( configuration );
        graphStructuredStack < PushdownStoreSymbolType > stack = std::get < 3 > ( configuration );
        graphStructuredStack < OutputSymbolType > output = std::get < 4 > ( configuration );
 
        if ( ! bftVisited.insert ( ext::make_tuple ( state, symbolIter, stack ) ).second )
            continue;
 
        if ( symbolIter == string . getContent () . end () ) {
            if ( automaton . getFinalStates () . contains ( state ) || stack.m_value == nullptr ) {
                res.insert ( ext::make_tuple ( state, occurrences, reconstruct ( stack ), reconstruct ( output ) ) );
            }
        }
 
        for ( const auto & transition : automaton . getTransitionsFromState ( state ) ) {
            if ( ( symbolIter == string.getContent ( ).end ( ) || std::get<1>(transition . first) != * symbolIter ) && ! std::get<1>(transition . first) . is_epsilon ( ) )
                continue;
 
            const auto & pop = std::get<2>(transition . first);
 
            if ( ! canPop ( stack, pop ) )
                continue;
 
            std::shared_ptr < typename graphStructuredStack < PushdownStoreSymbolType >::Element > stackNodeCopy = stack.m_value;
            std::shared_ptr < typename graphStructuredStack < OutputSymbolType >::Element > outputNodeCopy = output.m_value;
 
            for ( unsigned j = 0; j < pop . size (); j ++ ) {
                stackNodeCopy = stackNodeCopy -> m_parent;
            }
 
            for ( const auto & elem : ext::make_reverse ( std::get<1>(transition . second ) ) ) {
                stackNodeCopy = std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( stackNodeCopy, elem );
            }
 
            for ( const auto & elem : std::get<2>(transition . second) ) {
                outputNodeCopy = std::make_shared < typename graphStructuredStack < OutputSymbolType >::Element > ( outputNodeCopy, elem );
            }
 
            typename ext::vector<InputSymbolType>::const_iterator nextSymbolIter = symbolIter;
            if ( ! std::get<1>(transition . first) . is_epsilon ( ) )
                ++ nextSymbolIter;
 
            bftQueue . emplace_back ( std::get<0>(transition . second), occurrences, nextSymbolIter, graphStructuredStack < PushdownStoreSymbolType > ( stackNodeCopy ), graphStructuredStack < OutputSymbolType > ( outputNodeCopy ) );
        }
    }
 
    return res;
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > > Run::calculateStates ( const automaton::NPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & automaton, const string::LinearString < InputSymbolType > & string ) {
    ext::set < ext::tuple < StateType, ext::set < unsigned >, ext::deque < PushdownStoreSymbolType > > > res;
 
    ext::deque < ext::tuple < StateType, ext::set < unsigned >, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType > > > bftQueue;
    graphStructuredStack < PushdownStoreSymbolType > initialStack ( std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( nullptr, automaton.getInitialSymbol ( ) ) );
    bftQueue . emplace_back ( automaton . getInitialState (), ext::set < unsigned > {}, string . getContent () . begin (), std::move ( initialStack ) );
 
    ext::set < ext::tuple < StateType, typename ext::vector<InputSymbolType>::const_iterator, graphStructuredStack < PushdownStoreSymbolType > > > bftVisited;
 
    while ( ! bftQueue . empty () ) {
        auto configuration = std::move ( bftQueue . front () );
        bftQueue . pop_front ();
 
        StateType state = std::move ( std::get < 0 > ( configuration ) );
        ext::set < unsigned > occurrences = std::move ( std::get < 1 > ( configuration ) );
        typename ext::vector<InputSymbolType>::const_iterator symbolIter = std::get < 2 > ( configuration );
        graphStructuredStack < PushdownStoreSymbolType > stack = std::get < 3 > ( configuration );
 
        if ( ! bftVisited.insert ( ext::make_tuple ( state, symbolIter, stack ) ).second )
            continue;
 
        if ( symbolIter == string . getContent () . end () ) {
            if ( automaton . getFinalStates () . contains ( state ) || stack.m_value == nullptr ) {
                res.insert ( ext::make_tuple ( state, occurrences, reconstruct ( stack ) ) );
            }
        }
 
        for ( const auto & transition : automaton . getTransitionsFromState ( state ) ) {
            if ( ( symbolIter == string.getContent ( ).end ( ) || std::get<1>(transition . first) != * symbolIter ) && ! std::get<1>(transition . first) . is_epsilon ( ) )
                continue;
 
            const auto & pop = std::get<2>(transition . first);
 
            if ( ! canPop ( stack, pop ) )
                continue;
 
            std::shared_ptr < typename graphStructuredStack < PushdownStoreSymbolType >::Element > stackNodeCopy = stack.m_value;
 
            for ( unsigned j = 0; j < pop . size (); j ++ ) {
                stackNodeCopy = stackNodeCopy -> m_parent;
            }
 
            for ( const auto & elem : ext::make_reverse ( std::get<1>(transition . second ) ) ) {
                stackNodeCopy = std::make_shared < typename graphStructuredStack < PushdownStoreSymbolType >::Element > ( stackNodeCopy, elem );
            }
 
            typename ext::vector<InputSymbolType>::const_iterator nextSymbolIter = symbolIter;
            if ( ! std::get<1>(transition . first) . is_epsilon ( ) )
                ++ nextSymbolIter;
 
            bftQueue . emplace_back ( std::get<0>(transition . second), occurrences, nextSymbolIter, graphStructuredStack < PushdownStoreSymbolType > ( stackNodeCopy ) );
        }
    }
 
    return res;
}
 
// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
} /* namespace run */
 
} /* namespace automaton */