BorderArrayNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
 
#include <global/GlobalData.h>
 
#include "SubtreeJumpTable.h"
 
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
#include <tree/ranked/PrefixRankedExtendedPattern.h>
#include <tree/ranked/PrefixRankedPattern.h>
 
namespace tree {
 
namespace properties {
 
class BorderArrayNaive {
    template < class SymbolType >
    static bool matches ( const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );
 
    template < class SymbolType >
    static bool matches ( const tree::PrefixRankedBarPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );
 
    template < class SymbolType >
    static bool matches ( const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );
 
    template < class SymbolType >
    static bool matches ( const tree::PrefixRankedPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );
 
    template < class SymbolType >
    static bool matches ( const tree::PrefixRankedExtendedPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );
 
public:
    template < class T >
    static ext::vector < size_t > construct ( const T & pattern );
};
 
template < class T >
ext::vector < size_t > BorderArrayNaive::construct ( const T & pattern ) {
    ext::vector < int > patternSubtreeJumpTable = SubtreeJumpTable::compute ( pattern );
    ext::vector < size_t > res;
 
    for ( size_t i = 0; i <= pattern.getContent ( ).size ( ); i++ )
        res.push_back ( 0 );
 
    res[0] = -1;
 
    for ( size_t i = 1; i <= pattern.getContent ( ).size ( ); i++ ) {
        size_t min = i;
 
        for ( size_t j = 1; j < i; j++ )
            if ( matches ( pattern, patternSubtreeJumpTable, i, j ) ) {
                min = j;
                break;
            }
 
        res[i] = i - min;
    }
 
    if ( common::GlobalData::verbose )
        common::Streams::log << res << std::endl;
 
    return res;
}
 
template < class SymbolType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
    unsigned i = 0;
 
    while ( offset < stop && i < pattern.getContent ( ).size ( ) )
        if ( pattern.getContent ( )[i] == pattern.getContent ( )[offset] ) {
            i++;
            offset++;
        } else if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( ) [ i ] ) )
             || ( pattern.getContent ( )[offset] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( ) [ offset ] ) ) ) {
            i = subtreeJumpTable[i];
            offset = subtreeJumpTable[offset];
        } else {
            return false;
        }
 
    return true;
}
 
template < class SymbolType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedBarPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
    unsigned i = 0;
 
    while ( offset < stop && i < pattern.getContent ( ).size ( ) )
        if ( pattern.getContent ( )[i] == pattern.getContent ( )[offset] ) {
            i++;
            offset++;
        } else if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getContent ( )[offset] == pattern.getSubtreeWildcard ( ) ) ) {
            i = subtreeJumpTable[i];
            offset = subtreeJumpTable[offset];
        } else {
            return false;
        }
 
    return true;
}
template < class SymbolType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
    size_t i = 0;
 
    while ( offset < stop && i < pattern.getContent ( ).size ( ) )
        if ( pattern.getContent ( )[i] == pattern.getContent ( )[offset] ) {
            i++;
            offset++;
        } else if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( ) [ i ] ) )
             || ( pattern.getContent ( )[offset] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( ) [ offset ] ) ) ) {
            i = subtreeJumpTable[i];
            offset = subtreeJumpTable[offset];
        } else {
            return false;
        }
 
    return true;
}
 
template < class SymbolType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
    size_t i = 0;
 
    while ( offset < stop && i < pattern.getContent ( ).size ( ) )
        if ( pattern.getContent ( )[i] == pattern.getContent ( )[offset] ) {
            i++;
            offset++;
        } else if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getContent ( )[offset] == pattern.getSubtreeWildcard ( ) ) ) {
            i = subtreeJumpTable[i];
            offset = subtreeJumpTable[offset];
        } else {
            return false;
        }
 
    return true;
}
 
template < class SymbolType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedExtendedPattern < SymbolType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
    size_t i = 0;
 
    while ( offset < stop && i < pattern.getContent ( ).size ( ) ) {
        const auto & iSymbol = pattern.getContent ( )[i];
        const auto & oSymbol = pattern.getContent ( )[offset];
        if ( iSymbol == oSymbol || ( iSymbol.getRank ( ) == oSymbol.getRank ( ) && ( pattern.getNodeWildcards ( ).contains ( iSymbol ) || pattern.getNodeWildcards ( ).contains ( oSymbol ) ) ) ) {
            i++;
            offset++;
        } else if ( iSymbol == pattern.getSubtreeWildcard ( ) || oSymbol == pattern.getSubtreeWildcard ( ) ) {
            i = subtreeJumpTable[i];
            offset = subtreeJumpTable[offset];
        } else {
            return false;
        }
    }
 
    return true;
}
 
} /* namespace properties */
 
} /* namespace tree */