BNDMOccurrences.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/BitSetIndex.h>
#include <string/LinearString.h>
#include <global/GlobalData.h>
 
#include <ext/foreach>
 
namespace stringology {
 
namespace query {
 
class BNDMOccurrences {
 
public:
    template < class SymbolType, size_t BitmaskBitCount >
    static ext::set < unsigned > query ( const indexes::stringology::BitSetIndex < SymbolType, BitmaskBitCount > & pattern, const string::LinearString < SymbolType > & subject );
 
};
 
template < class SymbolType, size_t BitmaskBitCount >
ext::set < unsigned > BNDMOccurrences::query ( const indexes::stringology::BitSetIndex < SymbolType, BitmaskBitCount > & pattern, const string::LinearString < SymbolType > & subject ) {
 
    ext::set < unsigned > occ;
 
    size_t patternLength = pattern.getString ( ).getContent ( ).size ( );
    size_t subjectLength = subject.getContent ( ).size ( );
    size_t posInSubject = 0;
    size_t bitmaskLength = std::min ( BitmaskBitCount, patternLength );
 
    ext::bitset < BitmaskBitCount > currentBitmask;
 
    while ( posInSubject + patternLength <= subjectLength ) {
        size_t posInPattern = bitmaskLength;
        size_t lastPosOfFactor = bitmaskLength;
 
         // Set the bitmask to all ones
        currentBitmask.set ( );
 
        while ( posInPattern > 0 && currentBitmask.any ( ) ) {
            typename ext::map < SymbolType, ext::bitset < BitmaskBitCount > >::const_iterator symbolVectorIter = pattern.getData ( ).find ( subject.getContent ( ).at ( posInSubject + posInPattern - 1 ) );
            if ( symbolVectorIter == pattern.getData ( ).end ( ) )
                break;
 
            currentBitmask &= symbolVectorIter->second;
            posInPattern--;
 
             // Test whether the most significant bit is set
            if ( currentBitmask.test ( bitmaskLength - 1 ) ) {
                 // and we didn't process all symbols of the pattern
                if ( posInPattern > 0 )
                    lastPosOfFactor = posInPattern;
                else {
                    size_t k = bitmaskLength;
 
                     // out of bitset fallback to naive checking of occurrence here
                    while ( k < patternLength && pattern.getString ( ).getContent ( ).at ( k ) == subject.getContent ( ).at ( posInSubject + k ) ) k++;
 
                    if ( k == patternLength )
                         // Yay, there is match!!!
                        occ.insert ( posInSubject );
                }
            }
 
            currentBitmask <<= 1;
        }
 
        posInSubject += lastPosOfFactor;
    }
 
    return occ;
}
 
} /* namespace query */
 
} /* namespace stringology */