ExactPatternMatchingAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include "ExactSubtreeMatchingAutomaton.h"
 
#include <tree/properties/SubtreeJumpTable.h>
 
#include <tree/ranked/RankedTree.h>
#include <tree/ranked/RankedPattern.h>
#include <tree/ranked/UnorderedRankedTree.h>
#include <tree/ranked/UnorderedRankedPattern.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
 
#include <tree/unranked/UnrankedPattern.h>
#include <tree/unranked/UnrankedExtendedPattern.h>
 
#include <automaton/PDA/InputDrivenNPDA.h>
#include <automaton/PDA/VisiblyPushdownNPDA.h>
#include <automaton/PDA/NPDA.h>
#include <automaton/TA/NFTA.h>
#include <automaton/TA/UnorderedNFTA.h>
#include <automaton/TA/NondeterministicZAutomaton.h>
 
#include <common/ranked_symbol.hpp>
#include <alphabet/BottomOfTheStackSymbol.h>
 
namespace arbology {
 
namespace exact {
 
class ExactPatternMatchingAutomaton {
public:
    template < class SymbolType >
    static automaton::NPDA < common::ranked_symbol < SymbolType >, char, unsigned> construct ( const tree::PrefixRankedPattern < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > construct ( const tree::PrefixRankedTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::VisiblyPushdownNPDA < common::ranked_symbol < SymbolType >, char, unsigned > construct ( const tree::PrefixRankedBarPattern < 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::NFTA < SymbolType, unsigned > construct ( const tree::RankedPattern < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::UnorderedNFTA < SymbolType, unsigned > construct ( const tree::UnorderedRankedTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::UnorderedNFTA < SymbolType, unsigned > construct ( const tree::UnorderedRankedPattern < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::NondeterministicZAutomaton < SymbolType, unsigned > construct ( const tree::UnrankedTree < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::NondeterministicZAutomaton < SymbolType, unsigned > construct ( const tree::UnrankedPattern < SymbolType > & pattern );
 
    template < class SymbolType >
    static automaton::NondeterministicZAutomaton < SymbolType, unsigned > construct ( const tree::UnrankedExtendedPattern < SymbolType > & pattern );
 
};
 
template < class SymbolType >
ext::vector < char > computeRHS ( const tree::PrefixRankedPattern < SymbolType > & pattern, const ext::vector < int > & patternSubtreeJumpTable, int i ) {
    const ext::vector < common::ranked_symbol < SymbolType > > & content = pattern.getContent ( );
 
    unsigned rank = content [ i ].getRank ( );
 
    i++;
 
    ext::vector < char > res;
 
    for ( unsigned ranki = 0; ranki < rank; ranki++ ) {
        if ( content [ i ] == pattern.getSubtreeWildcard ( ) ) {
            res.push_back ( 'R' );
            i++;
        } else {
            res.push_back ( 'T' );
 
            i = patternSubtreeJumpTable [ i ];
        }
    }
 
    return res;
}
 
template < class SymbolType >
automaton::NPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedPattern < SymbolType > & pattern ) {
    automaton::NPDA < common::ranked_symbol < SymbolType >, char, unsigned > res ( 0, 'T' );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        if ( symbol == pattern.getSubtreeWildcard ( ) ) continue;
 
        res.addInputSymbol ( symbol );
    }
 
    res.setPushdownStoreAlphabet ( { 'T', 'R' } );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        if ( symbol == pattern.getSubtreeWildcard ( ) ) continue;
 
        res.addTransition ( 0, symbol, ext::vector < char > ( 1, 'T' ), 0, ext::vector < char > ( symbol.getRank ( ), 'T' ) );
    }
 
    ext::vector < int > patternSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( pattern );
 
    unsigned i = 1;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getContent ( ) ) {
        res.addState ( i );
 
        if ( symbol == pattern.getSubtreeWildcard ( ) )
            for ( const common::ranked_symbol < SymbolType > & alphabetSymbol : pattern.getAlphabet ( ) ) {
                if ( alphabetSymbol == pattern.getSubtreeWildcard ( ) ) continue;
 
                if ( alphabetSymbol.getRank ( ) == 0 ) {
                    res.addTransition ( i - 1, alphabetSymbol, ext::vector < char > ( 1, 'T' ), i - 1, ext::vector < char > { } );
 
                    res.addTransition ( i - 1, alphabetSymbol, ext::vector < char > ( 1, 'R' ), i, ext::vector < char > { } );
                } else {
                    ext::vector < char > push ( alphabetSymbol.getRank ( ), 'T' );
                    res.addTransition ( i - 1, alphabetSymbol, ext::vector < char > ( 1, 'T' ), i - 1, push );
 
                    push [ alphabetSymbol.getRank ( ) - 1 ] = 'R';
                    res.addTransition ( i - 1, alphabetSymbol, ext::vector < char > ( 1, 'R' ), i - 1, push );
                }
            }
 
        else
            res.addTransition ( i - 1, symbol, ext::vector < char > ( 1, 'T' ), i, computeRHS ( pattern, patternSubtreeJumpTable, i - 1 ) );
 
        i++;
    }
 
    res.addFinalState ( i - 1 );
 
    return res;
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedTree < SymbolType > & pattern ) {
    return ExactSubtreeMatchingAutomaton::construct ( pattern );
}
 
template < class SymbolType >
automaton::VisiblyPushdownNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
    automaton::VisiblyPushdownNPDA < common::ranked_symbol < SymbolType >, char, unsigned > res ( alphabet::BottomOfTheStackSymbol::instance < char > ( ) );
 
    res.addState ( 0 );
    res.addInitialState ( 0 );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;
 
        if ( pattern.getBars ( ).count ( symbol ) )
            res.addReturnInputSymbol ( symbol );
        else
            res.addCallInputSymbol ( symbol );
    }
 
    res.setPushdownStoreAlphabet ( { alphabet::BottomOfTheStackSymbol::instance < char > ( ) , 'T', 'R' } );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getAlphabet ( ) ) {
        if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;
 
        if ( pattern.getBars ( ).count ( symbol ) )
            res.addReturnTransition ( 0, symbol, 'T', 0 );
        else
            res.addCallTransition ( 0, symbol, 0, 'T' );
    }
 
    unsigned i = 1;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getContent ( ) ) {
        res.addState ( i );
 
        if ( symbol == pattern.getSubtreeWildcard ( ) ) {
            for ( const common::ranked_symbol < SymbolType > & alphabetSymbol : pattern.getAlphabet ( ) ) {
                if ( ( alphabetSymbol == pattern.getSubtreeWildcard ( ) ) || ( alphabetSymbol == pattern.getVariablesBar ( ) ) || ( pattern.getBars ( ).count ( alphabetSymbol ) ) ) continue;
 
                res.addCallTransition ( i - 1, alphabetSymbol, i, 'R' );
            }
        } else if ( symbol == pattern.getVariablesBar ( ) ) {
            for ( const common::ranked_symbol < SymbolType > & alphabetSymbol : pattern.getAlphabet ( ) ) {
                if ( ( alphabetSymbol == pattern.getSubtreeWildcard ( ) ) || ( alphabetSymbol == pattern.getVariablesBar ( ) ) ) continue;
 
                if ( pattern.getBars ( ).count ( alphabetSymbol ) )
                    res.addReturnTransition ( i - 1, alphabetSymbol, 'T', i - 1 );
                else
                    res.addCallTransition ( i - 1, alphabetSymbol, i - 1, 'T' );
            }
 
            for ( const common::ranked_symbol < SymbolType > & alphabetSymbol : pattern.getAlphabet ( ) ) {
                if ( ( alphabetSymbol == pattern.getSubtreeWildcard ( ) ) || ( alphabetSymbol == pattern.getVariablesBar ( ) ) || ( ! pattern.getBars ( ).count ( alphabetSymbol ) ) ) continue;
 
                res.addReturnTransition ( i - 1, alphabetSymbol, 'R', i );
            }
        } else if ( pattern.getBars ( ).count ( symbol ) ) {
            res.addReturnTransition ( i - 1, symbol, 'T', i );
        } else {
            res.addCallTransition ( i - 1, symbol, i, 'T' );
        }
 
        i++;
    }
 
    res.addFinalState ( i - 1 );
    return res;
}
 
template < class SymbolType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType >, char, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::PrefixRankedBarTree < SymbolType > & pattern ) {
    return ExactSubtreeMatchingAutomaton::construct ( pattern );
}
 
template < class SymbolType >
automaton::NFTA < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::RankedTree < SymbolType > & pattern ) {
    return ExactSubtreeMatchingAutomaton::construct ( pattern );
}
 
template < class SymbolType >
unsigned constructRecursivePattern ( const ext::tree < common::ranked_symbol < SymbolType > > & node, automaton::NFTA < SymbolType, unsigned > & res, const common::ranked_symbol < SymbolType > & subtreeWildcard, unsigned & nextState ) {
    if ( node.getData ( ) == subtreeWildcard ) {
        unsigned state = nextState++;
        res.addState ( state );
 
        for ( const common::ranked_symbol < SymbolType > & symbol : res.getInputAlphabet ( ) ) {
            ext::vector < unsigned > states;
            states.reserve ( symbol.getRank ( ) );
 
            for ( unsigned i = 0; i < symbol.getRank ( ); i++ )
                states.push_back ( state );
 
            res.addTransition ( symbol, states, state );
        }
 
        return state;
    } else {
        ext::vector < unsigned > states;
        states.reserve ( node.getData ( ).getRank ( ) );
 
        for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) )
            states.push_back ( constructRecursivePattern ( child, res, subtreeWildcard, nextState ) );
 
        unsigned state = nextState++;
        res.addState ( state );
        res.addTransition ( node.getData ( ), states, state );
        return state;
    }
}
 
template < class SymbolType >
automaton::NFTA < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::RankedPattern < SymbolType > & pattern ) {
    ext::set < common::ranked_symbol < SymbolType> > alphabet = pattern.getAlphabet ( );
 
    alphabet.erase ( pattern.getSubtreeWildcard ( ) );
 
    automaton::NFTA < SymbolType, unsigned > res;
    res.setInputAlphabet ( alphabet );
 
    unsigned nextState = 0;
 
    res.addFinalState ( constructRecursivePattern ( pattern.getContent ( ), res, pattern.getSubtreeWildcard ( ), nextState ) );
    return res;
}
 
template < class SymbolType >
automaton::UnorderedNFTA < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::UnorderedRankedTree < SymbolType > & pattern ) {
    return ExactSubtreeMatchingAutomaton::construct ( pattern );
}
 
template < class SymbolType >
unsigned constructRecursivePattern ( const ext::tree < common::ranked_symbol < SymbolType > > & node, automaton::UnorderedNFTA < SymbolType, unsigned > & res, const common::ranked_symbol < SymbolType > & subtreeWildcard, unsigned & nextState ) {
    if ( node.getData ( ) == subtreeWildcard ) {
        unsigned state = nextState++;
        res.addState ( state );
 
        for ( const common::ranked_symbol < SymbolType > & symbol : res.getInputAlphabet ( ) ) {
            ext::multiset < unsigned > states;
 
            for ( unsigned i = 0; i < symbol.getRank ( ); i++ )
                states.insert ( state );
 
            res.addTransition ( symbol, states, state );
        }
 
        return state;
    } else {
        ext::multiset < unsigned > states;
 
        for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : node.getChildren ( ) )
            states.insert ( constructRecursivePattern ( child, res, subtreeWildcard,  nextState ) );
 
        unsigned state = nextState++;
        res.addState ( state );
        res.addTransition ( node.getData ( ), states, state );
        return state;
    }
}
 
template < class SymbolType >
automaton::UnorderedNFTA < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::UnorderedRankedPattern < SymbolType > & pattern ) {
    ext::set < common::ranked_symbol < SymbolType> > alphabet = pattern.getAlphabet ( );
 
    alphabet.erase ( pattern.getSubtreeWildcard ( ) );
 
    automaton::UnorderedNFTA < SymbolType, unsigned > res;
    res.setInputAlphabet ( alphabet );
 
    unsigned nextState = 0;
 
    res.addFinalState ( constructRecursivePattern ( pattern.getContent ( ), res, pattern.getSubtreeWildcard ( ), nextState ) );
    return res;
}
 
template < class SymbolType >
automaton::NondeterministicZAutomaton < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::UnrankedTree < SymbolType > & pattern ) {
    return ExactSubtreeMatchingAutomaton::construct ( pattern );
}
 
template < class SymbolType >
automaton::NondeterministicZAutomaton < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::UnrankedPattern < SymbolType > & pattern ) {
    return ExactPatternMatchingAutomaton::construct ( tree::UnrankedExtendedPattern ( pattern ) );
}
 
template < class SymbolType >
unsigned constructRecursivePattern ( const ext::tree < SymbolType > & node, automaton::NondeterministicZAutomaton < SymbolType, unsigned > & res, const SymbolType & subtreeWildcard, const SymbolType & subtreeGap, const SymbolType & nodeWildcard, unsigned & nextState ) {
    unsigned state = nextState ++;
    res.addState ( state );
    if ( node.getData ( ) == nodeWildcard ) {
        for ( const SymbolType & symbol : res.getInputAlphabet ( ) ) {
            res.addTransition ( symbol, { }, state );
        }
    } else {
        res.addTransition ( node.getData ( ), { }, state );
    }
 
    for ( const ext::tree < SymbolType > & child : node.getChildren ( ) ) {
        res.addState ( nextState );
        unsigned target = nextState ++;
        if ( child.getData ( ) == subtreeWildcard ) {
            res.addTransition ( state, { 0u }, target );
        } else if ( child.getData ( ) == subtreeGap ) {
            res.addTransition ( state, { 0u }, state );
 
            res.addTransition ( state, { }, target );
        } else {
            unsigned result = constructRecursivePattern ( child, res, subtreeWildcard, subtreeGap, nodeWildcard, nextState );
            res.addTransition ( state, { result }, target );
        }
        state = target;
    }
 
    return state;
}
 
template < class SymbolType >
automaton::NondeterministicZAutomaton < SymbolType, unsigned > ExactPatternMatchingAutomaton::construct ( const tree::UnrankedExtendedPattern < SymbolType > & pattern ) {
    ext::set < SymbolType > alphabet = pattern.getAlphabet ( );
 
    alphabet.erase ( pattern.getSubtreeWildcard ( ) );
    alphabet.erase ( pattern.getSubtreeGap ( ) );
    alphabet.erase ( pattern.getNodeWildcard ( ) );
 
    automaton::NondeterministicZAutomaton < SymbolType, unsigned > res;
    res.setInputAlphabet ( alphabet );
 
    res.addState ( 0 );
 
    for ( const SymbolType & symbol : res.getInputAlphabet ( ) )
        res.addTransition ( symbol, { }, 0 );
 
    res.addTransition ( 0u, { 0u }, 0 );
 
    unsigned nextState = 1;
 
    res.addFinalState ( constructRecursivePattern ( pattern.getContent ( ), res, pattern.getSubtreeWildcard ( ), pattern.getSubtreeGap ( ), pattern.getNodeWildcard ( ), nextState ) );
    return res;
}
 
} /* namespace exact */
 
} /* namespace arbology */