RegularEquationSolver.h

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

#ifndef REGULAR_EQUATIONS_SOLVER_H_
#define REGULAR_EQUATIONS_SOLVER_H_

#include <algorithm>
#include <map>
#include <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 SymbolType >
class RegularEquationSolver {
public:
	/**
	 * Adds nonterminal symbol into system.
	 *
	 * @param symb given symbol
	 */
	void addSymbol(const SymbolType& symbol);

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

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

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

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

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

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

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

	/**
	 * @see symbolsByDepth
	 */
	std::deque<SymbolType> nonterminalSymbolsByDepth;

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

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

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

template < class SymbolType >
void RegularEquationSolver < SymbolType >::setSymbols(const ext::set<SymbolType>& newSymbols) {
	ext::set<SymbolType> removed, 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 auto& symb : removed) {
		removeSymbol(symb);
	}

	for(const auto& symb : added) {
		addSymbol(symb);
	}
}

template < class SymbolType >
void RegularEquationSolver < SymbolType >::removeSymbol(const SymbolType& symb) {
	for(const auto& kv : equationTransition) {
		const SymbolType& from = kv.first.first;
		const SymbolType& to = kv.first.second;
		const regexp::UnboundedRegExpAlternation < SymbolType > & alt = kv.second;

		if((from == symb || to == symb) && alt.getElements().size() != 0) {
			throw exception::CommonException("Symbol '" + (std::string) symb + "' is in use.");
		}
	}

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

		if(from == symb && alt.getElements().size() != 0) {
			throw exception::CommonException("Symbol '" + (std::string) from + "' is in use.");
		}
	}


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

	for(const auto& s : nonterminalSymbols) {
		equationTransition.erase(equationTransition.find(std::make_pair(s, symb)));
		equationTransition.erase(equationTransition.find(std::make_pair(symb, s)));
	}
	equationTransition.erase(equationTransition.find(std::make_pair(symb, symb)));
}

template < class SymbolType >
void RegularEquationSolver < SymbolType >::addSymbol(const SymbolType& symb) {
	for(const auto& s : nonterminalSymbols) {
		equationTransition.insert(std::make_pair(std::make_pair(symb, s), regexp::UnboundedRegExpAlternation < SymbolType >  { }));
		equationTransition.insert(std::make_pair(std::make_pair(s, symb), regexp::UnboundedRegExpAlternation < SymbolType >  { }));
	}
	equationTransition.insert(std::make_pair(std::make_pair(symb, symb), regexp::UnboundedRegExpAlternation < SymbolType >  { }));

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

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

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

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

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

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

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

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

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

	while(! queue.empty()) {
		SymbolType s = queue.front();
		queue.pop();

		nonterminalSymbolsByDepth.push_back(s);

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

template < class SymbolType >
regexp::UnboundedRegExp < SymbolType > RegularEquationSolver < SymbolType >::solve(const SymbolType& solveFor) {
	if(nonterminalSymbols.count(solveFor) == 0) {
		throw exception::CommonException("Symbol solveFor ('" + (std::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_ */