/****************************************************************************

**

** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtXmlPatterns module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

/*

 * NOTE: This file is included by qxsdstatemachine_p.h

 * if you need some includes, put them in qxsdstatemachine_p.h (outside of the namespace)

 */

template <typename TransitionType>

XsdStateMachine<TransitionType>::XsdStateMachine()

    : m_counter(50)

{

}

template <typename TransitionType>

XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool)

    : m_namePool(namePool)

    , m_counter(50)

{

}

template <typename TransitionType>

typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::addState(StateType type)

{

#ifndef QT_NO_DEBUG

    // make sure we don't have two start states

    if (type == StartState) {

        QHashIterator<StateId, StateType> it(m_states);

        while (it.hasNext()) {

            it.next();

            Q_ASSERT(it.value() != StartState && it.value() != StartEndState);

        }

    }

#endif // QT_NO_DEBUG

    // reserve new state id

    const StateId id = ++m_counter;

    m_states.insert(id, type);

    // if it is a start state, we make it to our current state

    if (type == StartState || type == StartEndState)

        m_currentState = id;

    return id;

}

template <typename TransitionType>

void XsdStateMachine<TransitionType>::addTransition(StateId start, TransitionType transition, StateId end)

{

    QHash<TransitionType, QVector<StateId> > &hash = m_transitions[start];

    QVector<StateId> &states = hash[transition];

    if (!states.contains(end))

        states.append(end);

}

template <typename TransitionType>

void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end)

{

    QVector<StateId> &states = m_epsilonTransitions[start];

    states.append(end);

}

template <typename TransitionType>

void XsdStateMachine<TransitionType>::reset()

{

    // reset the machine to the start state

    QHashIterator<StateId, StateType> it(m_states);

    while (it.hasNext()) {

        it.next();

        if (it.value() == StartState || it.value() == StartEndState) {

            m_currentState = it.key();

            return;

        }

    }

    Q_ASSERT(false);

}

template <typename TransitionType>

void XsdStateMachine<TransitionType>::clear()

{

    m_states.clear();

    m_transitions.clear();

    m_epsilonTransitions.clear();

    m_currentState = -1;

    m_counter = 50;

}

template <typename TransitionType>

bool XsdStateMachine<TransitionType>::proceed(TransitionType transition)

{

    // check that we are not in an invalid state

    if (!m_transitions.contains(m_currentState)) {

        return false;

    }

    // fetch the transition entry for the current state

    const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

    if (entry.contains(transition)) { // is there an transition for the given input?

        m_currentState = entry.value(transition).first();

        m_lastTransition = transition;

        return true;

    } else {

        return false;

    }

}

template <typename TransitionType>

QList<TransitionType> XsdStateMachine<TransitionType>::possibleTransitions() const

{

    // check that we are not in an invalid state

    if (!m_transitions.contains(m_currentState)) {

        return QList<TransitionType>();

    }

    // fetch the transition entry for the current state

    const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

    return entry.keys();

}

template <typename TransitionType>

template <typename InputType>

bool XsdStateMachine<TransitionType>::proceed(InputType input)

{

    // check that we are not in an invalid state

    if (!m_transitions.contains(m_currentState)) {

        return false;

    }

    // fetch the transition entry for the current state

    const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

    QHashIterator<TransitionType, QVector<StateId> > it(entry);

    while (it.hasNext()) {

        it.next();

        if (inputEqualsTransition(input, it.key())) {

            m_currentState = it.value().first();

            m_lastTransition = it.key();

            return true;

        }

    }

    return false;

}

template <typename TransitionType>

template <typename InputType>

bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const

{

    return false;

}

template <typename TransitionType>

bool XsdStateMachine<TransitionType>::inEndState() const

{

    // check if current state is an end state

    return (m_states.value(m_currentState) == StartEndState || m_states.value(m_currentState) == EndState);

}

template <typename TransitionType>

TransitionType XsdStateMachine<TransitionType>::lastTransition() const

{

    return m_lastTransition;

}

template <typename TransitionType>

typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::startState() const

{

    QHashIterator<StateId, StateType> it(m_states);

    while (it.hasNext()) {

        it.next();

        if (it.value() == StartState || it.value() == StartEndState)

            return it.key();

    }

    Q_ASSERT(false); // should never be reached

    return -1;

}

template <typename TransitionType>

QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const

{

    Q_UNUSED(type)

    return QString();

}

template <typename TransitionType>

bool XsdStateMachine<TransitionType>::outputGraph(QIODevice *device, const QString &graphName) const

{

    if (!device->isOpen()) {

        qWarning("device must be open for writing");

        return false;

    }

    QByteArray graph;

    QTextStream s(&graph);

    QHashIterator<StateId, QHash<TransitionType, QVector<StateId> > > it(m_transitions);

    QHashIterator<StateId, StateType> it3(m_states);

    s << "digraph " << graphName << " {\n";

    s << "  mindist = 2.0\n";

    // draw edges

    while (it.hasNext()) {

        it.next();

        QHashIterator<TransitionType, QVector<StateId> > it2(it.value());

        while (it2.hasNext()) {

            it2.next();

            for (int i = 0; i < it2.value().count(); ++i)

                s << "  " << it.key() << " -> " << it2.value().at(i) << " [label=\"" << transitionTypeToString(it2.key()) << "\"]\n";

        }

    }

    QHashIterator<StateId, QVector<StateId> > it4(m_epsilonTransitions);

    while (it4.hasNext()) {

        it4.next();

        const QVector<StateId> states = it4.value();

        for (int i = 0; i < states.count(); ++i)

            s << "  " << it4.key() << " -> " << states.at(i) << " [label=\"&#949;\"]\n";

    }

    // draw node infos

    while (it3.hasNext()) {

        it3.next();

        QString style;

        if (it3.value() == StartState) {

            style = QLatin1String("shape=circle, style=filled, color=blue");

        } else if (it3.value() == StartEndState) {

            style = QLatin1String("shape=doublecircle, style=filled, color=blue");

        } else if (it3.value() == InternalState) {

            style = QLatin1String("shape=circle, style=filled, color=red");

        } else if (it3.value() == EndState) {

            style = QLatin1String("shape=doublecircle, style=filled, color=green");

        }

        s << "  " << it3.key() << " [" << style << "]\n";

    }

    s << "}\n";

    s.flush();

    if (device->write(graph) == -1)

        return false;

    return true;

}

template <typename TransitionType>

typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::dfaStateForNfaState(QSet<StateId> nfaState,

                                                                                                       QList< QPair<QSet<StateId>, StateId> > &stateTable,

                                                                                                       XsdStateMachine<TransitionType> &dfa) const

{

    // check whether we have the given state in our lookup table

    // already, in that case simply return it

    for (int i = 0; i < stateTable.count(); ++i) {

        if (stateTable.at(i).first == nfaState)

            return stateTable.at(i).second;

    }

    // check if the NFA state set contains a Start or End

    // state, in that case our new DFA state will be a

    // Start or End state as well

    StateType type = InternalState;

    QSetIterator<StateId> it(nfaState);

    bool hasStartState = false;

    bool hasEndState = false;

    while (it.hasNext()) {

        const StateId state = it.next();

        if (m_states.value(state) == EndState) {

            hasEndState = true;

        } else if (m_states.value(state) == StartState) {

            hasStartState = true;

        }

    }

    if (hasStartState) {

        if (hasEndState)

            type = StartEndState;

        else

            type = StartState;

    } else if (hasEndState) {

        type = EndState;

    }

    // create the new DFA state

    const StateId dfaState = dfa.addState(type);

    // add the new DFA state to the lookup table

    stateTable.append(qMakePair<QSet<StateId>, StateId>(nfaState, dfaState));

    return dfaState;

}

template <typename TransitionType>

XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const

{

    XsdStateMachine<TransitionType> dfa(m_namePool);

    dfa.m_counter = 100;

    QList< QPair< QSet<StateId>, StateId> > table;

    QList< QSet<StateId> > isMarked;

    // search the start state as the algorithm starts with it...

    StateId startState = -1;

    QHashIterator<StateId, StateType> stateTypeIt(m_states);

    while (stateTypeIt.hasNext()) {

        stateTypeIt.next();

        if (stateTypeIt.value() == StartState) {

            startState = stateTypeIt.key();

            break;

        }

    }

    Q_ASSERT(startState != -1);

    // our list of state set that still have to be processed

    QList< QSet<StateId> > workStates;

    // add the start state to the list of to processed state sets

    workStates.append(epsilonClosure(QSet<StateId>() << startState));

    while (!workStates.isEmpty()) { // as long as there are state sets to process left

        // enqueue set of states

        const QSet<StateId> states = workStates.takeFirst();

        if (isMarked.contains(states)) // we processed this state set already

            continue;

        // mark as processed

        isMarked.append(states);

        // select a list of all inputs that are possible for

        // the 'states' set

        QList<TransitionType> input;

        {

            QSetIterator<StateId> it(states);

            while (it.hasNext()) {

                input << m_transitions.value(it.next()).keys();

            }

        }

        // get the state in DFA that corresponds to the 'states' set in the NFA

        const StateId dfaBegin = dfaStateForNfaState(states, table, dfa);

        for (int i = 0; i < input.count(); ++i) { // for each possible input

            // retrieve the states that can  be reached from the 'states' set by the

            // given input or by epsilon transition

            const QSet<StateId> followStates = epsilonClosure(move(states, input.at(i)));

            // get the state in DFA that corresponds to the 'followStates' set in the NFA

            const StateId dfaEnd = dfaStateForNfaState(followStates, table, dfa);

            // adds a new transition to the DFA that corresponds to the transitions between

            // 'states' and 'followStates' in the NFA

            dfa.addTransition(dfaBegin, input.at(i), dfaEnd);

            // add the 'followStates' to the list of to be processed state sets

            workStates.append(followStates);

        }

    }

    return dfa;

}

template <typename TransitionType>

QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const

{

    return m_states;

}