1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of the QtWidgets 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 The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/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 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39
40 #ifndef QSIMPLEX_P_H
41 #define QSIMPLEX_P_H
42
43 //
44 // W A R N I N G
45 // -------------
46 //
47 // This file is not part of the Qt API. It exists purely as an
48 // implementation detail. This header file may change from version to
49 // version without notice, or even be removed.
50 //
51 // We mean it.
52 //
53
54 #include <QtWidgets/private/qtwidgetsglobal_p.h>
55 #include <QtCore/qhash.h>
56 #include <QtCore/qpair.h>
57 #include <QtCore/qstring.h>
58
59 QT_REQUIRE_CONFIG(graphicsview);
60
61 QT_BEGIN_NAMESPACE
62
63 struct QSimplexVariable
64 {
QSimplexVariableQSimplexVariable65 QSimplexVariable() : result(0), index(0) {}
66
67 qreal result;
68 int index;
69 };
70
71
72 /*!
73 \internal
74
75 Representation of a LP constraint like:
76
77 (c1 * X1) + (c2 * X2) + ... = K
78 or <= K
79 or >= K
80
81 Where (ci, Xi) are the pairs in "variables" and K the real "constant".
82 */
83 struct QSimplexConstraint
84 {
QSimplexConstraintQSimplexConstraint85 QSimplexConstraint() : constant(0), ratio(Equal), artificial(nullptr) {}
86
87 enum Ratio {
88 LessOrEqual = 0,
89 Equal,
90 MoreOrEqual
91 };
92
93 QHash<QSimplexVariable *, qreal> variables;
94 qreal constant;
95 Ratio ratio;
96
97 QPair<QSimplexVariable *, qreal> helper;
98 QSimplexVariable * artificial;
99
100 void invert();
101
isSatisfiedQSimplexConstraint102 bool isSatisfied() {
103 qreal leftHandSide(0);
104
105 QHash<QSimplexVariable *, qreal>::const_iterator iter;
106 for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
107 leftHandSide += iter.value() * iter.key()->result;
108 }
109
110 Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant));
111
112 if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.0000001)
113 return true;
114
115 switch (ratio) {
116 case LessOrEqual:
117 return leftHandSide < constant;
118 case MoreOrEqual:
119 return leftHandSide > constant;
120 default:
121 return false;
122 }
123 }
124
125 #ifdef QT_DEBUG
toStringQSimplexConstraint126 QString toString() {
127 QString result;
128 result += QString::fromLatin1("-- QSimplexConstraint %1 --").arg(quintptr(this), 0, 16);
129
130 QHash<QSimplexVariable *, qreal>::const_iterator iter;
131 for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
132 result += QString::fromLatin1(" %1 x %2").arg(iter.value()).arg(quintptr(iter.key()), 0, 16);
133 }
134
135 switch (ratio) {
136 case LessOrEqual:
137 result += QString::fromLatin1(" (less) <= %1").arg(constant);
138 break;
139 case MoreOrEqual:
140 result += QString::fromLatin1(" (more) >= %1").arg(constant);
141 break;
142 default:
143 result += QString::fromLatin1(" (eqal) == %1").arg(constant);
144 }
145
146 return result;
147 }
148 #endif
149 };
150
151 class QSimplex
152 {
153 Q_DISABLE_COPY_MOVE(QSimplex)
154 public:
155 QSimplex();
156 ~QSimplex();
157
158 qreal solveMin();
159 qreal solveMax();
160
161 bool setConstraints(const QList<QSimplexConstraint *> &constraints);
162 void setObjective(QSimplexConstraint *objective);
163
164 void dumpMatrix();
165
166 private:
167 // Matrix handling
168 inline qreal valueAt(int row, int column);
169 inline void setValueAt(int row, int column, qreal value);
170 void clearRow(int rowIndex);
171 void clearColumns(int first, int last);
172 void combineRows(int toIndex, int fromIndex, qreal factor);
173
174 // Simplex
175 bool simplifyConstraints(QList<QSimplexConstraint *> *constraints);
176 int findPivotColumn();
177 int pivotRowForColumn(int column);
178 void reducedRowEchelon();
179 bool iterate();
180
181 // Helpers
182 void clearDataStructures();
183 void solveMaxHelper();
184 enum SolverFactor { Minimum = -1, Maximum = 1 };
185 qreal solver(SolverFactor factor);
186 void collectResults();
187
188 QList<QSimplexConstraint *> constraints;
189 QList<QSimplexVariable *> variables;
190 QSimplexConstraint *objective;
191
192 int rows;
193 int columns;
194 int firstArtificial;
195
196 qreal *matrix;
197 };
198
valueAt(int rowIndex,int columnIndex)199 inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
200 {
201 return matrix[rowIndex * columns + columnIndex];
202 }
203
setValueAt(int rowIndex,int columnIndex,qreal value)204 inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
205 {
206 matrix[rowIndex * columns + columnIndex] = value;
207 }
208
209 QT_END_NAMESPACE
210
211 #endif // QSIMPLEX_P_H
212