ReversedQuickSearch.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
#include <alib/map>
#include <common/ranked_symbol.hpp>
 
#include <tree/properties/ReversedQuickSearchBadCharacterShiftTable.h>
#include <tree/properties/SubtreeJumpTable.h>
#include <tree/properties/ExactSubtreeRepeatsNaive.h>
#include <tree/exact/ForwardOccurrenceTest.h>
 
#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
 
namespace arbology {
 
namespace exact {
 
class ReversedQuickSearch {
public:
    template < class SymbolType >
    static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarTree < SymbolType > & pattern );
    template < class SymbolType >
    static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedTree < SymbolType > & pattern );
    template < class SymbolType >
    static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedPattern < SymbolType > & pattern );
    template < class SymbolType >
    static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern );
 
};
 
template < class SymbolType >
ext::set < unsigned > ReversedQuickSearch::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarTree < SymbolType > & pattern ) {
    return match ( subject, tree::PrefixRankedBarPattern < SymbolType > ( pattern ) );
}
 
template < class SymbolType >
ext::set < unsigned > ReversedQuickSearch::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::map < common::ranked_symbol < SymbolType >, size_t > bcs = tree::properties::ReversedQuickSearchBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
    ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
 
    if ( subject.getContent ( ).size ( ) < pattern.getContent ( ).size ( ) )
           return occ;
 
    // index to the subject
    size_t i = subject.getContent ( ).size ( ) - pattern.getContent ( ).size ( );
 
    // main loop of the algorithm over all possible indexes where the pattern can start
    while ( true ) {
         // index to the pattern
        unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, pattern, i );
 
        // match was found
        if ( j == pattern.getContent ( ).size ( ) ) occ.insert ( i );
 
        // we have to break if the pattern is already aligned at the leftmost position
        // otherwise we would ask for symbol at the position -1 in the shift heuristics
        if ( i == 0 ) {
            break;
        }
 
        // shift heuristics
        size_t shift = bcs [ subject.getContent ( ) [ i - 1 ] ];
 
        if ( shift > i )
            break;
 
        i -= shift;
    }
 
    return occ;
}
 
template < class SymbolType >
ext::set < unsigned > ReversedQuickSearch::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::map < common::ranked_symbol < SymbolType >, size_t > bcs = tree::properties::ReversedQuickSearchBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
    ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
    ext::map < common::ranked_symbol < SymbolType >, unsigned > variablesSetting;
 
    tree::PrefixRankedBarTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
 
    if ( subject.getContent ( ).size ( ) < pattern.getContent ( ).size ( ) )
           return occ;
 
    // index to the subject
    size_t i = subject.getContent ( ).size ( ) - pattern.getContent ( ).size ( );
 
    // main loop of the algorithm over all possible indexes where the pattern can start
    while ( true ) {
        // index to the pattern
        unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, repeats, pattern, i );
 
        // match was found
        if ( j == pattern.getContent ( ).size ( ) ) occ.insert ( i );
 
        // we have to break if the pattern is already aligned at the leftmost position
        // otherwise we would ask for symbol at the position -1 in the shift heuristics
        if ( i == 0 ) {
            break;
        }
 
        // shift heuristics
        size_t shift = bcs [ subject.getContent ( ) [ i - 1 ] ];
 
        if ( shift > i )
            break;
 
        i -= shift;
    }
 
    return occ;
}
 
template < class SymbolType >
ext::set < unsigned > ReversedQuickSearch::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedTree < SymbolType > & pattern ) {
    return match ( subject, tree::PrefixRankedPattern < SymbolType > ( pattern ) );
}
 
template < class SymbolType >
ext::set < unsigned > ReversedQuickSearch::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedPattern < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::map < common::ranked_symbol < SymbolType >, size_t > bcs = tree::properties::ReversedQuickSearchBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
    ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
 
    if ( subject.getContent ( ).size ( ) < pattern.getContent ( ).size ( ) )
           return occ;
 
    // index to the subject
    size_t i = subject.getContent ( ).size ( ) - pattern.getContent ( ).size ( );
 
    // main loop of the algorithm over all possible indexes where the pattern can start
    while ( true ) {
        // index to the pattern
        unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, pattern, i );
 
        // match was found
        if ( j == pattern.getContent ( ).size ( ) ) occ.insert ( i );
 
        // we have to break if the pattern is already aligned at the leftmost position
        // otherwise we would ask for symbol at the position -1 in the shift heuristics
        if ( i == 0 ) {
            break;
        }
 
        // shift heuristics
        size_t shift = bcs [ subject.getContent ( ) [ i - 1 ] ];
 
        if ( shift > i )
            break;
 
        i -= shift;
    }
 
    return occ;
}
 
template < class SymbolType >
ext::set < unsigned > ReversedQuickSearch::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::map < common::ranked_symbol < SymbolType >, size_t > bcs = tree::properties::ReversedQuickSearchBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
    ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
    tree::PrefixRankedTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
 
    if ( subject.getContent ( ).size ( ) < pattern.getContent ( ).size ( ) )
           return occ;
 
    // index to the subject
    size_t i = subject.getContent ( ).size ( ) - pattern.getContent ( ).size ( );
 
    // main loop of the algorithm over all possible indexes where the pattern can start
    while ( true ) {
        // index to the pattern
        unsigned j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, repeats, pattern, i );
 
        // match was found
        if ( j == pattern.getContent ( ).size ( ) ) occ.insert ( i );
 
        // we have to break if the pattern is already aligned at the leftmost position
        // otherwise we would ask for symbol at the position -1 in the shift heuristics
        if ( i == 0 ) {
            break;
        }
 
        // shift heuristics
        size_t shift = bcs [ subject.getContent ( ) [ i - 1 ] ];
 
        if ( shift > i )
            break;
 
        i -= shift;
    }
 
    return occ;
}
 
} /* namespace exact */
 
} /* namespace arbology */