C:/CVUT/diplomka/Automata_editor/algorithms/algorithms.cpp

Go to the documentation of this file.

#include "algorithms.h"

#include "interfaces/iautomaton.h"
#include "interfaces/istate.h"
#include "interfaces/itransition.h"

#include <QSet>
#include <QQueue>
#include <QStringList>
#include <QMap>

#include <QDialog>
#include <QGridLayout>
#include <QCheckBox>
#include <QPushButton>

#include <QtPlugin>

#include "utility/dbglog.h"
#include "utility/utils.h"

#define DBGLOG_ALGO(x) DBGLOG_("ALGORITHMS", x)

//<-- SettingsDialog -----------------------------------------------------------------------

class SettingsDialog : public QDialog
{
public:
    SettingsDialog(BasicAlgorithmWithSettings &algorithm, QWidget *parent)
    :   QDialog(parent), m_algorithm(algorithm)        
    {
        m_checkPreserveNames = new QCheckBox(tr("Preserve state names"), this);
        m_checkPreserveNames->setChecked(m_algorithm.preserveNames());
        
        m_checkPreserveLabels = new QCheckBox(tr("Preserve state labels"), this);
        m_checkPreserveLabels->setChecked(m_algorithm.preserveLabels());
        
        // buttons
        QWidget *hBox = new QWidget(this);
        QPushButton *buttonOk = new QPushButton("Ok");
        QPushButton *buttonCancel = new QPushButton("Cancel");
        QHBoxLayout *hBoxLayout = new QHBoxLayout;
        hBoxLayout->addWidget(buttonOk);
        hBoxLayout->addWidget(buttonCancel);
        hBox->setLayout(hBoxLayout);    
        hBox->setMaximumWidth(300);
        connect(buttonOk, SIGNAL(clicked()), this, SLOT(accept()));
        connect(buttonCancel, SIGNAL(clicked()), this, SLOT(reject()));
        
        QGridLayout *gridLayout = new QGridLayout(this);
        gridLayout->addWidget(m_checkPreserveNames, 0, 0);
        gridLayout->addWidget(m_checkPreserveLabels, 1, 0);
        gridLayout->addWidget(hBox, 2, 0);
        
        QString s = m_algorithm.getName() + " - settings";        
        setWindowTitle(s);
        setWindowIcon(QIcon(":images/grid.xpm"));
    }
    
    bool preserveNames() const { return m_checkPreserveNames->checkState() == Qt::Checked; }
    bool preserveLabels() const { return m_checkPreserveLabels->checkState() == Qt::Checked; }
    
private:
    QCheckBox                   *m_checkPreserveNames;
    QCheckBox                   *m_checkPreserveLabels;
    BasicAlgorithmWithSettings  &m_algorithm;
};

//----------------------------------------------------------------------- SettingsDialog -->



//<-- BasicAlgorithm -----------------------------------------------------------------------

BasicAlgorithm::BasicAlgorithm()
:   m_creator(QSharedPointer<IAutomataCreator>(NULL))    
{}

void BasicAlgorithm::setAutomataCreator(const QSharedPointer<IAutomataCreator> &creator)
{
    m_creator = creator;
}

bool BasicAlgorithm::run(const IAutomaton::TAutomataList &input,
                         QSharedPointer<IAutomaton> &result,
                         QString *report) const
{    
    m_report = "";
    
    if (!m_creator)
    {
        addReport("Creator is not set, contact plugin's developer");
        RELLOG(getName() << " -> creator is not set!!!");
        return false;
    }

    DBGLOG_ALGO(getName() << " -> " << input.count()
                << (input.count() != 1 ? "automata" : "automaton") << "on input");

    bool ret = runInternal(input, result);
    
    // fill report if required
    if (report)
    {
        *report = m_report;
    }
    
    return ret;
}

IState::TIStateNameSet BasicAlgorithm::getEpsilonClosure
    (const QSharedPointer<IAutomaton> &automaton, const QSharedPointer<IState> &state) const
{
    IState::TIStateNameSet result;
    
    QQueue<QSharedPointer<IState> > openedStates;
    openedStates.enqueue(state);

    QSharedPointer<IState> currentState;
    QString workState;

    while(!openedStates.empty())
    {
        currentState = openedStates.dequeue();
        result << currentState->getName();

        foreach(const QSharedPointer<ITransition> &tr, currentState->getTransitions())
        {            
            if (tr->getCharacters().contains(automaton->getEpsilonSymbol()))
            {
                workState = tr->getDestinationState();
                
                if (result.contains(workState)) continue;
                result << workState;

                openedStates << automaton->getState(workState);
            }
        }
    }

    return result;
}

bool BasicAlgorithm::removeEpsilonTransitions(QSharedPointer<IAutomaton> &automaton) const
{
    QSharedPointer<IAlgorithm> epsAlgorithm(new RemoveEpsilonAlgorithm());
    epsAlgorithm->setAutomataCreator(m_creator);

    IAutomaton::TAutomataList automata;
    automata << automaton;
    
    QString report;
    if (!epsAlgorithm->run(automata, automaton, &report))
    {
        addReport(report);
        return false;
    }
    
    return true;
}

bool BasicAlgorithm::removeMultipleInitials(QSharedPointer<IAutomaton> &automaton) const
{
    QSharedPointer<IAlgorithm> miAlgorithm(new RemoveMultipleInitialsAlgorithm());
    miAlgorithm->setAutomataCreator(m_creator);

    IAutomaton::TAutomataList automata;
    automata << automaton;
    
    QString report;
    if (!miAlgorithm->run(automata, automaton, &report))
    {
        addReport(report);
        return false;
    }
    
    return true;
}

bool BasicAlgorithm::determinize(QSharedPointer<IAutomaton> &automaton) const
{
    QSharedPointer<IAlgorithm> determinizeAlg(new DeterminizeAlgorithm());
    determinizeAlg->setAutomataCreator(m_creator);
    
    IAutomaton::TAutomataList automata;
    automata << automaton;
    
    QString report;
    if (!determinizeAlg->run(automata, automaton, &report))
    {
        addReport(report);
        return false;
    }
    
    return true;
}

void BasicAlgorithm::makeSureNameUnique(const QSharedPointer<IAutomaton> &automaton,
                                        QString &name) const
{
    bool changed = false;
    while(automaton->hasState(name))
    {
        name += "*";
        changed = true;
    }
}

void BasicAlgorithm::makeSureNamesUnique(const QSharedPointer<IAutomaton> &automaton1,
                                         const QSharedPointer<IAutomaton> &automaton2) const
{
    IState::TIStateList a2States = automaton2->getStates();
    foreach(const QSharedPointer<IState> &state, a2States)
    {
        bool changed = false;
        QString newName = state->getName();
        while(automaton1->hasState(newName) || 
             (changed && automaton2->hasState(newName)))
        {
            newName += "*";
            changed = true;
        }
        if (changed)
            automaton2->renameState(state, newName);
    }
}

void BasicAlgorithm::addReport(const QString &text) const
{
    m_report += text;
}

bool BasicAlgorithm::tryMergeAlphabet(const ITransition::TCharSet &alphabet1,
                                      const ITransition::TCharSet &alphabet2,
                                      ITransition::TCharSet &alphabet) const
{
    // check if one of alphabets if subset of the other
    ITransition::TCharSet intersection = alphabet1 & alphabet2;
    if (!(alphabet1 - intersection).empty() &&
        !(alphabet2 - intersection).empty())
    {
        return false;
    }

    alphabet = alphabet1;
    alphabet |= alphabet2;
    return true;
}

//----------------------------------------------------------------------- BasicAlgorithm -->



//<-- BasicAlgorithmWithSettings -----------------------------------------------------------

BasicAlgorithmWithSettings::BasicAlgorithmWithSettings(bool preserveNames, bool preserveLabels)
:   m_preserveNames(preserveNames), m_preserveLabels(preserveLabels)
{}

void BasicAlgorithmWithSettings::runSettingsDialog(QWidget *parent)
{
    SettingsDialog sd(*this, parent);
    
    if (sd.exec() == QDialog::Rejected) return;
    
    setPreserveNames(sd.preserveNames());
    setPreserveLabels(sd.preserveLabels());
    
    // TODO: make settings persistent (store it somewhere)
}

QString BasicAlgorithmWithSettings::chooseStateName(QSharedPointer<IAutomaton> &automaton,
                                                    const QStringList &nameList, int num) const
{
    QString name;
    if (preserveNames())
        name = nameList.join(""); // don't use '[', ']' and ',' symbols due to VauCanSon-G format!
    else
        name = QString("Q%1").arg(num);
    
    makeSureNameUnique(automaton, name);
    return name;
}

QString BasicAlgorithmWithSettings::chooseStateLabel(const QStringList &labelList, int num) const
{
    QString label;
    if (preserveLabels())
        label = labelList.join("");
    else
        label = QString("%1").arg(num);
    return label;
}

//----------------------------------------------------------- BasicAlgorithmWithSettings -->



//<-- RemoveEpsilonAlgorithm ---------------------------------------------------------------

RemoveEpsilonAlgorithm::~RemoveEpsilonAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString RemoveEpsilonAlgorithm::getName() const
{
    return "Remove epsilon transitions";
}

bool RemoveEpsilonAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                         QSharedPointer<IAutomaton> &result) const
{
    if (input.empty())
    {        
        RELLOG("nothing on input");
        addReport("nothing on input");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton = input[0];

    typedef QMap<QString, IState::TIStateNameSet> TEpsilonClosureMap;
    TEpsilonClosureMap closureMap;
    
    foreach(const QSharedPointer<IState> &state, automaton->getStates())
    {
        closureMap[state->getName()] = getEpsilonClosure(automaton, state);
        DBGLOG_ALGO("epsilonClosure(" << state->getName() << ")=" << closureMap[state->getName()]);
    }

    QSharedPointer<IAutomaton> newAutomaton = 
        m_creator->createAutomaton(automaton->getAlphabet(), automaton->getAlphabetSymbol(),
                                   automaton->getEpsilonSymbol());

    // TODO: should be really all original states included in the resulting automaton
    // copy states
    foreach(const QSharedPointer<IState> &currentState, automaton->getStates())
    {    
        newAutomaton->createState(currentState->getName(), currentState->getLabel(),
                                  currentState->isInitial(), currentState->isFinal());
    }

    bool ok = true;
    foreach(const QSharedPointer<IState> &currentState, newAutomaton->getStates())
    {
        bool isFinal = false;

        foreach(const QString &character, automaton->getAlphabet())
        {
            IState::TIStateNameSet destinations;

            ITransition::TCharSet charset;
            charset << character;

            foreach(const QString &stateName, closureMap[currentState->getName()])
            {
                const QSharedPointer<IState> &state= automaton->getState(stateName);
                isFinal = isFinal || state->isFinal();
                
                destinations |= state->getStatesOn(character);
            }

            foreach(const QString &stateName, destinations)
            {
                newAutomaton->createTransition(currentState->getName(), stateName, charset);
            }
        }
        
        currentState->setFinal(isFinal);
    }

    if (ok)
    {
        result = newAutomaton;
        return true;
    }

    return false;
}

//--------------------------------------------------------------- RemoveEpsilonAlgorithm -->



//<-- RemoveInaccessibleAlgorithm ----------------------------------------------------------

RemoveInaccessibleAlgorithm::~RemoveInaccessibleAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString RemoveInaccessibleAlgorithm::getName() const
{
    return "Remove inaccessible states";
}

bool RemoveInaccessibleAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                              QSharedPointer<IAutomaton> &result) const
{
    if (input.empty())
    {
        RELLOG("nothing on input");
        addReport("nothing on input");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton = input[0];
    
    QSharedPointer<IAutomaton> newAutomaton =
        m_creator->createAutomaton(automaton->getAlphabet(), automaton->getAlphabetSymbol(),
                                   automaton->getEpsilonSymbol());

    // 1) Q_0 = I; i = 1; // I .. initial states
    IState::TIStateNameSet  accessibleSet;
    IState::TIStateList     accessibleList;
    foreach(const QSharedPointer<IState> &state, automaton->getInitialStates())
    {
        accessibleSet << state->getName();
        accessibleList << state;        
        
        newAutomaton->createState(state->getName(), state->getLabel(), state->isInitial(), state->isFinal());        
    }

    IState::TIStateList newListQi;
    IState::TIStateList listQi = accessibleList;
    QSharedPointer<IState> newState;
    QSharedPointer<IState> currentState;
   
    bool ok = true;
    // small modification .. in next steps only newStates are needed in loop
    // 2) Q_i = {q: q isfrom d(p, a), p isfrom lastAddedStates, a isfrom T} U Q_i-1
    do
    {
        foreach(const QSharedPointer<IState> &state, listQi)
        {
            foreach(const QSharedPointer<ITransition> &tr, state->getTransitions())
            {
                QString workState = tr->getDestinationState();
                if (accessibleSet.contains(workState)) continue;
                
                accessibleSet << workState;
                
                currentState = automaton->getState(workState);
                accessibleList << currentState;
                newListQi << currentState;
                
                ok = ok && (newAutomaton->createState(currentState->getName(),
                                                      currentState->getLabel(),
                                                      currentState->isInitial(),
                                                      currentState->isFinal()) != NULL);
            }
        }
        
        listQi = newListQi;
        newListQi.clear();
    }
    while(!listQi.empty());
    
    if (!ok) return false;
    
    foreach(const QSharedPointer<IState> &state, accessibleList)
    {
        foreach(const QSharedPointer<ITransition> &tr, state->getTransitions())
        {
            if (!accessibleSet.contains(tr->getDestinationState())) continue;
            
            ok = ok && 
                (newAutomaton->createTransition(tr->getSourceState(),
                                                tr->getDestinationState(),
                                                tr->getCharacters()) != NULL);
        }
    }
    
    if (ok)
    {
        result = newAutomaton;
        return true;
    }
    
    return false;
}

//---------------------------------------------------------- RemoveInaccessibleAlgorithm -->



//<-- RemoveUselessAlgorithm --------------------------------------------------------------

RemoveUselessAlgorithm::~RemoveUselessAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString RemoveUselessAlgorithm::getName() const
{
    return "Remove useless states";
}

bool RemoveUselessAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                          QSharedPointer<IAutomaton> &result) const
{
    if (input.empty())
    {
        RELLOG("nothing on input");
        addReport("nothing on input");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton = input[0];
    
    QSharedPointer<IAutomaton> newAutomaton =
        m_creator->createAutomaton(automaton->getAlphabet(), automaton->getAlphabetSymbol(),
                                   automaton->getEpsilonSymbol());

    // 1) Q_0 = F; i = 1; // F .. final states
    IState::TIStateNameSet  usefulSet;
    IState::TIStateList     usefulList;
    foreach(const QSharedPointer<IState> &state, automaton->getFinalStates())
    {
        usefulSet << state->getName();
        usefulList << state;
        newAutomaton->createState(state->getName(),
                                  state->getLabel(),
                                  state->isInitial(),
                                  state->isFinal());
    }

    IState::TIStateList newListQi;
    IState::TIStateList listQi = usefulList;
    QSharedPointer<IState> newState;
    QSharedPointer<IState> currentState;

    // 2) Q_i = {q : p isfrom d(q, a), p isfrom Q_i-1} U Q_i-1    
    do
    {
        foreach(const QSharedPointer<IState> &state, listQi)
        {
            foreach(const QSharedPointer<ITransition> &tr, state->getTransitionsTo())
            {
                QString workState = tr->getSourceState();
                if (usefulSet.contains(workState)) continue;
                
                usefulSet << workState;
                
                currentState = automaton->getState(workState);
                usefulList << currentState;
                newListQi << currentState;
                
                newAutomaton->createState(currentState->getName(),
                                          currentState->getLabel(),
                                          currentState->isInitial(),
                                          currentState->isFinal());
            }
        }
        
        listQi = newListQi;
        newListQi.clear();
    }
    while (!listQi.empty());

    bool ok = true;
    foreach(const QSharedPointer<IState> &state, usefulList)
    {
        foreach(const QSharedPointer<ITransition> &tr, state->getTransitionsTo())
        {
            if (!usefulSet.contains(tr->getSourceState())) continue;
            
            ok = ok && (newAutomaton->createTransition(tr->getSourceState(),
                                                       tr->getDestinationState(),
                                                       tr->getCharacters()) != NULL);
        }
    }
    
    if (ok)
    {
        result = newAutomaton;
        return true;
    }
    
    return false;
}

//-------------------------------------------------------------- RemoveUselessAlgorithm -->



//<-- RemoveMultipleInitialsAlgorithm ------------------------------------------------------

RemoveMultipleInitialsAlgorithm::~RemoveMultipleInitialsAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString RemoveMultipleInitialsAlgorithm::getName() const
{
    return "Remove multiple inital states";
}

bool RemoveMultipleInitialsAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                                  QSharedPointer<IAutomaton> &result) const
{
    if (input.empty())
    {
        RELLOG("nothing on input");
        addReport("nothing on input");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton = input[0];

    // 1) q0 = I // I ... initial states    
    IState::TIStateList initialStates = automaton->getInitialStates();
    
    if (initialStates.empty())
        return false; // no inital states!
    
    if (initialStates.count() == 1)
    {
        result = automaton;
        return true;
    }
    
    QStringList q0NameList, q0LabelList;
    bool q0final = false;    
    foreach(const QSharedPointer<IState> &state, initialStates)
    {
        q0NameList << state->getName();
        q0LabelList << state->getLabel();
        state->setInitial(false);
        q0final = q0final || state->isFinal();
    }
    
    QString q0Name = "["+q0NameList.join(",")+"]";
    makeSureNameUnique(automaton, q0Name);
    
    // 3) Q' = Q U {q0}
    automaton->createState(q0Name,
                           q0LabelList.join(""),
                           true,
                           // 4,5) if some q in I is final, q0 is final too
                           q0final);
                            
    // 2) d'(q0,a) = U d(q, a), q isfrom I, a isfrom T                          
    foreach(const QSharedPointer<IState> &state, initialStates)
    {
        foreach(const QSharedPointer<ITransition> &tr, state->getTransitions())
        {
            automaton->createTransition(q0Name, tr->getDestinationState(), tr->getCharacters());
        }
    }
    
    // here could arise some inacessible states (from originally initial states), so remove them
    // (if state was originally intial and no transition from q0 (new initial) leads to it, is now inaccessible)
    foreach(const QSharedPointer<IState> &state, initialStates)
    {
        bool accessible = false;
        foreach(const QSharedPointer<ITransition> &tr, state->getTransitionsTo())
        {
            accessible |= (tr->getSourceState() == q0Name);
        }
        
        if (!accessible)
            automaton->removeState(state);
    }
    
    result = automaton;
    return true;
}

//------------------------------------------------------ RemoveMultipleInitialsAlgorithm -->



//<-- DeterminizeAlgorithm -----------------------------------------------------------------

DeterminizeAlgorithm::DeterminizeAlgorithm()
:   BasicAlgorithmWithSettings(false, true)
{}

DeterminizeAlgorithm::~DeterminizeAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString DeterminizeAlgorithm::getName() const
{
    return "Determinize automaton";
}

bool DeterminizeAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                       QSharedPointer<IAutomaton> &result) const
{
    if (input.empty())
    {
        RELLOG("nothing on input");
        addReport("nothing on input");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton = input[0];
    if (automaton->hasEpsilonTransitions())
    {
        if (!removeEpsilonTransitions(automaton))
            return false;
    }
    
    if (automaton->hasMultipleInitials())
    {
        if (!removeMultipleInitials(automaton))
            return false;
    }
    
    // now automaton is prepared
    Q_ASSERT(automaton->getInitialStates().count() == 1);
    
    QSharedPointer<IAutomaton> automatonDFA(m_creator->createAutomaton(automaton->getAlphabet(),
                                                                       automaton->getAlphabetSymbol(),
                                                                       automaton->getEpsilonSymbol()));
    
    int stateNum = 0;
    
    // 4) q0' = q0
    QSharedPointer<IState> newState = (automaton->getInitialStates())[0];
    QStringList newStateNameList(newState->getName());
    
    QString newStateName = chooseStateName(automatonDFA, newStateNameList, stateNum);
    QString newStateLabel = chooseStateLabel(QStringList(newState->getLabel()), stateNum);
    newState = automatonDFA->createState(newStateName, newStateLabel, true, newState->isFinal());
    stateNum++;
    
    // 1) Q' = {{q0}}, q0 .. no marked
    QQueue<QSharedPointer<IState> > openedStates;
    openedStates.enqueue(newState);
        
    QMap<QString, QStringList> nameToNameListMap;
    nameToNameListMap[newStateName] = newStateNameList;    
    
    // 2) all states in Q' marked, goto 4)
    while (!openedStates.empty())
    {
        QSharedPointer<IState> currentState = openedStates.dequeue();
        
        // 3a) d'(q',a) = U_(p isform q') d(p, a), foreach a isform T
        ITransition::TCharSet alphabet = automaton->getAlphabet();
        foreach(const QString &character, alphabet)
        {
            IState::TIStateNameSet newStateNameSet;            
            
            Q_ASSERT(nameToNameListMap.contains(currentState->getName()));
            QStringList origNameList = nameToNameListMap[currentState->getName()];
            foreach(const QString &stateName, origNameList)
            {
                QSharedPointer<IState> state = automaton->getState(stateName); // get original automaton's state
                newStateNameSet |= state->getStatesOn(character);                
            }
            
            if (newStateNameSet.empty()) continue; // no next state
            
            newStateNameList = newStateNameSet.toList();
            qSort(newStateNameList); // required since QSet's elements is in undefined order
            
            QStringList newStateLabelList;
            bool newStateIsFinal = false;
            // 5) F' = { q' : q' isform Q', q' intersect F not empty }
            foreach(const QString &partName, newStateNameSet)
            {
                QSharedPointer<IState> state = automaton->getState(partName);
                newStateIsFinal = newStateIsFinal || state->isFinal();
                newStateLabelList << state->getLabel();
            }
            
            if (nameToNameListMap.values().contains(newStateNameList))
            {                
                newState = automatonDFA->getState(nameToNameListMap.key(newStateNameList));
                
                //DBGLOG("Adding tr: " << currentState->getName() << "," << newState->getName() << " on char " << character);
                automatonDFA->createTransition(currentState->getName(), newState->getName(),
                                               (ITransition::TCharSet() << character));
                
                continue; // not add state more than once
            }
            
            newStateName = chooseStateName(automatonDFA, newStateNameList, stateNum);            
            newStateLabel = chooseStateLabel(newStateLabelList, stateNum);
            
            // now we have to create new state which belongs to DFA
            newState = automatonDFA->createState(newStateName, newStateLabel, false, newStateIsFinal);
            stateNum++;
            
            openedStates.enqueue(newState);
            nameToNameListMap[newStateName] = newStateNameList;
            
            //DBGLOG("Adding tr: " << currentState->getName() << "," << newStateName << " on char " << character);
            automatonDFA->createTransition(currentState->getName(), newStateName,
                                           (ITransition::TCharSet() << character));
        }
    }
    
    result = automatonDFA;
    
    return true;
}

//----------------------------------------------------------------- DeterminizeAlgorithm -->



//<-- MinimalizeAlgorithm ------------------------------------------------------------------

class GroupItem
{
public:
    typedef QStringList  TTrList;

    explicit GroupItem(const QString &state, const TTrList &trList = TTrList(), bool initial = false)
    :   m_state(state), m_trList(trList), m_initial(initial)
    {}
    
    QString getState() const { return m_state; }
    TTrList getTrList() const { return m_trList; }
    bool isInitial() const { return m_initial; }
    
private:
    QString             m_state;
    TTrList             m_trList;
    bool                m_initial;
};

inline bool operator==(const GroupItem &lhs, const GroupItem &rhs)
{
    return lhs.getState() == rhs.getState();
}

inline uint qHash(const GroupItem &key)
{
    return qHash(key.getState());
}

class Group
{
public:
    typedef QVector<QSharedPointer<Group> >     TGroupList;
    typedef QSet<GroupItem>                     TItemSet;
    
    Group(int id)
    : m_id(id)
    {}
    
    int id() const { return m_id; }
    
    int count() const { return m_states.count(); }
    
    bool contains(const QString &state) const { return m_states.contains(GroupItem(state)); }
    
    TItemSet items() const { return m_states; }
    
    void insert(const GroupItem &state) { m_states << state; }
    
    bool initial() const
    {        
        foreach(const GroupItem &state, m_states)
        {
            if (state.isInitial()) return true;
        }
        return false;
    }
    
    //! number of groups can be increased, return true if is splitted
    //! only current group can be changed due tu splitting (new group is than added)
    TGroupList computeAndSplit(const TGroupList &groups)
    {
        QList<QVector<int> > trGroupLists;
        TGroupList newGroups;
        
        TItemSet::Iterator stateIt = m_states.begin();
        while(stateIt != m_states.end())
        {   
            QVector<int> trGroupList = computeTransitionGroupList(groups, stateIt->getTrList());            
            
            int idx = -1;
            if ((idx = trGroupLists.indexOf(trGroupList)) != -1) // just existing group
            {
                Q_ASSERT(newGroups.count() > idx && trGroupLists.count() > idx);
                newGroups[idx]->insert(*stateIt); // add to right group
            }
            else // create new group
            {
                trGroupLists << trGroupList;
                newGroups << QSharedPointer<Group>(new Group(newGroups.count())); // create new group with original id
                newGroups.last()->insert(*stateIt);                               // and add state to it
            }
            
            ++stateIt;
        }
        
        return newGroups;
    }
    
protected:
    typedef QVector<int>    TTrGroupList;
    TTrGroupList computeTransitionGroupList(const TGroupList &groups, 
                                            const GroupItem::TTrList &trList)
    {
        TTrGroupList trGroupList;
        trGroupList.reserve(trList.count());        
        for (GroupItem::TTrList::ConstIterator trIt = trList.begin();
             trIt != trList.end();
             ++trIt)
        {
            if (*trIt == "")
            {
                trGroupList << -1;
                continue;
            }
            
            for (TGroupList::ConstIterator groupIt = groups.begin();
                 groupIt != groups.end();
                 ++groupIt)
            {
                if ((*groupIt)->contains(*trIt))
                {
                    trGroupList << (*groupIt)->id();
                    break;
                }
            }
        }
        
        Q_ASSERT(trGroupList.count() == trList.count());
        return trGroupList;
    }
    
private:
    TItemSet        m_states;
    int             m_id;
};

#ifndef QT_NO_DEBUG_OUTPUT

QDebug operator<<(QDebug dbg, const Group &g)
{
    dbg.nospace() << "Group "<< g.id() << ": (";
    Group::TItemSet items = g.items();
    for (Group::TItemSet::ConstIterator itemIt = items.begin();
         itemIt != items.end();
         ++itemIt)
    {
        if (itemIt != items.begin())
            dbg.nospace() << ",";
        dbg.nospace() << itemIt->getState();
    }
    dbg.nospace() << ")";
    return dbg.nospace();
}

#endif

MinimalizeAlgorithm::~MinimalizeAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString MinimalizeAlgorithm::getName() const
{
    return "Minimalize automaton";
}

bool MinimalizeAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                      QSharedPointer<IAutomaton> &result) const
{
    if (input.empty())
    {
        RELLOG("nothing on input");
        addReport("nothing on input");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton = input[0];
    
    if (!automaton->isDeterministic())
    {
        if (!determinize(automaton))
            return false;
    }
    
    // now automaton is prepared
    Q_ASSERT(automaton->getInitialStates().count() == 1);
    
    QStringList alphabet = automaton->getAlphabet().toList();
    qSort(alphabet);
    
    Group::TGroupList groups;
    // create two groups, one for final states and second for other
    groups << QSharedPointer<Group>(new Group(groups.count())); // final states
    groups << QSharedPointer<Group>(new Group(groups.count())); // other
    foreach(const QSharedPointer<IState> &state, automaton->getStates())
    {
        GroupItem::TTrList trList;
        foreach(const QString &character, alphabet)
        {
            IState::TIStateNameSet statesOn = state->getStatesOn(character);
            Q_ASSERT(statesOn.count() < 2); // it's deterministic automaton
            if (statesOn.isEmpty())
                trList << "";
            else
                trList << *statesOn.begin();
        }
        
        if (state->isFinal())   groups[0]->insert(GroupItem(state->getName(), trList, state->isInitial()));
        else                    groups[1]->insert(GroupItem(state->getName(), trList, state->isInitial()));
    }

    // if no final state exists, remove final group
    if (groups[0]->count() == 0) // TODO: should this be reduced as no automaton (all states are useless)
    {
        groups.remove(0);
    }
    
    while (true)
    {
        Group::TGroupList newGroups;
        for (Group::TGroupList::ConstIterator groupIt = groups.begin();
             groupIt != groups.end();
             ++groupIt)
        {
            newGroups << (*groupIt)->computeAndSplit(groups);
        }
        
        if (newGroups.count() == groups.count())
            break;
        
        groups = newGroups;
    }
    
#ifndef QT_NO_DEBUG_OUTPUT
    for (Group::TGroupList::ConstIterator groupIt = groups.begin();
         groupIt != groups.end();
         ++groupIt)
    {
        DBGLOG_ALGO(**groupIt);
    }
#endif
    
    IState::TIStateNameSet removedStates;
    // remove equivalent states and reconnect all transitions which lead to them
    for (Group::TGroupList::ConstIterator groupIt = groups.begin();
         groupIt != groups.end();
         ++groupIt)
    {
        Q_ASSERT((*groupIt)->count() != 0 && "shouldn't be empty!");
        
        Group::TItemSet items = (*groupIt)->items();
        
        Group::TItemSet::ConstIterator itemIt = items.begin();
        QString firstStateName = itemIt->getState();
        
        if ((*groupIt)->initial()) // set state inital if some state in group is
        {
            QSharedPointer<IState> state = automaton->getState(firstStateName);
            state->setInitial(true);
        }
        
        ++itemIt;        
        while (itemIt != items.end())
        {
            QSharedPointer<IState> state = automaton->getState(itemIt->getState());
            ITransition::TITransitionList transitionsTo = state->getTransitionsTo();
            foreach(const QSharedPointer<ITransition> &tr, transitionsTo)
            {
                if (removedStates.contains(tr->getSourceState())) // don't reconnect loops from removed states
                    continue;
                if (tr->getSourceState() == tr->getDestinationState()) // don't reconnect loops
                    continue;
                automaton->createTransition(tr->getSourceState(), firstStateName, tr->getCharacters());
            }
            
            automaton->removeState(state);
            removedStates << state->getName();
            ++itemIt;
        }
    }
    
    result = automaton;
    
    return true;
}

//------------------------------------------------------------------ MinimalizeAlgorithm -->



//<-- UniteParallelAlgorithm ---------------------------------------------------------------

UniteParallelAlgorithm::UniteParallelAlgorithm()
:   BasicAlgorithmWithSettings(false, true)
{}

UniteParallelAlgorithm::~UniteParallelAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString UniteParallelAlgorithm::getName() const
{
    return "Unite automata - parallel running";
}

bool UniteParallelAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                 QSharedPointer<IAutomaton> &result) const
{
    if (input.count() < 2)
    {
        RELLOG("not enough automata on input");
        addReport("not enough automata on input, required 2");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton1 = input[0];
    QSharedPointer<IAutomaton> automaton2 = input[1];
    
    ITransition::TCharSet alphabet = automaton1->getAlphabet();
    if (automaton1->getAlphabet() != automaton2->getAlphabet())
    {
        if (!tryMergeAlphabet(automaton1->getAlphabet(), automaton2->getAlphabet(), alphabet))
        {
            addReport("inconsistent alphabets on input, alphabets have to be same or one has to be a subset of the other!\n"
                      "try to set alphabet manually ...");
            RELLOG("not same alphabets");
            return false;
        }
    }
    
    if (automaton1->getAlphabetSymbol() != automaton2->getAlphabetSymbol() ||
        automaton1->getEpsilonSymbol() != automaton2->getEpsilonSymbol())
    {
        addReport("not same automata symbols settings, use same epsilon and alphabet symbol!");
        RELLOG("not same automata symbols settings");
        return false;
    }
    
    // prepare input
    if (automaton1->hasEpsilonTransitions())
        if (!removeEpsilonTransitions(automaton1))
            return false;
    if (automaton2->hasEpsilonTransitions())
        if (!removeEpsilonTransitions(automaton2))
            return false;
    
    if (automaton1->hasMultipleInitials())
        if (!removeMultipleInitials(automaton1))
            return false;
    if (automaton2->hasMultipleInitials())
        if (!removeMultipleInitials(automaton2))
            return false;
    
    QSharedPointer<IAutomaton> automatonUnited(m_creator->createAutomaton(alphabet,
                                                                          automaton1->getAlphabetSymbol(),
                                                                          automaton1->getEpsilonSymbol()));
    
    makeSureNamesUnique(automaton1, automaton2);

    Q_ASSERT(automaton1->getInitialStates().count() == 1);
    Q_ASSERT(automaton2->getInitialStates().count() == 1);
    // simulate parlalel running
    QSharedPointer<IState> state1 = automaton1->getInitialStates()[0];
    QSharedPointer<IState> state2 = automaton2->getInitialStates()[0];
    
    int stateNum = 0;
    
    QStringList newStateNameList = QStringList() << state1->getName() << state2->getName();
    QString newStateName = chooseStateName(automatonUnited, newStateNameList, stateNum);
    QString newStateLabel = chooseStateLabel((QStringList() << state1->getLabel() << state2->getLabel()), stateNum);
    QSharedPointer<IState> newState = 
        automatonUnited->createState(newStateName, newStateLabel, true, state1->isFinal() || state2->isFinal());    
    stateNum++;
    
    QQueue<QSharedPointer<IState> > openedStates;    
    openedStates.enqueue(newState);
    
    QMap<QString, QStringList> nameToNameListMap;        
    nameToNameListMap[newState->getName()] = newStateNameList;
    
    while (!openedStates.empty())
    {
        QSharedPointer<IState> currentState = openedStates.dequeue();
        
        foreach(const QString &character, automatonUnited->getAlphabet())
        {
            IState::TIStateNameSet newStateNameSet;            
            
            Q_ASSERT(nameToNameListMap.contains(currentState->getName()));
            QStringList origNameList = nameToNameListMap[currentState->getName()];
            foreach(const QString &stateName, origNameList)
            {
                Q_ASSERT(automaton1->hasState(stateName) || automaton2->hasState(stateName));
                // get original automaton's state
                QSharedPointer<IState> state =
                    automaton1->hasState(stateName) ? automaton1->getState(stateName)
                                                    : automaton2->getState(stateName);
                
                newStateNameSet |= state->getStatesOn(character);
            }
            
            if (newStateNameSet.empty()) continue; // no next state
            
            newStateNameList = newStateNameSet.toList();
            qSort(newStateNameList); // required since QSet's elements is in undefined order
            
            bool newStateIsFinal = false;
            QStringList newStateLabelList;
            foreach(const QString &partName, newStateNameList)
            {
                Q_ASSERT(automaton1->hasState(partName) || automaton2->hasState(partName));
                const QSharedPointer<IState> state = 
                    automaton1->hasState(partName) ? automaton1->getState(partName)
                                                   : automaton2->getState(partName);

                 newStateIsFinal = newStateIsFinal || state->isFinal();
                 newStateLabelList << state->getLabel();
            }
            
            if (nameToNameListMap.values().contains(newStateNameList))
            {
                newState = automatonUnited->getState(nameToNameListMap.key(newStateNameList));
                
                automatonUnited->createTransition(currentState->getName(), newState->getName(),
                                                 (ITransition::TCharSet() << character));
                
                continue; // not add state more than once
            }
            
            newStateName = chooseStateName(automatonUnited, newStateNameList, stateNum);
            newStateLabel = chooseStateLabel(newStateLabelList, stateNum);
            // now we have to create new state which belongs to united automaton
            newState = automatonUnited->createState(newStateName, newStateLabel, false, newStateIsFinal);
            stateNum++;
            
            openedStates.enqueue(newState);            
            nameToNameListMap[newStateName] = newStateNameList;
            
            automatonUnited->createTransition(currentState->getName(), newStateName,
                                              (ITransition::TCharSet() << character));
        }
    }
    
    result = automatonUnited;
    
    addReport("Automata united sucessfully\n");
    
    return true;
}

//--------------------------------------------------------------- UniteParallelAlgorithm -->



//<-- IntersectionParallelAlgorithm --------------------------------------------------------

IntersectionParallelAlgorithm::IntersectionParallelAlgorithm()
:   BasicAlgorithmWithSettings(false, true)
{}

IntersectionParallelAlgorithm::~IntersectionParallelAlgorithm()
{
    DBGLOG_ALGO("deleted");
}

QString IntersectionParallelAlgorithm::getName() const
{
    return "Intersect automata - parallel running";
}

bool IntersectionParallelAlgorithm::runInternal(const IAutomaton::TAutomataList &input,
                                               QSharedPointer<IAutomaton> &result) const
{
    if (input.count() < 2)
    {
        RELLOG("not enough automata on input");
        addReport("not enough automata on input - required 2");
        return false;
    }
    
    QSharedPointer<IAutomaton> automaton1 = input[0];
    QSharedPointer<IAutomaton> automaton2 = input[1];
    
    ITransition::TCharSet alphabet = automaton1->getAlphabet();
    if (automaton1->getAlphabet() != automaton2->getAlphabet())
    {
        if (!tryMergeAlphabet(automaton1->getAlphabet(), automaton2->getAlphabet(), alphabet))
        {
            addReport("inconsistent alphabets on input, alphabets have to be same or one has to be a subset of the other!");
            RELLOG("not same alphabets");
            return false;
        }
    }
    
    if (automaton1->getAlphabetSymbol() != automaton2->getAlphabetSymbol() ||
        automaton1->getEpsilonSymbol() != automaton2->getEpsilonSymbol())
    {
        addReport("not same automata symbols settings, use same epsilon and alphabet symbol!");
        RELLOG("not same automata symbols settings");
        return false;
    }

    // prepare input
    if (automaton1->hasEpsilonTransitions())
        if (!removeEpsilonTransitions(automaton1))
            return false;
    if (automaton2->hasEpsilonTransitions())
        if (!removeEpsilonTransitions(automaton2))
            return false;
    
    if (automaton1->hasMultipleInitials())
        if (!removeMultipleInitials(automaton1))
            return false;
    if (automaton2->hasMultipleInitials())
        if (!removeMultipleInitials(automaton2))
            return false;
    
    QSharedPointer<IAutomaton> automatonIntersect(m_creator->createAutomaton(alphabet,
                                                                             automaton1->getAlphabetSymbol(),
                                                                             automaton1->getEpsilonSymbol()));
                                                                          
    Q_ASSERT(automaton1->getInitialStates().count() == 1);
    Q_ASSERT(automaton2->getInitialStates().count() == 1);
    
    makeSureNamesUnique(automaton1, automaton2);
    
    // simulate parlalel running
    QSharedPointer<IState> state1 = automaton1->getInitialStates()[0];
    QSharedPointer<IState> state2 = automaton2->getInitialStates()[0];
    
    int stateNum = 0;
    
    QStringList newStateNameList = QStringList() << state1->getName() << state2->getName();
    QString newStateName = chooseStateName(automatonIntersect, newStateNameList, stateNum);
    QString newStateLabel = chooseStateLabel((QStringList() << state1->getLabel() << state2->getLabel()), stateNum);
    QSharedPointer<IState> newState = 
        automatonIntersect->createState(newStateName, newStateLabel, true, state1->isFinal() && state2->isFinal());
    stateNum++;
    
    QQueue<QSharedPointer<IState> > openedStates;    
    openedStates.enqueue(newState);
        
    QMap<QString, QStringList> nameToNameListMap;
    nameToNameListMap[newState->getName()] = newStateNameList;   
    
    while (!openedStates.empty())
    {
        QSharedPointer<IState> currentState = openedStates.dequeue();
        
        foreach(const QString &character, automatonIntersect->getAlphabet())
        {
            IState::TIStateNameSet newStateNameSet;
            QStringList origNameList = nameToNameListMap[currentState->getName()];
            foreach(const QString &stateName, origNameList)
            {
                Q_ASSERT(automaton1->hasState(stateName) || automaton2->hasState(stateName));
                QSharedPointer<IState> state = 
                    automaton1->hasState(stateName) ? automaton1->getState(stateName)
                                                    : automaton2->getState(stateName);
                
                newStateNameSet |= state->getStatesOn(character);
            }
            
            if (newStateNameSet.empty()) continue; // no next state
            
            newStateNameList = newStateNameSet.toList();
            qSort(newStateNameList); // required since QSet's elements is in undefined order
            
            unsigned char belongsTo = 0;
            bool newStateIsFinal = true;
            QStringList newStateLabelList;
            foreach(const QString &partName, newStateNameList)
            {
                Q_ASSERT(automaton1->hasState(partName) || automaton2->hasState(partName));
                QSharedPointer<IState> state;
                if (automaton1->hasState(partName))
                {
                    state = automaton1->getState(partName);
                    belongsTo |= 1; // 0001b
                }
                else
                {
                    state = automaton2->getState(partName);
                    belongsTo |= 2; // 0010b
                }
                
                newStateIsFinal = newStateIsFinal && state->isFinal();
                newStateLabelList << state->getLabel();
            }
            
            newStateIsFinal &= belongsTo == 3; // 0011b // has to belong to both automaton
            
            if (nameToNameListMap.values().contains(newStateNameList))
            {
                newState = automatonIntersect->getState(nameToNameListMap.key(newStateNameList));
                
                automatonIntersect->createTransition(currentState->getName(), newState->getName(),
                                                     (ITransition::TCharSet() << character));
                
                continue; // not add state more than once
            }
            
            newStateName = chooseStateName(automatonIntersect, newStateNameList, stateNum);
            newStateLabel = chooseStateLabel(newStateLabelList, stateNum);
            
            // now we have to create new state which belongs to united automaton
            newState = automatonIntersect->createState(newStateName, newStateLabel, false, newStateIsFinal);
            stateNum++;
                        
            openedStates.enqueue(newState);
            nameToNameListMap[newStateName] = newStateNameList;
            
            automatonIntersect->createTransition(currentState->getName(), newStateName,
                                                 (ITransition::TCharSet() << character));
        }
    }
    
    result = automatonIntersect;
    
    addReport("Automata intersected sucessfully\n");
    
    return true;
}

//-------------------------------------------------------- IntersectionParallelAlgorithm -->



/*------------------------------------------------------|
 * AlgorithmHolder -> exported from library             |
 *------------------------------------------------------V*/

AlgorithmHolder::AlgorithmHolder()
{}

IAlgorithm::TAlgorithmList AlgorithmHolder::getAlgorithms() const
{
    IAlgorithm::TAlgorithmList algorithmList;

// one automaton algorithms
    algorithmList << QSharedPointer<IAlgorithm>(new RemoveEpsilonAlgorithm());
    algorithmList << QSharedPointer<IAlgorithm>(new RemoveInaccessibleAlgorithm());
    algorithmList << QSharedPointer<IAlgorithm>(new RemoveUselessAlgorithm());
    algorithmList << QSharedPointer<IAlgorithm>(new RemoveMultipleInitialsAlgorithm());

    algorithmList << QSharedPointer<IAlgorithm>(new DeterminizeAlgorithm());    
    algorithmList << QSharedPointer<IAlgorithm>(new MinimalizeAlgorithm());
   
// two automata algorithms    
    algorithmList << QSharedPointer<IAlgorithm>(new UniteParallelAlgorithm());
    algorithmList << QSharedPointer<IAlgorithm>(new IntersectionParallelAlgorithm());
    
    return algorithmList;
}

AlgorithmHolder::~AlgorithmHolder()
{
    DBGLOG_ALGO("deleted");
}

Q_EXPORT_PLUGIN2(algorithms, AlgorithmHolder)