ForwardOccurrenceTest.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/PrefixRankedExtendedPattern.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 ForwardOccurrenceTest {
public:
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarTree < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const tree::PrefixRankedBarTree < unsigned > & repeats, const PrefixRankedBarNonlinearPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
 
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedTree < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedExtendedPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
    template < class SymbolType >
    static size_t occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const tree::PrefixRankedTree < unsigned > & repeats, const PrefixRankedNonlinearPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex = 0 );
};
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarTree < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
    return occurrence ( subject, subjectSubtreeJumpTable, tree::PrefixRankedBarPattern < SymbolType > ( pattern ), subjectPosition, patternStartIndex );
}
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedBarPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
     // offset to the subject
    size_t offset = subjectPosition + patternStartIndex;
    size_t j = patternStartIndex;
 
    while ( ( j < pattern.getContent ( ).size ( ) ) && ( offset < subject.getContent ( ).size ( ) ) ) {
        if ( subject.getContent ( )[offset] == pattern.getContent ( )[j] ) {
             // match of symbol
            offset = offset + 1;
            j = j + 1;
        } else if ( ( pattern.getContent ( )[j] == pattern.getSubtreeWildcard ( ) ) && ( ! 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 j;
}
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedBarTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const tree::PrefixRankedBarTree < unsigned > & repeats, const PrefixRankedBarNonlinearPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
 
     // to represent state of variable to subtree repeat
    ext::map < common::ranked_symbol < SymbolType >, unsigned > variablesSetting;
 
    // offset to the subject
    unsigned offset = subjectPosition + patternStartIndex;
    unsigned j = patternStartIndex;
 
    while ( ( j < pattern.getContent ( ).size ( ) ) && ( offset < subject.getContent ( ).size ( ) ) ) {
        if ( subject.getContent ( )[offset] == pattern.getContent ( )[j] ) {
             // match of symbol
            offset = offset + 1;
            j = j + 1;
        } else if ( ( pattern.getContent ( )[j] == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[j] ) ) && ( ! subject.getBars ( ).count ( subject.getContent ( )[offset] ) ) ) { //the second part of the condition is needed to handle S |S
             // check nonlinear variable
            if ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[ j ] ) ) {
                auto setting = variablesSetting.find ( pattern.getContent ( )[ j ] );
 
                if ( setting != variablesSetting.end ( ) && repeats.getContent ( )[ offset ].getSymbol ( ) != setting->second )
                    break;
 
                variablesSetting.insert ( std::make_pair ( pattern.getContent ( )[ j ], repeats.getContent( )[ offset ].getSymbol ( ) ) );
            }
 
             // match of variable with subtree
            offset = subjectSubtreeJumpTable[offset];
            j = j + 2;
        } else {
            break;
        }
    }
 
    return j;
}
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedTree < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
    return occurrence ( subject, subjectSubtreeJumpTable, tree::PrefixRankedPattern < SymbolType > ( pattern ), subjectPosition, patternStartIndex );
}
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
    return occurrence ( subject, subjectSubtreeJumpTable, tree::PrefixRankedExtendedPattern < SymbolType > ( pattern ), subjectPosition, patternStartIndex );
}
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const PrefixRankedExtendedPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
     // offset to the subject
    unsigned offset = subjectPosition + patternStartIndex;
    size_t j = patternStartIndex;
 
    while ( ( j < pattern.getContent ( ).size ( ) ) && ( offset < subject.getContent ( ).size ( ) ) ) {
        if ( ( subject.getContent ( )[offset] == pattern.getContent ( )[j] /* match of symbol */ )
          || ( pattern.getContent ( )[j].getRank ( ) == subject.getContent ( )[offset].getRank ( ) && pattern.getNodeWildcards ( ).contains ( pattern.getContent ( )[j] ) /* match node wildcard */ ) )
            offset = offset + 1;
        else if ( pattern.getContent ( )[j] == pattern.getSubtreeWildcard ( ) )
             // match of variable with subtree
            offset = subjectSubtreeJumpTable[offset];
        else
            break;
 
        j = j + 1;
    }
 
    return j;
}
 
template < class SymbolType >
size_t ForwardOccurrenceTest::occurrence ( const PrefixRankedTree < SymbolType > & subject, const ext::vector < int > & subjectSubtreeJumpTable, const tree::PrefixRankedTree < unsigned > & repeats, const PrefixRankedNonlinearPattern < SymbolType > & pattern, size_t subjectPosition, size_t patternStartIndex ) {
     // to represent state of variable to subtree repeat
    ext::map < common::ranked_symbol < SymbolType >, unsigned > variablesSetting;
 
     // offset to the subject
    unsigned offset = subjectPosition + patternStartIndex;
    unsigned j = patternStartIndex;
 
    while ( ( j < pattern.getContent ( ).size ( ) ) && ( offset < subject.getContent ( ).size ( ) ) ) {
        if ( subject.getContent ( )[offset] == pattern.getContent ( )[j] )
             // match of symbol
            offset = offset + 1;
        else if ( pattern.getContent ( )[j] == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[ j ] ) ) {
             // check nonlinear variable
            if ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[ j ] ) ) {
                auto setting = variablesSetting.find ( pattern.getContent ( )[ j ] );
 
                if ( setting != variablesSetting.end ( ) && repeats.getContent ( )[ offset ].getSymbol ( ) != setting->second )
                    break;
 
                variablesSetting.insert ( std::make_pair ( pattern.getContent ( )[ j ], repeats.getContent( )[ offset ].getSymbol ( ) ) );
            }
 
             // match of variable with subtree
            offset = subjectSubtreeJumpTable[offset];
        } else
            break;
 
        j = j + 1;
    }
 
    return j;
}
 
} /* namespace exact */
 
} /* namespace tree */