ApproximateEnhancedCoversCommon.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/pair>
#include <alib/set>
#include <alib/vector>
#include <string/LinearString.h>
 
namespace stringology::cover {
 
class ApproximateEnhancedCoversCommon {
public:
    virtual ~ApproximateEnhancedCoversCommon ( ) = 0;
 
protected:
    struct Element {
        unsigned depth, level;
        Element ( ) = default;
        Element ( unsigned d, unsigned l ) : depth ( d ), level ( l ) { }
    };
 
    struct State {
         // depth is equal to the number of transitions from the starting state to
         // this state
        unsigned depth = 0;
 
         // Pair of two integers - depth of the element with level 0 and length of
         // corresponding factor
        ext::pair < unsigned, unsigned > lfactor;
 
         // d-subset of this state
        ext::vector < Element > elements;
 
        State ( ) = default;
        ~State ( ) = default;
 
         // default move constructor
        State ( State && other ) = default;
 
         // default move assignment operator
        State & operator =( State && other ) = default;
    };
 
    static unsigned distEnhCov ( const State & q ) {
        unsigned r = 0;
        unsigned m = q.elements[0].depth;
 
        for ( size_t i = 1; i < q.elements.size ( ); ++i ) {
            if ( q.elements[i].depth - q.elements[i - 1].depth < m )
                r += q.elements[i].depth - q.elements[i - 1].depth;
            else
                r += m;
        }
 
        return r + m;
    }
 
    static void updateEnhCov ( const State & state, ext::set < ext::pair < unsigned, unsigned > > & enhCovers, unsigned & h ) {
        unsigned hNext = distEnhCov ( state );
 
         // update the current set if this state covers more positions
        if ( hNext > h ) {
            h = hNext;
            enhCovers.clear ( );
        }
 
        if ( hNext == h )
            enhCovers.insert ( state.lfactor );
    }
 
    template < class SymbolType >
    static State constrFirstState ( const string::LinearString < SymbolType > & x, unsigned k, const SymbolType & symbol ) {
        State firstState;
 
        firstState.depth = 1;
        firstState.lfactor = ext::pair < unsigned, unsigned > ( 1, 1 );
 
        for ( size_t i = 0; i < x.getContent ( ).size ( ); ++i ) {
            if ( symbol == x.getContent ( )[i] )
                firstState.elements.emplace_back ( i + 1, 0 );
            else if ( k > 0 )
                firstState.elements.emplace_back ( i + 1, 1 );
        }
 
        return firstState;
    }
 
    template < class SymbolType >
    static State constrNextState ( const string::LinearString < SymbolType > & x, const State & previousState, unsigned k, const SymbolType & symbol ) {
        State nextState;
 
        nextState.depth = previousState.depth + 1;
        nextState.lfactor = previousState.lfactor;
 
        for ( const auto & element : previousState.elements )
            if ( element.depth < x.getContent ( ).size ( ) ) {
                if ( symbol == x.getContent ( )[element.depth] ) {
                    nextState.elements.emplace_back ( element.depth + 1, element.level );
                    nextState.lfactor = ext::pair < unsigned, unsigned > ( element.depth + 1, nextState.depth );
                } else if ( element.level < k ) {
                    nextState.elements.emplace_back ( element.depth + 1, element.level + 1 );
                }
            }
 
        return nextState;
    }
 
    template < class SymbolType >
    static bool isBorder ( const State & state, const string::LinearString < SymbolType > & x, unsigned k ) {
        Element lastElement = state.elements[state.elements.size ( ) - 1];
        Element firstElement = state.elements[0];
 
        return firstElement.depth == state.depth && firstElement.level == 0 && lastElement.depth == x.getContent ( ).size ( ) && lastElement.level == 0 && state.depth > k;
    }
 
    template < class SymbolType >
    static ext::set < string::LinearString < SymbolType > > getFactors ( const string::LinearString < SymbolType > & x, ext::set < ext::pair < unsigned int, unsigned int > > & enhCovers ) {
        ext::set < string::LinearString < SymbolType > > result;
 
        for ( const auto & p : enhCovers )
            result.insert ( string::LinearString ( ext::vector < SymbolType > ( x.getContent ( ).cbegin ( ) + p.first - p.second, x.getContent ( ).cbegin ( ) + p.first ) ) );
 
        return result;
    }
 
};
 
} // namespace stringology::cover