PositionHeapFactors.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/PositionHeap.h>
#include <string/LinearString.h>
#include <global/GlobalData.h>
 
namespace stringology {
 
namespace query {
 
class PositionHeapFactors {
    template < class SymbolType >
    static void accumulateResult ( const ext::trie < SymbolType, unsigned > & trie, ext::set < unsigned > & res, unsigned indexedStringSize ) {
        res.insert ( indexedStringSize - trie.getData ( ) );
 
        for ( const std::pair < const SymbolType, ext::trie < SymbolType, unsigned > > & child : trie.getChildren ( ) ) {
            accumulateResult ( child.second, res, indexedStringSize );
        }
    }
 
    template < class SymbolType >
    static bool checkOcc ( const string::LinearString < SymbolType > & needle, unsigned validSymbols, const ext::vector < SymbolType > & haystack, unsigned haystackPosition ) {
        if ( haystackPosition + needle.getContent ( ).size ( ) > haystack.size ( ) )
            return false;
 
        for ( unsigned i = validSymbols; i < needle.getContent ( ).size ( ); i++ ) {
            if ( needle.getContent ( ) [ i ] != haystack [ haystackPosition + i ] )
                return false;
        }
        return true;
    }
 
public:
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::stringology::PositionHeap < SymbolType > & positionHeap, const string::LinearString < SymbolType > & string );
 
};
 
template < class SymbolType >
ext::set < unsigned > PositionHeapFactors::query ( const indexes::stringology::PositionHeap < SymbolType > & positionHeap, const string::LinearString < SymbolType > & string ) {
    ext::set < unsigned > res;
 
    const ext::trie < SymbolType, unsigned > * node = & positionHeap.getRoot ( );
    unsigned depth = 0;
    unsigned indexedStringSize = positionHeap.getString ( ).getContent ( ).size ( );
 
    for ( const SymbolType & symbol : string.getContent ( ) ) {
 
        if(common::GlobalData::verbose)
            common::Streams::log << "on path possible occ (raw, string index): (" << node->getData ( ) << ", " << indexedStringSize - node->getData ( ) << ")" << std::endl;
 
        if ( checkOcc ( string, depth, positionHeap.getString ( ).getContent ( ), indexedStringSize - node->getData ( ) ) )
            res.insert ( indexedStringSize - node->getData ( ) );
 
        auto iter = node->getChildren ( ).find ( symbol );
        if ( iter == node->getChildren ( ).end ( ) )
            return res;
 
        depth++;
        node = & iter->second;
    }
 
    accumulateResult ( * node, res, indexedStringSize );
    return res;
}
 
} /* namespace query */
 
} /* namespace stringology */