/*
 * StateEliminationUnbounded.h
 *
 *  Created on: 9. 2. 2014
 *      Author: Tomas Pecka
 */

#ifndef STATEELIMINATIONUNBOUNDED_H_
#define STATEELIMINATIONUNBOUNDED_H_

#include <regexp/RegExp.h>
#include <regexp/unbounded/UnboundedRegExpElements.h>

#include <automaton/Automaton.h>
#include <automaton/FSM/DFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/ExtendedNFA.h>

namespace conversions
{

namespace fa2re
{

/**
 * Converts FSM to RE using State Elimination algorithm.
 * Source: Melichar 2.118
 */
class StateEliminationUnbounded : public automaton::VisitableAutomatonBase::const_visitor_type
{
public:
    /**
     * Performs conversion.
     * @return regular expression equivalent to source NFA.
     */
    template<class T>
    static regexp::RegExp convert(const T& automaton);

private:
    void Visit(void*, const automaton::UnknownAutomaton& automaton) const;
    void Visit(void*, const automaton::EpsilonNFA& automaton) const;
    void Visit(void*, const automaton::NFA& automaton) const;
    void Visit(void*, const automaton::DFA& automaton) const;
    void Visit(void*, const automaton::ExtendedNFA& automaton) const;
    void Visit(void*, const automaton::CompactNFA& automaton) const;
    void Visit(void*, const automaton::DPDA& automaton) const;
    void Visit(void*, const automaton::SinglePopDPDA& automaton) const;
    void Visit(void*, const automaton::InputDrivenNPDA& automaton) const;
    void Visit(void*, const automaton::VisiblyPushdownNPDA& automaton) const;
    void Visit(void*, const automaton::NPDA& automaton) const;
    void Visit(void*, const automaton::SinglePopNPDA& automaton) const;
    void Visit(void*, const automaton::OneTapeDTM& automaton) const;

    template<class T>
    static automaton::ExtendedNFA constructExtendedNFA(const T& automaton);

    static void extendExtendedNFA(automaton::ExtendedNFA& automaton);

    static const regexp::UnboundedRegExpElement* transition(const automaton::ExtendedNFA& automaton, const automaton::State& from, const automaton::State& to);

    static automaton::ExtendedNFA eliminateState(const automaton::ExtendedNFA& extendedAutomaton, const automaton::State& state);

    static const StateEliminationUnbounded STATE_ELIMINATION_UNBOUNDED;
};

} /* namespace fa2re */

} /* namespace conversions */

#endif /* STATEELIMINATIONUNBOUNDED_H_ */