ExactTreePatternAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <alphabet/WildcardSymbol.h>
 
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedBarTree.h>
 
#include <automaton/PDA/InputDrivenNPDA.h>
 
#include <alib/deque>
 
namespace arbology {
 
namespace exact {
 
class ExactTreePatternAutomaton {
public:
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > construct ( const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & variablesBar );
 
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > construct ( const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard );
};
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactTreePatternAutomaton::construct ( const tree::PrefixRankedBarTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const common::ranked_symbol < SymbolType > & variablesBar ) {
    char S = alphabet::WildcardSymbol::instance < char > ( );
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > res ( 0, S );
 
    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 > { } );
 
    unsigned i = 1;
    ext::deque < unsigned > subtreeJumps;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : tree.getContent ( ) ) {
        res.addState ( i );
        res.addTransition ( i - 1, symbol, i );
 
        if ( tree.getBars ( ).count ( symbol ) ) {
            unsigned source = subtreeJumps.back ( );
            subtreeJumps.pop_back ( );
 
            res.addState ( ~0 - i );
            res.addTransition ( source, subtreeWildcard, ~0 - i );
            res.addTransition ( ~0 - i, variablesBar, i );
        } else {
            res.addTransition ( res.getInitialState ( ), symbol, i ); // transition from the initial state only allowed for nonbar symbols
 
            subtreeJumps.push_back ( i - 1 );
        }
 
        i++;
    }
 
    return res;
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactTreePatternAutomaton::construct ( const tree::PrefixRankedTree < SymbolType > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard ) {
    char S = alphabet::WildcardSymbol::instance < char > ( );
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > res ( 0, S );
 
    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 > { } );
 
    unsigned i = 1;
    ext::deque < std::pair < size_t, unsigned > > subtreeJumps;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : tree.getContent ( ) ) {
        subtreeJumps.push_back ( std::make_pair ( symbol.getRank ( ), i - 1 ) );
 
        res.addState ( i );
        res.addTransition ( i - 1, symbol, i );
        res.addTransition ( 0, std::move ( symbol ), i );
 
        while ( !subtreeJumps.empty ( ) && subtreeJumps.back ( ).first == 0 ) {
            res.addTransition ( subtreeJumps.back ( ).second, subtreeWildcard, i );
            subtreeJumps.pop_back ( );
        }
 
        if ( !subtreeJumps.empty ( ) ) subtreeJumps.back ( ).first--;
 
        i++;
    }
 
    return res;
}
 
} /* namespace exact */
 
} /* namespace arbology */