Qt 4.8
qxsdstatemachine_p.h
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 //
43 // W A R N I N G
44 // -------------
45 //
46 // This file is not part of the Qt API. It exists purely as an
47 // implementation detail. This header file may change from version to
48 // version without notice, or even be removed.
49 //
50 // We mean it.
51 
52 #ifndef Patternist_XsdStateMachine_H
53 #define Patternist_XsdStateMachine_H
54 
55 #include "qnamepool_p.h"
56 
57 #include <QtCore/QHash>
58 #include <QtCore/QSet>
59 #include <QtCore/QTextStream>
60 
61 class QIODevice;
62 
64 
66 
67 namespace QPatternist
68 {
75  template <typename TransitionType>
77  {
78  public:
79  typedef qint32 StateId;
80 
84  enum StateType
85  {
90  };
91 
96 
102  XsdStateMachine(const NamePool::Ptr &namePool);
103 
109  StateId addState(StateType type);
110 
118  void addTransition(StateId start, TransitionType transition, StateId end);
119 
126  void addEpsilonTransition(StateId start, StateId end);
127 
131  void reset();
132 
136  void clear();
137 
143  bool proceed(TransitionType transition);
144 
150 
159  template <typename InputType>
160  bool proceed(InputType input);
161 
165  template <typename InputType>
166  bool inputEqualsTransition(InputType input, TransitionType transition) const;
167 
171  bool inEndState() const;
172 
176  TransitionType lastTransition() const;
177 
181  StateId startState() const;
182 
187  QString transitionTypeToString(TransitionType type) const;
188 
193  bool outputGraph(QIODevice *device, const QString &graphName) const;
194 
199 
204 
212  {
213  return m_transitions;
214  }
215 
216  private:
221  StateId dfaStateForNfaState(QSet<StateId> nfaState, QList< QPair< QSet<StateId>, StateId> > &stateTable, XsdStateMachine<TransitionType> &dfa) const;
222 
231  {
232  // every state can reach itself by epsilon transition, so include the input states
233  // in the result as well
234  QSet<StateId> result = input;
235 
236  // add the input states to the list of to be processed states
237  QList<StateId> workStates = input.toList();
238  while (!workStates.isEmpty()) { // while there are states to be processed left...
239 
240  // dequeue one state from list
241  const StateId state = workStates.takeFirst();
242 
243  // get the list of states that can be reached by the epsilon transition
244  // from the current 'state'
245  const QVector<StateId> targetStates = m_epsilonTransitions.value(state);
246  for (int i = 0; i < targetStates.count(); ++i) {
247  // if we have this target state not in our result set yet...
248  if (!result.contains(targetStates.at(i))) {
249  // ... add it to the result set
250  result.insert(targetStates.at(i));
251 
252  // add the target state to the list of to be processed states as well,
253  // as we want to have the epsilon transitions not only for the first
254  // level of following states
255  workStates.append(targetStates.at(i));
256  }
257  }
258  }
259 
260  return result;
261  }
262 
270  QSet<StateId> move(const QSet<StateId> &states, TransitionType input) const
271  {
272  QSet<StateId> result;
273 
274  QSetIterator<StateId> it(states);
275  while (it.hasNext()) { // iterate over all given states
276  const StateId state = it.next();
277 
278  // get the transition table for the current state
280 
281  // get the target states for the given input
282  const QVector<StateId> targetStates = transitions.value(input);
283 
284  // add all target states to the result
285  for (int i = 0; i < targetStates.size(); ++i)
286  result.insert(targetStates.at(i));
287  }
288 
289  return result;
290  }
291 
296  StateId m_currentState;
298  TransitionType m_lastTransition;
299  };
300 
301  #include "qxsdstatemachine.cpp"
302 }
303 
305 
307 
308 #endif
int type
Definition: qmetatype.cpp:239
XsdStateMachine< TransitionType > toDFA() const
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
int qint32
Definition: qglobal.h:937
void addTransition(StateId start, TransitionType transition, StateId end)
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
#define it(className, varName)
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
QHash< StateId, QHash< TransitionType, QVector< StateId > > > m_transitions
The QString class provides a Unicode character string.
Definition: qstring.h:83
Any state that is not start or end state.
const T value(const Key &key) const
Returns the value associated with the key.
Definition: qhash.h:606
bool isEmpty() const
Returns true if the list contains no items; otherwise returns false.
Definition: qlist.h:152
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
QString transitionTypeToString(TransitionType type) const
bool contains(const T &value) const
Definition: qset.h:91
T takeFirst()
Removes the first item in the list and returns it.
Definition: qlist.h:489
QList< T > toList() const
Definition: qset.h:296
QHash< StateId, StateType > states() const
The namespace for the internal API of QtXmlPatterns.
const_iterator insert(const T &value)
Definition: qset.h:179
bool outputGraph(QIODevice *device, const QString &graphName) const
The state the machine will start with, can be end state as well.
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
QHash< StateId, QVector< StateId > > m_epsilonTransitions
StateId dfaStateForNfaState(QSet< StateId > nfaState, QList< QPair< QSet< StateId >, StateId > > &stateTable, XsdStateMachine< TransitionType > &dfa) const
QHash< StateId, StateType > m_states
QHash< StateId, QHash< TransitionType, QVector< StateId > > > transitions() const
void addEpsilonTransition(StateId start, StateId end)
bool proceed(TransitionType transition)
QSet< StateId > move(const QSet< StateId > &states, TransitionType input) const
A state machine used for evaluation.
The state the machine will start with.
Any state where the machine is allowed to stop.
QList< TransitionType > possibleTransitions() const
static const KeyPair *const end
The QIODevice class is the base interface class of all I/O devices in Qt.
Definition: qiodevice.h:66
#define QT_END_HEADER
Definition: qglobal.h:137
QSet< StateId > epsilonClosure(const QSet< StateId > &input) const
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
bool inputEqualsTransition(InputType input, TransitionType transition) const
TransitionType lastTransition() const
StateId addState(StateType type)
The QList class is a template class that provides lists.
Definition: qdatastream.h:62