RegularEquationSolver.h

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

#ifndef REGULAREQUATIONSOLVER_H_
#define REGULAREQUATIONSOLVER_H_

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

#include <alphabet/Symbol.h>
#include <exception/AlibException.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
#include <regexp/unbounded/UnboundedRegExpAlternation.h>

#include "common/macros.h"

// #include "RegExpOptimize.h" //TODO uncomment when implemented

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 & symb );

	/**
	 * 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& eq );

	/**
	 * Adds equation in form: FROM = eq
	 *
	 * @param from
	 * @param eq
	 */
	void addEquation( const alphabet::Symbol & from, const regexp::UnboundedRegExpElement& 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::UnboundedRegExpElement* eliminate( void ) = 0;

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

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

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

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

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

} /* namespace equations */

#endif /* REGULAREQUATIONSOLVER_H_ */