ExactSubtreeMatch.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/foreach>
 
#include <alib/set>
#include <alib/tree>
#include <alib/deque>
#include <common/ranked_symbol.hpp>
 
#include <tree/ranked/RankedTree.h>
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/unranked/UnrankedTree.h>
 
namespace arbology {
 
namespace exact {
 
class ExactSubtreeMatch {
public:
    template < class SymbolType >
    static ext::set<unsigned> match(const tree::UnrankedTree < SymbolType > & subject, const tree::UnrankedTree < SymbolType > & pattern);
    template < class SymbolType >
    static ext::set<unsigned> match(const tree::RankedTree < SymbolType > & subject, const tree::RankedTree < SymbolType > & pattern);
    template < class SymbolType >
    static ext::set<unsigned> match(const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedTree < SymbolType > & pattern);
    template < class SymbolType >
    static ext::set<unsigned> match(const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarTree < SymbolType > & pattern);
private:
    template < class SymbolType >
    static bool matchHelper(const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern);
    template < class SymbolType >
    static bool matchHelper(const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern);
 
    template < class SymbolType >
    static void matchInternal(unsigned& index, ext::set<unsigned>& occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern);
 
};
 
template < class SymbolType >
bool ExactSubtreeMatch::matchHelper ( const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern ) {
    if ( subject.getData ( ) != pattern.getData ( ) ) return false;
 
    auto patternIter = pattern.getChildren ( ).begin ( );
    auto subjectIter = subject.getChildren ( ).begin ( );
 
    while ( patternIter != pattern.getChildren ( ).end ( ) && subjectIter != subject.getChildren ( ).end ( ) ) {
        if ( ! matchHelper ( * subjectIter, * patternIter ) )
            return false;
 
        ++ patternIter;
        ++ subjectIter;
    }
 
    return patternIter == pattern.getChildren ( ).end ( );
}
 
template < class SymbolType >
bool ExactSubtreeMatch::matchHelper ( const ext::tree < common::ranked_symbol < SymbolType > > & subject, const ext::tree < common::ranked_symbol < SymbolType > > & pattern ) {
    if ( subject.getData ( ) != pattern.getData ( ) ) return false;
 
     // ranked symbols are the same; test for number of children is not needed
    for ( const ext::tuple < const ext::tree < common::ranked_symbol < SymbolType > > &, const ext::tree < common::ranked_symbol < SymbolType > > & > & childs : ext::make_tuple_foreach ( subject.getChildren ( ), pattern.getChildren ( ) ) )
        if ( !matchHelper ( std::get < 0 > ( childs ), std::get < 1 > ( childs ) ) ) return false;
 
    return true;
}
 
template < class SymbolType >
void ExactSubtreeMatch::matchInternal ( unsigned & index, ext::set < unsigned > & occ, const ext::tree < SymbolType > & subject, const ext::tree < SymbolType > & pattern ) {
    if ( matchHelper ( subject, pattern ) ) occ.insert ( index );
 
    index++;
 
    for ( const ext::tree < SymbolType > & child : subject.getChildren ( ) )
        matchInternal ( index, occ, child, pattern );
}
 
template < class SymbolType >
ext::set < unsigned > ExactSubtreeMatch::match ( const tree::UnrankedTree < SymbolType > & subject, const tree::UnrankedTree < SymbolType > & pattern ) {
    unsigned i = 0;
    ext::set < unsigned > occ;
 
    matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ) );
    return occ;
}
 
template < class SymbolType >
ext::set < unsigned > ExactSubtreeMatch::match ( const tree::RankedTree < SymbolType > & subject, const tree::RankedTree < SymbolType > & pattern ) {
    unsigned i = 0;
    ext::set < unsigned > occ;
 
    matchInternal ( i, occ, subject.getContent ( ), pattern.getContent ( ) );
    return occ;
}
 
template < class SymbolType >
ext::set < unsigned > ExactSubtreeMatch::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedTree < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
 
    for ( unsigned i = 0; i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ); i++ ) {
        unsigned j = 0;
 
        for ( ; j < pattern.getContent ( ).size ( ); j++ )
            if ( pattern.getContent ( )[j] != subject.getContent ( )[i + j] ) break;
 
        if ( j == pattern.getContent ( ).size ( ) )
            occ.insert ( i );
    }
 
    return occ;
}
 
template < class SymbolType >
ext::set < unsigned > ExactSubtreeMatch::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarTree < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
 
    for ( unsigned i = 0; i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ); i++ ) {
        unsigned j = 0;
 
        for ( ; j < pattern.getContent ( ).size ( ); j++ )
            if ( pattern.getContent ( )[j] != subject.getContent ( )[i + j] ) break;
 
        if ( j == pattern.getContent ( ).size ( ) )
            occ.insert ( i );
    }
 
    return occ;
}
 
} /* namespace exact */
 
} /* namespace arbology */