ExactFactorOracleAutomaton.h

/*
 * Author: Radovan Cerveny
 */

#pragma once

#include <limits>

#include <indexes/stringology/FactorOracleAutomaton.h>
#include <string/LinearString.h>

namespace stringology {

namespace indexing {

class ExactFactorOracleAutomaton {
private:
	static constexpr unsigned infinity = std::numeric_limits < unsigned >::max ( );

	template < class SymbolType >
	static void oracleAddLetter ( automaton::DFA < SymbolType, unsigned > & oracle, const SymbolType & symbol, ext::map < unsigned, unsigned > & supplyFunction );

public:
	/**
	 * Constructs factor oracle automaton for given pattern.
	 * @return factor oracle automaton for given pattern
	 */
	template < class SymbolType >
	static indexes::stringology::FactorOracleAutomaton < SymbolType > construct ( const string::LinearString < SymbolType > & pattern );

};

template < class SymbolType >
indexes::stringology::FactorOracleAutomaton < SymbolType > ExactFactorOracleAutomaton::construct ( const string::LinearString < SymbolType > & pattern ) {
	automaton::DFA < SymbolType, unsigned > oracleAutomaton ( 0u );

	oracleAutomaton.addFinalState ( oracleAutomaton.getInitialState ( ) );

	ext::vector < unsigned > supplyFunction { infinity }; //vector is fine, the state number is exactly the index to the vector

	oracleAutomaton.setInputAlphabet ( pattern.getAlphabet ( ) );

	for ( const SymbolType & symbol : pattern.getContent ( ) )
		oracleAddLetter ( oracleAutomaton, symbol, supplyFunction );

	return indexes::stringology::FactorOracleAutomaton < SymbolType > ( std::move ( oracleAutomaton ) );
}

template < class SymbolType >
void ExactFactorOracleAutomaton::oracleAddLetter ( automaton::DFA < SymbolType, unsigned > & oracle, const SymbolType & symbol, ext::map < unsigned, unsigned > & supplyFunction ) {
	unsigned lastState = oracle.getStates ( ).size ( ) - 1;
	unsigned newState = lastState + 1;

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

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

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

	unsigned supplyState = 0;

	if ( kState != infinity )
		supplyState = oracle.getTransitions ( ).find( { kState, symbol } )->second;

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

} /* namespace indexing */

} /* namespace stringology */