RegularEquationSolver.h

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

#ifndef REGULAREQUATIONSOLVER_H_
#define REGULAREQUATIONSOLVER_H_

#include <regexp/unbounded/UnboundedRegExp.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
#include <alphabet/Symbol.h>

#include <map>
#include <deque>
#include <queue>

namespace equations {

/**
 * Base class for regular equations solvers.
 */
class RegularEquationSolver {
public:
	/**
	 * Adds nonterminal symbol into system.
	 *
	 * @param symb given symbol
	 * @
	 */
	void addSymbol(const alphabet::Symbol& symbol);

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

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

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

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

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

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

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

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

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

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

	/**
	 * Set of symbols
	 */
	std::set<alphabet::Symbol> nonterminalSymbols;
};

} /* namespace equations */

#endif /* REGULAREQUATIONSOLVER_H_ */