ReversedBadCharacterShiftTable.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
#include <alib/map>
 
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
 
#include "FirstVariableOffsetFront.h"
 
namespace tree {
 
namespace properties {
 
class ReversedBadCharacterShiftTable {
public:
    template < class SymbolType >
    static ext::map < common::ranked_symbol < SymbolType >, size_t > bcs ( const tree::PrefixRankedBarPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::map < common::ranked_symbol < SymbolType >, size_t > bcs ( const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::map < common::ranked_symbol < SymbolType >, size_t > bcs ( const tree::PrefixRankedPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::map < common::ranked_symbol < SymbolType >, size_t > bcs ( const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern );
 
};
 
template < class SymbolType >
ext::map < common::ranked_symbol < SymbolType >, size_t > ReversedBadCharacterShiftTable::bcs ( const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
    return bcs ( tree::PrefixRankedBarNonlinearPattern < SymbolType > ( pattern ) );
}
 
template < class SymbolType >
ext::map < common::ranked_symbol < SymbolType >, size_t > ReversedBadCharacterShiftTable::bcs ( const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
    const ext::set < common::ranked_symbol < SymbolType > > & alphabet = pattern.getAlphabet ( );
 
    ext::map < common::ranked_symbol < SymbolType >, size_t > bcs;
 
     // initialisation of bcs table to the size of the pattern
    for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
        if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( symbol ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;
 
        bcs.insert ( std::make_pair ( symbol, pattern.getContent ( ).size ( ) ) );
    }
 
     // find the distance between the beginning of the pattern and the index
     // of the first symbol representing the variable's bar
    size_t firstSBarOffset = FirstVariableOffsetFront::offset ( pattern ) + 1;
 
    // limit the shift by occurrence of the last variable's bar
    for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
        if ( ( symbol == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( symbol ) ) || ( symbol == pattern.getVariablesBar ( ) ) ) continue;
 
        size_t tmp = firstSBarOffset;
 
        if ( pattern.getBars ( ).count ( symbol ) )
             // size of the smallest subtree containing given terminal depend
             // on the arity of the terminal
            tmp += symbol.getRank ( ) * 2;
        else if ( tmp >= 2 )
             // bar symbols match the variable bar which is one symbol after
             // the last variable, conditioned because of the case S S| where
             // the -1 would cause shift by 0 -- illegal
            tmp -= 1;
 
        if ( bcs[symbol] > tmp )
            bcs[symbol] = tmp;
    }
 
     // limit the shift by position of symbols within the pattern
    for ( unsigned i = pattern.getContent ( ).size ( ) - 1; i >= 1; i-- ) { // first symbol is not concerned
        if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[i] ) ) || ( pattern.getContent ( )[i] == pattern.getVariablesBar ( ) ) ) continue;
 
        size_t tmp = i;
 
        if ( bcs[pattern.getContent ( )[i]] > tmp )
            bcs[pattern.getContent ( )[i]] = tmp;
    }
 
    return bcs;
}
 
template < class SymbolType >
ext::map < common::ranked_symbol < SymbolType >, size_t > ReversedBadCharacterShiftTable::bcs ( const tree::PrefixRankedPattern < SymbolType > & pattern ) {
    return bcs ( tree::PrefixRankedNonlinearPattern < SymbolType > ( pattern ) );
}
 
template < class SymbolType >
ext::map < common::ranked_symbol < SymbolType >, size_t > ReversedBadCharacterShiftTable::bcs ( const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern ) {
    const ext::set < common::ranked_symbol < SymbolType > > & alphabet = pattern.getAlphabet ( );
 
    ext::map < common::ranked_symbol < SymbolType >, size_t > bcs;
 
     // initialisation of bcs table to the size of the pattern
    for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
        if ( symbol == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( symbol ) ) continue;
 
        bcs.insert ( std::make_pair ( symbol, pattern.getContent ( ).size ( ) ) );
    }
 
     // find the distance between the beginning of the pattern and the index
     // of the first symbol representing the variable
    size_t firstSOffset = FirstVariableOffsetFront::offset ( pattern );
 
    // handle situation when the pattern is just S
    if ( firstSOffset == 0 ) firstSOffset = 1;
 
     // limit the shift by occurrence of the last variable
    for ( const common::ranked_symbol < SymbolType > & symbol : alphabet ) {
        if ( symbol == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( symbol ) ) continue;
 
        if ( bcs[symbol] > firstSOffset )
            bcs[symbol] = firstSOffset;
    }
 
     // limit the shift by position of symbols within the pattern
    for ( unsigned i = pattern.getContent ( ).size ( ) - 1; i >= 1; i-- ) { // first symbol is not concerned
        if ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[i] ) ) continue;
        size_t tmp = i;
 
        if ( bcs[pattern.getContent ( )[i]] > tmp )
            bcs[pattern.getContent ( )[i]] = tmp;
    }
 
    return bcs;
}
 
} /* namespace properties */
 
} /* namespace tree */