NonlinearCompressedBitParallelismPatterns.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/arbology/NonlinearCompressedBitParallelTreeIndex.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
#include <global/GlobalData.h>
 
namespace arbology {
 
namespace query {
 
class NonlinearCompressedBitParallelismPatterns {
 
public:
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::arbology::NonlinearCompressedBitParallelTreeIndex < SymbolType > & nonlinearCompressedBitParallelIndex, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
};
 
template < class SymbolType >
bool include ( unsigned i, const ext::vector < unsigned > & repeats, const ext::vector < int > & jumps, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
    ext::map < common::ranked_symbol < SymbolType >, unsigned > variablesSetting;
 
     // index to the pattern
    int j = pattern.getContent ( ).size ( ) - 1;
 
    while ( j >= 0 ) {
        if ( pattern.getContent ( )[j] == pattern.getVariablesBar ( ) ) {
            i = jumps[i];
            j = j - 2;
 
             // check nonlinear variable
            if ( pattern.getNonlinearVariables ( ).count ( pattern.getContent ( )[ j + 1 ] ) ) {
                auto setting = variablesSetting.find ( pattern.getContent ( )[ j + 1 ] );
 
                if ( setting != variablesSetting.end ( ) && repeats [ i + 1 ] != setting->second )
                    break;
 
                variablesSetting.insert ( std::make_pair ( pattern.getContent ( )[ j + 1 ], repeats [ i + 1 ] ) );
            }
        } else {
             // match of symbol
            i = i - 1;
            j = j - 1;
        }
    }
 
    return j == -1;
 
}
 
template < class SymbolType >
ext::set < unsigned > NonlinearCompressedBitParallelismPatterns::query ( const indexes::arbology::NonlinearCompressedBitParallelTreeIndex < SymbolType > & nonlinearCompressedBitParallelIndex, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
    auto symbolIter = pattern.getContent ( ).begin ( );
 
    if ( pattern.getSubtreeWildcard ( ) == * symbolIter || pattern.getNonlinearVariables ( ).count ( * symbolIter ) ) {
        ext::set < unsigned > res;
 
        for ( size_t i = 0; i < nonlinearCompressedBitParallelIndex.getJumps ( ).size ( ) - 1; ++ i ) //last index maps to -1
            if ( static_cast < size_t > ( nonlinearCompressedBitParallelIndex.getJumps ( ) [ i ] ) > i )
                res.insert ( i );
 
        return res;
    }
 
    typename ext::map < common::ranked_symbol < SymbolType >, common::SparseBoolVector >::const_iterator symbolVectorIter = nonlinearCompressedBitParallelIndex.getData ( ).find ( * symbolIter );
 
    if ( symbolVectorIter == nonlinearCompressedBitParallelIndex.getData ( ).end ( ) )
        return { };
 
    common::SparseBoolVector indexVector = symbolVectorIter->second;
 
    for ( ++ symbolIter; symbolIter != pattern.getContent ( ).end ( ); ++ symbolIter ) {
        if ( * symbolIter == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).count ( * symbolIter ) ) {
            common::SparseBoolVector newVector;
            newVector.resize ( indexVector.size ( ) );
 
            for ( unsigned i : ( indexVector << 1 ) )
                newVector [ nonlinearCompressedBitParallelIndex.getJumps ( ) [ i ] - 1 ] = true;
 
            indexVector = newVector;
 
            ++ symbolIter;
        } else {
            symbolVectorIter = nonlinearCompressedBitParallelIndex.getData ( ).find ( * symbolIter );
 
            if ( symbolVectorIter == nonlinearCompressedBitParallelIndex.getData ( ).end ( ) )
                return { };
 
            indexVector = ( indexVector << 1 ) & symbolVectorIter->second;
        }
    }
 
    ext::set < unsigned > res;
 
    for ( unsigned i : indexVector )
        if ( include ( i, nonlinearCompressedBitParallelIndex.getRepeats ( ), nonlinearCompressedBitParallelIndex.getJumps ( ), pattern ) )
            res.insert ( i + 1 );
 
    return res;
}
 
} /* namespace query */
 
} /* namespace arbology */