SuffixArrayFactors.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/SuffixArray.h>
#include <string/LinearString.h>
#include <ext/algorithm>
 
namespace stringology {
 
namespace query {
 
class SuffixArrayFactors {
public:
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::stringology::SuffixArray < SymbolType > & suffixArray, const string::LinearString < SymbolType > & string );
 
};
 
template < class SymbolType >
ext::set < unsigned > SuffixArrayFactors::query ( const indexes::stringology::SuffixArray < SymbolType > & suffixArray, const string::LinearString < SymbolType > & string ) {
 
    auto comparator = [ & ] ( const ext::vector < SymbolType > & first, unsigned firstIndex, const ext::vector < SymbolType > & second, unsigned secondIndex, unsigned limit ) {
            for ( ; firstIndex < first.size ( ) && secondIndex < second.size ( ) && limit > 0; ++ firstIndex, ++ secondIndex, --limit ) {
                auto res = first [ firstIndex ] <=> second [ secondIndex ];
 
                if ( res != 0 )
                    return res;
            }
 
            if ( limit == 0 )
                return std::strong_ordering::equal;
 
            return ( first.size ( ) - firstIndex ) <=> ( second.size ( ) - secondIndex );
    };
 
    // The value returned by comparator indicates whether the first argument is considered to go before the second.
    ext::vector < unsigned >::const_iterator low = std::lower_bound ( suffixArray.getData ( ).begin ( ), suffixArray.getData ( ).end ( ), string, [ & ] ( unsigned first, const string::LinearString < SymbolType > & str ) {
            return comparator ( suffixArray.getString ( ).getContent ( ), first, str.getContent ( ), 0, str.getContent ( ).size ( ) ) < 0;
    } );
 
    // The value returned by comparator indicates whether the first argument is considered to go before the second.
    ext::vector < unsigned >::const_iterator high = std::upper_bound ( suffixArray.getData ( ).begin ( ), suffixArray.getData ( ).end ( ), string, [ & ] ( const string::LinearString < SymbolType > & str, unsigned second ) {
            return comparator ( str.getContent ( ), 0, suffixArray.getString ( ).getContent ( ), second, str.getContent ( ).size ( ) ) < 0;
    } );
 
    return ext::set < unsigned > ( low, high );
}
 
} /* namespace query */
 
} /* namespace stringology */