NonlinearFullAndLinearIndexPatterns.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/arbology/NonlinearFullAndLinearIndex.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
#include <global/GlobalData.h>
 
#include <stringology/query/PositionHeapFactors.h>
 
namespace arbology {
 
namespace query {
 
class NonlinearFullAndLinearIndexPatterns {
    template < class StringIndexQueryAlgo, class SymbolType, template < typename > class StringIndex >
    static ext::vector < std::pair < unsigned, unsigned > > FindOccurrences ( const StringIndex < common::ranked_symbol < SymbolType > > & stringIndex, const ext::vector < common::ranked_symbol < SymbolType > > & string ) {
        ext::vector < std::pair < unsigned, unsigned > > res;
        for ( unsigned occurrence : StringIndexQueryAlgo::query ( stringIndex, string::LinearString < common::ranked_symbol < SymbolType > > ( string ) ) ) {
            res.push_back ( std::make_pair ( occurrence, occurrence + string.size ( ) ) );
        }
        return res;
    }
 
    static ext::vector < std::pair < unsigned, unsigned > > MergeOccurrences ( const ext::vector < std::pair < unsigned, unsigned > > & prevOcc, const ext::vector < std::pair < unsigned, unsigned > > & subOcc, ext::vector < unsigned > & rev ) {
        ext::vector < std::pair < unsigned, unsigned > > res;
 
        for ( const std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
            rev [ occurrence.second ] = occurrence.first;
        }
 
        for ( const std::pair < unsigned, unsigned > & subOccurrence : subOcc ) {
            if ( rev [ subOccurrence.first ] != static_cast < unsigned > ( -1 ) )
                res.push_back ( std::make_pair ( rev [ subOccurrence.first ], subOccurrence.second ) );
        }
 
        for ( const std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
            rev [ occurrence.second ] = static_cast < unsigned > ( -1 );
        }
 
        return res;
    }
public:
    template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo = stringology::query::PositionHeapFactors >
    static ext::set < unsigned > query ( const indexes::arbology::NonlinearFullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern );
 
    template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo = stringology::query::PositionHeapFactors >
    static ext::set < unsigned > query ( const indexes::arbology::NonlinearFullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
};
 
template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo >
ext::set < unsigned > NonlinearFullAndLinearIndexPatterns::query ( const indexes::arbology::NonlinearFullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern ) {
    ext::map < std::pair < unsigned, common::ranked_symbol < SymbolType > >, unsigned > nonlinearVariablesMap;
    ext::vector < unsigned > rev ( fullAndLinearIndex.getJumps ( ).size ( ), static_cast < unsigned > ( -1 ) );
 
    ext::vector < ext::vector < common::ranked_symbol < SymbolType > > > treePatternParts;
    treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getContent ( ) ) {
        if ( pattern.getSubtreeWildcard ( ) == symbol || pattern.getNonlinearVariables ( ).count ( symbol ) ) {
            treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
            treePatternParts.back ( ).push_back ( symbol );
            treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
        } else {
            treePatternParts.back ( ).push_back ( symbol );
        }
    }
 
    ext::vector < std::pair < unsigned, unsigned > > prevOcc = NonlinearFullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ 0 ] );
 
    for ( unsigned i = 1; i < treePatternParts.size ( ); ++ i ) {
        for ( std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
            if ( pattern.getNonlinearVariables ( ).count ( treePatternParts [ i ].back ( ) ) ) {
                auto variableSettingIter = nonlinearVariablesMap.find ( std::make_pair ( occurrence.first, treePatternParts [ i ].back ( ) ) );
                if ( variableSettingIter == nonlinearVariablesMap.end ( ) )
                    nonlinearVariablesMap.insert ( std::make_pair ( std::make_pair ( occurrence.first, treePatternParts [ i ].back ( ) ), fullAndLinearIndex.getRepeats ( ) [ occurrence.second ] ) );
                else if ( variableSettingIter->second != fullAndLinearIndex.getRepeats ( ) [ occurrence.second ] )
                    occurrence.first = static_cast < unsigned > ( -1 );
            }
            occurrence.second = fullAndLinearIndex.getJumps ( ) [ occurrence.second ];
        }
 
        ++ i;
 
        if ( ! treePatternParts [ i ].empty ( ) )
            prevOcc = MergeOccurrences ( prevOcc, NonlinearFullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ i ] ), rev );
    }
 
    ext::set < unsigned > res;
    for ( const std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
        if ( occurrence.first != static_cast < unsigned > ( -1 ) )
            res.insert ( occurrence.first );
    }
 
    return res;
}
 
template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo >
ext::set < unsigned > NonlinearFullAndLinearIndexPatterns::query ( const indexes::arbology::NonlinearFullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
    ext::map < std::pair < unsigned, common::ranked_symbol < SymbolType > >, unsigned > nonlinearVariablesMap;
    ext::vector < unsigned > rev ( fullAndLinearIndex.getJumps ( ).size ( ), static_cast < unsigned > ( -1 ) );
 
    ext::vector < ext::vector < common::ranked_symbol < SymbolType > > > treePatternParts;
    treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
    for ( const common::ranked_symbol < SymbolType > & symbol : pattern.getContent ( ) ) {
        if ( symbol == pattern.getVariablesBar ( ) )
            continue;
 
        if ( pattern.getSubtreeWildcard ( ) == symbol || pattern.getNonlinearVariables ( ).count ( symbol ) ) {
            treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
            treePatternParts.back ( ).push_back ( symbol );
            treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
        } else {
            treePatternParts.back ( ).push_back ( symbol );
        }
    }
 
    ext::vector < std::pair < unsigned, unsigned > > prevOcc = NonlinearFullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ 0 ] );
 
    for ( unsigned i = 1; i < treePatternParts.size ( ); ++ i ) {
        for ( std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
            if ( pattern.getNonlinearVariables ( ).count ( treePatternParts [ i ].back ( ) ) ) {
                auto variableSettingIter = nonlinearVariablesMap.find ( std::make_pair ( occurrence.first, treePatternParts [ i ].back ( ) ) );
                if ( variableSettingIter == nonlinearVariablesMap.end ( ) )
                    nonlinearVariablesMap.insert ( std::make_pair ( std::make_pair ( occurrence.first, treePatternParts [ i ].back ( ) ), fullAndLinearIndex.getRepeats ( ) [ occurrence.second ] ) );
                else if ( variableSettingIter->second != fullAndLinearIndex.getRepeats ( ) [ occurrence.second ] )
                    occurrence.first = static_cast < unsigned > ( -1 );
            }
            occurrence.second = fullAndLinearIndex.getJumps ( ) [ occurrence.second ];
        }
 
        ++ i;
 
        if ( ! treePatternParts [ i ].empty ( ) )
            prevOcc = MergeOccurrences ( prevOcc, NonlinearFullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ i ] ), rev );
    }
 
    ext::set < unsigned > res;
    for ( const std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
        if ( occurrence.first != static_cast < unsigned > ( -1 ) )
            res.insert ( occurrence.first );
    }
 
    return res;
}
 
} /* namespace query */
 
} /* namespace arbology */