Qt 4.8
qsimplex_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 QtGui 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 #ifndef QSIMPLEX_P_H
43 #define QSIMPLEX_P_H
44 
45 //
46 // W A R N I N G
47 // -------------
48 //
49 // This file is not part of the Qt API. It exists purely as an
50 // implementation detail. This header file may change from version to
51 // version without notice, or even be removed.
52 //
53 // We mean it.
54 //
55 
56 #include <QtCore/qhash.h>
57 #include <QtCore/qpair.h>
58 
60 
62 {
64 
66  int index;
67 };
68 
69 
82 {
83  QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {}
84 
85  enum Ratio {
86  LessOrEqual = 0,
88  MoreOrEqual
89  };
90 
94 
97 
98  void invert();
99 
100  bool isSatisfied() {
101  qreal leftHandSide(0);
102 
104  for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
105  leftHandSide += iter.value() * iter.key()->result;
106  }
107 
108  Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant));
109 
110  if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.0000001)
111  return true;
112 
113  switch (ratio) {
114  case LessOrEqual:
115  return leftHandSide < constant;
116  case MoreOrEqual:
117  return leftHandSide > constant;
118  default:
119  return false;
120  }
121  }
122 
123 #ifdef QT_DEBUG
125  QString result;
126  result += QString::fromAscii("-- QSimplexConstraint %1 --").arg(quintptr(this), 0, 16);
127 
129  for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
130  result += QString::fromAscii(" %1 x %2").arg(iter.value()).arg(quintptr(iter.key()), 0, 16);
131  }
132 
133  switch (ratio) {
134  case LessOrEqual:
135  result += QString::fromAscii(" (less) <= %1").arg(constant);
136  break;
137  case MoreOrEqual:
138  result += QString::fromAscii(" (more) >= %1").arg(constant);
139  break;
140  default:
141  result += QString::fromAscii(" (eqal) == %1").arg(constant);
142  }
143 
144  return result;
145  }
146 #endif
147 };
148 
149 class QSimplex
150 {
151 public:
152  QSimplex();
153  virtual ~QSimplex();
154 
155  qreal solveMin();
156  qreal solveMax();
157 
158  bool setConstraints(const QList<QSimplexConstraint *> constraints);
159  void setObjective(QSimplexConstraint *objective);
160 
161  void dumpMatrix();
162 
163 private:
164  // Matrix handling
165  qreal valueAt(int row, int column);
166  void setValueAt(int row, int column, qreal value);
167  void clearRow(int rowIndex);
168  void clearColumns(int first, int last);
169  void combineRows(int toIndex, int fromIndex, qreal factor);
170 
171  // Simplex
172  bool simplifyConstraints(QList<QSimplexConstraint *> *constraints);
173  int findPivotColumn();
174  int pivotRowForColumn(int column);
175  void reducedRowEchelon();
176  bool iterate();
177 
178  // Helpers
179  void clearDataStructures();
180  void solveMaxHelper();
181  enum solverFactor { Minimum = -1, Maximum = 1 };
182  qreal solver(solverFactor factor);
183  void collectResults();
184 
188 
189  int rows;
190  int columns;
192 
194 };
195 
196 inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
197 {
198  return matrix[rowIndex * columns + columnIndex];
199 }
200 
201 inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
202 {
203  matrix[rowIndex * columns + columnIndex] = value;
204 }
205 
207 
208 #endif // QSIMPLEX_P_H
double qreal
Definition: qglobal.h:1193
QIntegerForSizeof< void * >::Unsigned quintptr
Definition: qglobal.h:986
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
static QString fromAscii(const char *, int size=-1)
Returns a QString initialized with the first size characters from the string str. ...
Definition: qstring.cpp:4276
QString toString()
Definition: qsimplex_p.h:124
QPair< QSimplexVariable *, qreal > helper
Definition: qsimplex_p.h:95
int firstArtificial
Definition: qsimplex_p.h:191
QSimplexVariable * artificial
Definition: qsimplex_p.h:96
QList< QSimplexConstraint * > constraints
Definition: qsimplex_p.h:185
static Q_DECL_CONSTEXPR bool qFuzzyCompare(double p1, double p2)
Definition: qglobal.h:2030
The QString class provides a Unicode character string.
Definition: qstring.h:83
Q_DECL_CONSTEXPR T qAbs(const T &t)
Definition: qglobal.h:1201
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
QSimplexConstraint * objective
Definition: qsimplex_p.h:187
QHash< QSimplexVariable *, qreal > variables
Definition: qsimplex_p.h:91
static double ratio(Bigint *a, Bigint *b)
const T value(const Key &key) const
Returns the value associated with the key.
Definition: qhash.h:606
int columns
Definition: qsimplex_p.h:190
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
qreal valueAt(int row, int column)
Definition: qsimplex_p.h:196
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the hash.
Definition: qhash.h:466
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the hash...
Definition: qhash.h:469
QString arg(qlonglong a, int fieldwidth=0, int base=10, const QChar &fillChar=QLatin1Char(' ')) const Q_REQUIRED_RESULT
Definition: qstring.cpp:7186
int rows
Definition: qsimplex_p.h:189
const Key key(const T &value) const
Returns the first key mapped to value.
Definition: qhash.h:674
QList< QSimplexVariable * > variables
Definition: qsimplex_p.h:186
void setValueAt(int row, int column, qreal value)
Definition: qsimplex_p.h:201
The QSimplex class is a Linear Programming problem solver based on the two-phase simplex method...
Definition: qsimplex_p.h:149
qreal * matrix
Definition: qsimplex_p.h:193
The QList class is a template class that provides lists.
Definition: qdatastream.h:62