RegularEquationSolver.h

/*
 * RegularEquationSolver.h
 *
 *  Created on: 4. 3. 2014
 *	  Author: Tomas Pecka
 */

#ifndef REGULAR_EQUATIONS_SOLVER_H_
#define REGULAR_EQUATIONS_SOLVER_H_

#include <alib/algorithm>
#include <alib/map>
#include <alib/deque>
#include <queue>

#include <exception/CommonException.h>

#include <regexp/unbounded/UnboundedRegExp.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
#include <regexp/unbounded/UnboundedRegExpElements.h>

namespace equations {

/**
 * Base class for regular equations solvers.
 */
template < class TerminalSymbolType, class VariableSymbolType >
class RegularEquationSolver {
public:
	/**
	 * Adds nonterminal symbol into system.
	 *
	 * @param symbol given symbol
	 */
	void addVariableSymbol ( const VariableSymbolType & symbol );

	/**
	 * Removes nonterminal symbol from equation system.
	 *
	 * @param symbol given symbol
	 * @throws CommonException when symbol is in use
	 */
	void removeVariableSymbol ( const VariableSymbolType & symbol );

	/**
	 * Sets nonterminal symbols of the equation system.
	 * @param symbol Symbols to set
	 * @throws CommonException
	 */
	void setVariableSymbols ( const ext::set < VariableSymbolType > & newSymbols );

	/**
	 * Adds equation in form FROM = eq TO
	 *
	 * @param from symbol
	 * @param to symbol
	 * @param eq equation
	 */
	void addEquation ( const VariableSymbolType & from, const VariableSymbolType & to, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq );

	/**
	 * Adds equation in form: FROM = eq
	 *
	 * @param from
	 * @param eq
	 */
	void addEquation ( const VariableSymbolType & from, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq );

	/**
	 * Solve expression system
	 *
	 * @param solveFor will solve equation system for given symbol
	 * @return regexp
	 */
	regexp::UnboundedRegExp < TerminalSymbolType > solve ( const VariableSymbolType & solveFor );

protected:
	/**
	 * actual equations elimination
	 * @return pointer to solutions RegExp tree root
	 */
	virtual regexp::UnboundedRegExp < TerminalSymbolType > eliminate ( void ) = 0;

	/**
	 * Runs BFS to determine depth of symbols in equation system and stores it in nonterminalSymbolsByDepth;
	 * @see nonterminalSymbolsByDepth
	 */
	void sortSymbolsByDepth ( const VariableSymbolType & solveFor );

	/**
	 * @see symbolsByDepth
	 */
	ext::deque < VariableSymbolType > nonterminalSymbolsByDepth;

	/**
	 * Stores transitions from nonterminal to nonterminal, eg A = 2A + 2B + 1C
	 */
	ext::map < std::pair < VariableSymbolType, VariableSymbolType >, regexp::UnboundedRegExpAlternation < TerminalSymbolType > > equationTransition;

	/**
	 * Stores equation not going to particular nonterminal, eg A = 01*
	 */
	ext::map < VariableSymbolType, regexp::UnboundedRegExpAlternation < TerminalSymbolType > > equationFinal;

	/**
	 * Set of symbols
	 */
	ext::set < VariableSymbolType > nonterminalSymbols;
};

template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::setVariableSymbols ( const ext::set < VariableSymbolType > & newSymbols ) {
	ext::set < VariableSymbolType > removed;
	ext::set < VariableSymbolType > added;

	std::set_difference ( nonterminalSymbols.begin ( ), nonterminalSymbols.end ( ), newSymbols.begin ( ), newSymbols.end ( ), std::inserter ( removed, removed.end ( ) ) );
	std::set_difference ( newSymbols.begin ( ), newSymbols.end ( ), nonterminalSymbols.begin ( ), nonterminalSymbols.end ( ), std::inserter ( added, added.end ( ) ) );

	for ( const VariableSymbolType & symbol : removed ) {
		removeVariableSymbol ( symbol );
	}

	for ( const VariableSymbolType & symbol : added ) {
		addVariableSymbol ( symbol );
	}
}

template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::removeVariableSymbol ( const VariableSymbolType & symbol ) {
	for ( const auto & kv : equationTransition ) {
		const VariableSymbolType & from = kv.first.first;
		const VariableSymbolType & to = kv.first.second;
		const regexp::UnboundedRegExpAlternation < TerminalSymbolType > & alt = kv.second;

		if ( ( from == symbol || to == symbol ) && !alt.getElements ( ).empty ( ) ) {
			throw exception::CommonException ( "Symbol '" + ext::to_string ( symbol ) + "' is in use." );
		}
	}

	for ( const auto & kv : equationFinal ) {
		const VariableSymbolType & from = kv.first;
		const regexp::UnboundedRegExpAlternation < TerminalSymbolType > & alt = kv.second;

		if ( from == symbol && !alt.getElements ( ).empty ( ) ) {
			throw exception::CommonException ( "Symbol '" + ext::to_string ( from ) + "' is in use." );
		}
	}


	nonterminalSymbols.erase ( nonterminalSymbols.find ( symbol ) );
	equationFinal.erase ( equationFinal.find ( symbol ) );

	for ( const VariableSymbolType & variable : nonterminalSymbols ) {
		equationTransition.erase ( equationTransition.find ( std::make_pair ( variable, symbol ) ) );
		equationTransition.erase ( equationTransition.find ( std::make_pair ( symbol, variable ) ) );
	}

	equationTransition.erase ( equationTransition.find ( std::make_pair ( symbol, symbol ) ) );
}

template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::addVariableSymbol ( const VariableSymbolType & symbol ) {
	for ( const VariableSymbolType & variable : nonterminalSymbols) {
		equationTransition.insert ( std::make_pair ( std::make_pair ( symbol, variable ), regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
		equationTransition.insert ( std::make_pair ( std::make_pair ( variable, symbol ), regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
	}

	equationTransition.insert ( std::make_pair ( std::make_pair ( symbol, symbol ), regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );

	nonterminalSymbols.insert ( symbol );
	equationFinal.insert ( std::make_pair ( symbol, regexp::UnboundedRegExpAlternation < TerminalSymbolType > { } ) );
}

template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::addEquation ( const VariableSymbolType & from, const VariableSymbolType & to, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq ) {
	if ( nonterminalSymbols.count ( from ) == 0 ) {
		throw exception::CommonException ( "Symbol from ('" + ext::to_string ( from ) + "') is not in equation system." );
	}

	if ( nonterminalSymbols.count ( to ) == 0 ) {
		throw exception::CommonException ( "Symbol to ('" + ext::to_string ( to ) + "') is not in equation system." );
	}

	equationTransition.find ( std::make_pair ( from, to ) )->second.appendElement ( eq );
}

template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::addEquation ( const VariableSymbolType & from, const regexp::UnboundedRegExpElement < TerminalSymbolType > & eq ) {
	if ( nonterminalSymbols.count ( from ) == 0 ) {
		throw exception::CommonException ( "Symbol from ('" + ext::to_string ( from ) + "') is not in equation system." );
	}

	equationFinal.find ( from )->second.appendElement ( eq );
}

template < class TerminalSymbolType, class VariableSymbolType >
void RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::sortSymbolsByDepth ( const VariableSymbolType & solveFor ) {
	ext::map < VariableSymbolType, bool > visited;
	std::queue < VariableSymbolType > queue;

	for(const VariableSymbolType & symbol : nonterminalSymbols ) {
		visited [ symbol ] = false;
	}

	visited [ solveFor ] = true;
	queue.push ( solveFor );

	while ( ! queue.empty ( ) ) {
		VariableSymbolType variable = std::move ( queue.front ( ) );
		queue.pop ( );

		nonterminalSymbolsByDepth.push_back ( variable );

		for ( const auto & kv : equationTransition ) {
			// find all transitions from current symbol that are non-empty, enqueue transition'variable target symbol
			if ( kv.first.first == variable && ! visited [ kv.first.second ] && !kv.second.getElements ( ).empty ( ) ) {
				visited [ kv.first.second ] = true;
				queue.push ( kv.first.second );
			}
		}
	}
}

template < class TerminalSymbolType, class VariableSymbolType >
regexp::UnboundedRegExp < TerminalSymbolType > RegularEquationSolver < TerminalSymbolType, VariableSymbolType >::solve ( const VariableSymbolType & solveFor ) {
	if ( nonterminalSymbols.count ( solveFor ) == 0 ) {
		throw exception::CommonException ( "Symbol solveFor ('" + ext::to_string ( solveFor ) + "') is not in equation system." );
	}

	/*
	 * Firstly, organize states by depth so we can output better looking
	 * expressions. We need to solve equation system for automaton's initial state,
	 * so lets start with the deepest ones and walk towards the initial one.
	 */
	sortSymbolsByDepth ( solveFor );
	return eliminate ( );
}

} /* namespace equations */

#endif /* REGULAR_EQUATIONS_SOLVER_H_ */