C:/CVUT/diplomka/Automata_editor/sources/automataCreator.cpp

Go to the documentation of this file.

#include "constants.h"

#include "automataCreator.h"
#include "stringProcessor.h"
#include "state.h"
#include "transition.h"
#include "utils.h"

#include "istate.h"
#include "itransition.h"
#include <QStringList>
#include <QVector>
#include <QSharedPointer>
#include <QQueue>
#include <QPainterPath>

#include <QtDebug>

const QStringList AutomataCreator::defaultAlphabetSymbList = QStringList() << "A" << "\\Sigma";
const QStringList AutomataCreator::defaultEpsilonSymbList = QStringList() << "\\varepsilon" << "\\epsilon";

#ifdef TESTING_AUTOMATA_CREATOR
#   define DBGLOG_AC(x) DBGLOG_("AUTOMATACREATOR", x)
#else
#   define DBGLOG_AC(x)
#endif

//<-- TTRowImpl -------------------------------------------------------

class TTRowImpl : public ITTRow
{
public:
    TTRowImpl(const QStringList &head)
    : m_head(head)
    {}
    
    typedef QMap<QString, QStringList>   TRowDataMap;
    TTRowImpl(const QStringList &head, const TRowDataMap &rowDataMap)
    : m_head(head), m_dataMap(rowDataMap), m_initialFlag(false), m_finalFlag(false)
    {}

    const QStringList head() const
    {
        return m_head;
    }

    const QStringList getValue(const QString &character) const
    {
        return m_dataMap[character];
    }

    /*QStringList& headRef()
    {
        return m_head;
    }*/

    QStringList& operator[](const QString &character)
    {
        return m_dataMap[character];
    }

    QList<QString> getUniqueKeys() const
    {
        return m_dataMap.uniqueKeys();
    }
    
    void setInitialFlag(bool initial)
    {
        m_initialFlag = initial;
    }
    
    void setFinalFlag(bool final)
    {
        m_finalFlag = final;
    }
    
    bool initialFlag() const
    {
        return m_initialFlag;
    }
    
    bool finalFlag() const
    {
        return m_finalFlag;
    }

protected:
    QStringList     m_head;
    TRowDataMap     m_dataMap;
    
    bool            m_initialFlag;
    bool            m_finalFlag;
};

//------------------------------------------------------- TTRowImpl -->



//<-- TransitionTableImpl ---------------------------------------------

class TransitionTableImpl : public ITransitionTable
{
public:
    TransitionTableImpl()
    {}

    typedef QVector<QSharedPointer<ITTRow> >    TITTRowList;
    
    TransitionTableImpl(const TITTRowList &rows)
    : m_rows(rows)
    {}

    ~TransitionTableImpl()
    {
        DBGLOG_AC("called");
    }

    int getRowCount() const
    {
        return m_rows.count();
    }

    QSharedPointer<ITTRow> getRow(int idx) const
    {
        if (idx >= m_rows.count()) return QSharedPointer<ITTRow>(NULL);

        return m_rows[idx];
    }

    int addRow(const QSharedPointer<ITTRow> &row)
    {
        m_rows << row;

        return m_rows.count()-1;
    }

    QList<QString> getUniqueKeys() const
    {
        QSet<QString> uniqueKeys;
        foreach(const QSharedPointer<ITTRow> &row, m_rows)
        {
            uniqueKeys |= row->getUniqueKeys().toSet();
        }

        return uniqueKeys.toList();
    }

    QString toLaTeXTable() const
    {
        QString laTeXTable;

        laTeXTable += "\
\\begin{table}[h]\n\
\\begin{center}\n\
\\begin{tabular}{r r|";

        QString rowString = " & $\\mathbf{\\delta{}_M}$";
        QList<QString> uniqueKeys = getUniqueKeys();
        foreach(const QString &character, uniqueKeys)
        {
            laTeXTable += "|c";
            QString symb =
                StringProcessor::isSpecialSymbol(character) ?
                    "$%1$" : "%1";
            rowString += " & \\textbf{" + symb.arg(character) + "}";
        }
        laTeXTable += "}\n";
        laTeXTable += rowString + "\\\\\n";
        
        for (int i = 0; i < getRowCount(); ++i)
        {
            laTeXTable += QString("\\cline{2-%1}\n").arg(2+uniqueKeys.count());
            //laTeXTable += "\\hline\n";
            QSharedPointer<ITTRow> row = getRow(i);            

            Q_ASSERT(row->head().count() == 1);
            
            QString fieldString = " & " + row->head()[0];
            if (row->initialFlag() && row->finalFlag())
                fieldString = "$\\leftrightarrow$" + fieldString;
            else if (row->initialFlag())
                fieldString = "$\\rightarrow$" + fieldString;
            else if (row->finalFlag())
                fieldString = "$\\leftarrow$" + fieldString;
            
            rowString = fieldString;
            foreach(const QString &character, uniqueKeys)
            {
                fieldString = trStringListToString((*row)[character]);
                rowString += " & "  + fieldString;
            }

            laTeXTable += rowString + "\\\\\n";
        }

        laTeXTable += "\
\\end{tabular}\n\
\\end{center}\n\
\\caption{Transition table}\n\
\\label{tab:transitionTable}\n\
\\end{table}";
   
        return laTeXTable;
    }

    QString toStringTable() const
    {
        QString stringTable;

        const int columnWidth = 15;

        QList<QString> uniqueKeys = getUniqueKeys();
        QString rowString = QString("%1").arg("M", columnWidth+4) + " -> ";
        foreach(const QString &character, uniqueKeys)
        {
            rowString += QString("%1").arg(character, columnWidth);
        }
        stringTable += rowString + "\n";

        for (int i = 0; i < getRowCount(); ++i)
        {
            QSharedPointer<ITTRow> row = getRow(i);

            Q_ASSERT(row->head().count() == 1);
            
            QString fieldString = row->head()[0];
            if (row->initialFlag() && row->finalFlag())
                fieldString = "<=> " + fieldString;
            else if (row->initialFlag())
                fieldString = " -> " + fieldString;
            else if (row->finalFlag())
                fieldString = "<-  " + fieldString;
            rowString = QString("%1").arg(fieldString, columnWidth+4) + " -> ";
            foreach(const QString &character, uniqueKeys)
            {
                fieldString = trStringListToString((*row)[character]);
                rowString += QString("%1").arg(fieldString, columnWidth);
            }

            stringTable += rowString + "\n";
        }

        return stringTable;
    }

protected:
    TITTRowList m_rows;
};

//--------------------------------------------- TransitionTableImpl -->




//<-- TransitionImpl --------------------------------------------------


TransitionImpl::TransitionImpl(const QString &source, const QString &destination, 
                               const ITransition::TCharSet characters,
                               Transition *graphicsTransition)
: m_sourceState(source), m_destinationState(destination), m_characters(characters),
  m_graphicsTransition(graphicsTransition)
{}

TransitionImpl::~TransitionImpl()
{
    DBGLOG_AC(DBGPAR(m_sourceState) << DBGPAR(m_destinationState) <<
              DBGPAR(m_characters) << "deleted");
}

void TransitionImpl::setSourceState(const QString &stateName)
{
    m_sourceState = stateName;
}

void TransitionImpl::setDestinationState(const QString &stateName)
{
    m_destinationState = stateName;
}

QString TransitionImpl::getSourceState() const
{
    return m_sourceState;
}

QString TransitionImpl::getDestinationState() const
{
    return m_destinationState;
}

bool TransitionImpl::passOn(const QString &character) const
{
    return m_characters.contains(character);
}

ITransition::TCharSet TransitionImpl::getCharacters() const
{
    return m_characters;
}

void TransitionImpl::setCharacters(const TCharSet &characters)
{
    m_characters = characters;
}

Transition* TransitionImpl::getGraphicsTransition()
{
    return m_graphicsTransition;
}

//-------------------------------------------------- TransitionImpl -->



//<-- StateImpl -------------------------------------------------------

StateImpl::StateImpl(const QString &name, const QString &label, bool initial, bool final,
                     State *graphicsState)
:   m_name(name), m_label(label), m_initial(initial), m_final(final), m_graphicsState(graphicsState)
{}

StateImpl::~StateImpl()
{
    DBGLOG_AC(DBGPAR(getName()) << "deleted");
}

void StateImpl::setName(const QString &name)
{
    m_name = name;
    
    foreach(QSharedPointer<ITransition> tr, getTransitions())
    {
        tr->setSourceState(name);
    }
    
    foreach(QSharedPointer<ITransition> tr, getTransitionsTo())
    {
        tr->setDestinationState(name);
    }
}

QString StateImpl::getName() const
{
    return m_name;
}

void StateImpl::setLabel(const QString &label)
{
    m_label = label;
}

QString StateImpl::getLabel() const
{
    return m_label;
}

bool StateImpl::isInitial() const
{
    return m_initial;
}

bool StateImpl::isFinal() const
{
    return m_final;
}

void StateImpl::setInitial(bool is)
{
    m_initial = is;
}

void StateImpl::setFinal(bool is)
{
    m_final = is;
}

IState::TIStateNameSet StateImpl::getStatesOn(const QString &character) const
{
    IState::TIStateNameSet result;

    foreach(const QSharedPointer<TransitionImpl> &tr, m_transitions)
    {
        if (tr->passOn(character))
        {
            result << tr->getDestinationState();
        }
    }

    return result;
}

IState::TIStateNameList StateImpl::getAdjacentStates() const
{
    IState::TIStateNameList stateNames;
    foreach(const QSharedPointer<TransitionImpl> &tr, m_transitions)
    {
        stateNames << tr->getDestinationState();
    }
    
    return stateNames;
}

ITransition::TITransitionList StateImpl::getTransitions() const
{
    return trSharedPointerListStaticCast<TransitionImpl, ITransition>(m_transitions);
}

ITransition::TITransitionList StateImpl::getTransitionsTo() const
{
    return trSharedPointerListStaticCast<TransitionImpl, ITransition>(m_transitionsTo);
}

TransitionImpl::TTransitionList StateImpl::getPrivateTransitions() const
{
    return m_transitions;
}

TransitionImpl::TTransitionList StateImpl::getPrivateTransitionsTo() const
{
    return m_transitionsTo;
}

void StateImpl::addTransition(const QSharedPointer<TransitionImpl> &tr)
{
    Q_ASSERT(tr->getSourceState() == getName() &&
             "set only transitions which starts in this state");
    if (tr->getSourceState() != getName())
    {
        RELLOG("Transition isn't added because it doesn't start in this state!!!");
        return;
    }
    
    m_transitions << tr;
}

void StateImpl::addTransitionTo(const QSharedPointer<TransitionImpl> &tr)
{
    Q_ASSERT(tr->getDestinationState() == getName() &&
             "set only transitions which ends in this state");
    if (tr->getDestinationState() != getName())
    {
        RELLOG("Transition isn't added because it doesn't end in this state!!!");
        return;
    }
    
    m_transitionsTo << tr;
}

void StateImpl::removeTransition(const QSharedPointer<TransitionImpl> &tr)
{
    Q_ASSERT(tr->getSourceState() == m_name && "inconsistency in automaton system!");
    {        
        bool ret = m_transitions.removeOne(tr);
        Q_UNUSED(ret);
        Q_ASSERT(ret && "inconsistency in automaton system!");
    }
}

void StateImpl::removeTransitionTo(const QSharedPointer<TransitionImpl> &tr)
{
    Q_ASSERT(tr->getDestinationState() == m_name && "inconsistency in automaton system!");
    {        
        bool ret = m_transitionsTo.removeOne(tr);
        Q_UNUSED(ret);
        Q_ASSERT(ret && "inconsistency in automaton system!");
    }
}

State* StateImpl::getGraphicsState() const
{
    return m_graphicsState;
}

IState::TIStateNameSet StateImpl::getStatesAndPathsOn
    (const QString &character, QList<QPainterPath> &paths) const
{
    IState::TIStateNameSet result;    
    
    foreach(const QSharedPointer<TransitionImpl> &tr, m_transitions)
    {
        if (tr->passOn(character))
        {
            result << tr->getDestinationState();
        
            Transition *graphicsTransition = tr->getGraphicsTransition();
            paths << graphicsTransition->path();
        }
    }
    
    return result;
}

//------------------------------------------------------- StateImpl -->



//<-- AutomatonImpl ---------------------------------------------------


AutomatonImpl::AutomatonImpl(const ITransition::TCharSet &alphabet, const QString &alphabetSymbol,
                             const QString &epsilonSymbol)
:   m_alphabet(alphabet), m_alphabetSymbol(alphabetSymbol), m_epsilonSymbol(epsilonSymbol),
    m_allowRenundancies(false)
{
    Q_ASSERT(m_positioningMap.isEmpty() && "it should be empty by default!!!");
}

AutomatonImpl::~AutomatonImpl()
{
    DBGLOG_AC("called");
}

QSharedPointer<IState> AutomatonImpl::createState(const QString &name, const QString &label,
                                                  bool initial, bool final)
{
    if (m_stateMap.contains(name))
    {
        Q_ASSERT(0 && "state name has to be unique!");
        return QSharedPointer<IState>(NULL);
    }
    
    QSharedPointer<StateImpl> state(new StateImpl(name, label, initial, final, NULL));
    Q_ASSERT(state);
    
    bool ret = addState(state);
    Q_UNUSED(ret);
    Q_ASSERT(ret && "state couldn't be added!");
    
    return state;
}

QSharedPointer<ITransition> AutomatonImpl::createTransition(const QString &source, const QString &dest,
                                                            const ITransition::TCharSet &characters)
{
    if (!m_stateMap.contains(source) || !m_stateMap.contains(dest) || characters.isEmpty())
    {
        Q_ASSERT(0 && "some state doesn't exist!");
        return QSharedPointer<ITransition>(NULL);
    }

    if (allowRedundantTransitions())
    {
        QSharedPointer<TransitionImpl> newTransition(new TransitionImpl(source, dest, characters, NULL));
        Q_ASSERT(newTransition);
        bool ret = addTransition(newTransition);
        Q_UNUSED(ret)
        Q_ASSERT(ret && "transition couldn't be added!");

        return newTransition;
    }

    ITransition::TCharSet tmpCharacters = characters;

    bool eps = tmpCharacters.remove(getEpsilonSymbol());
    bool created = false;
    if (eps)
    {
        QSharedPointer<TransitionImpl> newTransition =
            createPrivateTransitionInternal(source, dest, ITransition::TCharSet() << getEpsilonSymbol(), created);
        Q_ASSERT(newTransition);
        if (created) // if created, add it to automaton, otherwise is already added, so just return
        {
            bool ret = addTransition(newTransition);
            Q_UNUSED(ret)
            Q_ASSERT(ret && "transition couldn't be added!");
        }
        if (tmpCharacters.isEmpty()) return newTransition;
    }

    created = false;
    QSharedPointer<TransitionImpl> newTransition = createPrivateTransitionInternal(source, dest, tmpCharacters, created);
    Q_ASSERT(newTransition);
    if (created)
    {
        bool ret = addTransition(newTransition);
        Q_UNUSED(ret)
        Q_ASSERT(ret && "transition couldn't be added!");
    }
    return newTransition;
}

QSharedPointer<TransitionImpl> AutomatonImpl::createPrivateTransitionInternal
    (const QString &source, const QString &dest, const ITransition::TCharSet &characters, bool &created)
{
    QSharedPointer<StateImpl> state = getPrivateState(source);
    TransitionImpl::TTransitionList transitions = state->getPrivateTransitions();

    return createPrivateTransitionIfNotExists(source, dest, characters, transitions, created, NULL);
}

QSharedPointer<TransitionImpl> AutomatonImpl::createAndAddPrivateTransition
    (const QString &source, const QString &dest, const ITransition::TCharSet &characters, Transition *graphicsTransition)
{
    QSharedPointer<StateImpl> state = getPrivateState(source);
    TransitionImpl::TTransitionList transitions = state->getPrivateTransitions();

    bool created = false;
    QSharedPointer<TransitionImpl> newTransition = createPrivateTransition(source, dest, characters, transitions, created, graphicsTransition);
    Q_ASSERT(newTransition);
    if (created)
    {
        bool ret = addTransition(newTransition);
        Q_UNUSED(ret)
        Q_ASSERT(ret && "transition couldn't be added!");
    }
    return newTransition;
}

QSharedPointer<TransitionImpl> AutomatonImpl::createPrivateTransition
    (const QString &source, const QString &dest, const ITransition::TCharSet &characters,
     const TransitionImpl::TTransitionList &transitions, bool &created, Transition *graphicsTransition)
{
    if (!m_stateMap.contains(source) || !m_stateMap.contains(dest) || characters.isEmpty())
    {
        Q_ASSERT(0 && "some state doesn't exist!");
        return QSharedPointer<TransitionImpl>(NULL);
    }

    if (allowRedundantTransitions())
    {
        created = true;
        return QSharedPointer<TransitionImpl>(new TransitionImpl(source, dest, characters, graphicsTransition));
    }

    return createPrivateTransitionIfNotExists(source, dest, characters, transitions, created, graphicsTransition);
}

QSharedPointer<TransitionImpl> AutomatonImpl::createPrivateTransitionIfNotExists
    (const QString &source, const QString &dest, const ITransition::TCharSet &characters,
     const TransitionImpl::TTransitionList &transitions, bool &created, Transition *graphicsTransition)
{
    ITransition::TCharSet tmpCharacters = characters;

    bool eps = tmpCharacters.remove(getEpsilonSymbol());
    if (eps) // it's epsilon transition, check if exists, otherwise create new
    {
        Q_ASSERT(tmpCharacters.isEmpty() && "epsilon transition has to be created separately!!!");
#ifdef QT_NO_DEBUG
        if (!tmpCharacters.isEmpty())
            RELLOG("Epsilon transition has to be created separately when redundancies are disallowed!");
#endif
        return createEpsilonTransitionIfNotExists(source, dest, getEpsilonSymbol(), transitions, created, graphicsTransition);
    }
    else // it's transition on some characters, check if exists, otherwise create new
    {
        Q_ASSERT(!tmpCharacters.isEmpty() && "no characters for transition!!!");
        return createCharactersTransitionIfNotExists(source, dest, tmpCharacters, transitions, created, graphicsTransition);
    }
}

QSharedPointer<TransitionImpl> AutomatonImpl::createEpsilonTransitionIfNotExists
    (const QString &source, const QString &dest, const QString &epsilonSymbol,
     const TransitionImpl::TTransitionList &transitions, bool &created, Transition *graphicsTransition)
{
    foreach(const QSharedPointer<TransitionImpl> &transition, transitions)
    {
        if (transition->getSourceState() != source || transition->getDestinationState() != dest) continue;

        if (transition->getCharacters().contains(epsilonSymbol))
        {
            Q_ASSERT(transition->getCharacters().size() == 1 &&
                    "should be transition only for epsilon symbol when redundancies aren't allowed");
            return transition;
        }
    }
    created = true;
    return QSharedPointer<TransitionImpl>(new TransitionImpl(source, dest, ITransition::TCharSet() << getEpsilonSymbol(), graphicsTransition));
}

QSharedPointer<TransitionImpl> AutomatonImpl::createCharactersTransitionIfNotExists
    (const QString &source, const QString &dest, ITransition::TCharSet &characters,
     const TransitionImpl::TTransitionList &transitions, bool &created, Transition *graphicsTransition)
{
    foreach(const QSharedPointer<TransitionImpl> &transition, transitions)
    {
        if (transition->getSourceState() != source ||transition->getDestinationState() != dest) continue;

        characters |= transition->getCharacters();
        transition->setCharacters(characters);
        return transition;
    }
    created = true;
    return QSharedPointer<TransitionImpl>(new TransitionImpl(source, dest, characters, graphicsTransition));
}

IState::TIStateList AutomatonImpl::getStates() const
{
    return trSharedPointerListStaticCast<StateImpl, IState>(getPrivateStates());
}

IState::TIStateList AutomatonImpl::getInitialStates() const
{
    IState::TIStateList initialStates;
    
    StateImpl::TStateList states = getPrivateStates();
    foreach(const QSharedPointer<StateImpl> &state, states)
    {
        if (state->isInitial())
            initialStates << state;
    }
    
    return initialStates;
}

IState::TIStateList AutomatonImpl::getFinalStates() const
{
    IState::TIStateList finalStates;
    
    StateImpl::TStateList states = getPrivateStates();
    foreach(const QSharedPointer<StateImpl> &state, states)
    {
        if (state->isFinal())
            finalStates << state;
    }
    
    return finalStates;
}

IState::TIStateNameList AutomatonImpl::getStateNameList() const
{
    return m_stateMap.keys();
}

StateImpl::TStateList AutomatonImpl::getPrivateStates() const
{
    return m_stateMap.values();
}

StateImpl::TStateList AutomatonImpl::getPrivateInitialStates() const
{
    StateImpl::TStateList initialStates;
    
    StateImpl::TStateList states = getPrivateStates();
    foreach(const QSharedPointer<StateImpl> &state, states)
    {
        if (state->isInitial())
            initialStates << state;
    }
    
    return initialStates;
}

StateImpl::TStateList AutomatonImpl::getPrivateFinalStates() const
{
    StateImpl::TStateList finalStates;
    
    StateImpl::TStateList states = getPrivateStates();
    foreach(const QSharedPointer<StateImpl> &state, states)
    {
        if (state->isFinal())
            finalStates << state;
    }
    
    return finalStates;
}

IAutomaton::TPositioningMap AutomatonImpl::getPositioningMap() const
{
    return m_positioningMap;
}

void AutomatonImpl::setPositioningMap(const IAutomaton::TPositioningMap &map)
{
    m_positioningMap = map;
}

ITransition::TITransitionList AutomatonImpl::getTransitions() const
{
    return trSharedPointerListStaticCast<TransitionImpl, ITransition>(m_transitions);
}

TransitionImpl::TTransitionList AutomatonImpl::getPrivateTransitions() const
{
    return m_transitions;
}

QSharedPointer<ITransitionTable> AutomatonImpl::getTransitionTable() const
{
    QSharedPointer<ITransitionTable> trTable(new TransitionTableImpl());

    QSharedPointer<ITTRow> ttRow;

    IState::TIStateNameSet foundedStates;
    IState::TIStateList initialStates = getInitialStates();

    IState::TIStateNameSet restStates = m_stateMap.uniqueKeys().toSet();

    while (!restStates.isEmpty())
    {
        foreach(const QSharedPointer<IState> &state, initialStates)
        {
            if (foundedStates.contains(state->getName())) continue;
            foundedStates << state->getName();

            QQueue<QSharedPointer<IState> > openedStates;
            openedStates.enqueue(state);

            QSharedPointer<IState> currentState;
            while(!openedStates.empty())
            {
                currentState = openedStates.dequeue();

                ttRow = QSharedPointer<ITTRow>(new TTRowImpl(QStringList(currentState->getName())));
                fillRowData(currentState, *ttRow);
                ttRow->setInitialFlag(currentState->isInitial());
                ttRow->setFinalFlag(currentState->isFinal());
                trTable->addRow(ttRow);

                ITransition::TITransitionList currentTransitions = currentState->getTransitions();
                foreach(const QSharedPointer<ITransition> &tr, currentTransitions)
                {
                    QString workState = tr->getDestinationState();
                    if (foundedStates.contains(workState)) continue;
                    foundedStates << workState;

                    openedStates << getState(workState);
                }
            }
        }

        restStates -= foundedStates;
        initialStates.clear();
        foreach(const QString &stateName, restStates)
        {
            initialStates << getState(stateName);
        }
    }

    return trTable;
}

void AutomatonImpl::setAlphabet(const ITransition::TCharSet &alphabet)
{
    m_alphabet = alphabet;
}

void AutomatonImpl::setAlphabetSymbol(const QString &alphabetSymbol)
{
    m_alphabetSymbol = alphabetSymbol;
}

void AutomatonImpl::setEpsilonSymbol(const QString &epsilonSymbol)
{
    m_epsilonSymbol = epsilonSymbol;
}

ITransition::TCharSet AutomatonImpl::getAlphabet() const
{
    return m_alphabet;
}

QString AutomatonImpl::getAlphabetSymbol() const
{
    return m_alphabetSymbol;
}

QString AutomatonImpl::getEpsilonSymbol() const 
{
    return m_epsilonSymbol;
}

bool AutomatonImpl::addState(const QSharedPointer<StateImpl> &state)
{
    if (m_stateMap.contains(state->getName()))
    {
        Q_ASSERT(0 && "unexpected state, check logic of client code");
        return false;        
    }
    
    m_stateMap[state->getName()] = state;        
    return true;
}

QSharedPointer<StateImpl> AutomatonImpl::getPrivateState(const QString &name) const
{
    if (!m_stateMap.contains(name))
    {
        Q_ASSERT(0 && "State doesn't exist!!!");
        return QSharedPointer<StateImpl>(NULL);
    }
    return m_stateMap[name];
}

QSharedPointer<IState> AutomatonImpl::getState(const QString &name) const
{
    return getPrivateState(name); // implicit cast ...
}

bool AutomatonImpl::removeState(const QSharedPointer<IState> &state)
{
    return removeState(state->getName());
}

bool AutomatonImpl::removeState(const QString &stateName)
{
    if (!m_stateMap.contains(stateName)) 
    {
        Q_ASSERT(0 && "unexpected state, check logic of client code");
        return false;
    }

    QSharedPointer<StateImpl> state = m_stateMap[stateName];
    Q_ASSERT(state->getName() == stateName);
    
    // remove related transitions too
    TransitionImpl::TTransitionList transitions = state->getPrivateTransitions();
    foreach(const QSharedPointer<TransitionImpl> &tr, transitions)
    {
        removeTransition(tr);
    }
    
    transitions = state->getPrivateTransitionsTo();
    foreach(const QSharedPointer<TransitionImpl> &tr, transitions)
    {
        removeTransition(tr);
    }
    
    m_stateMap.remove(stateName);
    
    return true;
}

bool AutomatonImpl::renameState(const QSharedPointer<IState> &state,
                                const QString &newName)
{
    if (!m_stateMap.contains(state->getName()))
    {
        Q_ASSERT(0 && "unexpected state, check logic of client code");
        return false;
    }
    
    QSharedPointer<StateImpl> stateImpl = getPrivateState(state->getName());
    
    m_stateMap.remove(state->getName());
    
    stateImpl->setName(newName);
    m_stateMap[newName] = stateImpl;
    
    return true;
}

bool AutomatonImpl::removeTransition(const QSharedPointer<TransitionImpl> &tr)
{
    if (!m_stateMap.contains(tr->getSourceState()) ||
        !m_stateMap.contains(tr->getDestinationState()))
    {
        RELLOG("transition couldn't be in automaton, some of its states aren't here!");
        return false;
    }
    
    m_stateMap[tr->getSourceState()]->removeTransition(tr);
    m_stateMap[tr->getDestinationState()]->removeTransitionTo(tr);
    
    return m_transitions.removeOne(tr);
}

bool AutomatonImpl::removeTransition(const QSharedPointer<ITransition> &tr)
{
    Q_ASSERT(0 && "not implemented yet");
    Q_UNUSED(tr);
    // TODO: implement this -> maybe use dynamic_cast and simply return false
    //       if it's impossible to cast ITransition to TransitionImpl
    //       and if it's ok, call overloaded removeTransition for TransitionImpl
    return false;
}

bool AutomatonImpl::addTransition(const QSharedPointer<TransitionImpl> &tr)
{
    if (!m_stateMap.contains(tr->getSourceState()) || 
        !m_stateMap.contains(tr->getDestinationState()))
    {
        Q_ASSERT(0 && "Some state doesn't exist, check logic of client code");
        return false;
    }

    m_transitions << tr;

    m_stateMap[tr->getSourceState()]->addTransition(tr);
    m_stateMap[tr->getDestinationState()]->addTransitionTo(tr);
    
    return true;
}

void AutomatonImpl::addLists(const StateImpl::TStateList &states, 
                             const TransitionImpl::TTransitionList &transitions)
{
    foreach(const QSharedPointer<StateImpl> &state, states)
    {
        m_stateMap[state->getName()] = state;
    }        
    
    m_transitions << transitions;
}

bool AutomatonImpl::hasMultipleInitials() const
{
    return (getInitialStates().count() > 1);
}

bool AutomatonImpl::hasEpsilonTransitions() const
{
    foreach(const QSharedPointer<ITransition> &tr, m_transitions)
    {
        if (tr->getCharacters().contains(m_epsilonSymbol))
            return true;
    }
    
    return false;
}

bool AutomatonImpl::isDeterministic() const
{
    if (hasMultipleInitials() || hasEpsilonTransitions()) return false;
    
    for(StateImpl::TStateMap::ConstIterator stateIt = m_stateMap.begin();
        stateIt != m_stateMap.end();
        ++stateIt)
    {
        const QSharedPointer<IState> &state = stateIt.value();
        foreach(const QString &character, m_alphabet)
        {
            if (state->getStatesOn(character).count() > 1) return false;
        }
    }
    
    return true;
}

bool AutomatonImpl::hasState(const QString &name) const
{
    return m_stateMap.contains(name);
}

ITransition::TCharSet AutomatonImpl::getTransitionSymbols(const QString &source, const QString &dest) const
{
    if (!hasState(source) || !hasState(dest)) return ITransition::TCharSet();
    
    const QSharedPointer<IState> state = getState(source);    
    ITransition::TITransitionList transitions = state->getTransitions();
    
    ITransition::TCharSet result;
    foreach(const QSharedPointer<ITransition> &tr, transitions)
    {
        if (tr->getDestinationState() != dest) continue;
        
        result |= tr->getCharacters();
    }
    
    return result;
}

void AutomatonImpl::setAllowRedundantTransitions(bool allow)
{
        Q_ASSERT(m_transitions.isEmpty());
        if (!m_transitions.isEmpty())
        {
                RELLOG("automaton already contains transition, setting " <<
                                DBGPAR(allow) << "has no effect!");
                return;
        }
    m_allowRenundancies = allow;
}

void AutomatonImpl::reset()
{
    m_activeStates = getPrivateInitialStates();
    m_processedString.clear();
}

bool AutomatonImpl::processCharacter(const QString &character)
{
    IState::TIStateNameSet names;
    StateImpl::TStateList newActiveStates;
    foreach(const QSharedPointer<StateImpl> &state, m_activeStates)
    {
        IState::TIStateNameSet nextStates = state->getStatesOn(character);
        foreach(const QString &stateName, nextStates)
        {
            if (names.contains(stateName)) continue;
            names << stateName;
            newActiveStates << getPrivateState(stateName);
        }
    }
    
    // change current configuration
    m_activeStates = newActiveStates;
    m_processedString << character;
    
    return !names.empty();
}

bool AutomatonImpl::isConfigurationAccepted() const
{
    foreach(const QSharedPointer<StateImpl> &state, m_activeStates)
    {
        if (state->isFinal()) return true;
    }
    
    return false;
}

IState::TIStateList AutomatonImpl::getActiveStates() const
{
    return trSharedPointerListStaticCast<StateImpl, IState>(getPrivateActiveStates());
}

QStringList AutomatonImpl::getActiveStatesNames() const
{   
    QStringList result; 
    
    foreach(const QSharedPointer<StateImpl> &state, m_activeStates)
    {
        result << state->getName();
    }
    
    return result;
}

StateImpl::TStateList AutomatonImpl::getPrivateActiveStates() const
{
    return m_activeStates;
}

QStringList AutomatonImpl::getProcessedString() const
{
    return m_processedString;
}

IState::TIStateNameSet AutomatonImpl::processCharacterWithInfo
    (const QString &character, QList<QPainterPath> &paths)
{
    IState::TIStateNameSet result;
    
    StateImpl::TStateList activeStates = getPrivateActiveStates();
    StateImpl::TStateList newActiveStates;
    foreach(const QSharedPointer<StateImpl> &state, activeStates)
    {
        IState::TIStateNameSet nextStates = state->getStatesAndPathsOn(character, paths);
        foreach(const QString &stateName, nextStates)
        {
            if (result.contains(stateName)) continue;
            result << stateName;
            newActiveStates << getPrivateState(stateName);
        }
    }
    
    // change current configuration
    m_activeStates = newActiveStates;
    m_processedString << character;
    
    return result;
}

void AutomatonImpl::fillRowData(const QSharedPointer<IState> &state, ITTRow &row) const
{
    QList<QString> usedCharacters;
    foreach(const QSharedPointer<ITransition> &tr, state->getTransitions())
    {
        foreach(const QString &character, tr->getCharacters())
        {
            if (usedCharacters.contains(character)) continue;
            usedCharacters << character;

            row[character] = QStringList(state->getStatesOn(character).toList());
        }
    }
}

//--------------------------------------------------- AutomatonImpl -->

/*--------------------------------------------|
 * AutomataCreator functions                  |
 *--------------------------------------------V*/

QSharedPointer<AutomatonImpl> AutomataCreator::createPrivateAutomaton
    (const ITransition::TCharSet &alphabet, 
     const QString &alphabetSymbol,
     const QString &epsilonSymbol)
{
    return QSharedPointer<AutomatonImpl>(
        new AutomatonImpl(alphabet, alphabetSymbol, epsilonSymbol));
}

QSharedPointer<StateImpl> AutomataCreator::createPrivateState
    (const QString &name, const QString &label, bool initial, bool final, State *graphicsState)
{
    return QSharedPointer<StateImpl>(
        new StateImpl(name, label, initial, final, graphicsState));
}

QSharedPointer<IAutomaton> AutomataCreator::createAutomaton(const ITransition::TCharSet &alphabet, 
                                                            const QString &alphabetSymbol,
                                                            const QString &epsilonSymbol)
{
    return QSharedPointer<IAutomaton>(new AutomatonImpl(alphabet, alphabetSymbol, epsilonSymbol));
}