BackwardOccurrenceTest.h

Go to the documentation of this file.

 
#pragma once
 
#include <climits>
 
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
 
namespace tree {
 
namespace exact {
 
class BackwardOccurrenceTest {
public:
    template < class SymbolType >
    static ext::pair < int, int > occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarTree < SymbolType > & pattern, size_t subjectPosition );
    template < class SymbolType >
    static ext::pair < int, int > occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarPattern < SymbolType > & pattern, size_t subjectPosition );
    template < class SymbolType >
    static ext::pair < int, int > occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const tree::PrefixRankedBarTree < unsigned > & repeats, const PrefixRankedBarNonlinearPattern < SymbolType > & pattern, size_t subjectPosition );
 
};
 
template < class SymbolType >
ext::pair < int, int > BackwardOccurrenceTest::occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarTree < SymbolType > & pattern, size_t subjectPosition ) {
    return occurrence ( subject, subjectSubtreeJumpTable, tree::PrefixRankedBarPattern < SymbolType > ( pattern ), subjectPosition );
}
 
template < class SymbolType >
ext::pair < int, int > BackwardOccurrenceTest::occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarPattern < SymbolType > & pattern, size_t subjectPosition ) {
     // index to the pattern
    int j = pattern.getContent ( ).size ( ) - 1;
 
     // offset to the subject
    int offset = subjectPosition;
 
    while ( ( j >= 0 ) && ( offset >= 0 ) ) {
        if ( subject.getContent ( )[offset] == pattern.getContent ( )[j] ) {
             // match of symbol
            offset = offset - 1;
            j = j - 1;
        } else if ( ( pattern.getContent ( )[j] == pattern.getVariablesBar ( ) ) && ( subject.getBars ( ).count ( subject.getContent ( )[offset] ) ) ) { //the second part of the condition is needed to handle S |S
             // match of variable with subtree
            offset = subjectSubtreeJumpTable[offset];
            j = j - 2;
        } else {
            break;
        }
    }
 
    return ext::make_pair ( j, offset );
}
 
template < class SymbolType >
ext::pair < int, int > BackwardOccurrenceTest::occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const tree::PrefixRankedBarTree < unsigned > & repeats, const PrefixRankedBarNonlinearPattern < SymbolType > & pattern, size_t subjectPosition ) {
 
     // to represent state of variable to subtree repeat
    ext::map < common::ranked_symbol < SymbolType >, unsigned > variablesSetting;
 
     // index to the pattern
    int j = pattern.getContent ( ).size ( ) - 1;
 
     // offset to the subject
    int offset = subjectPosition;
 
    while ( ( j >= 0 ) && ( offset >= 0 ) ) {
        if ( subject.getContent ( )[offset] == pattern.getContent ( )[j] ) {
             // match of symbol
            offset = offset - 1;
            j = j - 1;
        } else if ( ( pattern.getContent ( )[j] == pattern.getVariablesBar ( ) ) && ( subject.getBars ( ).count ( subject.getContent ( )[offset] ) ) ) { //the second part of the condition is needed to handle S |S
             // else match of variable with subtree
            offset = subjectSubtreeJumpTable[offset];
            j = j - 2;
 
             // check nonlinear variable
            if ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[ j + 1 ] ) ) {
                auto setting = variablesSetting.find ( pattern.getContent ( )[ j + 1 ] );
 
                if ( setting != variablesSetting.end ( ) && repeats.getContent ( )[ offset + 1 ].getSymbol ( ) != setting->second )
                    break;
 
                variablesSetting.insert ( std::make_pair ( pattern.getContent ( )[ j + 1 ], repeats.getContent( )[ offset + 1 ].getSymbol ( ) ) );
            }
        } else {
            break;
        }
    }
 
    return ext::make_pair ( j, offset );
}
 
} /* namespace exact */
 
} /* namespace tree */