FactorOracleAutomaton.cpp

/*
 * Author: Radovan Cerveny
 */

#include "FactorOracleAutomaton.hpp"
#include <exception/AlibException.h>
#include <string/LinearString.h>

namespace stringology {

namespace exact {

automaton::Automaton FactorOracleAutomaton::construct ( const string::String & pattern ) {
    return getInstance ( ).dispatch ( pattern.getData ( ) );
}

automaton::DFA FactorOracleAutomaton::construct ( const string::LinearString & pattern ) {
    automaton::DFA oracle ( automaton::State ( 0 ) );

    std::map < automaton::State, automaton::State > supplyFunction { { automaton::State ( 0 ), automaton::State ( -1 ) } };

    oracle.setInputAlphabet ( pattern.getAlphabet ( ) );

    for ( const alphabet::Symbol & symbol : pattern.getContent ( ) )
        oracleAddLetter ( oracle, symbol, supplyFunction );

    return oracle;
}

void FactorOracleAutomaton::oracleAddLetter ( automaton::DFA & oracle, const alphabet::Symbol & symbol, std::map < automaton::State, automaton::State > & supplyFunction ) {
    int m = ( int ) oracle.getStates ( ).size ( ) - 1;

    automaton::State lastState ( m );
    automaton::State newState ( m + 1 );

    oracle.addState ( newState );
    oracle.addFinalState ( newState );

    oracle.addTransition ( lastState, symbol, newState );
    automaton::State kState = supplyFunction.find( lastState ) -> second;

    while ( kState != automaton::State ( -1 ) && oracle.getTransitions ( ).find ( { kState, symbol } ) == oracle.getTransitions ( ).end ( ) ) {
        oracle.addTransition ( kState, symbol, newState );
        kState = supplyFunction.find( kState ) -> second;
    }

    automaton::State supplyState = automaton::State ( 0 );

    if ( kState != automaton::State ( -1 ) )
        supplyState = oracle.getTransitions ( ).find( { kState, symbol } ) -> second;

    supplyFunction.insert( { newState, supplyState } );
}

auto FactorOracleAutomatonLinearString = FactorOracleAutomaton::RegistratorWrapper < automaton::DFA, string::LinearString > ( FactorOracleAutomaton::getInstance ( ), FactorOracleAutomaton::construct );

} /* namespace exact */

} /* namespace stringology */