ExactSubtreeMatchingAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/RankedTree.h>
#include <tree/ranked/UnorderedRankedTree.h>
#include <tree/unranked/UnrankedTree.h>
 
#include <automaton/PDA/InputDrivenNPDA.h>
#include <automaton/TA/NFTA.h>
#include <automaton/TA/UnorderedNFTA.h>
#include <automaton/TA/NondeterministicZAutomaton.h>
 
#include <alphabet/BottomOfTheStackSymbol.h>
 
namespace arbology {
 
namespace exact {
 
class ExactSubtreeMatchingAutomaton {
public:
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > construct ( const tree::PrefixRankedTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > construct ( const tree::PrefixRankedBarTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::NFTA < SymbolType, unsigned > construct ( const tree::RankedTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::UnorderedNFTA < SymbolType, unsigned > construct ( const tree::UnorderedRankedTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::NondeterministicZAutomaton < SymbolType, unsigned > construct ( const tree::UnrankedTree < SymbolType > & pattern );
};
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactSubtreeMatchingAutomaton::construct ( const tree::PrefixRankedTree < SymbolType > & pattern ) {
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > res ( 0, 'S' );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        res.addInputSymbol ( symbol );
        res.setPushdownStoreOperation ( symbol, ext::vector < char > ( 1, 'S' ), ext::vector < char > ( symbol.getRank ( ), 'S' ) );
    }
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        res.addTransition ( 0, symbol, 0 );
    }
 
    unsigned i = 1;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getContent ( ) ) {
        res.addState ( i );
        res.addTransition ( i - 1, symbol, i );
        i++;
    }
 
    res.addFinalState ( i - 1 );
    return res;
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactSubtreeMatchingAutomaton::construct ( const tree::PrefixRankedBarTree < SymbolType > & pattern ) {
    automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > res ( 0, alphabet::BottomOfTheStackSymbol::instance < char > ( ) );
 
    res.setPushdownStoreAlphabet ( { alphabet::BottomOfTheStackSymbol::instance < char > ( ), 'S' } );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        res.addInputSymbol ( symbol );
 
        if ( pattern.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' ) );
    }
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        res.addTransition ( 0, symbol, 0 );
    }
 
    unsigned i = 1;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getContent ( ) ) {
        res.addState ( i );
        res.addTransition ( i - 1, symbol, i );
        i++;
    }
 
    res.addFinalState ( i - 1 );
    return res;
}
 
template < class SymbolType >
unsigned constructRecursive ( const ext::tree < common::ranked_symbol < SymbolType > > & node, automaton::NFTA < SymbolType, unsigned > & res, unsigned & nextState ) {
    ext::vector < unsigned > states;
 
    states.reserve ( node.getData ( ).getRank ( ) );
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) )
        states.push_back ( constructRecursive ( child, res, nextState ) );
 
    unsigned state = nextState++;
    res.addState ( state );
    res.addTransition ( node.getData ( ), states, state );
    return state;
}
 
template < class SymbolType >
automaton::NFTA < SymbolType, unsigned > ExactSubtreeMatchingAutomaton::construct ( const tree::RankedTree < SymbolType > & pattern ) {
    automaton::NFTA < SymbolType, unsigned > res;
 
    res.setInputAlphabet ( pattern.getAlphabet ( ) );
    unsigned nextState = 0;
    res.addFinalState ( constructRecursive ( pattern.getContent ( ), res, nextState ) );
    return res;
}
 
template < class SymbolType >
unsigned constructRecursive ( const ext::tree < common::ranked_symbol < SymbolType > > & node, automaton::UnorderedNFTA < SymbolType, unsigned > & res, unsigned & nextState ) {
    ext::multiset < unsigned > states;
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) )
        states.insert ( constructRecursive ( child, res, nextState ) );
 
    unsigned state = nextState++;
    res.addState ( state );
    res.addTransition ( node.getData ( ), states, state );
    return state;
}
 
template < class SymbolType >
automaton::UnorderedNFTA < SymbolType, unsigned > ExactSubtreeMatchingAutomaton::construct ( const tree::UnorderedRankedTree < SymbolType > & pattern ) {
    automaton::UnorderedNFTA < SymbolType, unsigned > res;
 
    res.setInputAlphabet ( pattern.getAlphabet ( ) );
    unsigned nextState = 0;
    res.addFinalState ( constructRecursive ( pattern.getContent ( ), res, nextState ) );
    return res;
}
 
template < class SymbolType >
unsigned constructRecursive ( const ext::tree < SymbolType > & node, automaton::NondeterministicZAutomaton < SymbolType, unsigned > & res, unsigned & nextState ) {
    ext::vector < ext::variant < SymbolType, unsigned > > states;
 
    for ( const ext::tree < SymbolType > & child : node.getChildren ( ) )
        states.push_back ( constructRecursive ( child, res, nextState ) );
 
    unsigned state = nextState++;
    res.addState ( state );
    res.addTransition ( node.getData ( ), states, state );
    return state;
}
 
template < class SymbolType >
automaton::NondeterministicZAutomaton < SymbolType, unsigned > ExactSubtreeMatchingAutomaton::construct ( const tree::UnrankedTree < SymbolType > & pattern ) {
    automaton::NondeterministicZAutomaton < SymbolType, unsigned > res;
 
    res.setInputAlphabet ( pattern.getAlphabet ( ) );
    unsigned nextState = 0;
    res.addFinalState ( constructRecursive ( pattern.getContent ( ), res, nextState ) );
    return res;
}
 
} /* namespace exact */
 
} /* namespace arbology */