ExactNonlinearTreePatternAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/pair>
#include <alib/deque>
#include <alib/vector>
 
#include <common/ranked_symbol.hpp>
 
#include <tree/ranked/PrefixRankedTree.h>
#include <automaton/PDA/InputDrivenNPDA.h>
 
#include <tree/properties/ExactSubtreeRepeatsNaive.h>
 
namespace arbology {
 
namespace exact {
 
class ExactNonlinearTreePatternAutomaton {
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > constructInternal ( const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables );
 
    template < class SymbolType >
    static void constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, unsigned subtreeId, bool nonlinearJumps, typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator rankedSymbolsIter, unsigned i, typename ext::vector < common::ranked_symbol < unsigned > >::const_iterator subtreeRepeatsIter );
 
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > constructInternal ( const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const common::ranked_symbol < SymbolType > & variablesBar );
 
    template < class SymbolType >
    static void constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const common::ranked_symbol < SymbolType > & variablesBar, unsigned subtreeId, bool nonlinearJumps, typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator rankedSymbolsIter, unsigned i, typename ext::vector < common::ranked_symbol < unsigned > >::const_iterator subtreeRepeatsIter );
 
public:
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > construct ( const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables );
 
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > construct ( const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const common::ranked_symbol < SymbolType > & variablesBar );
};
 
template < class SymbolType >
void ExactNonlinearTreePatternAutomaton::constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, unsigned subtreeId, bool nonlinearJumps, typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator rankedSymbolsIter, unsigned i, typename ext::vector < common::ranked_symbol < unsigned > >::const_iterator subtreeRepeatsIter ) {
    ext::deque < std::pair < size_t, unsigned > > subtreeJumps;
    ext::deque < unsigned > subtreeRepeatsStack;
 
    for (++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i; rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i ) {
        common::ranked_symbol < SymbolType > symbol = * rankedSymbolsIter;
        subtreeJumps.push_back ( std::make_pair ( symbol.getRank ( ), i - 1 ) );
        subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );
 
        ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, subtreeId + 1 );
        ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, subtreeId + 1 );
 
        res.addState ( currentState );
 
        res.addTransition ( previousState, std::move ( symbol ), currentState );
 
        while ( !subtreeJumps.empty ( ) && subtreeJumps.back ( ).first == 0 ) {
            ext::pair < unsigned, unsigned > source = ext::make_pair ( subtreeJumps.back ( ).second, subtreeId + 1 );
            res.addTransition ( source, subtreeWildcard, currentState );
 
            for ( const common::ranked_symbol < SymbolType > & nonlinearVariable : nonlinearVariables )
                if ( nonlinearVariable != currentNonlinearVariable || ( subtreeId == subtreeRepeatsStack.back ( ) && nonlinearJumps ) )
                    res.addTransition ( source, nonlinearVariable, currentState );
 
            if ( !subtreeJumps.empty ( ) ) {
                subtreeJumps.pop_back ( );
                subtreeRepeatsStack.pop_back ( );
            }
        }
 
        if ( !subtreeJumps.empty ( ) ) subtreeJumps.back ( ).first--;
    }
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::constructInternal ( const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables ) {
    char S = alphabet::WildcardSymbol::instance < char > ( );
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > res ( ext::make_pair ( 0u, 0u ), S );
 
    tree::PrefixRankedTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( tree );
 
    std::vector < unsigned > repeatsFrequency ( repeats.getContent ( ).size ( ), 0 );
    for ( const common::ranked_symbol < unsigned > & repeat : repeats.getContent ( ) )
        ++ repeatsFrequency [ repeat.getSymbol ( ) ];
 
    for ( const common::ranked_symbol < SymbolType > & symbol : tree.getAlphabet ( ) ) {
        res.addInputSymbol ( symbol );
        res.setPushdownStoreOperation ( symbol, ext::vector < char > ( 1, S ), ext::vector < char > ( symbol.getRank ( ), S ) );
    }
 
    res.addInputSymbol ( subtreeWildcard );
    res.setPushdownStoreOperation ( subtreeWildcard, ext::vector < char > ( 1, S ), ext::vector < char > { } );
 
    for ( const common::ranked_symbol < SymbolType > & nonlinearVariable : nonlinearVariables ) {
        res.addInputSymbol ( nonlinearVariable );
        res.setPushdownStoreOperation ( nonlinearVariable, ext::vector < char > ( 1, S ), ext::vector < char > { } );
    }
 
    unsigned i = 1;
    ext::deque < std::pair < size_t, unsigned > > subtreeJumps;
    ext::deque < unsigned > subtreeRepeatsStack;
 
    typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator rankedSymbolsIter;
    typename ext::vector < common::ranked_symbol < unsigned > >::const_iterator subtreeRepeatsIter;
    for ( rankedSymbolsIter = tree.getContent ( ).begin(), subtreeRepeatsIter = repeats.getContent ( ).begin ( ); rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++ i ) {
        common::ranked_symbol < SymbolType > symbol = * rankedSymbolsIter;
        subtreeJumps.push_back ( std::make_pair ( symbol.getRank ( ), i - 1 ) );
        subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );
 
        ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, 0u );
        ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, 0u );
 
        res.addState ( currentState );
 
        res.addTransition ( previousState, symbol, currentState );
        res.addTransition ( res.getInitialState ( ), std::move ( symbol ), currentState );
 
        while ( !subtreeJumps.empty ( ) && subtreeJumps.back ( ).first == 0 ) {
            ext::pair < unsigned, unsigned > source = ext::make_pair ( subtreeJumps.back ( ).second, 0u );
            res.addTransition ( source, subtreeWildcard, currentState );
 
            for ( const common::ranked_symbol < SymbolType > & nonlinearVariable : nonlinearVariables )
                if ( nonlinearVariable != currentNonlinearVariable )
                    res.addTransition ( source, nonlinearVariable, currentState );
                else {
                    unsigned subtreeId = subtreeRepeatsStack.back ( );
                    bool multiRepeat = repeatsFrequency [ subtreeId ] > 1;
                    if ( ! multiRepeat )
                        subtreeId = repeats.getContent ( ) [ 0 ].getSymbol ( );
 
                    ext::pair < unsigned, unsigned > targetState = ext::make_pair ( i, subtreeId + 1 );
 
                    res.addState ( targetState );
                    res.addTransition ( source, nonlinearVariable, targetState );
 
                    constructTail ( res, tree, subtreeWildcard, currentNonlinearVariable, nonlinearVariables, subtreeId, multiRepeat, rankedSymbolsIter, i, subtreeRepeatsIter );
                }
 
            subtreeJumps.pop_back ( );
            subtreeRepeatsStack.pop_back ( );
        }
 
        if ( !subtreeJumps.empty ( ) ) subtreeJumps.back ( ).first--;
    }
 
    return res;
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::construct ( const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables ) {
    return constructInternal ( tree, subtreeWildcard, * nonlinearVariables.begin ( ), nonlinearVariables );
}
 
template < class SymbolType >
void ExactNonlinearTreePatternAutomaton::constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const common::ranked_symbol < SymbolType > & variablesBar, unsigned subtreeId, bool nonlinearJumps, typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator rankedSymbolsIter, unsigned i, typename ext::vector < common::ranked_symbol < unsigned > >::const_iterator subtreeRepeatsIter ) {
    ext::deque < unsigned > subtreeJumps;
    ext::deque < unsigned > subtreeRepeatsStack;
 
    for (++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i; rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i ) {
        common::ranked_symbol < SymbolType > symbol = * rankedSymbolsIter;
 
        ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, subtreeId + 1 );
        ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, subtreeId + 1 );
 
        res.addState ( currentState );
 
        res.addTransition ( previousState, symbol, currentState );
 
        if ( tree.getBars ( ).count ( symbol ) ) {
            if ( !subtreeJumps.empty ( ) ) {
                ext::pair < unsigned, unsigned > source = ext::make_pair ( subtreeJumps.back ( ), subtreeId + 1 );
                ext::pair < unsigned, unsigned > middle = ext::make_pair ( ~0 - i, subtreeId + 1 );
                res.addState ( middle );
 
                res.addTransition ( source, subtreeWildcard, middle );
                res.addTransition ( middle, variablesBar, currentState );
 
                for ( const common::ranked_symbol < SymbolType > & nonlinearVariable : nonlinearVariables )
                    if ( nonlinearVariable != currentNonlinearVariable || ( subtreeId == subtreeRepeatsStack.back ( ) && nonlinearJumps ) )
                        res.addTransition ( source, nonlinearVariable, middle );
 
                subtreeJumps.pop_back ( );
                subtreeRepeatsStack.pop_back ( );
            }
        } else {
            subtreeJumps.push_back ( i - 1 );
            subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );
        }
    }
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::constructInternal ( const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const common::ranked_symbol < SymbolType > & variablesBar ) {
    char S = alphabet::WildcardSymbol::instance < char > ( );
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > res ( ext::make_pair ( 0u, 0u ), S );
 
    tree::PrefixRankedBarTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( tree );
 
    std::vector < unsigned > repeatsFrequency ( repeats.getContent ( ).size ( ), 0 );
    for ( const common::ranked_symbol < unsigned > & repeat : repeats.getContent ( ) )
        if ( ! repeats.getBars ( ).count ( repeat ) )
            ++ repeatsFrequency [ repeat.getSymbol ( ) ];
 
    for ( const common::ranked_symbol < SymbolType > & symbol : tree.getAlphabet ( ) ) {
        res.addInputSymbol ( symbol );
        if ( tree.getBars ( ).count ( symbol ) )
            res.setPushdownStoreOperation ( symbol, ext::vector < char > ( 1, S ), ext::vector < char > { } );
        else
            res.setPushdownStoreOperation ( symbol, ext::vector < char > { }, ext::vector < char > ( 1, S ) );
    }
 
    res.addInputSymbol ( subtreeWildcard );
    res.setPushdownStoreOperation ( subtreeWildcard, ext::vector < char > { }, ext::vector < char > ( 1, S ) );
 
    res.addInputSymbol ( variablesBar );
    res.setPushdownStoreOperation ( variablesBar, ext::vector < char > ( 1, S ), ext::vector < char > { } );
 
    for ( const common::ranked_symbol < SymbolType > & nonlinearVariable : nonlinearVariables ) {
        res.addInputSymbol ( nonlinearVariable );
        res.setPushdownStoreOperation ( nonlinearVariable, ext::vector < char > { }, ext::vector < char > ( 1, S ) );
    }
 
    unsigned i = 1;
    ext::deque < unsigned > subtreeJumps;
    ext::deque < unsigned > subtreeRepeatsStack;
 
    typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator rankedSymbolsIter;
    typename ext::vector < common::ranked_symbol < unsigned > >::const_iterator subtreeRepeatsIter;
    for ( rankedSymbolsIter = tree.getContent ( ).begin(), subtreeRepeatsIter = repeats.getContent ( ).begin ( ); rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++ i ) {
        common::ranked_symbol < SymbolType > symbol = * rankedSymbolsIter;
 
        ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, 0u );
        ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, 0u );
 
        res.addState ( currentState );
 
        res.addTransition ( previousState, symbol, currentState );
 
        if ( tree.getBars ( ).count ( symbol ) ) {
            ext::pair < unsigned, unsigned > source = ext::make_pair ( subtreeJumps.back ( ), 0u );
            ext::pair < unsigned, unsigned > middle = ext::make_pair ( ~0 - i, 0u );
            res.addState ( middle );
 
            res.addTransition ( source, subtreeWildcard, middle );
            res.addTransition ( middle, variablesBar, currentState );
 
            for ( const common::ranked_symbol < SymbolType > & nonlinearVariable : nonlinearVariables )
                if ( nonlinearVariable != currentNonlinearVariable )
                    res.addTransition ( source, nonlinearVariable, middle );
                else {
                    unsigned subtreeId = subtreeRepeatsStack.back ( );
                    bool multiRepeat = repeatsFrequency [ subtreeId ] > 1;
                    if ( ! multiRepeat )
                        subtreeId = repeats.getContent ( ) [ 0 ].getSymbol ( );
 
                    ext::pair < unsigned, unsigned > targetState = ext::make_pair ( i, subtreeId + 1 );
                    ext::pair < unsigned, unsigned > middleState = ext::make_pair ( ~0 - i, subtreeId + 1 );
 
                    res.addState ( targetState );
                    res.addState ( middleState );
 
                    res.addTransition ( source, nonlinearVariable, middleState );
                    res.addTransition ( middleState, variablesBar, targetState );
 
                    constructTail ( res, tree, subtreeWildcard, currentNonlinearVariable, nonlinearVariables, variablesBar, subtreeId, multiRepeat, rankedSymbolsIter, i, subtreeRepeatsIter );
                }
 
            subtreeJumps.pop_back ( );
            subtreeRepeatsStack.pop_back ( );
        } else {
            subtreeJumps.push_back ( i - 1 );
            subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );
 
            res.addTransition ( res.getInitialState ( ), symbol, currentState );
        }
    }
 
    return res;
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::construct ( const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const common::ranked_symbol < SymbolType > & variablesBar ) {
    return constructInternal ( tree, subtreeWildcard, * nonlinearVariables.begin ( ), nonlinearVariables, variablesBar );
}
 
} /* namespace exact */
 
} /* namespace arbology */