BorderArray.h

Go to the documentation of this file.

 
#pragma once
 
#include <cstdlib>
 
#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/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedExtendedPattern.h>
 
namespace {
 
template < class PrefixRankedPatternType >
bool symbolCompare ( [[maybe_unused]] const PrefixRankedPatternType& pattern, size_t i, size_t j ) {
    return pattern.getContent ( )[ i ] == pattern.getContent ( )[ j ];
}
 
template < class SymbolType >
bool symbolCompare ( const tree::PrefixRankedExtendedPattern < SymbolType > & pattern, size_t i, size_t j ) {
    const auto& symbol1 = pattern.getContent ( )[ i ];
    const auto& symbol2 = pattern.getContent ( )[ j ];
    return symbol1 == symbol2 || ( symbol1.getRank ( ) == symbol2.getRank ( ) && ( pattern.getNodeWildcards ( ).contains ( symbol1 ) || pattern.getNodeWildcards ( ).contains ( symbol2 ) ) );
}
}
 
namespace tree::properties {
 
class BorderArray {
 
public:
    template < class PrefixRankedPatternType >
    static ext::vector < size_t > construct ( const PrefixRankedPatternType & pattern );
};
 
template < class PrefixRankedPatternType >
ext::vector < size_t > BorderArray::construct ( const PrefixRankedPatternType & pattern ) {
    ext::vector < int > subtreeJumpTable = SubtreeJumpTable::compute ( pattern );
    ext::vector < size_t > res ( pattern.getContent ( ).size ( ) + 1, 0 );
    ext::vector < unsigned > maxs ( pattern.getContent ( ).size ( ) + 1 );
    for ( unsigned i = 0; i <= pattern.getContent ( ).size ( ); i++ )
        maxs [ i ] = 0;
    res [ 0 ] = -1;
 
    for ( unsigned ofs = 1; ofs < pattern.getContent ( ).size ( ); ofs++ ) {
 
        unsigned i = 0;   // index do patternu
        unsigned j = ofs; // index do factoru
 
        while ( true ) {
            if ( i >= pattern.getContent ( ).size ( ) ) {
                while ( j < pattern.getContent ( ).size ( ) ) {
                    maxs [ j ] = std::max ( maxs [ j ], j + 1 - ofs );
                    j++;
                }
                break;
            } else if ( j >= pattern.getContent ( ).size ( ) ) { // NOLINT (bugprone-branch-clone) just a break statement
                break;
            } else if ( symbolCompare ( pattern, i, j ) ) {
                maxs [ j ] = std::max ( maxs [ j ], j + 1 - ofs );
                i++;
                j++;
            } else if ( pattern.getContent ( )[ i ] == pattern.getSubtreeWildcard ( ) || pattern.getContent ( )[ j ] == pattern.getSubtreeWildcard ( ) ) {
                for ( int k = static_cast < int > ( j ); k < subtreeJumpTable [ j ] ; k++ )
                    maxs [ k ] = std::max ( maxs [ k ], k + 1 - ofs );
 
                i = subtreeJumpTable[ i ];
                j = subtreeJumpTable[ j ];
            } else {
                break;
            }
        }
    }
 
    // std::cout << maxs << std::endl;
 
    res [ 1 ] = 0;
    for ( size_t i = 2; i <= pattern.getContent ( ).size ( ); i++ ) {
        res [ i ] = maxs [ i - 1 ];
    }
 
    return res;
}
 
} /* namespace tree::properties */