FullAndLinearIndexPatterns.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/arbology/FullAndLinearIndex.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <global/GlobalData.h>
 
#include <stringology/query/PositionHeapFactors.h>
 
namespace arbology {
 
namespace query {
 
class FullAndLinearIndexPatterns {
    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::FullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedPattern < SymbolType > & pattern );
 
    template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo = stringology::query::PositionHeapFactors >
    static ext::set < unsigned > query ( const indexes::arbology::FullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedBarPattern < SymbolType > & pattern );
};
 
template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo >
ext::set < unsigned > FullAndLinearIndexPatterns::query ( const indexes::arbology::FullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedPattern < SymbolType > & pattern ) {
    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 ) {
            treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
        } else {
            treePatternParts.back ( ).push_back ( symbol );
        }
    }
 
    ext::vector < std::pair < unsigned, unsigned > > prevOcc = FullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ) , treePatternParts [ 0 ] );
 
    for ( unsigned i = 1; i < treePatternParts.size ( ); ++ i ) {
        for ( std::pair < unsigned, unsigned > & occurrence : prevOcc )
            occurrence.second = fullAndLinearIndex.getJumps ( ) [ occurrence.second ];
 
        if ( ! treePatternParts [ i ].empty ( ) )
            prevOcc = MergeOccurrences ( prevOcc, FullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ i ] ), rev );
    }
 
    ext::set < unsigned > res;
    for ( const std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
        res.insert ( occurrence.first );
    }
 
    return res;
}
 
template < class SymbolType, template < typename > class StringIndex, class StringIndexQueryAlgo >
ext::set < unsigned > FullAndLinearIndexPatterns::query ( const indexes::arbology::FullAndLinearIndex < SymbolType, StringIndex > & fullAndLinearIndex, const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
    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 ( typename ext::vector < common::ranked_symbol < SymbolType > >::const_iterator symbolIter = pattern.getContent ( ).begin ( ); symbolIter != pattern.getContent ( ).end ( ); ++symbolIter ) {
        if ( pattern.getSubtreeWildcard ( ) == * symbolIter ) {
            treePatternParts.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( ) );
            ++ symbolIter;
        } else {
            treePatternParts.back ( ).push_back ( * symbolIter );
        }
    }
 
    ext::vector < std::pair < unsigned, unsigned > > prevOcc = FullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ 0 ] );
 
    for ( unsigned i = 1; i < treePatternParts.size ( ); ++ i ) {
        for ( std::pair < unsigned, unsigned > & occurrence : prevOcc )
            occurrence.second = fullAndLinearIndex.getJumps ( ) [ occurrence.second ];
 
        if ( ! treePatternParts [ i ].empty ( ) )
            prevOcc = MergeOccurrences ( prevOcc, FullAndLinearIndexPatterns::FindOccurrences < StringIndexQueryAlgo > ( fullAndLinearIndex.getStringIndex ( ), treePatternParts [ i ] ), rev );
    }
 
    ext::set < unsigned > res;
    for ( const std::pair < unsigned, unsigned > & occurrence : prevOcc ) {
        res.insert ( occurrence.first );
    }
 
    return res;
}
 
} /* namespace query */
 
} /* namespace arbology */