CompressedBitParallelismPatterns.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/arbology/CompressedBitParallelTreeIndex.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <global/GlobalData.h>
 
namespace arbology {
 
namespace query {
 
class CompressedBitParallelismPatterns {
 
public:
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::arbology::CompressedBitParallelTreeIndex < SymbolType > & compressedBitParallelIndex, const tree::PrefixRankedPattern < SymbolType > & pattern );
 
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::arbology::CompressedBitParallelTreeIndex < SymbolType > & compressedBitParallelIndex, const tree::PrefixRankedBarPattern < SymbolType > & pattern );
};
 
template < class SymbolType >
ext::set < unsigned > CompressedBitParallelismPatterns::query ( const indexes::arbology::CompressedBitParallelTreeIndex < SymbolType > & compressedBitParallelIndex, const tree::PrefixRankedPattern < SymbolType > & pattern ) {
    auto symbolIter = pattern.getContent ( ).begin ( );
 
    if ( pattern.getSubtreeWildcard ( ) == * symbolIter ) {
        ext::set < unsigned > res;
 
        for ( size_t i = 0; i < compressedBitParallelIndex.getJumps ( ).size ( ); ++ i )
            res.insert ( i );
 
        return res;
    }
 
    typename ext::map < common::ranked_symbol < SymbolType >, common::SparseBoolVector >::const_iterator symbolVectorIter = compressedBitParallelIndex.getData ( ).find ( * symbolIter );
 
    if ( symbolVectorIter == compressedBitParallelIndex.getData ( ).end ( ) )
        return { };
 
    common::SparseBoolVector indexVector = symbolVectorIter->second;
 
    for ( ++ symbolIter; symbolIter != pattern.getContent ( ).end ( ); ++ symbolIter ) {
        if ( * symbolIter == pattern.getSubtreeWildcard ( ) ) {
            common::SparseBoolVector newVector;
            newVector.resize ( indexVector.size ( ) );
 
            for ( unsigned i : ( indexVector << 1 ) )
                newVector [ compressedBitParallelIndex.getJumps ( ) [ i ] - 1 ] = true;
 
            indexVector = newVector;
        } else {
            symbolVectorIter = compressedBitParallelIndex.getData ( ).find ( * symbolIter );
 
            if ( symbolVectorIter == compressedBitParallelIndex.getData ( ).end ( ) )
                return { };
 
            indexVector = ( indexVector << 1 ) & symbolVectorIter->second;
        }
    }
 
    ext::set < unsigned > res;
 
    for ( unsigned i : indexVector )
        res.insert ( i + 1 );
 
    return res;
}
 
template < class SymbolType >
ext::set < unsigned > CompressedBitParallelismPatterns::query ( const indexes::arbology::CompressedBitParallelTreeIndex < SymbolType > & compressedBitParallelIndex, const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
    auto symbolIter = pattern.getContent ( ).begin ( );
 
    if ( pattern.getSubtreeWildcard ( ) == * symbolIter ) {
        ext::set < unsigned > res;
 
        for ( size_t i = 0; i < compressedBitParallelIndex.getJumps ( ).size ( ) - 1; ++ i ) //last index maps to -1
            if ( static_cast < size_t > ( compressedBitParallelIndex.getJumps ( ) [ i ] ) > i )
                res.insert ( i );
 
        return res;
    }
 
    typename ext::map < common::ranked_symbol < SymbolType >, common::SparseBoolVector >::const_iterator symbolVectorIter = compressedBitParallelIndex.getData ( ).find ( * symbolIter );
 
    if ( symbolVectorIter == compressedBitParallelIndex.getData ( ).end ( ) )
        return { };
 
    common::SparseBoolVector indexVector = symbolVectorIter->second;
 
    for ( ++ symbolIter; symbolIter != pattern.getContent ( ).end ( ); ++ symbolIter ) {
        if ( * symbolIter == pattern.getSubtreeWildcard ( ) ) {
            common::SparseBoolVector newVector;
            newVector.resize ( indexVector.size ( ) );
 
            for ( unsigned i : ( indexVector << 1 ) )
                newVector [ compressedBitParallelIndex.getJumps ( ) [ i ] - 1 ] = true;
 
            indexVector = newVector;
 
            ++ symbolIter;
        } else {
            symbolVectorIter = compressedBitParallelIndex.getData ( ).find ( * symbolIter );
 
            if ( symbolVectorIter == compressedBitParallelIndex.getData ( ).end ( ) )
                return { };
 
            indexVector = ( indexVector << 1 ) & symbolVectorIter->second;
        }
    }
 
    ext::set < unsigned > res;
 
    for ( unsigned i : indexVector )
        res.insert ( i + 1 );
 
    return res;
}
 
} /* namespace query */
 
} /* namespace arbology */