GlushkovFollowNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/map>
#include <alib/set>
#include <alib/vector>
#include <common/ranked_symbol.hpp>
 
#include <rte/formal/FormalRTE.h>
#include <rte/formal/FormalRTEElements.h>
 
#include "GlushkovFirst.h"
#include "GlushkovPos.h"
 
namespace rte {
 
class GlushkovFollowNaive {
 
    // --------------------------------------------------------------------
 
    template < class SymbolType >
    using TSubstMap = ext::map < common::ranked_symbol < SymbolType >, ext::set < common::ranked_symbol < SymbolType > > >;
 
    template < class SymbolType >
    using TAlphabet = ext::set < common::ranked_symbol < SymbolType > >;
 
    // --------------------------------------------------------------------
 
    template < class SymbolType >
    static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > replaceConstants ( const TAlphabet < SymbolType > & alphabetK, const ext::vector < ext::set < common::ranked_symbol < SymbolType > > > & follow, const TSubstMap < SymbolType > & subMap2 );
 
    template < class SymbolType >
    static void preprocessSubMap ( const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap );
 
    template < class SymbolType >
    static ext::vector < ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > cartesian ( const ext::vector < ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > & input );
 
    template < class T >
    static void cartesian_rec ( const ext::vector < ext::vector < T > > & input, ext::vector < ext::vector < T > > & ret, ext::vector < T > & current, size_t depth );
 
public:
    template < class SymbolType >
    static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > follow ( const rte::FormalRTE < SymbolType > & rte, const common::ranked_symbol < SymbolType > & symbol );
 
    template < class SymbolType >
    class Formal {
    public:
        static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > visit ( const rte::FormalRTEAlternation < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap );
        static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > visit ( const rte::FormalRTESubstitution < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap );
        static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > visit ( const rte::FormalRTEIteration < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap );
        static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > visit ( const rte::FormalRTESymbolAlphabet < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap );
        static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > visit ( const rte::FormalRTESymbolSubst < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbol, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subM );
        static ext::set < ext::vector < common::ranked_symbol < SymbolType > > > visit ( const rte::FormalRTEEmpty < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbol, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subM );
    };
 
};
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::follow ( const rte::FormalRTE < SymbolType > & rte, const common::ranked_symbol < SymbolType > & symbol ) {
    TSubstMap < SymbolType > subMap;
 
     /* Init substitution map, ie \forall a \in K: sub[a] = \emptyset */
    for ( const common::ranked_symbol < SymbolType > & ssymb : rte.getSubstitutionAlphabet ( ) )
        subMap.insert ( std::make_pair ( ssymb, TAlphabet < SymbolType > { } ) );
 
     /* recursively compute follow */
    return rte.getRTE ( ).getStructure ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbol, rte.getSubstitutionAlphabet ( ), subMap );
}
 
// -----------------------------------------------------------------------------
 
template < class T >
void GlushkovFollowNaive::cartesian_rec ( const ext::vector < ext::vector < T > > & input, ext::vector < ext::vector < T > > & ret, ext::vector < T > & current, size_t depth ) {
    if ( depth == input.size ( ) )
        ret.push_back ( current );
    else
        for ( size_t i = 0; i < input[depth].size ( ); i++ ) {
            current[depth] = input[depth][i];
            cartesian_rec ( input, ret, current, depth + 1 );
        }
}
 
template < class SymbolType >
ext::vector < ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > GlushkovFollowNaive::cartesian ( const ext::vector < ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > & input ) {
    ext::vector < ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > ret;
    ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > current ( input.size ( ), common::ranked_symbol < ext::pair < SymbolType, unsigned > > ( ext::make_pair ( SymbolType ( 0 ), 0u ), 0 ) );
 
    cartesian_rec ( input, ret, current, 0 );
 
    return ret;
}
 
template < class SymbolType >
void GlushkovFollowNaive::preprocessSubMap ( const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap ) {
    for ( bool change = true; change; change = false )
        for ( std::pair < const common::ranked_symbol < SymbolType >, TAlphabet < SymbolType > > & kv : subMap ) {
            TAlphabet < SymbolType > & substSet = kv.second;
 
            for ( auto eIter = substSet.begin ( ); eIter != substSet.end ( ); ) {
                if ( alphabetK.count ( * eIter ) == 0 ) {
                    ++eIter;
                } else {
                    auto it = subMap.find ( * eIter );
                    size_t oldSize = substSet.size ( );
                    substSet.insert ( it->second.begin ( ), it->second.end ( ) );
                    change = ( oldSize != substSet.size ( ) ); // something was added
                    eIter = substSet.erase ( eIter );
                }
            }
        }
}
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::replaceConstants ( const TAlphabet < SymbolType > & alphabetK, const ext::vector < ext::set < common::ranked_symbol < SymbolType > > > & follow, const TSubstMap < SymbolType > & subMap2 ) {
    TSubstMap < SymbolType > subMap ( subMap2 );
    preprocessSubMap ( alphabetK, subMap );
 
    ext::vector < ext::vector < common::ranked_symbol < SymbolType > > > input;
 
    for ( const ext::set < common::ranked_symbol < SymbolType > > & s : follow ) {
        for ( const common::ranked_symbol < SymbolType > & e : s ) {
            if ( alphabetK.count ( e ) > 0 )
                input.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( subMap.at ( e ).begin ( ), subMap.at ( e ).end ( ) ) );
            else
                input.push_back ( ext::vector < common::ranked_symbol < SymbolType > > { e } );
        }
    }
 
     /* now do the cartesian product on "input" */
    ext::vector < ext::vector < common::ranked_symbol < SymbolType > > > followSet = cartesian ( input );
    return ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ( followSet.begin ( ), followSet.end ( ) );
}
 
// -----------------------------------------------------------------------------
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::Formal < SymbolType >::visit ( const rte::FormalRTEAlternation < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap ) {
    ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ret;
    ext::set < ext::vector < common::ranked_symbol < SymbolType > > > tmp;
 
    tmp = node.getLeftElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
    ret.insert ( tmp.begin ( ), tmp.end ( ) );
 
    tmp = node.getRightElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
    ret.insert ( tmp.begin ( ), tmp.end ( ) );
 
    return ret;
}
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::Formal < SymbolType >::visit ( const rte::FormalRTESubstitution < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap ) {
 
    TSubstMap < SymbolType > subMap2 ( subMap );
    auto itMap = subMap2.find ( node.getSubstitutionSymbol ( ).getSymbol ( ) );
 
    itMap->second.clear ( );
 
    for ( const auto & s : node.getRightElement ( ).template accept < TAlphabet < SymbolType >, GlushkovFirst::Formal < SymbolType > > ( ) )
        itMap->second.insert ( s );
 
    /*
     * E sub F
     *   1. if symbolF in F subtree, then Follow(F, symbolF);
     *   2. if symbolF in E subtree, then Follow(E, symbolF);
     */
 
    if ( node.getLeftElement ( ).template accept < bool, GlushkovPos::Formal < SymbolType > > ( symbolF ) )
        return node.getLeftElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap2 );
    else
        return node.getRightElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
}
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::Formal < SymbolType >::visit ( const rte::FormalRTEIteration < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap ) {
 
    ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ret;
 
    auto itMap = subMap.find ( node.getSubstitutionSymbol ( ).getSymbol ( ) );
    ext::set < common::ranked_symbol < SymbolType > > backup = itMap->second;
 
    for ( const auto & s : node.getElement ( ).template accept < TAlphabet < SymbolType >, GlushkovFirst::Formal < SymbolType > > ( ) )
        subMap[node.getSubstitutionSymbol ( ).getSymbol ( )].insert ( s );
 
    auto res = node.getElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
    itMap->second = backup;
    return res;
}
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::Formal < SymbolType >::visit ( const rte::FormalRTESymbolAlphabet < SymbolType > & node, const common::ranked_symbol < SymbolType > & symbolF, const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap ) {
 
    ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ret;
    ext::set < ext::vector < common::ranked_symbol < SymbolType > > > tmp;
 
    if ( symbolF == node.getSymbol ( ) ) {
        ext::vector < ext::set < common::ranked_symbol < SymbolType > > > children;
 
        for ( const rte::FormalRTEElement < SymbolType > & c : node.getElements ( ) )
            children.push_back ( c.template accept < TAlphabet < SymbolType >, GlushkovFirst::Formal < SymbolType > > ( ) );
 
        return replaceConstants ( alphabetK, children, subMap );
    }
 
    for ( const auto & c : node.getElements ( ) ) {
        tmp = c.template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
        ret.insert ( tmp.begin ( ), tmp.end ( ) );
    }
 
    return ret;
}
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::Formal < SymbolType >::visit ( const rte::FormalRTESymbolSubst < SymbolType > & /* node */, const common::ranked_symbol < SymbolType > & /* symbolF */, const TAlphabet < SymbolType > & /* alphabetK */, TSubstMap < SymbolType > & /* subMap */ ) {
    return ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ( );
}
 
template < class SymbolType >
ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::Formal < SymbolType >::visit ( const rte::FormalRTEEmpty < SymbolType > & /* node */, const common::ranked_symbol < SymbolType > & /* symbolF */, const TAlphabet < SymbolType > & /* alphabetK */, TSubstMap < SymbolType > & /* subMap */ ) {
    return ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ( );
}
 
} /* namespace rte */